Сведение игры к задаче линейной оптимизации

Решение общей матричной игры (m x n) достаточно трудоемко, однако может быть сведено к решению задачи линейной оптимизации (ЛО). Пусть игра задана платежной матрицей

Игрок А имеет стратегии А₁, А₂, …,А_m, а игрок В стратегии В₁, В₂, …,В_n. Найдем оптимальные стратегии

где p_i^*, q_j^* - вероятности применения чистых стратегий А_i и В_j, причем

При любой стратегии игрока В оптимальная стратегия игрока А обеспечивает ему средний выигрыш не меньше цены игры v и выигрыш, равный цене игры v, при оптимальной стратегии игрока В. Пусть игрок А применяет смешанную стратегию А^* против какой-нибудь чистой стратегии B_j игрока В. Тогда он получает средний выигрыш (математическое ожидание выигрыша)

Итак, имеет место следующая система линейных неравенств

или в развернутой форме

Разделим каждое неравенство на v и обозначим . Полученная выше система примет вид:

(7)

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

(8)

Игрок А старается максимизировать свой выигрыш. Это эквивалентно минимизации функции Z. Таким образом, задача поиска оптимальной стратегии А^* свелась к задаче ЛО: минимизировать линейную функцию вида (8) при линейных ограничениях вида (7).

При любой стратегии игрока А оптимальная стратегия игрока В обеспечивает ему средний проигрыш не больше цены игры v и проигрыш, равный цене игры v, при оптимальной стратегии игрока А. Пусть игрок В применяет смешанную стратегию В^* против какой-нибудь чистой стратегии А_i игрока A. Тогда он имеет средний проигрыш (математическое ожидание проигрыша)

Итак, имеет место следующая система линейных неравенств

или в развернутой форме

Разделим каждое неравенство на v и обозначим . Полученная выше система примет вид:

(9)

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

(10)

Игрок В старается минимизировать свой проигрыш. Это эквивалентно максимизации функции F. Таким образом, задача поиска оптимальной стратегии B^* также свелась к задаче ЛО: максимизировать линейную функцию вида (10) при линейных ограничениях вида (9).

Нетрудно заметить, что полученные задачи ЛО являются взаимно двойственными. Первую из задач можно решить, например, методом искусственного базиса. Однако проще сначала решить вторую из рассмотренных задач, а затем по последней симплексной таблице найти решение первой задачи. Если платежная матрица имеет большой размер, обе задачи целесообразно решать с помощью оптимизатора Поиск решения в табличном процессоре Excel