Конечные игры и их решение как задачи линейного программирования

Пусть имеется игра m x n без седловой точки с матрицей (a_ij):

Допустим, что все выигрыши a_ij положительны (этого всегда можно добиться, прибавляя ко всем членам матрицы достаточно большое число М. От этого цена игры увеличится на М, а решение S_A и S_B не изменится). Если все a_ij положительны, то и цена игры, т.е. средний выигрыш при оптимальной стратегии, тоже положителен: v>0.

Мы хотим найти решение игры, т. е. две оптимальные смешанные стратегии S_A = (p₁, p₂, …, p_m) и S_B = (q₁, q₂, …, q_n) дающие каждой стороне максимально возможный для нее средний выигрыш (минимальный проигрыш).

Найдем сначала S_A. Мы знаем, что если один из игроков (в данном случае это А)применяет свою оптимальную стратегию, то другой (B) не может улучшить свое положение, отступая от своей. Заставим противника (В)отступать от своей оптимальной стратегии, пользуясь чистыми стратегиями В₁, В₂,..., В_п (а мы тем временем упорно держимся стратегии S_A). В любом случае наш выигрыш будет не меньше, чем v:

Разделим неравенства на положительную величину v и введем обозначения:

.

Тогда условия примут вид:

,

где - неотрицательные переменные. В силу введенных обозначений и того, что p₁+p₂+…+p_m=1, переменные удовлетворяют условию . Но v есть не что иное, как наш гарантированный выигрыш. Естественно, мы хотим сделать его максимальным, а значит величину - минимальной. Таким образом, задача решения игры свелась к математической задаче: найти неотрицательные значения переменных , такие, чтобы они удовлетворяли линейным ограничениям-неравенствам нашей задачи и обращали в минимум линейную функцию этих переменных:

Таким образом, задача решения игры тХп свелась к задаче линейного программирования с п ограничениями-неравенствами и т переменными. Зная , можно по формулам найти (p₁, p₂, …, p_m) и, значит, оптимальную стратегию и цену игры v.

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

Пара задач линейного программирования, по которой находятся оптимальные стратегии S_A и S_В, называется парой двойственных задач линейного программирования (доказано, что максимум линейной функции в одной из них равен минимуму линейной функции в другой, так что все в порядке — разных значений цены игры мы не получим).

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

Поиск по сайту: