Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 17

Посчитаем математическое ожидание выигрыша первого игрока:

Определим  и . Тогда

,

.

Сведение матричной игры к ЛП

Заметим, что .       v   v*=min A_j    A_j                     Тогда

Нахождение v₁ является задачей линейного программирования, т.к. ограничения и  линейны относительно переменных  v и p_i. Кроме того, задачей ЛП, двойственной к предыдущей, является нахождение v₂: Лемма 4: Матричная игра всегда имеет решение в смешанных стратегиях.

Т.к. значения функционалов в прямой и двойственной задачах ЛП совпадают, то в смешанных стратегиях v₁=v₂, Þ игра имеет решение по Нэшу.

Если p^опт найдена (например, графоаналитическим методом), то q^опт находят по теореме о доп. нежесткости: p_i(B_i(q)-u₂)=0, q_j(A_j(p)-u₁)=0.

Графоаналитический метод решения для  игр 2´n и n´2

Из графика (шаг сетки =2) видно, что A₁(p)>A₃(p) (доминирование), максимум нижней огибающей лежит на пересечении прямых А₂ и А₃, т.е. -6p₁+4p₂=2p₁-3p₂ Þ 8p₁=7p₂.      Но p₁+p₂=1 Þ p^опт= (⁷/₁₅, ⁸/₁₅).   Проверим:

A₁(p^опт) = ¹³/₁₅ > -²/₃ = A₂(p^опт) = A₃(p^опт) Þ нижняя огибающая в окрестности p^опт в самом деле сформирована прямыми А₂(p) и А₃(p). Производная огибающей меняет в точке  p^опт знак с + на - :  A₃'(p^опт) = 5, а A₂'(p^опт) = -10

Þ p^опт является точкой max. Цена игры  = A₂(p^опт) = – ²/₃.

Для нахождения q^опт графоаналитический метод неприменим: функции B_i(q) и их верхнюю огибающую сложно нарисовать (в равенстве q₁+q₂+q₃=1 две переменные свободны). Воспользуемся ТДН: p_i·[B_i(q) - v₂] = 0 = q_j·[A_j(p) - v₁]. A₁(p^опт) > v₁ Þ q₁= 0, но p₁, p₂> 0 Þ -6q₂+2q₃= B₁(q) = v₂= B₂(q) = 4q₂– 3q₃.Þ
5q₃= 10 q₂, но q₂+q₃=1, Þ  q^опт= (0, ¹/₃, ²/₃) и v₂= B₁(q^опт) = – ²/₃.

Замечание: Если матрица игры кососимметрична (т.е. квадратная и ƒ_ij=-ƒ_ji), то игроки равносильны и их оптимальные стратегии совпадают.

J !!!   При решении игр размера 2´n алгоритмом Меджидо не нужно предварительно удалять доминируемые строки и столбцы (это требует O(n²) операций, а они удаляются алгоритмом автоматически),  I^–=Æ для p,  I⁺= Æ для q, интервал [u₁,u₂] = [0,1]  сразу.

Пример М3. v₁¹v₂ Þ Решаем в смешанных стратегиях.

Доминирование: X₁ > X₃ Þ отбрасываем X₃,

Y¢₃ > Y¢₂ Þ отбрасываем Y¢₃ (больший проигрыш хуже)

A₁(p)=7p₁+2p₂ ,   Из графика получаем A₄= A₂,

A₂(p)=3p₁+4p₂,     5p₁+3p₂=3p₁+4p₂    2p₁=p₂ ,     p₁+p₂ = 1 Þ

A₄(p)=5p₁+3p₂.     p₁= ¹/₃ ,  p₂= ²/₃.

v=A₄(p)=5p₁+3p₂= ⁵⁺⁶⁼¹¹/₃. A₁(p)=7p₁+2p₂ = v.

Þ Все прямые пересекаются в одной точке.   Ищем q _опт по ТДН: p₁, p₂>0 Þ B₁(q)=v=B₂(q) Þ7q₁+3q₂+5q₄=2q₁+4q₂+3q₄    q₁+q₂+q₄ =1   q₂ =5q₁ +2q₄ Þ 6q₁ +3q₄ = 1   2q₁ + q₄ = ¹/₃ . q₄ = ¹/₃ - 2q₁ , q₂=5q₁ +2(¹/₃-2q₁) = ²/₃+q₁.

  q^опт= (q₁ , ²/₃+q₁ , 0, ¹/₃-2q₁) ³ 0  Û q₁ Î [0, ¹/₆]

Пример М4: Проверим, можно ли отбросить  Y₁ (т.е. q₁ =0). Остается игра 2 ´ 3: