Максиминная и минимаксная стратегия

Если функция выигрышей является выпуклой, то такая игра называется выпуклой. Для них разработаны приемлемые методы решения, состоящие в отыскании чистой оптимальной стратегии (определённого числа) для одного игрока и вероятностей применения чистых оптимальных стратегий другого игрока. Такая задача решается сравнительно легко.Как было отмечено, каждый игрок стремится обеспечить себе максимально возможный выигрыш при любых действиях противника. Поэтому рассмотрим следующий вопрос: как должны вести себя игроки в матричной игре, чтобы получить больший выигрыш, т. е. в чем состоит оптимальность в матричной игре?

Пусть игрок I выбрал стратегию Максиминная и минимаксная стратегия - student2.ru , тогда игрок II выберет такую стратегию Максиминная и минимаксная стратегия - student2.ru , которая максимизирует его выигрыш и тем самым минимизирует выигрыш его противника. Стратегия игрока I, обеспечивающая ему наибольший выигрыш из всех возможных, независимо от действий противника, будет состоять в выборе такого Максиминная и минимаксная стратегия - student2.ru , для которого минимальный выигрыш будет наибольшим, т. е.

Максиминная и минимаксная стратегия - student2.ru .

Величину

Максиминная и минимаксная стратегия - student2.ru (17.3)

принято обозначать через Максиминная и минимаксная стратегия - student2.ru (или просто v) и называть нижним значением (нижней ценой) игры, а соответствующую этому значению стратегию i° игрока I — максиминной стратегией. Если игрок I придерживается данной стратегии, то его выигрыш будет не меньше максиминного значения, то есть

Максиминная и минимаксная стратегия - student2.ru (17.4)

Аналогично стратегия j°, определяемая равенством

Максиминная и минимаксная стратегия - student2.ru

называется минимаксной стратегией игрока II, а соответствующее значение Максиминная и минимаксная стратегия - student2.ru (или просто Максиминная и минимаксная стратегия - student2.ru ) — верхним значением (верхней ценой) игры.

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

Максиминная и минимаксная стратегия - student2.ru (17.5)

Полагая, что в неравенстве (17.4) j = j°, а в выражении (17.5) i = i°, получим:

Максиминная и минимаксная стратегия - student2.ru (17.6)

Принцип, которого придерживается игрок I, называется принципом максимина, так как его гарантированный выигрыш равен величине (17.3). Игрок II также придерживается этого принципа, так как

Максиминная и минимаксная стратегия - student2.ru .

Из неравенства (17.6) следует, что во всякой матричной игре Максиминная и минимаксная стратегия - student2.ru .При этом возможны два следующих случая:

Максиминная и минимаксная стратегия - student2.ru . (17.7)

В первом случае игрок I может обеспечить себе выигрыш Максиминная и минимаксная стратегия - student2.ru , игрок II в состоянии ему не дать больше, чем Максиминная и минимаксная стратегия - student2.ru .

Вопрос о разделе между игроками разности Максиминная и минимаксная стратегия - student2.ru (а в рассматриваемом случае она положительна) остается, таким образом, открытым. Это влечет за собой неопределенность в действиях игроков. Поясним сказанное.

Пример.

Максиминная и минимаксная стратегия - student2.ru .

Нахождение Максиминная и минимаксная стратегия - student2.ru и Максиминная и минимаксная стратегия - student2.ru матрицы Н может быть проведено по следующей схеме:

Максиминная и минимаксная стратегия - student2.ru

Максиминная и минимаксная стратегия - student2.ru

Максиминная и минимаксная стратегия - student2.ru = 3, Максиминная и минимаксная стратегия - student2.ru = 4, Максиминная и минимаксная стратегия - student2.ru ; 2-я строка — максиминная стратегия; 1-й столбец - минимаксная стратегия. Применение максиминной и минимаксной стратегий приводит к выигрышу игрока I, равному Максиминная и минимаксная стратегия - student2.ru (разность Максиминная и минимаксная стратегия - student2.ru достается игроку II, но можно привести пример, когда эта разность достается игроку I). Однако игрок I в игре Максиминная и минимаксная стратегия - student2.ru , отклоняясь от максиминной и выбирая первую стратегию, может выиграть 4>3 (при условии, что игрок II придерживается минимаксной стратегии). Но игрок II, разгадав намерения игрока I, может выбрать свою четвертую стратегию и тем самым наказать его (даст ему 2<3). Игрок I в свою очередь может изменить решение и выбрать такую стратегию, при которой будет наказан игрок II, и т. д. И это будет происходить во всех играх, в которых Максиминная и минимаксная стратегия - student2.ru .

Итак, при Максиминная и минимаксная стратегия - student2.ru Максиминная и минимаксная стратегия - student2.ru максиминная и минимаксная стратегии не являются оптимальными.

Рассмотрим теперь второй случай. Равенство (17.7) означает, что величина, которую гарантирует себе игрок I, совпадает с величиной, больше которой игрок II не позволит ему получить. Поэтому игрокам необходимо выбрать максиминную и минимаксную стратегии соответственно.

Пример.

Максиминная и минимаксная стратегия - student2.ru

Максиминная и минимаксная стратегия - student2.ru 2-я строка — максиминная стратегия; 2-й столбец — минимаксная стратегия. В этом случае любое отклонение каждого из игроков от этих стратегий (игрока I — от максиминной, игрока II — от минимаксной) не может оказаться выгодным.

В случае Максиминная и минимаксная стратегия - student2.ru максиминная и минимаксная стратегии называются оптимальными стратегиями игроков, а общее значение Максиминная и минимаксная стратегия - student2.ru (в дальнейшем мы его будем обозначать через v) — значениемили ценой игры.

Оптимальные стратегии будем обозначать через i*, j*. Нужно установить связь между принципом максимина и седловой точкой функции H(i, j). Вспомним определение седловой точки.

Точка (а, b) называется седловой точкой функции Н, если

Максиминная и минимаксная стратегия - student2.ru .

Это неравенство выражает следующее свойство функции Н в точке (а, b): при любом изменении значения переменной а значение функции Н может уменьшиться, а при изменении значения переменной b — увеличиться. Термин “седловая точка” вводится по аналогии с термином “поверхность седла”, которая искривляется вверх в одном направлении и вниз — в другом.



Наши рекомендации