13.5. решение матричных антагонистических игр

13.5. решение матричных антагонистических игр

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

Для уменьшения размерности игры используется доминирование строк и столбцов. Обычно говорят, что /с-я строка матрицы Я доминирует /-тую строку (т.е. одна чистая стратегия доминирует другую), если

h;j < А для всех j, А < А,. хотя бы для одного /. Аналогично 1-й столбец доминируету'-й столбец, если

А(7 < п{. для всех /,

hH < h0 хотя бы для одного /.

Смысл этого определения состоит в том, что доминирующая стратегия никогда не хуже, а в некоторых случаях даже лучше, чем доминируемая стратегия. Отсюда следует, что игроку нет необходимости использовать доминируемую стратегию. В самом деле, будут существовать оптимальные смешанные стратегии, при которых вероятность использования доминируемых строк и столбцов равна нулю, и при решении игры все доминируемые строки и столбцы могут быть отброшены, что позволяет уменьшить размеры матрицы. (Этот подход может использоваться также при поиске решения игры в чистых стратегиях.)

Рассмотрим, например, игру со следующей матрицей:

5 2 1

13

6 4

Третья строка этой матрицы доминирует вторую. Исключение второй строки приводит к матрице

5 2 1 3 6 4'

Третий столбец в этой урезанной матрице доминирует второй, и исключение второго столбца дает

5 1 3 4 '

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

Другой метод упрощения матрицы выигрышей основывается на доказанном в теории игр свойстве, согласно которому аффинное преобразование матрицы платежей (т.е. преобразование всех элементов матрицы Н по правилу Л'.. = а А +Ь, где а * 0) не изменяет решения игры; кроме того, цена'У преобразованной игры v' может быть получена из цены первоначальной игры по такому же правилу: v' = av + b. Это означает, что для задания игры в принципе безразлично, в каких единицах измеряются выигрыши (например, в рублях или долларах); прибавление (вычитание) некоторой фиксированной суммы b изменит на такую же сумму выигрыш (проигрыш) каждого из игроков, не меняя решения игры.

Это свойство может быть использовано для упрощения и придания наглядности матрице выигрышей: так, если в клетках этой матрицы имеются дроби с общим знаменателем, всю матрицу можно умножить на некоторую константу для получения целых чисел; если большинство клеток матрицы заполнено одинаковыми элементами, их можно вычесть из всей матрицы для получения нулей в этих клетках. Кроме того, это свойство позволяет любую матричную антагонистическую игру сделать справедливой для этого необходимо вычесть цену игры из всех элементов матрицы выигрышей.

Для решения игры 2x2 (и вообще игр 2х« или тх2) может быть использован, например, графический метод. Проиллюстрируем его на примере решения описанной игры в орлянку. Матрица выигрыша для этой игры, как было показано, имеет вид 1 -1 -1 1 "

Пусть Игрок 1 избирает свою первую стратегию с вероятностью х и вторую стратегию с вероятностью (1-х). Если Игрок 2 выбирает свою первую стратегию, то (из первого столбца матрицы) математическое ожидание выигрыша для Игрока 1 будет равно

= х (1 -х) = 2х 1.

Если Игрок 2 выбирает свою вторую стратегию, то, в соответствии со вторым столбцом матрицы,

v( = -х + (1 -х) = 1 2х.

Каждое из этих уравнений может быть изображено графически отрезком прямой линии в области [0,1] на графике с координатами хи vr Они представлены на левой части рис.1 соответственно как отрезки АХА и А2А'2, которые пересекаются в точке Р. При данном х на рис.1 показаны две величины v,, которые Игрок 1 может получить, если Игрок 2 применяет свои чистые стратегии. Промежуточные значения v,, соответствующие точкам между этими графиками, получаются, если Игрок 2 применяет смешанные стратегии. Меньшая из этих величин, соответствующая каждому значению х, показывает тот минимум, который может получить Игрок 1, выбирая стратегию (х,(1-х)). Следовательно, линия AtPA'2 показывает платеж, который Игрок 1 может гарантированно получить при любой стратегии Игрока 2. Игрок 1 выбирает такое значение х, чтобы достичь наивысшей точки. Для графика на рис. 13.1 этой точкой является точка Р, для которой х=0,5 и v,=0.

Аналогично может быть проанализирована игра для Игрока 2, который использует свою первую стратегию с вероятностью у, а вторую с вероятностью (1-У). В правой части рис. 13.1 ломанная линия B2QBt представляет наибольший проигрыш Игрока 2 при различных выборах у. Игрок 2 выбирает у так, чтобы достичь низшей точки на этой линии, т.е. точки Q, для которой у = 0,5 и v2 = 0. Следовательно, игроки в орлянку должны применять свои стратегии с одинаковой вероятностью 0,5, и цена игры при этом будет равна нулю, т.е. описанная игра справедлива.

Другой метод решения матричных игр базируется на указанном выше свойстве, гарантирующем, что применение чистых стратегий Игроком 2 (Игроком 1) против оптимальной смешанной стратегии Игрока 1 не позволяет ему проиграть меньше (выиграть больше), чем значение цены игры v. Это позволяет сформулировать следующую задачу для Игрока 1:

max v

Выписанная задача типичная задача линейного программирования и легко поддается решению его методами. Задача для Игрока 2 выглядит аналогично и является двойственной задачей линейного программирования к задаче Игрока 1.

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