Принцип минимакса

Парную игру с нулевой суммой удобно исследовать, если функция выигрыша задается платежной матрицей.

Пусть игроки А и В располагают конечным числом возможных действий – чистых стратегий. Обозначим их соответственно А ₁, А ₂, …, А_m и В ₁, В ₂, …, В_n. Игрок А может выбрать любую чистую стратегию А_i , а игрок В может выбрать любую чистую стратегию В_j . Пара стратегий (А_i, В_j) однозначно определяет результат игры a_ij (a_ij – выигрыш игрока А или проигрыш игрока В при условии, если игрок A придерживается своей чистой стратегии A_i, а игрок B – чистой стратегии B_j)_. Если известны значения исхода игры a_ij для каждой пары (А_i, В_j) чистых стратегий, то можно составить платежную матрицу выигрышей игрока А (проигрышей игрока В) (рисунок 1).

Рисунок 1. Платежная матрица игры

Решить матричную игру означает определить наилучшую стратегию игрока A, а также наилучшую стратегию игрока B. Если рассматривается стратегическая игра, то предполагается, что противники одинаково разумны, и каждый из них делает все для того, чтобы добиться своей цели.

Используя этот принцип, найдем наилучшую стратегию игрока A. Выбирая стратегию A_i, мы должны рассчитывать, что игрок B ответит на нее той из своих стратегий B_j, для которой выигрыш игрока A будет минимальным. Найдем минимальное число a_ij в каждой строке матрицы:

.

Эта величина есть гарантированный (самый малый) выигрыш игрока A при выборе им чистой стратегии A _i. Значения a _i обычно записываются в правом столбце платежной матрицы (см. рисунок 1). Очевидно, что желающий перестраховаться игрок A должен предпочесть другим стратегиям ту, для которой гарантированный выигрыш a _i максимален.

Обозначим это максимальное значение . Величина есть гарантированный выигрыш, который игрок A может получить в игре, и называется нижней ценой игры или максимином. Стратегия, обеспечивающая игроку A получение нижней цены игры, называется максиминной стратегией.

Аналогичные рассуждения могут быть проведены по поводу действий игрока В. С его точки зрения, в платежной матрице приведены проигрыши. В каждом из столбцов он должен найти максимальное значение проигрыша при выборе стратегии B _j:

.

Значения b _j записываются в дополнительной строке платежной матрицы (см. рисунок 1).

Выбирать стратегию игроку B следует так, чтобы минимизировать величину проигрыша при любых действиях соперника, т. е. обеспечить . Величина называется верхней ценой игры (минимаксом), а соответствующая ей чистая стратегия B_j – минимаксной.

Можно показать, что максимин не превосходит минимакс, т. е. a £ b. Если в игре нижняя цена равна верхней (a = b), то говорят, что игра имеет седловую точку и чистую цену игры g = a = b. Пару чистых стратегий (, ), соотвествующих g, называют седловой точкой матричной игры, а элемент a_ij ^*платежной матрицы, стоящий на пересечении i ^*-й строки и j ^*-го столбца, – седловым элементом платежной матрицы. Он одновременно является минимальным в своей строке и максимальным в своем столбце. Стратегии и , образующие седловую точку, являются оптимальными. Значения ; ;g называют решением игры.