Максиминные и минимаксные стратегии. Нижняя и верхняя цены игры в чистых стратегия

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

Рассмотрим матричную - игру с игроками А и В, в которой игрок А обладает чистыми стратегиями , а игрок В - чистыми стратегиями . Значения функции выигрыша игрока А обозначим через , т. е. .

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

, (3.1)

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

(3.2)

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

, (3.3)

то по формуле (5.2)

. (3.4)

Описанный принцип (3.3) или (3.4) выбора эффективной стратегии игроком А называется макашштым принципом, а выигрыш - максимином. Стратегия , соответствующая максимину , называется максминной стратегией игрока А. Множество всех (чистых) максиминных стратегий игрока А обозначим через .

Аналогично вводится критерий оценки выигрышей для игрока В. Как игрок В предполагает, что игрок А играет наилучшим для себя образом, то выигрышем игрока А будет максимальное из чисел (5.7); обозначим его через :

(3.5)

и назовем показателем неэффективности стратегии . Таким образом, для любой стратегии игрока В наибольший его проигрыш равен. В интересах игрока В - выбрать стратегию с минимальным показателем неэффективности. Наименьшее из чисел (3.5) обозначим :

(5.9)

Отсюда в силу формулы (3.5) получим для выражение:

(3.6)

Выбор игроком В стратегии с наименьшим показателем оправдывает то, что он назван показателем неэффективности.

Критерий (3.6) выбора эффективной стратегии для игрока В называется минимаксным принципом, а выигрыш называется минимаксом. Стратегия , для которой

(3.7)

называется минимаксной стратегией игрока В. Множество всех (чистых) минимаксных стратегий игрока В обозначим через

Величину называют верхней ценой игры.

Для нахождения нижней и верхней цен игры удобно матрицу игры (4.1) увеличить в размерах, приписав -й столбец показателей эффективности стратегий игрока А и -ю строку показателей неэффективности , стратегий игрока В, В результате получим следующую матрицу:

А=	A_i			…		(3.8)
			…
			…
…	…	…	…	…	…
			...
				…

Теорема 5.1. Для элементов матрицы (3.8) имеют место неравенства

и, следовательно, нижняя цена игры не больше ее верхней цены в чистых стратегиях:

(3.9)

Пример 5.1. Найти нижнюю и верхнюю цены игры, а также макси- минные стратегии игрока А и минимаксные стратегии игрока В в условиях примера 4.2 при денежным единицам.

Решение. Определяя показатели эффективности стратегий и неэффективности стратегий , мы из матрицы (4.2) получим матрицу


-3			-3
	-2		-2
		-2	-2
			-2

из которой видно, что нижняя цена игры , а верхняя цена игры. Так как , то стратегии и игрока А являются максиминными: . Аналогично, из равенств вытекает, что каждая из стратегий игрокаВ является минимаксной: .