Антагонистические матричные игры.

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

Таблица 4.1.

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

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

 .

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

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

 .

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

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

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

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