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

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

ОГЛАВЛЕНИЕ

Следующая >>

В Таблице 16.11 подчеркнуты оптимальные отклики игроков на стратегии, выбранные партнером.
Из таблицы видно, что в рассматриваемой игре есть 3 равновесия Нэша. Только одно из этих равнове-
сий совпадает с решением, полученным обратной индукцией. Указанная ситуация является типичной,
т. е. решение, полученное методом обратной индукции всегда является равновесием по Нэшу, что по-
казывает следующая теорема.
Теорема 157:
В игре с совершенной информацией (и конечным числом ходов) любое решение, полученное
методом обратной индукции, является равновесием по Нэшу.

Опишем идею доказательства данной теоремы. В доказательстве мы используем следующий оче-
видный факт:
Пусть дан некоторый набор стратегий. Если делать ходы на основе этих стратегий, то каждой вер-
шине соответствует одна и только одна траектория (цепь ходов), соединяющая ее с одной из конечных
вершин. Можно сопоставить любой вершине единственный набор выигрышей, взяв его из той конечной
вершины, в которой заканчивается соответствующая ей траектория.
Предположим, что набор стратегий, полученный обратной индукцией, (s1 , . . . , sm ), не является
равновесием Нэша. Это означает, что у некоторого игрока i существует стратегия si = si , которая
?
может дать ему более высокий выигрыш при тех же стратегиях других игроков, s?i . Набору стратегий
( si , s?i ) соответствует некоторая альтернативная траектория игры, идущая из начальной вершины.
?
Можно рассмотреть эту траекторию, начиная с конечной вершины. В какой-то из вершин на данной
траектории выигрыш i-го игрока, соответствующий стратегиям (si , s?i ), должен оказаться ниже вы-
игрыша, соответствующего стратегиям ( si , s?i ). Это не может случиться впервые в вершине, где ход
?
16.3. Динамические игры с совершенной информацией 653

принадлежит какому-либо другому игроку, поскольку стратегии остальных игроков не меняются. Но
если ход в такой вершине принадлежит i-му игроку, то он должен был в этой вершине сделать выбор
соответствующий стратегии si , а не выбор, соответствующий стратегии si , поскольку это ему более
?
выгодно. Это противоречит рациональности, заложенной в алгоритме обратной индукции.
Вообще говоря, не любое равновесие по Нэшу можно получить методом обратной индукции, что
видно из рассматриваемого примера. Важно понять, почему это так.
Рассмотрим, например, равновесие ? Mac и (? Mac, ˜ Mac) (Рис. 16.12, с. 651). Содержательно его
можно интерпретировать следующим образом: 2-й игрок угрожает 1-му игроку тем, что он выберет Ма-
кинтош в случае, если тот выберет IBM; под влиянием этой угрозы 1-й игрок выбирает Макинтош. Но
такая ситуация противоречит предположению о рациональности, на которое опирается метод обратной
индукции. Действительно, если 2-й игрок окажется в точке ?, то предпочтет выбрать IBM. Посколь-
ку 1-й игрок знает о том, что второй игрок рационален, он не поверит этой (пустой) угрозе. Таким
образом, рассматриваемый набор стратегий вряд ли является естественным решением игры. Другое
«добавочное» равновесие, ? IBM и (? IBM, ˜ IBM), не имеет столь же интересной интерпретации, но
вызывает аналогичные подозрения по поводу своей обоснованности.
Таким образом, можно сказать, что равновесия по Нэшу, которые не могут быть получены методом
обратной индукции, не совместимы в данном случае с гипотезой рациональности и оказываются «лиш-
ними». Как уже было сказано, это типичная ситуация в динамических играх. Как ее можно объяснить?
Сделаем по этому поводу два замечания:

9 При представлении динамической игры в нормальной форме теряется информация о последователь-
ности ходов и информации, доступной игрокам на каждом ходе25 .

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

Напрашивается вывод, что концепция равновесия по Нэшу в случае динамических игр вообще
говоря, не дает удовлетворительного прогноза исхода игры и поэтому ее требуется каким-то образом
усилить. Укажем способ такого усиления26 .
Предположим, что несколько ходов в игре уже сделано. Можно рассматривать оставшуюся часть
игры как самостоятельную игру. Выбранные игроками стратегии предписывают, что в этой оставшейся
части игры игроки будут действовать строго определенным образом. Однако такое поведение может
оказаться невыгодно игрокам — они могут предпочесть изменить свои выборы. С этой точки зрения
естественным представляется требование динамической согласованности:
Равновесные стратегии должны быть такими, чтобы ни у одного из игроков не было стимула
менять их в процессе игры.
Часть игры, начинающаяся в некоторой вершине и включающая в себя все, что следует за этой
вершиной, в теории игр называют подыгрой.

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

В рассматриваемой игре есть 3 подыгры, одна из них — сама игра и две собственных подыгры,
начинающиеся в вершинах ? и ˜.
Основываясь на требовании динамической согласованности, можно ввести концепцию равновесия,
которая усилила бы концепцию Нэша.
25
В дальнейшем мы увидим, как из нормальной формы получить развернутую форму. При двойном преоб-
разовании получается, что полученная развернутая форма не совпадает с исходной развернутой формой.
26
По-английски процесс избавления от «лишних» равновесий называют refinement — усовершенствование,
уточнение. Особенно много способов уточнения равновесий предложено для динамических игр с несовершенной
и/или неполной информацией, о которых пойдет речь ниже.
16.3. Динамические игры с совершенной информацией 654
Определение 94:
Совершенным в подыграх равновесием27 называется набор стратегий, такой что он является равно-
весием Нэша в полной игре, а соответствующие части этого набора стратегий являются равновесиями
по Нэшу во всех собственных подыграх этой игры.

Приложим данное определение к динамической игре «Выбор компьютера» (Рис. 16.12 на с. 651).
Представим подыгру, начинающуюся в вершине ? в нормальной форме. Игрок 1 не осуществляет в
этой подыгре выбора. Игрок 2 имеет две стратегии: ? IBM и ? Mac. Матрица игры представлена в
Таблице 16.12.

Таблица 16.12.

Игрок 2
? IBM ? Mac
c b
a+c a
Игрок 1

В данной игре есть единственное равновесие Нэша. В нем 2-й игрок выбирает IBM. Таким образом,
чтобы равновесие Нэша в исходной игре было совершенным, требуется, чтобы оно предписывало в
вершине ? выбор IBM. Набор стратегий ? Mac и (? Mac, ˜ Mac) не удовлетворяет этому требованию,
поэтому он не может быть совершенным в подыграх равновесием.
Во второй собственной подыгре, которая начинается в вершине ˜, в равновесии Нэша 2-й игрок
выбирает Макинтош. Поэтому набор стратегий ? IBM и (? IBM, ˜ IBM) не является совершенным в
подыграх равновесием.
С другой стороны, набор ? IBM и (? IBM, ˜ Mac) является равновесием по Нэшу в полной
игре и соответствует равновесиям по Нэшу в каждой из собственных подыгр. Поэтому данный набор
стратегий является совершенным в подыграх равновесием. Видим, что он совпал с тем решением,
которое мы раньше получили, применив обратную индукцию. Это совпадение не является случайным,
как показывает следующая теорема.
Теорема 158:
В игре с совершенной информацией и конечным числом ходов множество решений, получаемых
обратной индукцией, совпадает с множеством совершенных в подыграх равновесий.

Рассуждения, аналогичные приведенным в доказательстве предыдущей теоремы (Теоремы 157),
позволяют показать, что решение, полученное обратной индукцией, составляет равновесие Нэша в
каждой подыгре, то есть оно является совершенным в подыграх равновесием.
Докажем, обратное: любое совершенное в подыграх равновесие может быть получено обратной ин-
дукцией. Предположим, что это не так. Рассматривая игру, начиная с конечных вершин, мы в таком
случае найдем некоторую вершину, в которой впервые выбор одного из игроков не соответствует алго-
ритму обратной индукции. Это означало бы, что выбор, соответствующий равновесной стратегии этого
игрока, не является оптимальным. Значит, заменив его на выбор, соответствующий обратной индук-
ции, этот игрок мог бы получить в данной подыгре более высокий выигрыш. Другими словами, если
бы сделанное предположение было верным, то у игрока нашлась бы в данной подыгре альтернатив-
ная стратегия, которая гарантирует ему более высокий выигрыш при неизменных стратегиях других
игроков, что противоречит предположению о том, что стратегия является оптимальным откликом
игрока.
Нормальная форма игры может быть очень громоздкой. Использование приведенной только что
теоремы позволяет сильно упростить поиск совершенных в подыграх равновесий, поскольку не требу-
ется записывать игры в нормальной форме и находить в них равновесия Нэша.
Например в игре «Рэкет», рассмотренной выше, стратегия фирмы должна указывать, как именно
фирма будет реагировать на каждый из возможных уровней ? , т. е. функцию y(?). Поэтому процесс
поиска равновесия по Нэшу по существу включает максимизацию в функциональном пространстве.
Использование обратной индукции позволяет упростить эту задачу.
27
Немецкий экономист Рейнгард Зельтен предложил концепцию совершенного в подыграх равновесия в ста-
тье, посвященной моделям олигополий (R. Selten: Spieltheoretische Behandlung eines Oligopolmodells mit Nach-
fragetragheit, Zeitschrift fur die gesamte Staatswissenschaft 12 (1965): 301–324, 667–689).
16.3. Динамические игры с совершенной информацией 655

Следует отметить, что многие игры являются довольно сложными, и, даже применяя обратную
индукцию, равновесие в них найти сложно. Характерным примером является игра в шахматы. По-
скольку это конечная игра с совершенной информацией, то в ней должно существовать по край ней
мере одно решение, получаемое обратной индукцией, и, соответственно, совершенное в подыграх равно-
весие. Тот факт, что в шахматах существует решение, известен уже давно, однако найти такое решение
в настоящее время не представляется возможным даже с применением компьютера. Понятно, что если
игроки обладают ограниченными способностями, то совершенное в подыграх равновесие может быть
не очень реалистичным предсказанием результата игры.
В сочетании с Теоремой 156 Теоремы 157 и 158 гарантируют существование совершенного в подыг-
рах равновесия в конечных играх с совершенной информацией. Если выигрыши различны, то имеет
место и единственность совершенного в подыграх равновесия.

Задачи
В следующих играх найдите решение, используя обратную индукцию.
 692. Два школьника играют в следующую игру. Каждый из кучки, состоящей из 6 камней, берет по
очереди один или два камня. Проигрывает тот, кто взял последний камень.
 693. Муж и жена выбирают, провести вечер дома или у друзей, причем друзья у них разные. Выиг-
рыши заданы следующей матрицей (Таблица 16.13), где a, b, c, d > 0 — параметры. Жена делает свой
выбор первой. При каких условиях на параметры супруги проведут вечер дома вместе?

Таблица 16.13.

муж
дома у друзей
b c
дома a 0
0 c
жена
у друзей d d


 694. Барин выбирает, какую долю ? стоимости y урожая забирать у крестьянина в виде издольщи-
ны. Он при этом максимизирует функцию вида

? y ? ? 2,

то есть желает побольше получить, но не желает прослыть жадным, что возможно при слишком боль-
шом ? (? ? [0, 1]). Крестьянин имеет целевую функцию (1 ? ? )y ? y 2 , то есть максимизирует прибыль
по y (y 0) при квадратичной функции затрат.
 695. Предположите, что в играх, представленных в задаче 676 предыдущего параграфа (с. 644)
игрок, выбирающий абсциссу, ходит первым.
 696. «Трудовое соглашение» (В. Леонтьев)
Профсоюз заключает с фирмой контракт на несколько лет, в котором оговаривается уровень за-
работной платы (w 0). Предполагается, что профсоюз достаточно мощный, чтобы навязать фирме
любой уровень заработной платы.
Фирма в течении срока действия контракта не может изменить уровень заработной платы, но
может выбирать количество нанимаемых работников (l 0 , в тыс. чел.). Профсоюз максимизирует
следующую целевую функцию:
u(w, l) = wl ? 2l2 ,
где 2l2 — издержки работы для членов профсоюза.
Фирма максимизирует свою прибыль:
v
?(w, l) = 2 l ? wl.

 697. «Справедливый дележ пирога»
В игре участвуют n игроков. Нужно разделить пирог между игроками, то есть выбрать вектор
n
(?1 , . . . , ?n ), где ?i 0, i=1 ?i = 1.
16.4. Динамические игры с несовершенной информацией 656

Предлагается следующая процедура дележа. Игрок с номером 1 режет пирог. Остальные игроки
по порядку номеров берут любой из кусков по выбору. Последний кусок достается 1 -му игроку.
(1) Нарисуйте дерево игры при n = 3. Опишите множество стратегий каждого из игроков.
(2) Найдите совершенное в подыграх равновесие. Докажите, что справедливый дележ ?i = 1/n
будет единственным равновесием.
 698. Дополните дерево, изображенное на Рис. 16.13 выигрышами игроков, используя номера букв
своего имени и фамилии (см. задачу 682 на с. 645). Найдите все совершенные в подыграх равновесия
в получившейся игре.

Игрок 1


Игрок 2




Рис. 16.13.

 699. Рассмотрите динамическую игру, сконструированную на основе статической антагонистиче-
ской игры двух лиц (см. определение в задаче 686 предыдущего параграфа, с. 646), так что игроки
делают ходы по очереди (например, сначала первый, потом второй), и тот, кто ходит вторым, знает,
какое решение принял тот, кто ходит первым. Пусть (x? , x? ) — седловая точка функции полезности
1 2
первого игрока, u1 (x1 , x2 ). Докажите, что набор стратегий (x? , x? ) является совершенным в подыграх
1 2
равновесием в этой игре вне зависимости от порядка ходов.
 700. Пусть, как и в предыдущей задаче, на основе статической антагонистической игры двух лиц
строится динамическая игра. Докажите, что делать ход вторым в общем случае (при отсутствии седло-
вой точки) более выгодно. Предполагается, что соответствующие совершенные в подыграх равновесия
существуют.



16.4 Динамические игры с несовершенной информацией
Особенность рассматриваемых в предыдущем разделе игр — каждый игрок, перед тем, как сделать
ход, полностью знает предысторию игры — выборы, сделанные ранее им и другими игроками. Другими
словами игрок знает, в какой вершине дерева он оказался. В этом разделе мы рассмотрим класс игр,
называемых играми с несовершенной информацией28 , в которых игроки могут не знать полностью
предысторию игры. Т. е., осуществляя очередной ход, они знают, что находятся в одной из вершин
некоторого подмножества множества всех вершин дерева игры (так называемого информационного
множества).
Примером игры с несовершенной информацией служит любая статическая игра. Ее можно искус-
ственно «динамизировать», задав произвольным образом порядок ходов и определив подходящим обра-
зом информационные множества, как это сделано ниже для Игры 16.2.1 (с. 624) «Выбор компьютера»
(см. Рис. 16.14).
Предположим, что первый игрок ходит первым, второй — вторым. Есть две вершины, в которых
ход принадлежит 2-му игроку, однако сам он не может различить, выбирая свои действия, в какой вер-
шине он находится; другими словами, эти две вершины находятся в одном и том же информационном
множестве.
Как видим, развернутая форма игр с несовершенной информацией несколько более сложна, чем
развернутая форма игр с совершенной информацией. Дополнительно к тем составляющим, которые
28
Мы используем кальку с английского термина games of imperfect information. В русскоязычной литературе
использовался термин «игры с неполной информацией», но его предпочтительнее использовать для обозначения
игр, которые по-английски называются games of incomplete information.
16.4. Динамические игры с несовершенной информацией 657

? Игрок 1
IBM
Mac

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

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

ОГЛАВЛЕНИЕ

Следующая >>