Решение игр в смешанных стратегиях

Если игра не имеет седловой точки, т.е. (β ≠ a), то применение чистых стратегий не дает оптимального решения игры. В таком случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии.

Смешанной стратегией S_A игрока А называется применение чистых стратегий А₁, А₂, …, А_m с вероятностью р₁, р₂, …,р_i, …,р_m причем сумма вероятностей равна единице: =1.

Смешанные стратегии игрока А записываются в виде матрицы:

А₁ А₂ … A_i … A_m

S_A = p₁ p₂ … p_i … p_m

или в виде строки S_A = (p₁, p₂, …, p_i, …, p_m).

Аналогично смешанные стратегии игрока В обозначают:

В₁ В₂ … В_j … В_n

S_В = q₁ q₂ … q_j … q_n

или в виде строки S_В = (q₁, q_2, …, q_i, …, q_n), где сумма вероятностей появления стратегий равна единице: = 1.

Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*_A, S*_B в общем случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры υ. Цена игры удовлетворяет неравенству:

а ≤ υ ≤ β

где а и β – нижняя и верхняя цены игры.

Пример: определить нижнюю и верхнюю цены игры, заданной

0,5 0,6 0,8 платежной матрицей Р = 0,9 0,7 0,8. Имеет ли игра седловую точку?. 0,7 0,6 0,6

Решение: все расчеты удобно проводить в таблице, к которой кроме матрицы Р введены столбец a _i, и строка β _j.

Bi Aj	B1	B2	B3	a i
A1	0,5	0,6	0,8	0,5
A2	0,9	0,7	0,8	0,7
A3	0,7	0,6	0,6	0,6
β j	0,9	0,7	0,8	а=β = 0,7

Анализируя строки матрицы (стратегии игрока А),заполняем столбец a _i: a ₁ = 0,5, a ₂ = 0,7, a ₃ = 0,6 - минимальные числа в строках 1, 2, 3.

Аналогично β _j = 0,9, β _j = 0,7, β _j = 0,8 – максимальные числа в столбцах 1, 2, 3 соответственно.

Нижняя цена игры a = = max{0,5;0,7;0,6} = 0,7, i = 1, 2, 3 (наибольшее число в столбце) и верхняя цена игры β = = min{0,9;0,7;0,8} = 0,7, j = 1,2,3 (наименьшее число в строке). Эти значения равны, т.е. a = β, и достигаются на одной и той же паре стратегий (A₂; B₂) и цена игры υ = 0,7