Алгоритм принципа максимина (минимакса)

1. В каждой строке платежной матрицы, соответствующей определенной стратегии А_і игрока А, находят минимальное из чисел :

. (2.5.1)

Это гарантированный выигрыш игрока А, при использовании стратегии А_і. Очевидно, что игроку А выгодно выбирать такую стратегию А_і, для которой значение гарантированного выигрыша было бы самым большим.

2. Определяют число , которое находится по формуле (2.5.2)

= . (2.5.2)

Оно называется нижней ценой игры или максимином . Соответствующая стратегия называется максиминной.

ü Максимин – это гарантированный выигрыш, который игрок А может себе обеспечить в игре против разумного противника.

Максиминная стратегия неустойчива. Если игрок А будет придерживаться максиминной стратегии, и игрок В догадается об этом, то игрок В может ухудшить положение игрока А.

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

. (2.5.3)

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

4. Определяют число , которое находится по формуле (2.5.4)

. (2.5.4)

Оно называется верхней ценой игры или минимаксом . Соответствующая стратегия называется минимаксной.

ü Минимакс – это гарантированный проигрыш, который игрок В может себе позволить в игре против разумного противника.

Минимаксная стратегия также неустойчива

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

Замечание. Нижняя цена игры всегда не превосходит верхнюю цену игры.

ü Цена игры – это объективно возможный средний результат, характеризующий игру .

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

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

Пример 2.5.1.Решить матричную игру с платежной матрицей .