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

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

ОГЛАВЛЕНИЕ

Следующая >>

Изобразим полученное решение на дереве (см. Рис. 16.8). Те действия, которые были вы-
браны соответствующим игроком в каждой из вершин, изобразим двойными линиями. Исход
игры определяется траекторией, состоящей из выбранных действий, и идущей из начальной
вершины в одну из конечных вершин21 .

Пилот

Куба Нью-Йорк

?1
Террорист
1
взорвать
не взрывать
?100 1
?100 ?1

Рис. 16.8. Решение игры «Террорист»

В данном случае мы рассмотрели игру с совершенной информацией, то есть такую игру, в
которой каждый игрок, делая выбор, знает всю предыдущую историю игры, или, если говорить
с точки зрения представления игры в виде дерева, каждый игрок знает, в какой из возможных
ситуаций (вершин дерева) он находится.
Представление игры в виде дерева соответствует развернутой форме игры22 . В дальнейшем
мы увидим, как можно представить динамическую игру в нормальной форме. А сейчас пере-
числим, что должно включать описание динамической игры (с совершенной информацией) в
развернутой форме:
¦ множество вершин дерева игры, в том числе одну начальную вершину;
¦ для каждой вершины, кроме начальной, — единственную вершину, которая непосред-
ственно ей предшествует; при этом не должно быть циклов, то есть цепь предшествующих
вершин, построенная из любой вершины, должна заканчиваться в начальной вершине (что
предполагает, в том числе, отсутствие циклов);
¦ множество игроков;
¦ для каждой вершины, кроме конечных, — единственного игрока, которому принадлежит
ход в данной вершине;
21
Предсказанный исход игры кажется довольно странным. Ведь вполне естественно, что пилот будет опасать-
ся, что террорист все-таки взорвет самолет. Данный исход, однако, полностью соответствует описанию игры, а
также сделанным предположениям. Можно сделать игру более реалистичной, если добавить возможность того,
что может встретиться террорист, которому в соответствии с его целевой функцией будет выгодно взорвать
бомбу. Такую игру мы рассмотрим в дальнейшем, в параграфе, посвященном так называемым байесовским
динамическим играм.
22
Как и нормальная форма игры, развернутая форма была впервые в явном виде описана Дж. фон Нейманом
(см. ссылки в сноске 8). См. также H. W. Kuhn: Extensive Games and the Problem of Information, in Contributions
to the Theory of Games, vol. II, H. W. Kuhn and A. W. Tucker (ed.), Princeton University Press, 1953: 193–216.
16.3. Динамические игры с совершенной информацией 649

для каждой конечной вершины, то есть такой, которая не предшествует ни одной другой
¦
вершине, — вектор выигрышей всех игроков.
(Если в игре есть случайные ходы природы, то следует также задать распределение веро-
ятностей на множестве всех возможных ходов природы.)
Первые два пункта здесь соответствуют описанию игры как дерева.
Действие в этой конструкции однозначно задается парой непосредственно следующих од-
на за другой вершин. Для каждой вершины можно определить множество действий, которые
можно осуществить, находясь в данной вершине. Множество возможных действий связано
однозначным соответствием с множеством вершин, которые непосредственно следуют за дан-
ной вершиной (т. е. которым непосредственно предшествует данная вершина), то есть каждое
выбранное действие приводит в одну и только в одну вершину.
Каждой вершине в игре с совершенной информацией соответствует единственная предыс-
тория — то есть последовательность действий, которая приводит из начальной вершины в
данную вершину.
В случае, когда в динамической игре участвуют два игрока, и игра происходит в 2 этапа,
то обратную индукцию удобно провести на основе функции отклика 2-го игрока на действия
1-го. Следующая игра иллюстрирует использование этого приема.
Игра 8. «Рэкет»23
Рэкетиры выбирают, какую долю ? (? ? [0, 1]) выручки отбирать у фирмы. Они при этом
максимизируют ?py , где p — цена, y — выпуск фирмы. Фирма имеет квадратичную функцию
издержек, так что ее прибыль (выигрыш) равна

(1 ? ?)py ? y 2 .

Фирма максимизирует прибыль при ограничении y 0. Рэкетиры делают ход первыми.
Зная, какую долю выручки они хотят отбирать, фирма выбирает уровень выпуска.



Рэкетиры

?
Фирма
y
?py
(1??)py?y 2
Рис. 16.9. Игра «Рэкет»

На Рисунке изображена структура описанной игры. Поскольку множества возможных дей-
ствий игроков в рассматриваемой игре не конечны (например, у рэкетиров — интервал [0, 1]
? R), то на рисунке они изображены в виде секторов. При этом каждой точки верхнего сек-
тора, соответствующего выбору ?, начинается некий сектор, соответствующий выбору y . На
рисунке представлен лишь один из таких нижних секторов. Поскольку в данной игре имеется
бесконечное множество (континуум) действий и исходов, на диаграмме уместно представить
способы вычисления выигрышей для выбранных действий игроков как функции от действий
игроков.
Рэкетиры, зная функцию выигрыша фирмы, могут определить, как скажется на ее выпуске
выбор ими экспроприируемой доли выручки этой фирмы. Для того, чтобы предсказать объем
23
Можно интерпретировать игру несколько по другому: вместо рэкетиров рассматривать государство, уста-
навливающее ставку налога.
16.3. Динамические игры с совершенной информацией 650

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

(1 ? ?)p ? 2y = 0.

Если ? < 1, то y > 0. Поскольку функция прибыли вогнута, то условие первого порядка
является достаточным, т. е. определяемый на его основе объем выпуска фирмы является оп-
тимальным. При ? = 1 получаем решение y = 0. Таким образом, рэкетиры могут вывести
уравнение оптимального выпуска фирмы как функции доли ?:
(1 ? ?)p
y(?) = .
2
Зная эту функцию отклика, рэкетиры максимизируют свою целевую функцию24 , т. е. ре-
шают следующую задачу
?py(?) > max .
??[0,1]

или, после подстановки y(?),
p2
· (1 ? ?)? > max .
2 ??[0,1]

Максимум достигается при ? = 1/2, то есть рэкетиры будут отбирать у фирмы половину
выручки. При этом выпуск фирмы составит p/4. Графически поиск решения представлен на
Рис. 16.10.

?
? б)
a)
1 1


1
2



y
y
p p p
2 4 2



Рис. 16.10. (а) Получение функции отклика фирмы. (б) Выбор рэкетирами оптимальной
отбираемой доли.

Мы рассмотрели здесь примеры игр, в которых каждый раз при использовании обратной
индукции оптимальный выбор единственен. Если это не так, процесс поиска решения разветв-
ляется — решение будет зависеть от того, какую именно альтернативу из тех, которые дают
игроку одинаковый выигрыш, выберет этот игрок. На Рис. 16.11 показано использование об-
ратной индукции в такой игре. В этой игре обратная индукция дает два решения: (L 1 , R 2 ) и
(L 2 , R 1 ).
Если выигрыши всех игроков во всех конечных вершинах различны, то неоднозначности при ис-
пользовании обратной индукции не возникает, поэтому решение должно быть единственным.
Теорема 156:
В конечной игре с совершенной информацией алгоритм обратной индукции дает хотя бы одно
решение.
Если, кроме того, выигрыши всех игроков во всех конечных вершинах различны, то такое
решение единственно.
24
В моделях налогообложения аналог функции ?py(?) известен как кривая Лаффера.
16.3. Динамические игры с совершенной информацией 651

1-й
L1 R1
1
2-й
0
L2 R2
L1 L1
R1 R1
0 2
0 1 1
2
1 1
1 0 0
1

Рис. 16.11. Разветвление решения при использовании обратной индукции


Идея доказательства теоремы состоит в том, что задача оптимизации на конечном множестве аль-
тернатив всегда имеет хотя бы одно решение; если же целевая функция принимает различные значения
на множестве альтернатив, то решение этой задачи единственно. Кроме того, каждая из редуцирован-
ных игр, получаемых с помощью обратной индукции, будет конечной и с различными выигрышами,
если выигрыши были различными в исходной игре.
Мы рассмотрели, как находить решение динамической игры с совершенной информацией с по-
мощью обратной индукции. Другой подход состоит в том, чтобы применить к динамической игре
концепцию равновесия Нэша, так же, как мы применяли ее к статическим играм.
Для того, чтобы это сделать, следует записать динамическую игру в нормальной форме. Как мы
помним, описание игры в нормальной форме состоит из задания (1) множества игроков, (2) множества
стратегий каждого игрока и (3) функции выигрыша каждого игрока на множестве исходов.
Множество игроков, конечно, должно быть одним и тем же в нормальной форме и в развернутой
форме игры. Прежде всего уточним понятие стратегии для игр такого типа.
В игре в развернутой форме (чистая) стратегия — это полный план действий игрока: что он будет
делать в каждой из вершин, в которой ход принадлежит ему. Это должен быть действительно полный
план, то есть в нем должно быть определено, что игрок выберет в любой своей вершине, даже если из
каких-либо соображений ясно, что процесс игры вряд ли может привести в эту вершину. То есть это
должен быть настолько полный план, что доверенное лицо игрока может использовать его в качестве
инструкции, будучи уверенным, что его поведение будет совпадать с поведением самого игрока.

? Игрок 1
IBM
Mac

? ˜
Игрок 2
IBM
Mac Mac
IBM

a+c c
a 0
c b+c
b 0
Рис. 16.12. Динамический вариант игры «Выбор компьютера»

Процесс игры для динамической игры в нормальной форме можно условно представить себе следу-
ющим образом. Каждый игрок до начала игры сообщает выбранную им стратегию организатору игры.
Организатор, руководствуясь этими стратегиями, осуществляет за игроков их ходы. Когда последова-
тельность ходов приведет организатора в конечную вершину, он раздает всем игрокам выигрыши,
соответствующие этой конечной вершине. При такой интерпретации мы, по сути дела, имеем стати-
ческую игру в которой выигрыши определяются с помощью описанного только что алгоритма.
Проиллюстрируем, как на основе развернутой формы динамической игры получить ее нормальную
форму, на примере динамического варианта Игры 16.2.1 «Выбор компьютера» (с. 624). Предположим,
что 1-й игрок выбирает себе компьютер первым. Дерево такой игры представлено на Рис. 16.12.
Вершины на дереве пронумерованы для удобства обозначения альтернатив в разных вершинах.
Игрок 1 имеет в этой игре две стратегии, совпадающие с альтернативами в вершине ?. Игрок 2 имеет
16.3. Динамические игры с совершенной информацией 652
Таблица 16.11.

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


4 стратегии. Каждая его стратегия определяет действия в двух вершинах: ? и ˜. Таким образом, 2-го
игрок имеет следующие стратегии: (? IBM, ˜ IBM), (? IBM, ˜ Mac), (? Mac, ˜ IBM), (? Mac, ˜
Mac). В Таблице 16.11 представлена та же игра в нормальной форме.
План, соответствующий, например, второй из указанный стратегий, второй игрок формулирует
следующим образом: я выберу IBM, если первый игрок выберет IBM и Mac, если первый игрок выберет
Mac.
Можно заметить, что нормальная форма динамического варианта игры более сложна, чем нор-
мальная форма статического варианта игры (см. Таблицу 16.1). В игре с тремя типами компьютеров
у 2-го игрока было бы уже 9 стратегий. Еще более сложна нормальная форма динамической игры, в
которой у игроков — бесконечное множество стратегий.
Для нормальной формы игры естественным решением, как мы уже видели, является равновесие
Нэша. Сравним равновесия Нэша с результатом применения метода обратной индукции. По видимому,
содержательно наиболее интересен случай, когда a < c и b < c .
Сначала разберем, что предсказывает обратная индукция. При сделанных предположениях о па-
раметрах игры можно предсказать, что 2-й игрок в вершине ? выберет IBM, поскольку c < b (он
совместимость ценит больше, чем использование компьютера любимого типа), а в вершине ˜ выбе-
рет Макинтош, поскольку b + c > 0. В редуцированной игре 1-й игрок должен сделать выбор между
выигрышами a + c (IBM) и c (Макинтош). Он выберет IBM. Таким образом, обратная индукция
предсказывает, что игроки выберут следующие стратегии:

? IBM,
1-й —
(? IBM, ˜ Mac).
2-й —

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

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

ОГЛАВЛЕНИЕ

Следующая >>