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

стр. 159
(из 165 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

100 101 0 1 100 101 0 1
1-й 1-й


2-й 2-й


100 0 101 100 0 101
1 1
100 101 0 100 101 0
1 1



Рис. 16.29. Дважды повторяющаяся игра Ауманна


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

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

Будем считать в дальнейшем, что ?ij = ?i , т. е. дисконтирующий множитель не зависит от раунда.
Как нетрудно заметить, повторяющиеся игры являются разновидностью игр с почти совершенной
информацией, поэтому совершенное в подыграх равновесие в них можно находить обратной индукцией.
Проанализируем повторяющуюся игру Ауманна. Используя обратную индукцию, рассмотрим по-
следний раунд игры. Заметим, что все, что происходило в предыдущих раундах, влияет только на
выигрыши, но не на множества стратегий. Однако влияние на выигрыши сводится только к тому, что
ко всем выигрышам данного раунда добавляется одна и та же константа, определяемая предысторией
игры. Таким образом, при анализе можно не принимать во внимание выигрыши предыдущих раундов.
Тем самым, все сводится к анализу однократно повторенной игры Ауманна, равновесие которой нам
известно: каждый игрок попросит 1 доллар себе.
Далее рассмотрим игры предпоследнего раунда, которые становятся играми последнего раунда в
редуцированной игре. «Свертывание» последнего раунда добавляет к выигрышам предпоследнего ра-
унда одну и ту же константу (в нашем случае это 1 для обоих игроков). Предыстория игры тоже влияет
только тем, что добавляет константу к выигрышам. Таким образом, опять с точностью до константы
получаем исходную игру. Продолжая редуцировать игру, мы на всех раундах получим одно и то же
решение, совпадающее с равновесием исходной игры. Таким образом, равновесная траектория будет
представлять собой n раз повторенное равновесие обычной игры Ауманна. Догадка о возникновении
сотрудничества в повторяющейся игре в данном случае не подтверждается.
Можно сформулировать общую теорему для повторяющихся игр.
16.7. Игры и Парето-оптимальность 679
Теорема 160:
Пусть в игре G с совершенной информацией (и конечным числом ходов) существует единствен-
ное совершенное в подыграх равновесие. Тогда в повторенной n раз игре G , Gn , существует един-
ственное совершенное в подыграх равновесие, причем равновесные стратегии в игре Gn являются
повторениями равновесных стратегий в игре G .

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

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

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

Таким образом, чтобы отклоняться было не выгодно, должно быть выполнено неравенство
? ?
k?1
j?1 j?1 k?1
(?i )j?1 · 1
· 100 · 100 + (?i ) · 101 +
(?i ) (?i )
j=1 j=1 j=k+1

или
?
99?i 1
(?i )j?1 · 99 (?i )k?1 · 1 ? 1 ? 99?i 1 ? ?i ? ?i .
1 ? ?i 100
j=k+1

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

Существует теорема (в англоязычной литературе она известна под названием Folk Theorem, что
на русский можно перевести как «Народная теорема»), утверждающая, что в бесконечно повторяю-
щейся конечной статической игре с полной информацией любой «разумный» вектор выигрышей может
возникнуть в некотором совершенном в подыграх равновесии, если дисконтирующие множители доста-
точно близки к единице. Под разумным вектором выигрышей мы понимаем такой вектор выигрышей,
который является выпуклой комбинацией выигрышей исходной игры (с точностью до множителей
1 ? ?i , необходимых для того, чтобы сделать выигрыши сопоставимыми), и кроме того, в нем каж-
дый элемент должен быть не меньше некоторой пороговой величины. В разных вариантах теоремы
пороговая величина разная: это либо выигрыш в каком-либо равновесии Нэша исходной игры, либо
минимаксный выигрыш38 .
Эту теорему можно интерпретировать как утверждение о том, что в бесконечно повторяющейся
игре «почти все возможно». Кроме того, из теоремы можно сделать вывод, что в бесконечно повторяю-
щейся игре совершенных в подыграх равновесий бывает, как правило, «слишком много». Понятно, что
это снижает ценность полученного выше результата о возникновении сотрудничества в игре Ауманна.


16.7.2 Игры торга
Теперь мы рассмотрим важный класс игр, моделирующих достижение соглашений между эконо-
мическими субъектами, — так называемые игры торга. В таких играх в условиях полной информации
решения всегда Парето-оптимальны.
Игра 15. «Торг»39
Два игрока (A и B ) делят между собой некоторую сумму денег (или любое бесконечно делимое благо).
Будем считать, что общее количество равно 1. Дележ можно задать долей, x ? [0, 1], достающейся
игроку A. Если игрок A получает x, то игрок B , соответственно, получает 1 ? x. Торг происходит в
несколько раундов. На каждом раунде один из игроков предлагает дележ xj , где j — номер раунда.
Другой игрок может либо отклонить, либо принять этот дележ. Если дележ принимается, то торг
заканчивается и игроки получают свои доли (xj , 1 ? xj ). Если дележ отклоняется, то настает очередь
другого игрока предложить свой дележ. Игрок A предлагает дележ в раундах с нечетными номерами,
а игрок B — в раундах с четными номерами. Если за n раундов игроки не договорятся, то игра
заканчивается и каждый игрок получает 0 .
Предполагается, что игроки предпочитают получить деньги как можно раньше, поэтому получен-
ная сумма денег умножается на дисконтирующий множитель, то есть если игроки договорятся на j -м
j?1 j?1
раунде, то их выигрыши составят ?A xj и ?B (1 ? xj ) соответственно, где ?A , ?B ? (0, 1) — дискон-
тирующие множители.

Рассмотрим эту игру при n = 3. На Рис. 16.30 показано дерево игры.
Проанализируем эту игру, используя обратную индукцию. В
последнем раунде игрок B заведомо примет предложение игрока
Игрок A 2
A, если ?B (1 ? x3 ) > 0 , т. е. если x3 < 1. Если x3 = 1, то игроку
x1 B все равно, принять или отклонить предложение. Игроку A
Игрок B выгодно назвать x3 как можно б?льшим. Значит, в равновесной
о
x1 стратегии не может быть x3 < 1 , ведь игрок A тогда мог бы
1?x1
Игрок B немного увеличить x3 , не изменив выбора игрока B , и увеличил
x2 бы при этом свой выигрыш. Таким образом, в равновесии x3 = 1 .
Чтобы при этом действительно было равновесие, игрок B должен
Игрок A
?A x2 в своей стратегии быть «благожелательным» по отношению к
?B (1?x2 ) A, то есть принять его предложение; в противном случае игрок
Игрок A
A мог бы предложить x3 меньше 1 и увеличить при этом свой
x3
выигрыш.
Игрок B
Анализ 3-го раунда показывает, что игрок A должен будет
2
?A x3
0
предложить x3 = 1 , а игрок B должен будет принять этот де-
2
?B (1?x3 )
0

38
См. J. W. Friedman: A Non-cooperative Equilibrium for Supergames, Review of Economic Studies 38 (1971):
1–12. Рис. 16.30.
39
A. Rubinstein: Perfect Equilibrium in a Bargaining Model, Econometrica 50 (1982): 97–109.
16.7. Игры и Парето-оптимальность 681

леж. Мы можем теперь «свернуть» игру, заменив 3-й раунд на
2
конечный узел с выигрышами ?A и 0 .
2
Во 2-м раунде игрок A выбирает между ?A (если отклоня-
ет предложение) и ?A x2 (если принимает). Таким образом, если
x2 > ?A , то он примет предложенный дележ, а если x2 < ?A ,
то отклонит. При x2 = ?A игроку A все равно, какой выбор сделать. Игрок B предпочтет получить
выигрыш ?B (1 ? x2 ), а не 0 , поэтому он не станет предлагать x2 < ?A . С другой стороны любой дележ
x2 > ?A не является равновесным, поскольку игрок B в этом случае может уменьшить x2 , не меняя
выбора игрока A, и, тем самым, увеличить свой выигрыш. Таким образом, в равновесии x2 = ?A .
Чтобы этот выбор был равновесным, требуется, чтобы в равновесии игрок A принял дележ x2 = ?A ,
несмотря на то, что отказ от этого дележа должен принести ему такой же выигрыш40 .
2
Остается торг, состоящий из одного раунда, в котором игроки получат ?A и ?B (1 ? ?A ), если не
придут к соглашению (см. Рис. 16.31). Рассуждения, аналогичные приведенным выше, показывают,
что уже в первом раунде игроки придут к соглашению: игрок B примет дележ x1 = 1 ? ?B (1 ? ?A ),
предложенный игроком A . Выигрыши при этом составят 1 ? ?B (1 ? ?A ) и ?B (1 ? ?A ).

Игрок A
x1
Игрок B
2
?A x1
?B (1??A ) 1?x1

Рис. 16.31.

О торге в условиях полной информации можно сделать два замечания:
1) Торг заканчивается на первом раунде.
2) Равновесный исход Парето-оптимален.
Рис. 16.32 показывает графический способ нахождения равновесия в игре «Торг» при n = 3 . На
этом графике видно, как изменяется граница Парето от раунда к раунду, сжимаясь в сторону начала
координат из-за дисконтирования. Процесс нахождения решения изображен толстой кривой, выходя-
щей из начала координат.

u2
1




?B (1??A )

u1
2 1
?A
1??B (1??A )


Рис. 16.32. ??


Задачи
 710. Постройте по своему имени и фамилии игру, как это описано в задаче 682 на с. 645. Найдите в
этой игре границу Парето. Есть ли среди равновесий Нэша Парето-оптимальные?
40
Это довольно естественно, если взглянуть на ситуацию с той точки зрения, что игрок B всегда может
предложить игроку A дележ x2 = ?A ? ? , где ? — малое положительное число, тем самым гарантируя, что A
примет дележ. Число ? здесь можно выбрать произвольно малым.
16.7. Игры и Парето-оптимальность 682

 711. Объясните, почему в антагонистической игре (игре, в которой сумма выигрышей игроков —
постоянная величина) любой исход является Парето-оптимальным.
 712. Объясните, в чем состоит аналогия между аукционом, в котором игрок платит названную им
цену, и игрой Ауманна (дилеммой заключенных). Представьте аукцион с двумя участниками как игру
и сравните множество равновесий Нэша с границей Парето.
 713. Рассчитайте общие выигрыши (в каждой из конечных вершин) в повторяющейся дважды игре
Ауманна, изображенной на Рис. 16.29, считая, что дисконтирующие множители обоих игроков равны
1/2 .

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

стр. 159
(из 165 стр.)

ОГЛАВЛЕНИЕ

Следующая >>