Ситуация равновесия. Теоремы о седловой точке

В антагонистической игре естественно считать оптимальным такой исход, при котором ни одному из игроков невыгодно от него отклоняться. Подобный исход (x*,y*) называется ситуацией равновесия, а принцип оптимальности, основанный на отыскании ситуации равновесия, - принципом равновесия.

Определение. В матричной игре с матрицей размерности исход является ситуацией равновесия или седловой точкой, если

(2.6)

 

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

Принцип оптимального поведения: если в матричной игре имеется седловая точка, то оптимальным является выбор стратегии, соответствующей седловой точке. Что будет, если в игре окажется более одной седловой точки?

Теорема. Пусть две произвольные седловые точки в матричной игре. Тогда:

(2.7)

 

Доказательство. Из определения ситуации равновесия имеем:

(2.8)

(2.9)

 

Подставим в левую часть неравенства (2.8) , а в правую - , в левую часть неравенства (2.9) - , в правую - . Тогда получим:

 

Откуда следует равенство:

 

Из теоремы следует, что функция выигрыша принимает одно и то же значение во всех ситуациях равновесия. Именно поэтому число называется ценой игры. А стратегии , соответствующие любой из седловых точек, называются оптимальными стратегиями игроков 1 и 2, соответственно. В силу (2.7) все оптимальные стратегии игрока взаимозаменяемы.

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

Теорема. Для существования в матричной игре cедловой точки (i*,j*) необходимо и достаточно, чтобы максимин был равен минимаксу:

(2.10)

 

Доказательство. Необходимость. Если (i*,j*) – седловая точка, то, согласно (2.6):

Поэтому

(2.11)

Вместе с тем имеем:

(2.12)

 

Из (2.11) и (2.12) получаем:

(2.13)

 

Рассуждая аналогично, приходим к равенствам:

(2.14)

 

Таким образом,

 

С другой стороны, всегда выполняется обратное неравенство (2.5), поэтому справедливым оказывается (2.10).

Достаточность. Пусть справедливо (2.10). Докажем наличие седловой точки. Имеем:

(2.15)

(2.16)

 

Согласно равенству (2.10), неравенства (2.15) и (2.16) превращаются в равенства. После чего имеем:

Теорема доказана. Попутно доказано, что общее значение максимина и минимакса равно цене игры .

Смешанное расширение игры

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

(2.17)

 

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

Пример 3. Пусть матрица игры имеет вид:

 

Для такой матрицы , т.е. ситуации равновесия не существует. Осторожными стратегиями игроков являются i*=1, j*=2. Пусть игрок 2 придерживается стратегии j*=2, а игрок 1 выберет стратегию i=2. тогда последний получит выигрыш 3, что на две единицы больше, чем максимин. Если, однако, игрок 2 догадается о планах игрока 1, он сменит свою стратегию на j=1, и тогда первый получит выигрыш 0, то есть меньше своего максимина. Аналогичные рассуждения можно провести и для второго игрока. В целом можно сделать вывод, что применение авантюрной стратегии может в отдельной партии игры принести результат больший, чем гарантированный, но ее применение связано с риском. Возникает вопрос, нельзя ли скомбинировать надежную осторожную стратегию с авантюрной таким образом, чтобы увеличить свой средний выигрыш? По существу вопрос стоит о том, как разделить между игроками выигрыш (2.17)?

Оказывается, что разумным решением является применение смешанной стратегии, то есть случайный выбор чистых стратегий. Напомним, что стратегия игрока 1 называется смешанной, если выбор i-ой строки производится им с некоторой вероятностью p_i. Такую стратегию можно отождествить с распределением вероятностей на множестве строк. Предположим, что первый игрок имеет m чистых стратегий, а второй – n чистых стратегий. Тогда их смешанные стратегии – это вероятностные вектора:

(2.18)

Рассмотрим две возможные смешанные стратегии первого игрока из примера 3: . Эти стратегии отличаются распределениями вероятностей между чистыми стратегиями. Если в первом случае строки матрицы выбираются игроком с равными вероятностями, то во втором случае – с разными. Когда мы говорим о смешанной стратегии, то имеем ввиду под случайным выбором не выбор «наобум», а выбор, основанный на работе случайного механизма, обеспечивающего нужное нам распределение вероятностей. Так для реализации первой из смешанных стратегий хорошо подходит подбрасывание монетки. Игрок выбирает первую строку или вторую в зависимости от того, как выпадет монетка. В среднем игрок будет одинаково часто выбирать как первую строку, так и вторую, однако выбор на конкретной итерации игры не подчинен никакому фиксированному правилу и обладает максимальной степенью скрытности: до реализации случайного механизма он неизвестен даже самому первому игроку. Для реализации второй смешанной стратегии хорошо подходит механизм жеребьевки. Игрок берет семь одинаковых бумажек, пометив три их них крестиком, и бросает в шапку. Затем, наудачу, извлекает одну из них. Согласно классической теории вероятностей он вытащит бумажку с крестиком с вероятностью 3/7, а чистую бумажку – с вероятностью 4/7. Подобный механизм жеребьевки способен реализовывать любые рациональные вероятности.

Пусть игроки придерживаются смешанных стратегий (2.18). Тогда выигрыш первого игрока на отдельно взятой итерации игры является случайной величиной: v(X,Y). Поскольку игроки выбирают стратегии независимо друг от друга, то, согласно теореме умножения вероятностей, вероятность выбора исхода (i,j) с выигрышем равна произведению вероятностей . Тогда закон распределения случайной величины v(X,Y) задан следующей таблицей

Пусть теперь игра разыгрывается бесконечно долго. Тогда средний выигрыш в такой игре равен математическому ожиданию величины v(X,Y).

(2.19)

 

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

Пример 4. Рассчитаем средний выигрыш (2.19) для игры из примера 3 при использовании игроками следующих стратегий: . Матрица выигрышей и матрица вероятностей выглядят следующим образом:

Найдем среднее:

(2.20)

 

Таким образом, средний выигрыш (2.20) имеет промежуточное значение между максимином и минимаксом.

Поскольку для любой пары смешанных стратегий X и Y можно подсчитать среднее значение игры, то возникает задача о поиске оптимальной стратегии. Естественно начать с исследования осторожных стратегий. Осторожная стратегия первого игрока обеспечивает ему максимин. Осторожная стратегия второго игрока не позволяет первому выиграть более минимакса. Самым значительным результатом в теории игр с противоположными интересами можно считать следующий:

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

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

Решение игры 2х2

Пример 5. Решить игру . Не трудно убедиться, что седловой точки нет. Обозначим оптимальную стратегию первого игрока (х, 1-х) – это вектор столбец, но для удобства записываем его в виде строки. Оптимальную стратегию второго игрока обозначим (y,1-y).

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

v(x,y)	2	-1	-4	7
p	xy	x(1-y)	(1-x)y	(1-x)(1-y)

 

Находим средний выигрыш за итерацию первого игрока – математическое ожидание случайной величины v(x,y):

Преобразуем данное выражение:

Данное математическое ожидание состоит из константы (5/7) и переменной части: 14(x-11/14)(y-8/14). Если значение y отличается от 8/14, то первый игрок всегда может выбрать х таким образом, чтобы сделать переменную часть положительной, увеличивая свой выигрыш. Если значение х отличается от 11/14, то второй игрок всегда может выбрать y таким образом, чтобы сделать переменную часть отрицательной, уменьшая выигрыш первого игрока. Таким образом, седловая точка определяется равенствами: x*=11/14, y*=8/14.

2.5 Решение игр

Способ решения подобных игр покажем на примере.

Пример 6. Решить игру . Убеждаемся, что седловой точки нет. Обозначим смешанную стратегию первого игрока X=(х, 1-х) – это вектор столбец, но для удобства записываем его в виде строки.

Пусть первый игрок применяет стратегию Х, а второй – свою j-ю чистую стратегию. Обозначим средний выигрыш первого игрока в этой ситуации как . Имеем:

(2.21)

 

Изобразим графики функций (2.21) на отрезке [0,1].

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

Поскольку искомая точка В является пересечением линий и , то ее абсцисса может быть найдена как решение уравнения:

Таким образом, оптимальная смешанная стратегия первого игрока – (5/9, 4/9). Ордината точки В является ценой игры. Она равна:

(2.22)

 

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

Пусть оптимальная стратегия игрока 2 есть Y*=(y*, 0, 1-y*) и пусть первый игрок использует свою первую чистую стратегию. Тогда:

 

Таким образом, оптимальная стратегия второго игрока: Игра полностью решена.

Доминирование стратегий

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

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

Пусть - две строки матрицы игры, а - два ее столбца.

Определение. Говорят, что строка доминирует строку , если . Говорят, что столбец доминирует столбец , если .

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

Рассмотрим еще один пример.

Пример 7. Пусть дана матричная игра:

Первая строка покомпонентно меньше второй. Значит, игрок 1 никогда не будет ее применять, и потому матрицу можно упростить, удалив первую строку. В результате получается матрица:

У вновь полученной матрицы первый столбец доминируется вторым, поэтому его тоже можно убрать. Окончательно исходная матрица упрощается до: