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

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

ОГЛАВЛЕНИЕ

Следующая >>

Игрок 1


Игрок 2




?enoiie 162
33. Рассмотрите динамическую игру, сконструированную на основе статической антаго-
нистической игры двух лиц (см. определение в Задаче 20 предыдущего параграфа, стр.
651), так что игроки делают ходы по очереди (например, сначала первый, потом второй), и
* *
тот, кто ходит вторым, знает, какое решение принял тот, кто ходит первым. Пусть (x1, x2)
— седловая точка функции полезности первого игрока, u1(x1, x2). Докажите, что набор
* *
стратегий (x1, x2) является совершенным в подыграх равновесием в этой игре вне зависи-
мости от порядка ходов.


34. Пусть, как и в предыдущей задаче, на основе статической антагонистической игры
двух лиц строится динамическая игра. Докажите, что делать ход вторым в общем случае
(при отсутствии седловой точки) более выгодно. Предполагается, что соответствующие
совершенные в подыграх равновесия существуют.

Динамические игры с несовершенной информацией
Особенность рассматриваемых в предыдущем разделе игр — каждый игрок, перед тем,
как сделать ход, полностью знает предысторию игры — выборы, сделанные ранее им и
другими игроками. Другими словами игрок знает, в какой вершине дерева он оказался. В
этом разделе мы рассмотрим класс игр, называемых играми с несовершенной информаци-
254
в которых игроки могут не знать полностью предысторию игры. Т.е., осуществляя
ей,
очередной ход, они знают, что находятся в одной из вершин некоторого подмножества
множества всех вершин дерева игры (так называемого информационного множества).
Примером игры с несовершенной информацией служит любая статическая игра. Ее можно
искусственно «динамизировать», задав произвольным образом порядок ходов и определив
подходящим образом информационные множества, как это сделано ниже для Игры 1 (стр.
627) «Выбор компьютера» (см. Рис. 163).




254
Мы используем кальку с английского термина games of imperfect information. В русскоязычной литерату-
ре использовался термин «игры с неполной информацией», но его предпочтительнее использовать для обо-
значения игр, которые по-английски называются games of incomplete information.

664
665
Игрок 1
B
IBM
Mac

Игрок 2 C
D
IBM
Mac Mac
IBM

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

?enoiie 163. I?aanoaaeaiea noaoe?aneie ea?u «Auai? eiiiu?oa?a» a aeaa aa?aaa
Предположим, что первый игрок ходит первым, второй — вторым. Есть две вершины, в
которых ход принадлежит 2-му игроку, однако сам он не может различить, выбирая свои
действия, в какой вершине он находится; другими словами, эти две вершины находятся в
одном и том же информационном множестве.
Как видим, развернутая форма игр с несовершенной информацией несколько более слож-
на, чем развернутая форма игр с совершенной информацией. Дополнительно к тем состав-
ляющим, которые были указаны в прежнем определении, требуется также перечислить
информационные множества, которые задают разбиение множества вершин (кроме ко-
нечных). Информационные множества должны быть заданы так, чтобы каждая вершина,
кроме конечных, принадлежала одному и только одному из них. Кроме того, по смыслу
определения информационного множества, во всех его вершинах ход должен принадле-
жать одному и тому же игроку.
Дополнительно следует потребовать, чтобы множество возможных действий во всех вер-
шинах одного и того же информационного множества были одинаковыми. В противном
случае игрок мог бы по тому, какие альтернативы ему доступны, определить, в какой
именно вершине он находится. Дерево игры, представленное на Рис. 163 удовлетворяет
этому требованию — и в вершине D, и в вершине C 2-й игрок выбирает между IBM и
Mac.
Используя понятие информационного множества, мы можем дать формальное определе-
ние игр с совершенной информацией: в играх с совершенной информацией в каждом ин-
формационном множестве находится только одна вершина.255
В приложениях теории игр чаще всего рассматривают так называемые игры с идеальной
памятью, то есть такие игры, в которых игроки не забывают ту информацию, которой они
обладали на предыдущих ходах. Мы не будем давать формального определения таких игр.
Приведем только примеры игр, в которых предположение об идеальной памяти не выпол-
няется (см. Рис. 164).




255
Это определение, по-видимому, не годится в контексте игр с неполной информацией (но это зависит от
способа интерпретации).

665
666
Игрок 1 Игрок 1

Игрок 2
Игрок 2

Игрок 2
Игрок 1




?enoiie 164. I?eia?u ea?, ia yaey?ueony ea?aie n eaaaeuiie iaiyou?


Таким образом, существуют два представления любой игры — представление в нормаль-
ной и развернутой форме. Выше мы показали, как динамическую игру с совершенной ин-
формацией представить в нормальной форме, а статическую игру — в развернутой форме.
Таким образом, любую динамическую игру с совершенной информацией можно предста-
вить в нормальной форме, а затем, — на основе этой нормальной формы — построить
развернутую форму соответствующей игры. Приведем пример такого построения.
Если мы представим игру на Рис. 165 в нормальной форме, то получим Таблицу 19 (для
упрощения выигрыши не указаны).
Oaaeeoa 19
Игрок 2
L2 R2

L1
Игрок 1
Игрок 1
R1 L1 R1
Этой нормальной форме соответствует дерево игры, представленное Игрок 2
на Рис. 166. Как видим, при таком «двойном переводе» частично по- L2 R2
теряна информация о структуре игры и мы получили другую игру в
развернутой форме. Очевидно, что принципиально разным играм
может соответствовать одна и та же нормальная форма. ?enoiie 165
Игрок 1
L1 R1
Игрок 2
L2 R2 L2 R2


?enoiie 166
Таким образом, нормальная форма игры не является в общем случае адекватной для опи-
сания динамических игр. С помощью нее можно представлять корректно только статиче-
ские игры. Если операцию «двойного перевода» из развернутой формы в нормальную и
обратно осуществить со статической игрой, представленной на Рис. 163, то дерево игры
не поменяется (с точностью до выбора порядка ходов, что в данном случае несуществен-
но).
Использование нормальной формы для представления статических игр вполне допустимо
и даже предпочтительно, так как она более компактна.


666
667
Уточним понятие стратегии для рассматриваемого класса игр.
Стратегия игрока в играх с несовершенной информацией должна, указывать, какие этот
игрок выберет действия, если окажется в данном информационном множестве. Поскольку
в играх с совершенной информацией в каждом из информационных множеств находится
только одна вершина, то такая модификация определения стратегии полностью согласует-
ся с данным ранее определением. Пользуясь понятием стратегии, мы можем распростра-
нить концепцию равновесия Нэша на динамические игры с несовершенной информацией.
Определение ничем не будет отличаться от ранее данного.
Определение совершенного в подыграх равновесия в играх с несовершенной информаци-
ей совпадает с данным выше определением для игр с совершенной информацией. Однако,
в играх с несовершенной информацией следует дать несколько другое определение по-
дыгры. Отличие состоит в том, что подыгра может начинаться не из любой вершины.
Следует потребовать, чтобы если некоторая вершина содержалась в подыгре, то в этой же
подыгре содержалось и все информационное множество, содержащее данную вершину.
Например в игре, дерево которой показано на Рис. 167, в вершины D, C и E не являются
начальными вершинами подыгр. Таким образом, в этой игре нет собственных подыгр.
B Игрок 1
D Игрок 2
?2? Игрок 3
C E
?2?
?2? ?1? ?4? ?2?
?7?
?3? ?2? ?0?
?1?
?0? ?3? ?1?
?2?
?enoiie 167.
Заметим, что не к любой игре с несовершенной информацией можно применить алгоритм
обратной индукции. Игра на Рис. 167 представляет собой как раз такую игру, в которой
невозможно найти решение с помощью обратной индукции. Игрок 3 в этой игре не знает,
в какой именно из двух вершин информационного множества он находится, поэтому он не
может без каких-либо дополнительных предположений выбрать между двумя имеющими-
ся альтернативами. Мы рассмотрим концепцию решения подобных игр позже, в парагра-
фе, посвященном совершенному байесовскому равновесию.
Здесь мы рассмотрим лишь класс игр, для анализа которых можно использовать (при ес-
тественной его модификации) алгоритм обратной индукции. Эти игры можно назвать иг-
рами с почти совершенной информацией. Другое название — многоэтапные игры с наблю-
даемыми действиями. Такие игры можно разбить на несколько этапов: t = 1, ..., T, каж-
дый из которых представляет собой одну или несколько статических игр. В рамках t-го
этапа игроки одновременно выбирают действия, причем каждый игрок знает всю предыс-
торию, т.е. какие действия выбрали другие игроки на предыдущих этапах (1, ..., t – 1); бо-
лее того, предыстория игры является общеизвестной. Пример такой игры — повторяю-
щаяся конечное число раз статическая игра. Заметим, что множества стратегий некоторых
игроков в этих статических играх могут быть пустыми (как, например, на первом этапе
игры, представленной на Рис. 169).
Сначала при использовании обратной индукции последнем, T-м, этапе находятся равнове-
сия по Нэшу всех игр этого этапа. Затем, каждая их этих игр заменяется конечной верши-
ной. Ей сопоставляются выигрыши, соответствующие равновесию по Нэшу (одному из
равновесий, если их несколько). Тем самым мы получаем игру с T–1 этапом, и т.д.
Игры с почти полной информацией удобны для анализа, поскольку каждая статическая
игра (соответствующего этапа) начинает одну из подыгр. Этапы можно рассматривать
667
668
последовательно, а это фактически и означает, что в них не возникает трудностей с ис-
пользованием обратной индукции.


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


Игра 9. «m=Kaa, …= K=…*,»
Два инвестора вложили в банк одинаковые денежные суммы (например, по 2 рубля). Банк
обещает им вернуть через 3 месяца по 3 рубля. Они могут взять деньги из банка через 1, 2
или 3 месяца, однако банк сможет вернуть только половину общей суммы сделанных ин-
вестиций, если вкладчики потребуют деньги раньше срока (через 1 или 2 месяца). При
этом если оба потребуют деньги, то получат по 1 рублю, а если деньги потребует только
один, то он получит 2 рубля, а другой вкладчик не сможет получить ничего. (
Oaaeeoa 20. Ea?a «Iaaaae ia aaiee» ia aoi?ii yoaia
Игрок 2
L4 R4
3 2
L3 3 0
Игрок 1
0 1
R3 2 1


Дерево игры показано на Рис. 168. R обозначает «забрать деньги», L — «не забирать».
Игра происходит в 2 этапа, на каждом из которых вкладчики одновременно решают, заби-
рать ли деньги. Первый этап происходит по прошествии 1 месяца после вложения денег,
второй — по прошествии 2 месяцев. 1-й
В Таблице 20 изображена статическая игра, соответ- L1 R1
ствующая второму этапу. В игре имеется два равнове- 2-й
I этап
сия по Нэшу. Применяя обратную индукцию, мы ис- R2 L2 R2
L2
пользуем выигрыши, соответствующие этим равно-
весиям, чтобы сформулировать статическую игру, ?0? ?2? ? 1 ?
?2? ?0? ? 1 ?
1-й
соответствующую первому этапу.
L3 R3
II этап
2-й
Получающаяся редуцированная игра представлена в
R4 L4
L4 R4
Таблице 21. В ней выигрыши второго этапа обозначе-
ны через v1 и v2 соответственно.
?3? ?0? ?2? ? 1 ?
?3? ?2? ?0? ? 1 ?
Oaaeeoa 21. ?aaooe?iaaiiay ea?a «Iaaaae ia
aaiee» ia ia?aii yoaia
Игрок 2 ?enoiie 168. Aa?aai ea?u
«Iaaaae ia aaiee»
L2 R2
v2 2

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

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

ОГЛАВЛЕНИЕ

Следующая >>