Матричные антагонистические игры с нулевой суммой в чистых стратегиях (стр. 6 из 16)

2. нормальная или стратегическая форма. Каждый участник (игрок) k, где

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

Ранее упоминалось о таком понятии, как «антагонистическая игра». Примером такой игры может служить игра «Орлянка». Дадим определение антагонистической игре.

Антагонистическая игра - игра, в которой участвуют два игрока (обычно обозначаемые I и II) с противоположными интересами. Для антагонистической игры характерно, что выигрыш одного игрока равен проигрышу другого и наоборот, поэтому совместные действия игроков, их переговоры и соглашения лишены смысла.. Определяются антагонистические игры заданием множеств стратегий игроков и выигрышей игрока I в каждой ситуации, состоящей в выборе игроками своих стратегий. Таким образом, формально антагонистическая игра есть тройка ‹А, В, Н›, в которой А и В - множества стратегий игроков, а Н (а, b) - вещественная функция (функция выигрыша) от пар (а, b), где а  A, b  В. Игрок I, выбирая а, стремится максимизировать Н(а, b),а игрок II, выбирая b, - минимизировать Н (а, b).

Пример 2:

Рассмотрим игру G(4х5) в матричной форме.

	3	4	5	2	3
	1	8	4	3	4
	10	3	1	7	6
	4	5	3	4	8

Очевидно надо выбирать ту стратегию, при которой выигрыш максимален. (Это так называемый принцип минимакса. О нём чуть позже). В правом добавочном столбце запишем минимальное значение выигрыша в каждой строке; обозначим его для i-ой строки

.

	3	4	5	2	3	2
	1	8	4	3	4	1
	10	3	1	7	6	1
	4	5	3	4	8	3
	10	8	5	7	8

Из всех значений

выделено наибольшее (3). Ему соответствует величина - гарантированный выигрыш, который называется нижней ценой игры. Исходя из принципа осторожности, надо выбрать стратегию , а противник должен выбрать стратегию . Такая стратегия называется «минимаксной». Выше было упомянуто о принципе минимакса. Рассмотрим далее соответствующую терему.

Теорема о минимаксе.

Можно доказать, что для любой функции F(x,y) определённой на произвольном декартовом произведении X× Yимеет место неравенство

. Отсюда следует, что

Запишем 2 утверждения:

Утверждение 1. Точка 0 (в m-мерном пространстве) содержится в выпуклой оболочке m+nточек

и

Утверждение 2. Существуют числа

удовлетворяющие условиям

Доказательство: Пусть А – матричная игра. Имеет место либо утверждение 1, либо утверждение 2. Если верно утверждение 1 то 0 является выпуклой линейной комбинацией m+nвекторов. Поэтому существуют такие

что

Если бы все числа

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

тогда можно положить

и получится для всех i

Значит

и

Предположим, что верно утверждение 2. Тогда

, так что . Следовательно, неравенство не имеет смысла. Предположим, что игра А изменена на игру , где . Для любых х и y , поэтому . Так как неравенство не имеет смысла, то неравенство также не выполняется. Но kпроизвольно. Значит неравенство невозможно. Т.к. то . Что и требовалось доказать.

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

Рассмотрим игру

с платежной матрицей Следует определить наилучшую стратегию игрока I среди стратегий , и игрока II среди стратегий , . Определение наилучших стратегий игроков основано на принципе, который предполагает, что противники, участвующие в игре, одинаково разумны и каждый из них делает все для того, чтобы добиться своей цели. Найдем наилучшую стратегию игрока I. Допустим, что он выбрал i-ю стратегию (i –ю строку матрицы (1)). Тогда он получит меньше, чем – наименьшее число в этой строке. Причем это будет в том случае, если игрок II каким-то образом раскроет стратегию игрока I. Из сказанного следует, что I игрок, если он не желает рисковать, т.е. играть не оптимально, должен действовать следующим образом – определить наименьшие элементы всех строк и выбрать ту из них, в которой это число наибольшее. В этом случае он гарантирует себе выигрыш равный наибольшему из меньших чисел всех строк. Этот выигрыш равен Число это “низкий выигрыш” игрока I и его называют нижним значением или нижней ценой игры. Как же рассуждает второй игрок? “Если я выберу j-ую стратегию (j-ый столбец), то самый лучший выигрыш у игрока I будет наибольшее число этого столбца. Чтобы рисковать, я должен выбрать столбец, в котором это число наименьшее. В результате I игрок не сможет получить больше, чем Число представляет собой ”верхний выигрыш” игрока I и называется верхним значение или верхней ценой игры. Можно показать, что для всякой матричной игры выполняется условие . Если , то такие игры называются играми с седловой точкой. Из неравенства следует, что . Это фактически означает, игрок I мог бы рассчитывать на выигрыш .