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

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

Пусть игра задана платежной мат­рицей . Игрок А обладает стра­тегиями , игрок В – стратегиями . Необ­ходимо определить оптимальные стратегии и , где – вероятности применения соот­ветствующих чистых стратегий ,

, .

Оптимальная стратегия удовлетворяет следующему требо­ванию. Она обеспечивает игроку А средний выигрыш, не мень­ший, чем цена игры v, при любой стратегии игрока В и выиг­рыш, равный цене игры v, при оптимальной стратегии игрока В. Без ограничения общности полагаем v > 0; этого можно добиться, сделав все элементы . Если игрок А применяет смешанную стратегию против любой чистой стратегии игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша (т.е. элементы j-гo столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегий и резуль­таты складываются).

Для оптимальной стратегии все средние выигрыши не меньше цены игры v, поэтому получаем систему неравенств:

Каждое из неравенств можно разделить на число . Введем новые переменные: . Тогда система принимает вид

(1*)

Цель игрока А – максимизировать свой гарантированный вы­игрыш, т.е. цену игры v.

Разделив на равенство, получаем, что переменные удовлетворяют условию: . Максимизация цены игры v эквивалентна мини­мизации величины , поэтому задача может быть сформулиро­вана следующим образом: определить значения переменных , maк, чтобы они удовлетворяли линейным ограничени­ям (*) и при этом линейная функция (2*) обращалась в минимум.

Это задача линейного программирования. Решая задачу (1*)–(2*), получаем оптимальное решение и оптимальную стратегию.

Для определения оптимальной стратегии следует учесть, что игрок В стремится минимизировать гаранти­рованный выигрыш, т.е. найтиmax. Переменные удовлетворяют неравенствам

(3*)

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

Если обозначить (4*), то получим систему неравенств:

(5*)

Переменные удовлетворяют условию .

Игра свелась к следующей задаче.