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





Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



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

Предположим, что мы – 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) должно выполняться.






Последнее изменение этой страницы: 2016-09-05; просмотров: 228; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

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