Смешанные стратегии. Максиминные и минимаксные стратегии игроков.

Предположим, что мы играем в игру без седловой точки. Например, игра с матрицей

Предположим, что мы – 1 -й игрок. А второй игрок всегда угадывает нашу стратегию.

В этой ситуации мы можем гарантировать нижний выигрыш

.

Поставим себя на место 2 -го игрока, тогда в такой же ситуации (1 -й всегда угадывает нашу стратегию) и верхний проигрыш

Таким образом, для матричных игр мы имеем понятия нижнего выигрыша и верхнего проигрыша. Легко доказывается, что .

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

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

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

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

Определение. Смешанная стратегия игрока есть вероятностное распределение на множестве его чистых стратегий.

В случае, когда игрок имеет только конечное число m чистых стратегий, смешанная стратегия представляет собой m- мерный вектор , удовлетворяющий условиям:

, ( 1 )

( 2 )

Обозначим множество всех смешанных стратегий игрока 1 через , а множество всех смешанных стратегий игрока 2 – через .

Предполагаем, что игроки участвуют в игре с матрицей А. Если игрок 1 выбирает смешанную стратегию , а 2 -й – , то ожидаемый выигрыш будет равен

. ( 3 )

Или в матричных обозначениях ( 4 )

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

. ( 5 )

можно рассматривать как взвешенное среднее ожидаемых выигрышей для игрока 1, когда он использует против чистых стратегий игрока 2. Таким образом, этот минимум будет достигаться на некоторой чистой стратегии j:

( 6 )

где – j -й столбец матрицы А.

Поэтому игрок 1 должен выбрать так, чтоб максимизировать , т.е. что бы получить

. (7)

Такая стратегия называется максиминной стратегией игрока 1.

Аналогично, если игрок 2 выбирает стратегию , он будет иметь ожидаемый верхний проигрыш.

, ( 8 )

где – i -тая строка матрицы А, и должен выбрать так, что бы иметь

( 9 )

Такая стратегия у называется минимаксной стратегией игрока 2. Числа и называются значениями игры для игроков 1 и 2 соответственно.

Теорема о минимаксе. Лемма 1 (об опорной гиперплоскости).

Для любой функции , определенной на произвольном декартовом произведении , имеет место неравенство ( 1 )

Отсюда следует, что . Нижний выигрыш игрока 1 не может превышать верхнего проигрыша игрока 2.

Теорема о минимаксе утверждает, что .

Лемма1. (Теорема об опорной гиперплоскости)

Пусть – замкнутое выпуклое множество в n-мерном евклидовом пространстве, а – некоторая точка, не принадлежащая . Тогда существуют такие числа , что ( 2 ) и ( 3 )

(Геометрически это означает, что через точку можно провести гиперплоскость так, что будет лежать целиком «выше» этой гиперплоскости).

Доказательство.

Пусть – такая точка из , расстояние которой от минимально. (такая точка существует, т.к. замкнуто.) Положим

, ,

.

Очевидно, что равенство (2) выполняется, поскольку .

Необходимо показать, что имеет место (3). Мы имеем

 

и, следовательно,

Поэтому

Допустим, что существует , для которого

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

Квадрат расстояния от до имеет вид

 

 

Поэтому

При (т.е. при ) имеем

.

Здесь первое слагаемое по предположению не превосходит , а второе больше . Поэтому .

Отсюда следует, что для , достаточно близких к нулю

.

Но это противоречит выбору . Следовательно, для любых условие (3) должно выполняться.