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

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

ОГЛАВЛЕНИЕ

Следующая >>

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


Теорема 5.
В игре с совершенной информацией (и конечным числом ходов) любое решение, полу-
ченное методом обратной индукцией, является равновесием по Нэшу.


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


Вообще говоря, не любое равновесие по Нэшу можно получить методом обратной индук-
ции, что видно из рассматриваемого примера. Важно понять, почему это так.
Рассмотрим, например, равновесие BMac и (DMac, CMac) (Рис. 161, стр. 658). Содер-
жательно его можно интерпретировать следующим образом: 2-й игрок угрожает 1-му иг-
року тем, что он выберет Макинтош в случае, если тот выберет IBM; под влиянием этой
угрозы 1-й игрок выбирает Макинтош. Но такая ситуация противоречит предположению о
рациональности, на которое опирается метод обратной индукции. Действительно, если 2-й
игрок окажется в точке D, то предпочтет выбрать IBM. Поскольку 1-й игрок знает о том,
что второй игрок рационален, он не поверит этой (пустой) угрозе. Таким образом, рас-
сматриваемый набор стратегий вряд ли является естественным решением игры. Другое
«добавочное» равновесие, BIBM и (DIBM, CIBM), не имеет столь же интересной интер-
претации, но вызывает аналогичные подозрения по поводу своей обоснованности.
Таким образом, можно сказать, что равновесия по Нэшу, которые не могут быть получены
методом обратной индукции, не совместимы в данном случае с гипотезой рациональности

659
660
и оказываются «лишними». Как уже было сказано, это типичная ситуация в динамических
играх. Как ее можно объяснить? Сделаем по этому поводу два замечания:
* При представлении динамической игры в нормальной форме теряется информация о
последовательности ходов и информации, доступной игрокам на каждом ходе.251
* Сам способ записи динамической игры в нормальной форме, как он описан выше, за-
ключает в себе предположение, что игроки выбирают свои стратегии до начала игры раз и
навсегда и уже не меняют их в дальнейшем в ходе игры.
Напрашивается вывод, что концепция равновесия по Нэшу в случае динамических игр
вообще говоря, не дает удовлетворительного прогноза исхода игры и поэтому ее требует-
ся каким-то образом усилить. Укажем способ такого усиления.252
Предположим, что несколько ходов в игре уже сделано. Можно рассматривать оставшую-
ся часть игры как самостоятельную игру. Выбранные игроками стратегии предписывают,
что в этой оставшейся части игры игроки будут действовать строго определенным обра-
зом. Однако такое поведение может оказаться невыгодно игрокам — они могут предпо-
честь изменить свои выборы. С этой точки зрения естественным представляется требова-
ние динамической согласованности:
Равновесные стратегии должны быть такими, чтобы ни у одного из игроков не было
стимула менять их в процессе игры.
Часть игры, начинающаяся в некоторой вершине и включающая в себя все, что следует за
этой вершиной, в теории игр называют подыгрой.


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

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


Определение 11.
253
называется набор стратегий, такой что он яв-
Совершенным в подыграх равновесием
ляется равновесием Нэша в полной игре, а соответствующие части этого набора страте-
гий являются равновесиями по Нэшу во всех собственных подыграх этой игры.


251
В дальнейшем мы увидим, как из нормальной формы получить развернутую форму. При двойном преоб-
разовании получается, что полученная развернутая форма не совпадает с исходной развернутой формой.
252
По-английски процесс избавления от «лишних» равновесий называют refinement — усовершенствование,
уточнение. Особенно много способов уточнения равновесий предложено для динамических игр с несовер-
шенной и/или неполной информацией, о которых пойдет речь ниже.

660
661

Приложим данное определение к динамической игре «Выбор компьютера» (Рис. 658, стр.
658). Представим подыгру, начинающуюся в вершине D в нормальной форме. Игрок 1 не
осуществляет в этой подыгре выбора. Игрок 2 имеет две стратегии: DIBM и DMac. Мат-
рица игры представлена в Таблице 17.
В данной игре есть единственное равновесие Нэша. В нем 2-й игрок выбирает IBM. Таким
образом, чтобы равновесие Нэша в исходной игре было совершенным, требуется, чтобы
оно предписывало в вершине D выбор IBM. Набор стратегий BMac и (DMac, CMac) не
удовлетворяет этому требованию, поэтому он не может быть совершенным в подыграх
равновесием.
Во второй собственной подыгре, которая начинается в вершине C, в равновесии Нэша 2-й
игрок выбирает Макинтош. Поэтому набор стратегий BIBM и (DIBM, CIBM) не является
совершенным в подыграх равновесием.
С другой стороны, набор BIBM и (DIBM, CMac) является равновесием по Нэшу в полной
игре и соответствует равновесиям по Нэшу в каждой из собственных подыгр. Поэтому
данный набор стратегий является совершенным в подыграх равновесием. Видим, что он
совпал с тем решением, которое мы раньше получили, применив обратную индукцию. Это
совпадение не является случайным, как показывает следующая теорема.


Теорема 6.
В игре с совершенной информацией и конечным числом
ходов множество решений, получаемых обратной индук- Oaaeeoa 17
цией, совпадает с множеством совершенных в подыграх
Игрок 2
равновесий.
DIBM DMac
c b
Игрок 1
Рассуждения, аналогичные приведенным в доказательстве a +c a
предыдущей теоремы (Теоремы 5), позволяют показать, что
решение, полученное обратной индукцией, составляет равновесие Нэша в каждой подыг-
ре, то есть оно является совершенным в подыграх равновесием.
Докажем, обратное: любое совершенное в подыграх равновесие может быть получено об-
ратной индукцией. Предположим, что это не так. Рассматривая игру, начиная с конечных
вершин, мы в таком случае найдем некоторую вершину, в которой впервые выбор одного
из игроков не соответствует алгоритму обратной индукции. Это означало бы, что выбор,
соответствующий равновесной стратегии этого игрока, не является оптимальным. Значит,
заменив его на выбор, соответствующий обратной индукции, этот игрок мог бы получить
в данной подыгре более высокий выигрыш. Другими словами, если бы сделанное предпо-
ложение было верным, то у игрока нашлась бы в данной подыгре альтернативная страте-
гия, которая гарантирует ему более высокий выигрыш при неизменных стратегиях других
игроков, что противоречит предположению о том, что стратегия является оптимальным
откликом игрока.


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


253
Немецкий экономист Рейнгард Зельтен предложил концепцию совершенного в подыграх равновесия в
статье, посвященной моделям олигополий (R. Selten (1965), "Spieltheoretische Behandlung eines Oligopol-
modells mit Nachfragetragheit," Zeitschrift fur die gesamte Staatswissenschaft, 121, 301-24, 667-89).

661
662
сий, поскольку не требуется записывать игры в нормальной форме и находить в них рав-
новесия Нэша.
Например в игре «Рэкет», рассмотренной выше, стратегия фирмы должна указывать, как
именно фирма будет реагировать на каждый из возможных уровней ?, т.е. функцию y(?).
Поэтому процесс поиска равновесия по Нэшу по существу включает максимизацию в
функциональном пространстве. Использование обратной индукции позволяет упростить
эту задачу.
Следует отметить, что многие игры являются довольно сложными, и, даже применяя об-
ратную индукцию, равновесие в них найти сложно. Характерным примером является игра
в шахматы. Поскольку это конечная игра с совершенной информацией, то в ней должно
существовать по край ней мере одно решение, получаемое обратной индукцией, и, соот-
ветственно, совершенное в подыграх равновесие. Тот факт, что в шахматах существует
решение, известен уже давно, однако найти такое решение в настоящее время не пред-
ставляется возможным даже с применением компьютера. Понятно, что если игроки обла-
дают ограниченными способностями, то совершенное в подыграх равновесие может быть
не очень реалистичным предсказанием результата игры.


В сочетании с Теоремой 4 Теоремы 5 и 6 гарантируют существование совершенного в по-
дыграх равновесия в конечных играх с совершенной информацией. Если выигрыши раз-
личны, то имеет место и единственность совершенного в подыграх равновесия.

Задачи


В следующих играх найдите решение, используя обратную индукцию.


26. Два школьника играют в следующую игру. Каждый из кучки, состоящей из 6 камней,
берет по очереди один или два камня. Проигрывает тот, кто взял последний камень.


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


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



662
663
то есть желает побольше получить, но не желает прослыть жадным, что возможно при
слишком большом ? (??[0,1]). Крестьянин имеет целевую функцию (1 – ?) y – y2, то есть
максимизирует прибыль по y (y > 0) при квадратичной функции затрат.


29. Предположите, что в играх, представленных в задаче 10 предыдущего параграфа (стр.
649) игрок, выбирающий абсциссу, ходит первым.


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


31. «Справедливый дележ пирога»
В игре участвуют n игроков. Нужно разделить пирог между игроками, то есть выбрать
вектор (?1, ..., ?n), где ?i > 0, ¤i=1?i = 1.
n


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


32. Дополните дерево, изображенное на Рис. 162 выигрышами игроков, используя номера
букв своего имени и фамилии (см. задачу 16 на стр. 650). Найдите все совершенные в по-
дыграх равновесия в получившейся игре .




663
664

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

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

ОГЛАВЛЕНИЕ

Следующая >>