Решение матричных игр двух лиц с нулевой суммой.


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


Рассмотрим игру с платежной матрицей

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

Число это “низкий выигрыш” игрока I и его называют нижним значением или нижней ценой игры.
Как же рассуждает второй игрок? “Если я выберу j-ую стратегию (j-ый столбец), то самый лучший выигрыш у игрока I будет

– наибольшее число этого столбца. Чтобы рисковать, я должен выбрать столбец, в котором это число наименьшее. В результате I игрок не сможет получить больше, чем

Число представляет собой ”верхний выигрыш” игрока I и называется верхним значение или верхней ценой игры.
Можно показать, что для всякой матричной игры выполняется условие . Если , то такие игры называются играми с седловой точкой. Из неравенства следует, что . Это фактически означает, игрок I мог бы рассчитывать на выигрыш .
Рассмотрим два примера:

Пример 1:

        
, , , вторая строка максиминная стратегия. 2 - ой столбец – минимаксная стратегия.
В этом примере применение минимаксной стратегии приводит к выигрышу 1 игрока равному , а достается второму игроку.
Пример 2:


          
, , , 1 строка – максиминная стратегия. 1 столбец – минимаксная стратегия.
Применение в этой игре минимаксных и максиминных стратегий приводит к выигрышу 1 игрока равному , т.е. достается ему.
Из приведенных примеров видно, что при применение минимаксных и максиминных стратегий не приводит к определенному результату. В связи с этим возникает неопределенность в действиях игроков. Например, в первом примере 1 игрок отклоняясь от максиминной стратегии может выиграть 2 > 1(второй игрок при этом придерживается минимаксными стратегиями).
Поэтому при минимаксная и максиминная стратегии не являются оптимальными.
Рассмотрим – величина, которую себе гарантирует первый игрок, совпадает с той величиной, больше которой 2 игрок не позволит ему получить.
Пример 3:

             , , . Отклонение одностороннее от минимаксной и максиминной стратегий невыгодно игрокам.
Опр.: Если , то минимаксная или максиминная стратегии называются оптимальными стратегиями игроков, называется значениями или ценой игры.
Опр.: Стратегии и н0азываются минимальными в игре ,
,
, если

Пара , называется седловой точкой игры.
Можно доказать следующую теорему:
теорема: для того чтобы игра A имела седловую точку, необходимо и достаточно

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

            
, , . Здесь нет седловых точек! По субъективной оценке игрока I его первая стратегия лучше второй в два раза. Тогда он может смешивать с вероятностями 2/3 и 1/3, т.е. выбрать не первую и не вторую, а вектор . В этом случае средний выигрыш первого игрока составит

Число 1/3 называется ожидаемым выигрышем игрока I при использовании смешанной стратегии . Этот результат соответствует розыгрышу игры из большого числа партий.
Первый игрок может смешивать свой стратегии с любыми вероятностями . В результате, вместо двух первоначальных стратегий (1,0) и (0,1) оказывается бесконечное множество стратегий вида .
Аналогично может рассмотреть свои возможности второй игрок . Если , то ожидаемый выигрыш в нашем примере равен

В общем случае для игры под смешанной стратегией 1 игрока будем понимать вектор . Аналогично обозначим смешанную стратегию 2-го игрока . При этом выполняется условие и . Очевидно, каждая чистая стратегия является частичным случаем смешанной: все стратегии, кроме данной, имеют вероятности равные нулю, а данный единице.
Величина ожидаемого выигрыша игрока I при применении смешанных стратегий равна математическому ожиданию

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

Hosted by uCoz