5. Методы решения матричных игр.

Сведение к задаче линейного программирования. Пусть имеется игра mn без седловой точки c выигрышами a_ij>0 (это всегда можно сделать, прибавляя ко всем членам матрицы достаточно большое число, от чего цена игры увеличится, но решение не изменится). Пусть цена игры – v (v>0, т.к. матрица игры положительна)

Требуется найти решение игры, т.е. две оптимальные смешанные стратегии.

S_A=(p₁, p₂, …, p_m), S_B=(q₁, q₂, …q_n), дающие каждой стороне максимально возможный для неё выигрыш (минимальный проигрыш)

П редположим, что мы применяем свою оптимальную стратегию, а игрок В отступает от своей оптимальной смешанной стратегии и пользуется чистыми стратегиями В₁, В_2, … В_n . Тогда наш выигрыш не может быть меньше, чем v. Можно составить систему неравенств:

a₁₁ p_{1 +} a₂₁ p_{2 +} …+ a_m1 p_m  v

…

a_1n p_{1 +} a_2n p_{2 +} …+ a_{m n} p_m  v

Разделим неравенства на v и обозначим x₁ =p₁ / v, … x_m =p_m / v

Т огда условия примут вид

a₁₁ х_{1 +} a₂₁ х_{2 +} …+ a_m1 х_m  1

…

a_1n х_{1 +} a_2n х_{2 +} …+ a_{m n} х_m  1

где х_i – неотрицательные переменные.

Т.к. p₁ +p₂ +…,+p_m=1 , то х₁ +х₂ +…+х_m=1/v

v – наш гарантированный выигрыш и мы хотим сделать его максимальным. Получили задачу линейного программирования: найти х_i0, удовлетворяющие системе неравенств и обращающие в минимум линейную функцию L= х₁ + х₂ + …+ х_m. Следовательно, все методы линейного программирования можно использовать для нахождения оптимального решения игры. И наоборот, методы решения игры, можно применить для решения задач линейного программирования.

Метод итераций – один из самых простых численных методов решения игр (приближённый метод). Идея метода: разыгрывается «мысленный эксперимент», в котором А и В поочерёдно применяют друг против друга свои стратегии, стремясь выиграть побольше (проиграть поменьше). Эксперимент состоит из ряда «партий» игры. Игрок А выбирает произвольно одну из своих стратегий A_i. Противник отвечает ему той из своих стратегий B_j, которая хуже всего для А при стратегии A_i. Далее А выбирает ту стратегию A_k, которая даёт ему максимальный выигрыш при стратегии B_j. Теперь противник отвечает той стратегией, которая является наихудшей для нашей смешанной стратегии (A_i , A_k) , в которой до сих пор применённые стратегии встречаются с равными вероятностями=1/2. И так далее: на каждом шаге итерационного процесса каждый игрок отвечает на очередной ход другого той стратегией, которая является оптимальной для него относительно смешанной стратегии другого, в которую все применённые ранее стратегии входят пропорционально частотам их применения. Такой метод сходится: при увеличении числа партий средний выигрыш на 1 партию будет стремиться к цене игры, а частоты применения стратегий – к вероятностям в оптимальных смешанных стратегиях.

ПРИМЕР 5.3.

Рассмотрим задачу «про пальцы». Увеличим на 5 все элементы матрицы. Цена игры также увеличится на 5.

	В1	В2	В3
A1	7	2	9
A2	2	9	0
А3	9	0	11

Проведем мысленный эксперимент:

k	i	В1	В2	В3	J	A1	A2	А3	v		v*
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	3 2 2 2 1 3 1 2 2 1 3 2 2 1 3	9 11 13 15 22 31	0 9 18 27 29 29	11 11 11 11 20 31	2 2 3 3 3 2 2 2 3 1 2 2 3 1 2	2 4 13 22 31 33	9 18 18 18 18 27	0 0 11 22 33 33	0 4.5 3.67 2.75 4.0 4.84	9 9 6 5.5 6.6 5.5	4.5 6.75 4.84 4.13 5.3 5.17 4.79 5.3 4.78 5.1 4.87 5.2 4.84 5.07 4.9

v – нижняя оценка игры, равная минимальному накопленному выигрышу, делённому на число партий. Аналогично – верхняя оценка. v^* – среднее арифметическое между оценками.

v^* 5, p₁^*=4/150.266, p₂^*=7/150.468, p₃^*=4/150.266

q₁^*=2/150.133, q₂^*=8/150.534, q₃^*=5/150.333

v 0, p₁= q₁ =1/4=0.25, p₂= q₂ =1/2=0.5, p₃= q₃ =1/4=0.25

Графический метод.

Если матричная игра имеет размерность 2хn или mx2, то найти оптимальные смешанные стратегии можно графически.

ДАНО. игра 2хn

a_ij– выигрыш игрока А при использовании им стратегии i, когда игрок В использует стратегию j

НАЙТИ. v – цену игры.

(х₁*, х₂*) – вероятности использования игроком А соответственно 1 и 2 стратегий

(y₁*, y₂*, …y_n*) – вероятности использования игроком В своих стратегий.

РЕШЕНИЕ, х₁ +х₂ =1, 0x1.

Выигрыш игрока А при применении противником чистой стратегии В_i составит z_i:

z₁= a₁₁х₁ +a₂₁х₂= a₁₁х₁ +a₂₁ (1–х₁)=(a₁₁ –a₂₁) х₁ +a₂₁

z₂= a₁₂х₁ +a₂₂х₂= a₁₂х₁ +a₂₂ (1–х₁)=(a₁₂–a₂₂) х₁ +a₂₂

…

z_n= a_1nх₁ +a_2nх₂= a_1nх₁ +a_2n (1–х₁)=(a_1n–a_2n) х₁ +a_2n

П остроим на плоскости прямые z_i(x₁) .

z

z*

х* 1 x₁

Нижняя огибающая этих прямых – это минимальный гарантированный выигрыш игрока А. Действуя по принципу «минимакса», найдем точку на этой огибающей с максимальным выигрышем (х*, z*). Тогда v=z*, (х₁*, х₂*) =(х* , 1-х*)

Нижняя огибающая является наилучшим вариантом для игрока В (проиграть как можно меньше). Худший для него случай – точка (х*, z*). Эта точка является точкой пересечения прямых, соответствующих k и l стратегиям игрока В. Эти стратегии и являются оптимальными смешанными для него. Вероятность использования остальных стратегий y_i=0

При использовании игроком В пары оптимальных смешанных стратегий выигрыш игрока А будет не больше цены игры. В наилучшем случае для любой стратегии =v, т.е. a_1ky_k +a_1l y_l= a_2ky_k +a_2l y_l

Т.к. , то y_l =1–y_k . Решив уравнение, найдем y_k

ПРИМЕР 5.4.

	В1	В2	В3
A1	2	-3	4
A2	-3	4	-5

z₁= 2х₁ -3х₂= 2х₁ -3 (1–х₁)=5 х₁ –3

z₂= -3х₁ +4х₂=-3х₁ +4 (1–х₁)=-7 х₁ +4

z₃= 4х₁ -5х₂=4х₁ -5 (1–х₁)=9 х₁ –5

x ₁

x₃ x₂

z₁=z₂ 5 х₁ –3=-7 х₁ +4 12 х₁=7 х₁*=7/12 x₂*=5/12 v=z*=-1/12

y₃=0 2y₁–3y₂=-3y₁+4y₂ 5y₁-3=-7y₁+4 12y₁=7 y₁*=7/12 y₂*=5/12

Ответ: х*=(7/12, 5/12) y*=(7/12, 5/12, 0) v=-1/12