Равновесная ситуация

Пример 2. Два игрока А и В, не глядя друг на друга, кладут на стол по картонному кружку красного (r), зелёного (g) или синего (b) цветов. Сравнивают цвета кружков и расплачиваются друг с другом так, как показано в матрице игры

.

Считая, что эта игра повторяется многократно, определим оптимальные стратегии каждого из игроков.

Начнём с последовательного анализа стратегий игрока А, не забывая о том, что, выбирая стратегию игрока А, нужно принимать в расчёт ответную стратегию игрока В, которую он может выбрать так, чтобы свести выигрыш игрока А к минимуму.

Так, на стратегию он может ответить стратегией (минимальный выигрыш игрока А равен –2), на стратегию – стратегией или (минимальный выигрыш игрока А равен 1), а на стратегию – стратегией (минимальный выигрыш игрока А равен –3).

Игроку А следует остановить свой выбор на стратегии , при которой его минимальный выигрыш максимален (max{-2,1,-3}=1):

maxmin = 1.

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

Аналогичные рассуждения можно провести и за игрока В. Т.к. игрок В заинтересован в том, что чтобы обратить выигрыш игрока А в минимум, то ему нужно проанализировать каждую свою стратегию с точки зрения максимального выигрыша игрока А.

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

3 2 1

minmax = 1.

Игрок В должен остановить свой выбор на стратегии , при которой максимальный выигрыш игрока А минимален (min{3,2,1}=1). Если игрок В придерживается этой стратегии, то при любом поведении противника он проиграет не больше 1.

В рассмотренном примере числа maxmin и minmax совпали:

maxmin = minmax =1.

Стратегии и являются оптимальными стратегиями игроков А и В в следующем смысле: при многократном повторении игры отказ от выбранной стратеги любым из игроков уменьшает его шансы на выигрыш.

Ситуация {, } – равновесная.

Рассмотрим теперь произвольную матричную игру

Опишем общий алгоритм, посредством которого можно определить, есть ли в игре ситуация равновесия или нет.

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

Действия игрока А:

1-ый шаг. В каждой строке матрицы А находится минимальный элемент

2-ой шаг. Среди чисел выбирается максимальное число

, т.е.

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

Число называется нижней ценой игры.

Принцип построения стратегии игрока А, основанный на максимизации минимальных выигрышей, называется принципом максимина, а выбираемая в соответствии с этим принципом стратегия - максиминной стратегией игрока А.

Действия игрока B:

1-ый шаг. В каждом столбце матрицы А ищется максимальный элемент

,

2-ой шаг. Среди чисел выбирается число

или, подробнее,

.

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

Число называется верхней ценой игры.

Принцип построения стратегии игрока B, основанный на минимизации максимальных потерь, называется принципом минимакса, а выбираемая в соответствии с этим принципом стратегия - минимаксной стратегией игрока B.

Теорема 1. Нижняя цена игры всегда не превосходит верхней цены игры:

Если, т.е.

,

то ситуация оказывается равновесной, и ни один из игроков не заинтересован в том, чтобы её нарушить.

В случае, когда нижняя цена игры равна верхней цене игры, их общее значение называется просто ценой игры и обозначается через :

.

Цена игры совпадает с элементом матрицы игры А, расположенным на пересечении - ой строки (стратегия игрока А) и -го столбца (стратегия игрока B) – минимальным в своей строке и максимальным в своём столбце.

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

Стратегии и , соответствующие седловой точке, называются оптимальными, а совокупность пары оптимальных стратегий и цены игры – решением матричной игры с седловой точкой.

Замечание. Седловых точек (а значит пар оптимальных стратегий) в матричной игре может быть несколько.

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

.

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

.

Следовательно, и максиминная стратегия первого игрока .

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

.

Следовательно, и минимаксная стратегия второго игрока .

Поскольку верхняя и нижняя цена игры совпадают , то оптимальным поведением каждого из игроков будет выбор первой стратегии. Ситуация {, } – равновесная.

Дата добавления: 2014-01-11