<< Предыдущая

стр. 160
(из 163 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

42. Найдите совершенные байесовские равновесия в игре, изображенной на Рис. 167.


43. «Карточный блеф»
В начале игры игроки (A и B) вносят по 1 д.е. После этого с равной вероятностью игрок A
получает одну из двух возможных карт, «старшую» или «младшую». Далее игрок может
A повысить ставку, добавив 2 д.е. Если он этого не сделает, то игра заканчивается и день-
ги забирает игрок B. Если A повышает, то делает ход игрок B. Он либо уравнивает, до-
бавляя 2 д.е., либо пасует. В первом случае карта открывается и деньги забирает игрок A,
если карта старшая, и игрок B, если карта младшая. Во втором случае деньги забирает
игрок A.
Покажите, что в этой игре нет совершенного байесовского равновесия в чистых стратеги-
ях. Найдите равновесие в смешанных стратегиях. Как часто игрок A будет блефовать, т.е.
повышать, имея младшую карту? Как часто игрок B будет уравнивать?

Игры и Парето-оптимальность
В этой главе мы приведем укажем на условия, гарантирующие Парето-оптимальность ре-
шений некоторых игр, рассматриваемых в книге.
Пусть задана игра с полной информацией в нормальной форме:
G = ?I, {Xi}I , {ui}I ?.
Напомним определение Парето-оптимальности.


Определение 13.
Исход y ? X доминирует по Парето исход x ? X (является Парето-улучшением по
сравнению с x) , если в нем каждый игрок получает выигрыш не меньше, чем в исходе x,
а хотя бы один из игроков получает выигрыш строго больше, чем в x, т.е.
ui(yi) > ui(xi) ? i ? I,

687
688
и
? j ? I: uj(yi) > uj(xi).
Исход x ? X называется Парето-оптимальным, если не существует другого исхода x ?
^ ˜
^
X, такого что он доминирует x по Парето.
Множество всех Парето-оптимальных точек называют границей Парето.


Рассмотренные выше решения (равновесия) не являются в общем случае Парето-
оптимальными, что, в частности, показывает следующая игра.


Игра 14. «ha!= `3i=……=»262
Перед двумя участниками игры стоит следующий выбор. Каждый может потребовать,
чтобы организатор игры дал сто долларов другому игроку, либо потребовать, чтобы он
дал один доллар ему самому. Участники одновременно и независимо делают выбор, после
чего организатор игры исполняет их требования. (


Игру можно представить с помощью следующей матрицы (см. Таблицу 25).
Oaaeeoa 25
Второй игрок
$100 другому $1 ему
$100 100 101
другому
Первый 100 0
игрок 0 1
$1 ему 101 1


В этой игре у каждого игрока существует строго доминирующая стратегия — потребовать
1 доллар себе. Соответствующий исход является и равновесием в доминирующих страте-
гиях, и равновесием Нэша. Примечательным является то, что этот исход является единст-
венным не Парето-оптимальным исходом. Так, исход, в котором оба игрока требуют от-
дать сто долларов другому строго доминирует его по Парето.

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

262
Эта игра представляет собой вариант известнейшей игры «Дилемма заключенных». Сюжет «Дилеммы
заключенных» следующий. Двух человек арестовали по подозрению в совершении некоторого преступле-
ния. Судья предложил каждому следующую сделку. Если он сознается в преступлении, а другой нет, то
сознавшийся получает 1 год наказания, а не сознавшийся — 10 лет. Если сознаются оба, то каждый получит
по 7 лет. Заключенным также известно, что если никто из них не сознается, то оба получат по 3 года. (Циф-
ры у разных авторов разные.)

688
689
ной вершине исходной игры «прикрепить» дерево исходной игры. Рис. 178 показывает
как это сделать на примере игры Ауманна.
Аналогично, чтобы получить дерево n раз повторяющейся игры, следует к каждой конеч-
ной вершине n–1 раз повторяющейся игры «прикрепить» дерево исходной игры. Конечно,
для описания повторяющейся игры не обязательно задавать все дерево игры, достаточно
указать исходную игру и сколько раз она повторяется. В отличие от обычных игр, в по-
вторяющихся играх принято сопоставлять выигрыши не только конечным вершинам, но и
тем промежуточным, которые соответствуют конечным вершинам исходной игры. Общий
выигрыш рассчитывается суммированием выигрышей в вершинах, лежащих на траекто-
рии игры. Таким образом, если uij — выигрыш, полученный i-м игроком в результате j-го
повторения игры (на j-м «раунде»), то общий выигрыш в n раз повторяющейся игре со-
ставит
n
ui = ¤uij.
j=1

Часто в повторяющихся играх выигрыши дисконтируют, что отражает тот факт, что игро-
ки больше предпочитают получить выигрыш сейчас, а не в будущем. Другими словами,
пусть ?ij ? (0, 1) — дисконтирующий множитель i-го игрока для j-го раунда. Тогда общий
выигрыш рассчитывается по формуле
n
ui = ¤(?ij) uij.
j–1

j=1

Будем считать в дальнейшем, что ?ij = ?i, т.е. дисконтирующий множитель не зависит от
раунда.
Как нетрудно заметить, повторяющиеся игры являются разновидностью игр с почти со-
вершенной информацией, поэтому совершенное в подыграх равновесие в них можно на-
ходить обратной индукцией.
1-й


2-й
100
(100) (1)
1-й 1-й 1




2-й 2-й

0
(101)
(100) (101) (101) (1)
100 0
(101) (100) (101) (101) (1)
100 0
0 1 0 0 1
1-й 1-й


2-й 2-й


(100) (101) (101) (1) (100) (101) (101) (1)
100 0 100 0
0 0
1 1



?enoiie 178. Aaa?au iiaoi?y?uayny ea?a Aoiaiia
Проанализируем повторяющуюся игру Ауманна. Используя обратную индукцию, рас-
смотрим последний раунд игры. Заметим, что все, что происходило в предыдущих раун-
дах, влияет только на выигрыши, но не на множества стратегий. Однако влияние на выиг-
рыши сводится только к тому, что ко всем выигрышам данного раунда добавляется одна и
та же константа, определяемая предысторией игры. Таким образом, при анализе можно не
689
690
принимать во внимание выигрыши предыдущих раундов. Тем самым, все сводится к ана-
лизу однократно повторенной игры Ауманна, равновесие которой нам известно: каждый
игрок попросит 1 доллар себе.
Далее рассмотрим игры предпоследнего раунда, которые становятся играми последнего
раунда в редуцированной игре. «Свертывание» последнего раунда добавляет к выигры-
шам предпоследнего раунда одну и ту же константу (в нашем случае это 1 для обоих иг-
роков). Предыстория игры тоже влияет только тем, что добавляет константу к выигры-
шам. Таким образом, опять с точностью до константы получаем исходную игру. Продол-
жая редуцировать игру, мы на всех раундах получим одно и то же решение, совпадающее
с равновесием исходной игры. Таким образом, равновесная траектория будет представ-
лять собой n раз повторенное равновесие обычной игры Ауманна. Догадка о возникнове-
нии сотрудничества в повторяющейся игре в данном случае не подтверждается.
Можно сформулировать общую теорему для повторяющихся игр.


Теорема 7.
Пусть в игре G с совершенной информацией (и конечным числом ходов) существует
единственное совершенное в подыграх равновесие. Тогда в повторенной n раз игре G,
n
G ,существует единственное совершенное в подыграх равновесие, причем равновесные
n
стратегии в игре G являются повторениями равновесных стратегий в игре G.


Мы не будем приводить формальное доказательство. Доказательство очевидным образом
конструируется по схеме, которую мы применили, анализируя повторяющуюся игру Ау-
манна.
То, что гипотеза о возникновении сотрудничества не подтверждается может быть связано
с тем, что игроки знают, что игра закончится на n-м ходу. И в самом деле, если бы игра
Ауманна повторялась бесконечное число раз, то сотрудничество между игроками могло
бы иметь место.
Мы ранее не вводили в рассмотрение бесконечные игры, однако их основные элементы
можно определить по аналогии с конечными играми. Выигрыш в бесконечно повторяющей-
263
ся игре рассчитывается по формуле
?
j–1
ui = ¤(?i) uij.
j=1

В отличие от игры с конечным числом повторений, в бесконечно повторяющейся игре
Ауманна возможно возникновение сотрудничества. Рассмотрим стратегии следующего
вида:
- Сотрудничать, если на предыдущих ходах другой игрок сотрудничал (в том числе,
в первом раунде тоже сотрудничать).
- Не сотрудничать, если хотя бы на одном из предыдущих раундов другой игрок взял
1 доллар себе.
Такую стратегию называют триггерной.
Если дисконтирующие множители ?1, ?2 достаточно высоки, то такие стратегии будут со-
ставлять совершенное в подыграх равновесие.


263
Поскольку ?i ? (0, 1), то при ограниченности выигрышей в исходной игре ряд сходится.

690
691
Рассмотрим, при каких условиях игроку выгодно придерживаться триггерной стратегии,
если его партнер также ее придерживается.
Поскольку после того, как игрок взял 1 доллар себе, его партнер во всей дальнейшей игре
будет поступать таким же образом, то отказавшемуся от сотрудничества игроку будет вы-
годно брать 1 доллар себе во всей дальнейшей игре. Таким образом, если отказ от сотруд-
ничества произойдет в k-м раунде, то игрок не может получить больше, чем
?
k–1
¤(?i) ?100 + (?i) ?101 + ¤ (?i) ?1.
j–1 k–1 j–1

j=1 j=k+1

Если же не один из игроков не будет отклонятся от триггерной стратегии, то их выигрыши
составят
?
¤(?i) ?100.
j–1

j=1

Таким образом, чтобы отклоняться было не выгодно, должно быть выполнено неравенст-
во
? ?
k–1

¤(?i) ?100 > ¤(?i) ?100 + (?i) ?101 + ¤ (?i) ?1
j–1 j–1 k–1 j–1

j=1
j=1 j=k+1

или
99 ?i
?
1
¤ (?i) ?99 > (?i) ?1 ? > 1 ? 99 ?i > 1 – ?i ? ?i > 100.
j–1 k–1
1–?i
j=k+1

Таким образом, если дисконтирующие множители малы, то будущие выигрыши имеют
малое значение для игроков и им будет выгодно отклонится от триггерных стратегий. Ес-
ли же дисконтирующие множители достаточно велики, то триггерные стратегии будут
составлять равновесие, в котором будет иметь место сотрудничество.
Следует отметить, однако, что рассмотренное равновесие будет не единственным совер-
шенным в подыграх равновесием в бесконечно повторяющейся игре Ауманна. На самом
деле в бесконечно повторяющихся играх практически всегда равновесий бесконечно мно-
го. В частности, стратегии в которых независимо от предыстории игроки всегда берут 1
доллар себе тоже составляют равновесие.
Существует теорема (в англоязычной литературе она известна под названием Folk Theo-
rem, что на русский можно перевести как «Народная теорема»), утверждающая, что в бес-

<< Предыдущая

стр. 160
(из 163 стр.)

ОГЛАВЛЕНИЕ

Следующая >>