Смешанные стратегии

В общем случае V_* ≠ V^* - седловой точки не существует. Оптимальное решение в чистых стратегиях также не существует. Однако, если расширить понятие чистой стратегии введением понятия смешанной стратегии, то удаётся реализовать алгоритм нахождения оптимального решения не вполне определённой игровой задачи, аналогичный рассмотренному выше. В такой ситуации предлагается использование статистического (вероятностного) подхода к нахождению оптимального решения антагонистической игры. Для каждого игрока, наряду с данным набором возможных для него стратегий, вводится неизвестный вектор вероятностей (относительных частот), с которыми следует применять ту или иную стратегию.

Обозначим вектор вероятностей (относительных частот) выбора заданных стратегий игрока A следующим образом:

P = (p₁, p₂,…, p_m),

где p_i≥ 0, p₁ + p₂ +…+ p_m= 1. Величина p_i называется вероятностью (относительной частотой) применения стратегии A_i.

Аналогично для игрока B вводится неизвестный вектор вероятностей (относительных частот) имеет вид:

Q = (q₁, q₂,…, q_n),

где q_j≥ 0, q₁ + q₂ +…+ q_n = 1. Величина q_j называется вероятностью (относительной частотой) применения стратегии B_j. Совокупность (комбинация) чистых стратегий A₁, A₂, …A_m и B_1, B_2, …B_n в сочетании с векторами вероятностей выбора каждой из них называются смешанными стратегиями.

Основной теоремой в теории конечных антагонистических игр является Теорема фон Неймана: каждая конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий.

Из этой теоремы следует, что не вполне определённая игра имеет хотя бы одно оптимальное решение в смешанных стратегиях. В таких играх решением будет пара оптимальных смешанных стратегий P^* и Q^*, таких, что если один из игроков придерживается своей оптимальной стратегии, то и другому игроку не выгодно отклоняться от своей оптимальной стратегии.

Средний выигрыш игрока A определяется математическим ожиданием:

Если вероятность (относительная частота) применения стратегии отлична от нуля, то такая стратегия называется активной.

Стратегии P^*, Q^* называются оптимальными смешанными стратегиями, если

M_A(P, Q^*) ≤ M_A(P^*, Q^*) ≤ M_A(P^*, Q) (1)

В этом случае M_A(P^*, Q^*) называется ценой игры и обозначается через V (V_* ≤ V ≤ V^*). Первое из неравенств (1)означает, что отклонение игрока A от своей оптимальной смешанной стратегии при условии, что игрок B придерживается своей оптимальной смешанной стратегии, приводит к уменьшению среднего выигрыша игрока A. Второе из неравенств означает, что отклонение игрока B от своей оптимальной смешанной стратегии при условии, что игрок A придерживается своей оптимальной смешанной стратегии, приводит к увеличению среднего проигрыша игрока B.

Решение игры в смешанных стратегиях геометрическим методом

Пусть игра задана платежной матрицей  . По оси абсцисс отложим единичный отрезок А₁ А₂, где точка А₁ (0, 0) изображает стратегию А₁, А₂ (1, 0) – стратегию А₂, а каждая промежуточная точка S_A этого отрезка изображает смешанную стратегию первого игрока P_A = (p₁, p₂), где p₁– расстояние от точки S_A до A₂, p₂–расстояние от точки S_A до A₁. Выигрыш игрока A будем откладывать на вертикальных отрезках.

Случай 1. Если игрок B применит стратегию В₁, то выигрыш игрока A при стратегии А₁ равен а₁₁, поэтому на оси ординат отложим отрезок А₁В₁ = а₁₁. При применении игроком A стратегии А₂ выигрыш равен а₂₁, отложим этот отрезок на перпендикуляре из точки А₂, обозначим полученную точку В₁'. Ордината любой точки М₁ отрезка В₁В₁^′ равна среднему выигрышу игрока A при применении смешанной стратегии S_A(действительно, этот выигрыш равен математическому ожиданию случайной величины, т.е. a₁₁p₁ + a₂₁p₂). Запишем уравнение прямой В₁В₁^′:  , т. е.  , 

тогда при x = p₂ получим 

y = a₁₁ + p₂a₂₁ – p₂a₁₁ = a₁₁(1-p₂) + p₂a₂₁ = a₁₁p₁ + a₂₁p₂ 

Случай 2. Если игрок B применяет стратегию В₂, то аналогично откладываем отрезки а₁₂ и а₂₂ и получаем отрезок В₂В₂^′. Ордината любой точки М₂ отрезка В₂В₂^′ – выигрыш игрока A, если A применяет смешанную стратегию S_A, а B – стратегию В₂. 

Построим нижнюю границу выигрыша игрока А – ломаную В₁ NВ₂^′. Ординаты точек этой ломаной показывают минимальные выигрыши игрока А при использовании им любой смешанной стратегии. Оптимальное решение игры определяет точка N, в которой выигрыш игрока А принимает наибольшее значение. Ордината точки N равна цене игры. Проекция этой точки на ось ОХ показывает оптимальную стратегию (р₁, р₂). 

Аналогично находится оптимальная стратегия Q = (q₁ , q₂) игрока B, только в соответствии с принципом минимакса надо находить верхнюю границу выигрыша, т. е. строить ломаную А₂NА₁^′ и брать точку N с наименьшей ординатой. 

Абсцисса точки N определяет оптимальную стратегию игрока B, т. е. Q = (q₁ , q₂).

Пример. Решить игру, заданную платежной матрицей  , графоаналитическим способом. 

Решение. Нижняя цена игры a = 1,5, верхняя цена игры b = 2. Так как , седловой точки нет. Так как a₁ = 1,5, a₂₁ = 2  строим точки B₁(0;1,5) и B₂(1;2), соединяем их отрезком. Так как a₂₁ = 3, a₂₂ = 1 строим точки B₂(0;3) и B₂’(1;1), соединяем их отрезком.

Уравнение прямой В₁В₁^′:  , т. е. y = 0,5x + 1,5;  уравнение В₂В₂^′:  , т. е.  y = 3-2x. 

Найдем точку N пересечения прямых В₁В₁^′ и В₂В₂^′, для чего решим систему уравнений:

т. е. N(0,6; 1,8), откуда p₂= 0,6; p₁= 0,4; γ = 1,8 – цена игры. 

Аналогично строим точки А₁(0; 1,5) и А₁^′(1;3), А₂(0; 2) и А₂^′(1; 1) и находим точку M пересечения прямыхА₁А₁^′ и А₂А₂^′.

Ответ: смешанная стратегия игрока А: P_A= (0,4; 0,6), игрока В: Q_B = (0,8; 0,2); цена игры 1,8.

Решение игры 2×2

Покажем на примере платёжной матрицы размерностью 2×2 реализацию алгоритма построения оптимального решения игровой задачи в смешанных стратегиях.

Пример 1. Найдем решение матричной игры

.

V_* = -1, V* = 1, V_* ≠V* - решения в чистых стратегиях не существует.

Припишем строкам платёжной матрицы неизвестные вероятности p₁ и p₂ (вероятности выбора стратегий A₁ и A₂) соответственно:

  .

Поскольку p₁ + p₂ =1 → p₂ = 1 - p₁. Обозначим p₁ = p, тогда p₂ =1 - p. В результате получим:

Умножим столбец   поэлементно на 1-й столбец и, сложив произведения, получим - математическое ожидание (среднее значение) выигрыша первого игрока A, при условии, что второй игрок B следует первой стратегии.

M₁(p) = 1∙p + (-1)(1-p) = 2p-1

Умножим столбец   поэлементно на 2-й столбец и, сложив произведения, получим линейную зависимость - математическое ожидание (средний выигрыш) игрока A при применении игроком B второй стратегии

M₂(p) = (-1)∙p + 1(1-p) = -2p+1

Поскольку мы разыскиваем оптимальное решение первого игрока A, которое не должно зависеть от выбора стратегий вторым игроком B, приравняем полученные зависимости средних выигрышей:

2p-1 = -2p+1

Отсюда, p= ½, 1-p = ½, то есть оптимальная смешанная стратегия игрока A - это P = (½, ½ ) (каждую из стратегий надо применять с относительной частотой 1/2). Подставив   в любую из зависимостей  , i =1,2 найдем цену игры:

V=M_i(1/2) = 0.

Теперь припишем столбцам вероятности q₁ и q₂ соответственно, а поскольку:

q₁ + q₂ =1 →q₂ = 1 - q₁. Обозначим q₁ = q, тогда q₂ =1 - q. В результате получим:

.

Умножив строку (q, 1-q) на 1-ю строку и сложив произведения, получим линейную зависимость - математическое ожидание:

W₁(q) = 1· q + (-1) ·(1-q) = 2q - 1

Это средний выигрыш игрока A (равный проигрышу игрока B) при применении игроком A 1-й стратегии.

Умножив строку (q, 1-q) на 2-ю строку и сложив произведения, получим линейную зависимость - математическое ожидание:

W₂ = (-1) · q + 1· (1-q) = -2q + 1

Это средний выигрыш игрока A (равный проигрышу игрока B) при применении игроком A 2-й стратегии.

Приравняем полученные зависимости:

2q -1 = -2q + 1

Отсюда, q = ½, 1 - q = ½ , то есть оптимальная смешанная стратегия игрока B - это Q = (1/2, 1/2) (каждую из стратегий надо применять с относительной частотой 1/2).

Решение о конкретном выборе одной из своих стратегий каждый из игроков может принимать с помощью подбрасывания монеты или бинарного датчика случайных чисел.

Как показывает приведённый пример, оптимальные смешанные стратегии сравнительно легко находятся для игр, имеющих небольшую размерность платёжной матрицы (небольшие m и n), т.е. для игр, в которых каждый из игроков имеет небольшое число стратегий. В то же время для игр, имеющих большую размерность, поиск решения становится достаточно сложным. Поэтому до построения оптимального решения в смешанных стратегиях проводят предварительный анализ платёжной матрицы на предмет её упрощения, исключения из неё дублирующих и доминируемых стратегий, что позволяет существенно упростить поиск решения игровой задачи в смешанных стратегиях.