Задача поиска пары оптимальных смешанных стратегий для конечной парной игры с нулевой суммой формулируется следующим образом. Пусть имеется игра 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, а решение (,) не изменится). Поскольку все aij положительны, то и цена игры, то есть средний выигрыш при оптимальной стратегии, будет тоже положительным: ν > 0.
Найдем сначала стратегию. Предположим, что вероятности применения нами стратегий A 1, A 2, …, Am известны. Тогда, например, если противник всегда будет придерживаться стратегии B 1, а мы – выбирать случайным образом наши стратегии с указанными вероятностями, то наш средний выигрыш будет равен:
(этот результат равен произведению вектора на первый столбец матрицы игры M). Поскольку мы придерживаемся оптимальной стратегии, то наш выигрыш будет не меньше, чем цена игры ν:
Если противник будет придерживаться стратегии B 2, то наш средний выигрыш будет следующим:
Рассуждая аналогичным образом, получим систему неравенств:
причем p 1 ≥ 0, p 2 ≥ 0, …, pm ≥ 0, p 1 + p 2 + … + pm = 1.
Так как мы предположили, что все элементы матрицы игры положительные, а, следовательно, и цена игры больше нуля (ν > 0), то разделим неравенства системы на величину ν и введем обозначения:
(1) |
Тогда неравенства примут вид:
(2) |
В силу того, что p 1 + p 2 + … + pm = 1, переменные удовлетворяют условию
(3) |
Мы хотим максимизировать наш гарантированный выигрыш ν, что эквивалентно минимизации величины 1/ν. Таким образом, задача решения игры свелась к математической задаче: найти такие значения переменных, чтобы они удовлетворяли линейным ограничениям-неравенствам (2) и обращали в минимум линейную функцию этих переменных:
А это не что иное, как задача линейного программирования, решаемая с помощью методов оптимизации. Найдя значения, по формуле (3) можно определить цену игры ν, а по формулам (1) – искомые вероятности, то есть оптимальную стратегию.
Оптимальная смешанная стратегия игрока B находится аналогично, с той разницей, что B стремится минимизировать, а не максимизировать наш выигрыш ν, а значит обратить не в минимум, а в максимум величину 1/ν. При этом в ограничениях-неравенствах на средний выигрыш будет стоять вместо знака ≥ знак ≤:
Пара задач линейного программирования, по которой находятся оптимальные стратегии (,), называется парой двойственных задач линейного программирования. Доказано, что максимум линейной функции в одной из них равен минимуму линейной функции в другой, так что в обоих задачах мы получим одинаковую цену игры ν.
Таким образом, решение игры n×m эквивалентно решению задачи линейного программирования. И наоборот, для любой задачи линейного программирования может быть построена эквивалентная ей задача теории игр. Эта связь задач теории игр с задачами линейного программирования оказывается полезной не только для теории игр, но и для линейного программирования. Дело в том, что существуют приближенные численные методы решения игр, которые в некоторых случаях (при большой размерности задачи) оказываются проще, чем «классические» методы линейного программирования.