Антагонистические игры, седловая точка

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

Рассмотрим такую игру, в которой участвуют два игрока А и В, имеющие противоположные интересы: выигрыш одного равен проигрышу другого. Так как выигрыш игрока А равен выигрышу игрока В с противоположным знаком, мы можем интересоваться только выигрышем а игрока А. Цель игрока А — максимизировать свой выигрыш а, в свою очередь, цель игрока В — минимизировать эту же величину, которая является для него проигрышем. Пусть у игрока А имеется m возможных стратегий А₁, А₂,..., А_m, а у игрока В — n возможных стратегий В₁, В₂,..., В_n (такая игра называется игрой m ´ n). Выбор стратегии каждым игроком производится при полном незнании выбора другого игрока. Предположим, что для каждой пары стратегий А_i, В_j выигрыш a_ij нам известен. Тогда в принципе можно составить прямоугольную таблицу (матрицу), в которой перечислить стратегии игроков и соответствующие выигрыши.

Таблица 4.1.

Игра, представленная таким образом, называется матричной, а полученная таблица — платежной матрицей. Само по себе приведение игры к матричной форме уже может составить трудную задачу, а иногда и практически невыполнимую из-за необозримого множества стратегий. Заметим, что если игра приведена к такому виду, то многоходовая игра фактически сведена к одноходовой — от игрока требуется сделать только один ход: выбрать стратегию.

Пусть игрок А выбирает некоторую стратегию А_i; тогда в наихудшем случае (например, если выбор станет известным игроку В) он получит выигрыш, равный . Предвидя такую возможность, игрок А должен выбрать такую стратегию, чтобы максимизировать свой минимальный выигрыш a:

.

Величина a — гарантированный выигрыш игрока А — называется нижней ценой игры. Стратегия А_i, обеспечивающая получение a, называется максиминной.

Игрок В, выбирая стратегию, исходит из следующего принципа: при выборе некоторой стратегии В_j его проигрыш не превосходит максимального из значений элементов j -го столбца матрицы, т. е. меньше или равен . Рассматривая множество для различных значений j, игрок В, естественно, выберет такое значение j, при котором его максимальный проигрыш b минимизируется:

.

Величина b называется верхней ценой игры, а соответствующая выигрышу b стратегия В_j — минимаксной. Нижняя цена игры всегда не превосходит верхней цены игры. Если a=b=v, то число v называется ценой игры.

Фактический выигрыш игрока А при разумных действиях партнеров ограничен нижней и верхней ценой игры. Игра, для которой a=b, называется игрой с седловой точкой.

Для игры с седловой точкой нахождение решения состоит выборе максиминной и минимаксной стратегий, которые являются оптимальными.

Стратегии игроков, для которых вероятности u_i и z_i отличны от нуля, называются активными.