Решение игры без седловой точки. Поиск оптимальных смешанных стратегий

 

Задача поиска пары оптимальных смешанных стратегий для конечной парной игры с нулевой суммой формулируется следующим образом. Пусть имеется игра m×n без седловой точки со следующей платежной матрицей М:

 

Bj Ai B1 B2 Bn
A1 a11 a12 a1n
A2 a21 a22 a2n
Am am1 am2 amn

 

Необходимо найти решение игры, то есть две оптимальные смешанные стратегии

 

 

 

 

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

 

Пусть все значения в матрице игры положительны. (Если это не так, что можно к каждому элементу матрица добавить достаточно большое число N; от этого цена игры увеличится на N, а решение ( , ) не изменится). Поскольку все aij положительны, то и цена игры, то есть средний выигрыш при оптимальной стратегии, будет тоже положительным: ν > 0.

 

Найдем сначала стратегию . Предположим, что вероятности применения нами стратегий A1, A2, …, Am известны. Тогда, например, если противник всегда будет придерживаться стратегии B1, а мы – выбирать случайным образом наши стратегии с указанными вероятностями, то наш средний выигрыш будет равен:

 

 

 

(этот результат равен произведению вектора на первый столбец матрицы игры M). Поскольку мы придерживаемся оптимальной стратегии, то наш выигрыш будет не меньше, чем цена игры ν:

 

 

Если противник будет придерживаться стратегии B2, то наш средний выигрыш будет следующим:

 

 

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

 

 

 

причем p1 ≥ 0, p2 ≥ 0, …, pm ≥ 0, p1 + p2 + … + pm = 1.


 

Так как мы предположили, что все элементы матрицы игры положительные, а, следовательно, и цена игры больше нуля (ν > 0), то разделим неравенства системы на величину ν и введем обозначения:

  (1)

Тогда неравенства примут вид:

 

    (2)

 

В силу того, что p1 + p2 + … + pm = 1, переменные удовлетворяют условию

 

    (3)

Мы хотим максимизировать наш гарантированный выигрыш ν, что эквивалентно минимизации величины 1/ν. Таким образом, задача решения игры свелась к математической задаче: найти такие значения переменных , чтобы они удовлетворяли линейным ограничениям-неравенствам (2) и обращали в минимум линейную функцию этих переменных:

 

 

А это не что иное, как задача линейного программирования, решаемая с помощью методов оптимизации. Найдя значения , по формуле (3) можно определить цену игры ν, а по формулам (1) – искомые вероятности , то есть оптимальную стратегию .

 

Оптимальная смешанная стратегия игрока B находится аналогично, с той разницей, что B стремится минимизировать, а не максимизировать наш выигрыш ν, а значит обратить не в минимум, а в максимум величину 1/ν. При этом в ограничениях-неравенствах на средний выигрыш будет стоять вместо знака ≥ знак ≤:

 

 

 

 

 

 

Пара задач линейного программирования, по которой находятся оптимальные стратегии ( , ), называется парой двойственных задач линейного программирования. Доказано, что максимум линейной функции в одной из них равен минимуму линейной функции в другой, так что в обоих задачах мы получим одинаковую цену игры ν.

 

Таким образом, решение игры n×m эквивалентно решению задачи линейного программирования. И наоборот, для любой задачи линейного программирования может быть построена эквивалентная ей задача теории игр. Эта связь задач теории игр с задачами линейного программирования оказывается полезной не только для теории игр, но и для линейного программирования. Дело в том, что существуют приближенные численные методы решения игр, которые в некоторых случаях (при большой размерности задачи) оказываются проще, чем «классические» методы линейного программирования.