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

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

Bj Ai	B 1	B 2	…	Bn
A 1	a 11	a 12	…	a 1 n
A 2	a 21	a 22	…	a 2 n
…	…	…	…	…
Am	am 1	am 2	…	amn

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

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

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

Найдем сначала стратегию. Предположим, что вероятности применения нами стратегий A ₁, A ₂, …, A_m известны. Тогда, например, если противник всегда будет придерживаться стратегии B ₁, а мы – выбирать случайным образом наши стратегии с указанными вероятностями, то наш средний выигрыш будет равен:

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

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

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

причем p ₁ ≥ 0, p ₂ ≥ 0, …, p_m ≥ 0, p ₁ + p ₂ + … + p_m = 1.

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

(1)

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

(2)

В силу того, что p ₁ + p ₂ + … + p_m = 1, переменные удовлетворяют условию

(3)

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

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

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

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

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