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

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

ОГЛАВЛЕНИЕ

Следующая >>

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

?enoiie 157. ?aoaiea ea?u «Oa??i?eno»
В данном случае мы рассмотрели игру с совершенной информацией, то есть такую игру, в
которой каждый игрок, делая выбор, знает всю предыдущую историю игры, или, если го-
ворить с точки зрения представления игры в виде дерева, каждый игрок знает, в какой из
возможных ситуаций (вершин дерева) он находится.
Представление игры в виде дерева соответствует развернутой форме игры.248 В дальней-
шем мы увидим, как можно представить динамическую игру в нормальной форме. А сей-
час перечислим, что должно включать описание динамической игры (с совершенной ин-
формацией) в развернутой форме:
@ множество вершин дерева игры, в том числе одну начальную вершину;
@ для каждой вершины, кроме начальной, — единственную вершину, которая непосред-
ственно ей предшествует; при этом не должно быть циклов, то есть цепь предшествую-


247
Предсказанный исход игры кажется довольно странным. Ведь вполне естественно, что пилот будет опа-
саться, что террорист все-таки взорвет самолет. Данный исход, однако, полностью соответствует описанию
игры, а также сделанным предположениям. Можно сделать игру более реалистичной, если добавить воз-
можность того, что может встретиться террорист, которому в соответствии с его целевой функции будет
выгодно взорвать бомбу. Такую игру мы рассмотрим в дальнейшем, в параграфе, посвященном так назы-
ваемым байесовским динамическим играм.
248
Как и нормальная форма игры, развернутая форма была впервые в явном виде описана Дж. фон Нейма-
ном (См. ссылки в сноске 234). См также Kuhn, H. W. (1953), "Extensive Games and the Problem of Informa-
tion," pp. 193-216 in Contributions to the Theory of Games, Volume II (Annals of Mathematics Studies, 28) (H.W.
Kuhn and A. W. Tucker, eds.), Princeton: Princeton University Press.

654
655
щих вершин, построенная из любой вершины, должна заканчиваться в начальной вершине
(что предполагает, в том числе, отсутствие циклов);
@ множество игроков;
@ для каждой вершины, кроме конечных, — единственного игрока, которому принадле-
жит ход в данной вершине;
@ для каждой конечной вершины, то есть такой, которая не предшествует ни одной дру-
гой вершине, — вектор выигрышей всех игроков.
(Если в игре есть случайные ходы природы, то следует также задать распределение веро-
ятностей на множестве всех возможных ходов природы.)
Первые два пункта здесь соответствуют описанию дерева игры.
Действие в этой конструкции однозначно задается парой непосредственно следующих
одна за другой вершин. Для каждой вершины можно определить множество действий,
которые можно осуществить, находясь в данной вершине. Множество возможных дейст-
вий связано однозначным соответствием с множеством вершин, которые непосредственно
следуют за данной вершиной (т.е. которым непосредственно предшествует данная верши-
на), то есть каждое выбранное действие приводит в одну и только в одну вершину.
Каждой вершине в игре с совершенной информацией соответствует единственная предыс-
тория — то есть последовательность действий, которая приводит из на- Рэкетиры
чальной вершины в данную вершину.
?
Фирма
y
В случае, когда в динамической игре участвуют два игрока, и игра про-
?py
исходит в 2 этапа, то обратную индукцию удобно провести на основе ? ?
? (1 – ?) p y – y2 ?
функции отклика 2-го игрока на действия 1-го. Следующая игра иллюст-
рирует использование этого приема.
?enoiie 158.
Ea?a «?yeao»

Игра 8. «p.*a2»249
Рэкетиры выбирают, какую долю ? (? ? [0,1]) выручки отбирать у фирмы. Они при этом
максимизируют ? p y, где p — цена, y — выпуск фирмы. Фирма имеет квадратичную
функцию издержек, так что ее прибыль (выигрыш) равна
(1 – ?) p y – y2.
Фирма максимизирует прибыль при ограничении y > 0. Рэкетиры делают ход первыми.
Зная, какую долю выручки они хотят отбирать, фирма выбирает уровень выпуска. (


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

249
Можно интерпретировать игру несколько по другому: вместо рэкетиров рассматривать государство, ус-
танавливающее ставку налога.

655
656
Рэкетиры, зная функцию выигрыша фирмы, могут определить, как скажется на ее выпуске
выбор ими экспроприируемой доли выручки этой фирмы. Для того, чтобы предсказать
объем выпуска, им необходимо решить задачу фирмы: максимизировать прибыли по y
при заданном ?. Условия первого порядка такой задачи имеют вид:
(1 – ?) p – 2y = 0.
Если ? < 1, то y > 0. Поскольку функция прибыли вогнута, то условие первого порядка
является достаточным, т.е. определяемый на его основе объем выпуска фирмы является
оптимальным. При ? = 1 получаем решение y = 0. Таким образом, рэкетиры могут вывести
уравнение оптимального выпуска фирмы как функции доли ?:
(1 – ?) p
2.
y(?) =

Зная эту функцию отклика, рэкетиры максимизируют свою целевую функцию,250 т.е. ре-
шают следующую задачу

? p y(?) > max .
??[0,1]

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

?
?
б)
a) 1
1


1
2

y
y
p p p
2 4 2

?enoiie 159. (a) Iieo?aiea ooieoee ioeeeea oe?iu. (a) Auai? ?yeaoe?aie
iioeiaeuiie ioae?aaiie aiee.
Максимум достигается при ? = 1/2, то есть рэкетиры будут отбирать у фирмы половину
выручки. При этом выпуск фирмы составит p/4. Графически поиск решения представлен
на Рис. 159.


Мы рассмотрели здесь примеры игр, в которых каждый раз при использовании обратной
индукции оптимальный выбор единственен. Если это не так, процесс поиска решения раз-
ветвляется — решение будет зависеть от того, какую именно альтернативу из тех, которые
дают игроку одинаковый выигрыш, выберет этот игрок. На Рисунке 160 показано исполь-
зование обратной индукции в такой игре. В этой игре обратная индукция дает два реше-
ния: (L1, R2) и (L2, R1).




250
В моделях налогообложения аналог функции ?p y(?) известен как кривая Лаффера.

656
657
1-й
L1 R1

?1?
2-й
?0?
L2 R2
L1 L1
R1 R1
?0? ?2?
?1?
?0 ? ?1? ?1?
?1? ?2?
?1? ?0? ?0?
?1?
?enoiie 160. ?acaaoaeaiea ?aoaiey i?e eniieuciaaiee ia?aoiie eiaoeoee
Если выигрыши всех игроков во всех конечных вершинах различны, то неоднозначности
при использовании обратной индукции не возникает, поэтому решение должно быть
единственным.


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


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


Мы рассмотрели, как находить решение динамической игры с совершенной информацией
с помощью обратной индукции. Другой подход состоит в том, чтобы применить к дина-
мической игре концепцию равновесия Нэша, так же, как мы применяли ее к статическим
играм.
Для того, чтобы это сделать, следует записать динамическую игру в нормальной форме.
Как мы помним, описание игры в нормальной форме состоит из задания (1) множества
игроков, (2) множества стратегий каждого игрока и (3) функции выигрыша каждого игро-
ка на множестве исходов.
Множество игроков, конечно, должно быть одним и тем же в нормальной форме и в раз-
вернутой форме игры. Прежде всего уточним понятие стратегии для игр такого типа.
В игре в развернутой форме (чистая) стратегия — это полный план действий игрока: что
он будет делать в каждой из вершин, в которой ход принадлежит ему. Это должен быть
действительно полный план, то есть в нем должно быть определено, что игрок выберет в
любой своей вершине, даже если из каких-либо соображений ясно, что процесс игры вряд
ли может привести в эту вершину. То есть это должен быть настолько полный план, что
доверенное лицо игрока может использовать его в качестве инструкции, будучи уверен-
ным, что его поведение будет совпадать с поведением самого игрока.
Процесс игры для динамической игры в нормальной форме можно условно представить
себе следующим образом. Каждый игрок до начала игры сообщает выбранную им страте-
гию организатору игры. Организатор, руководствуясь этими стратегиями, осуществляет за
игроков их ходы. Когда последовательность ходов приведет организатора в конечную
657
658
вершину, он раздает всем игрокам выигрыши, соответствующие этой конечной вершине.
При такой интерпретации мы, по сути дела, имеем статическую игру в которой выигры-
ши определяются с помощью описанного только что алгоритма.
Проиллюстрируем, как на основе развернутой формы динамической игры получить ее
нормальную форму, на примере динамического варианта Игры 1 «Выбор компьютера»
(стр. 627). Предположим, что 1-й игрок выбирает себе компьютер первым. Дерево такой
игры представлено на Рисунке 161.
B Игрок 1
IBM
Mac
? Игрок 2
D C
IBM
Mac Mac
IBM

?a? ?c?
? a +c ? ?0?
?b? ? b +c ?
?c? ?0?

?enoiie 161. Aeiaie?aneee aa?eaio ea?u «Auai? eiiiu?oa?a»
Вершины на дереве пронумерованы для удобства обозначения альтернатив в разных вер-
шинах. Игрок 1 имеет в этой игре две стратегии, совпадающие с альтернативами в верши-
не B. Игрок 2 имеет 4 стратегии. Каждая его стратегия определяет действия в двух вер-
шинах: D и C. Таким образом, 2-го игрок имеет следующие стратегии: (DIBM, CIBM),
(DIBM, CMac), (DMac, CIBM), (DMac, CMac). В Таблице 16 представлена та же игра в
нормальной форме.
Oaaeeoa 16
Игрок 2

? DIBM DIBM DMac DMac
CIBM CMac CIBM CMac
c c b b
BIBM a +c a +c a a
Игрок 1
0 b+c 0 b+c
BMac 0 c 0 c
План, соответствующий, например, второй из указанный стратегий, второй игрок форму-
лирует следующим образом: я выберу IBM, если первый игрок выберет IBM и Mac, если
первый игрок выберет Mac.
Можно заметить, что нормальная форма динамического варианта игры более сложна, чем
нормальная форма статического варианта игры (см. Таблицу 5). В игре с тремя типами
компьютеров у 2-го игрока было бы уже 9 стратегий. Еще более сложна нормальная фор-
ма динамической игры, в которой у игроков — бесконечное множество стратегий.
Для нормальной формы игры естественным решением, как мы уже видели, является рав-
новесие Нэша. Сравним равновесия Нэша с результатом применения метода обратной
индукции. По видимому, содержательно наиболее интересен случай, когда a < c и b < c.
Сначала разберем, что предсказывает обратная индукция. При сделанных предположени-
ях о параметрах игры можно предсказать, что 2-й игрок в вершине D выберет IBM, по-
скольку c < b (он совместимость ценит больше, чем использование компьютера любимого
типа), а в вершине C выберет Макинтош, поскольку b + c > 0. В редуцированной игре 1-й
игрок должен сделать выбор между выигрышами a + c (IBM) и c (Макинтош). Он выберет
IBM. Таким образом, обратная индукция предсказывает, что игроки выберут следующие
стратегии:
BIBM,
1-й —
658
659

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

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

ОГЛАВЛЕНИЕ

Следующая >>