Нижняя и верхняя цена игры. Принцип минимакса

Рассмотрим конечную игру размерности m×n. Решим задачу: определить оптимальные стратегии игроков. Проанализируем каждую из стратегий первого игрока. Выбирая стратегию , он должен рассчитывать на то, что второй игрок ответит на нее той из своих стратегий , для которой выигрыш первого игрока минимален. Обозначим это значение выигрыша :

(1) .

Здесь знаком обозначено минимальное значение параметра при всех возможных .

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

, или ,учитывая формулу (1),

(2) .

Величина называется нижней ценой игры или максиминным выигрышем (максимином) первого игрока.

Число лежит в определенной строке платежной матрицы. Соответствующая этой строке стратегия первого игрока называется максиминной стратегией. Если он будет придерживаться максиминной стратегии, то ему при любом поведении противника гарантирован выигрыш не меньший . Это его гарантированный выигрыш, если он придерживается наиболее осторожной максиминной стратегии.

Аналогичное рассуждение можно провести за второго игрока. Так как он заинтересован в том, чтобы выигрыш первого игрока был минимальным, то он должен просмотреть каждую свою j–тую стратегию ( столбец чисел ) и определить максимальный выигрыш первого игрока при этой стратегии. Обозначим это значение выигрыша :

(3) .

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

(4)

Величина называется верхней ценой игры или минимаксным выигрышем (минимаксом) второго игрока.

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

Принцип осторожности, диктующий игрокам выбор своих наиболее осторожных стратегий (максиминной для первого и минимаксной для второго игроков) в теории игр называется «принципом минимакса». Максиминную и минимаксную стратегии игроков обозначают общим термином «минимаксные стратегии».

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

Пример 1. Игра Ани и Бори. Добавим к платежной матрице игры справа столбец чисел и снизу строку чисел :

Боря Аня	Б0	Ч1
Б1
Ч1	–1		–1

Вычисляем нижнюю цену игры по формуле (2): = 0, верхнюю цену игры по формуле (4): = 0. Они оказались одинаковыми.

Элемент = 0, выделенный в платежной матрице, является одновременно минимальным в строке и максимальным в столбце. В геометрии точку на поверхности, обладающую свойством: аппликата точки минимальна по одной координате и максимальна по другой, называют седловой точкой. По аналогии этот термин применяется в теории игр: элемент платежной матрицы с указанным свойством называется седловой точкой матрицы, а про игру говорят, что она имеет седловую точку.

Если нижняя цена игры равна верхней, то их общее значение называется ценой игры (иногда – чистой ценой игры).

Седловой точке соответствует пара минимаксных стратегий. В примере 1 – это стратегии и . Они являются оптимальными стратегиями игроков. Если один из игроков, например, Боря, отклонится от своей оптимальной второй стратегии, а Аня будет придерживаться своей первой оптимальной стратегии, то Боря проиграет 1 рубль. Таким образом, решением игры Ани и Бори является пара их минимаксных стратегий.

Для каждой игры с седловой точкой существует решение – пара минимаксных стратегий игроков, являющиеся оптимальными стратегиями игроков , а цена игры v равна общему значению нижней и верхней цены игры: v = = . Это решение обладает свойством:

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

Пример 2. Игра Эдварда и Фионы. Снова добавим к платежной матрице игры справа столбец чисел и снизу строку чисел . Вычисляем нижнюю цену игры по формуле (2): = –3 , верхнюю цену игры по формуле (4): = 2. Они оказались неодинаковыми. Заметим, что < , игра не имеет седловой точки.

Фиона Эдвард
		–3	–3
	–3		–3

Теорема. Для любой конечной игры выполняется неравенство:

£

Доказательство. Пусть = , = По определению чисел и имеем: £ , ³ , следовательно, £ .

Для первого игрока в примере 2 любая стратегия является максиминной, для второго игрока минимаксной стратегией является его первая стратегия.

В случае < , как в примере 2, минимаксные стратегии игроков являются неустойчивыми. В самом деле, пусть первый игрок применяет свою первую максиминную стратегию, а второй – свою минимаксную первую стратегию. До тех пор, пока оба игрока придерживаются этих стратегий, выигрыш первого игрока равен 2. Но если второму игроку станет известно, что первый игрок применяет первую стратегию, то он применит свою вторую стратегию и сведет выигрыш противника к –3. Наоборот, если первому игроку станет известно, что второй игрок применяет вторую стратегию, то он применит тоже вторую стратегию и увеличит свой выигрыш до 4. Поэтому минимаксные стратегии игроков в игре без седловой точки не являются оптимальными.

В случае игры без седловой точки неясно, как находить цену игры и как определять оптимальные стратегии. Для этого необходимо обобщить понятие стратегии, определив понятие смешанной стратегии, предложенной Д. Бернулли в 1732 году.