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

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

ОГЛАВЛЕНИЕ

Следующая >>

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

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


были указаны в прежнем определении, требуется также перечислить информационные множества,
которые задают разбиение множества вершин (кроме конечных). Информационные множества должны
быть заданы так, чтобы каждая вершина, кроме конечных, принадлежала одному и только одному
из них. Кроме того, по смыслу определения информационного множества, во всех его вершинах ход
должен принадлежать одному и тому же игроку.
Дополнительно следует потребовать, чтобы множество возможных действий во всех вершинах од-
ного и того же информационного множества были одинаковыми. В противном случае игрок мог бы по
тому, какие альтернативы ему доступны, определить, в какой именно вершине он находится. Дерево
игры, представленное на Рис. 16.14 удовлетворяет этому требованию — и в вершине ?, и в вершине
˜ 2-й игрок выбирает между IBM и Mac.
Используя понятие информационного множества, мы можем дать формальное определение игр с
совершенной информацией: в играх с совершенной информацией в каждом информационном множе-
стве находится только одна вершина29 .
В приложениях теории игр чаще всего рассматривают так называемые игры с идеальной памятью,
то есть такие игры, в которых игроки не забывают ту информацию, которой они обладали на предыду-
щих ходах. Мы не будем давать формального определения таких игр. Приведем только примеры игр,
в которых предположение об идеальной памяти не выполняется (см. Рис. 16.15).

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


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


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




Рис. 16.15. Примеры игр, не являющихся играми с идеальной памятью

Таким образом, существуют два представления любой игры — представление в нормальной и раз-
вернутой форме. Выше мы показали, как динамическую игру с совершенной информацией представить
в нормальной форме, а статическую игру — в развернутой форме. Таким образом, любую динамиче-
скую игру с совершенной информацией можно представить в нормальной форме, а затем, — на основе
этой нормальной формы — построить развернутую форму соответствующей игры. Приведем пример
такого построения.
Если мы представим игру на Рис. 16.16 в нормальной форме, то получим Таблицу 16.14 (для упро-
щения выигрыши не указаны).
29
Это определение, по-видимому, не годится в контексте игр с неполной информацией (но это зависит от
способа интерпретации).
16.4. Динамические игры с несовершенной информацией 658

Игрок 1
L1 R1
Игрок 2
L2 R2



Рис. 16.16.

Таблица 16.14.

Игрок 2
L2 R2
L1
Игрок 1
R1


Этой нормальной форме соответствует дерево игры, представленное на Рис. 16.17. Как видим, при
таком «двойном переводе» частично потеряна информация о структуре игры и мы получили другую
игру в развернутой форме. Очевидно, что принципиально разным играм может соответствовать одна
и та же нормальная форма.

Игрок 1
R1
L1

Игрок 2

L2 R2 L2 R2



Рис. 16.17.

Таким образом, нормальная форма игры не является в общем случае адекватной для описания
динамических игр. С помощью нее можно представлять корректно только статические игры. Если
операцию «двойного перевода» из развернутой формы в нормальную и обратно осуществить со ста-
тической игрой, представленной на Рис. 16.14, то дерево игры не поменяется (с точностью до выбора
порядка ходов, что в данном случае несущественно).
Использование нормальной формы для представления статических игр вполне допустимо и даже
предпочтительно, так как она более компактна.
Уточним понятие стратегии для рассматриваемого класса игр.
Стратегия игрока в играх с несовершенной информацией должна, указывать, какие этот игрок вы-
берет действия, если окажется в данном информационном множестве. Поскольку в играх с совершенной
информацией в каждом из информационных множеств находится только одна вершина, то такая мо-
дификация определения стратегии полностью согласуется с данным ранее определением. Пользуясь
понятием стратегии, мы можем распространить концепцию равновесия Нэша на динамические игры с
несовершенной информацией. Определение ничем не будет отличаться от ранее данного.
Определение совершенного в подыграх равновесия в играх с несовершенной информацией совпа-
дает с данным выше определением для игр с совершенной информацией. Однако, в играх с несовер-
шенной информацией следует дать несколько другое определение подыгры. Отличие состоит в том,
что подыгра может начинаться не из любой вершины. Следует потребовать, чтобы если некоторая вер-
шина содержалась в подыгре, то в этой же подыгре содержалось и все информационное множество,
содержащее данную вершину. Например в игре, дерево которой показано на Рис. 16.18, в вершины
?, ˜ и ? не являются начальными вершинами подыгр. Таким образом, в этой игре нет собственных
подыгр.
16.4. Динамические игры с несовершенной информацией 659

? Игрок 1

? Игрок 2
??
2 ˜ ?
Игрок 3
?2?
2
?? ??
??
1 2
4
??
7
?3? ?0?
?2?
?1?
0 1
3
2
Рис. 16.18.



Заметим, что не к любой игре с несовершенной информацией можно применить алгоритм обратной
индукции. Игра на Рис. 16.18 представляет собой как раз такую игру, в которой невозможно найти
решение с помощью обратной индукции. Игрок 3 в этой игре не знает, в какой именно из двух вершин
информационного множества он находится, поэтому он не может без каких-либо дополнительных пред-
положений выбрать между двумя имеющимися альтернативами. Мы рассмотрим концепцию решения
подобных игр позже, в параграфе, посвященном совершенному байесовскому равновесию.
Здесь мы рассмотрим лишь класс игр, для анализа которых можно использовать (при естественной
его модификации) алгоритм обратной индукции. Эти игры можно назвать играми с почти совершенной
информацией. Другое название — многоэтапные игры с наблюдаемыми действиями. Такие игры можно
разбить на несколько этапов: t = 1, . . . , T , каждый из которых представляет собой одну или несколько
статических игр. В рамках t -го этапа игроки одновременно выбирают действия, причем каждый игрок
знает всю предысторию, т. е. какие действия выбрали другие игроки на предыдущих этапах (1, . . . , t ?
1 ); более того, предыстория игры является общеизвестной. Пример такой игры — повторяющаяся
конечное число раз статическая игра. Заметим, что множества стратегий некоторых игроков в этих
статических играх могут быть пустыми (как, например, на первом этапе игры, представленной на
Рис. 16.20).
Сначала при использовании обратной индукции последнем, T -м, этапе находятся равновесия по
Нэшу всех игр этого этапа. Затем, каждая их этих игр заменяется конечной вершиной. Ей сопостав-
ляются выигрыши, соответствующие равновесию по Нэшу (одному из равновесий, если их несколько).
Тем самым мы получаем игру с T ? 1 этапом, и т. д.
Игры с почти полной информацией удобны для анализа, поскольку каждая статическая игра (со-
ответствующего этапа) начинает одну из подыгр. Этапы можно рассматривать последовательно, а это
фактически и означает, что в них не возникает трудностей с использованием обратной индукции.
Рассмотрим пример игры с почти полной информацией и использования обратной индукции для
поиска решения в таких играх.
Игра 9. «Набеги на банки»
Два инвестора вложили в банк одинаковые денежные суммы (например, по 2 рубля). Банк обещает им
вернуть через 3 месяца по 3 рубля. Они могут взять деньги из банка через 1, 2 или 3 месяца, однако
банк сможет вернуть только половину общей суммы сделанных инвестиций, если вкладчики потребуют
деньги раньше срока (через 1 или 2 месяца). При этом если оба потребуют деньги, то получат по 1
рублю, а если деньги потребует только один, то он получит 2 рубля, а другой вкладчик не сможет
получить ничего.

Дерево игры показано на Рис. 16.19. R обозначает «забрать деньги», L — «не забирать». Игра
происходит в два этапа, на каждом из которых вкладчики одновременно решают, забирать ли деньги.
Первый этап происходит по прошествии одного месяца после вложения денег, второй — по прошествии
двух месяцев.
В Таблице 16.15 изображена статическая игра, соответствующая второму этапу. В игре имеется
два равновесия по Нэшу. Применяя обратную индукцию, мы используем выигрыши, соответствующие
этим равновесиям, чтобы сформулировать статическую игру, соответствующую первому этапу.
Получающаяся редуцированная игра представлена в Таблице 16.16. В ней выигрыши второго этапа
обозначены через v1 и v2 соответственно.
16.4. Динамические игры с несовершенной информацией 660




1-й
L1 R1
2-й
I этап
R 2L 2 R2
L2
1
0 2
1
2 0
1-й
L3 R3
II этап
2-й
R 4L 4
L4 R4

2
3 0 1
0
3 2 1



Рис. 16.19. Дерево игры «Набеги на банки»




Таблица 16.15. Игра «Набеги на банки» на втором этапе

Игрок 2
L4 R4
3 2
L3 3 0
0 1
Игрок 1
R3 2 1




Таблица 16.16. Редуцированная игра «Набеги на банки» на первом этапе

Игрок 2
L2 R2
v2 2
L1 v1 0
0 1
Игрок 1
R1 2 1
16.4. Динамические игры с несовершенной информацией 661

Множество равновесий Нэша в редуцированной игре первого этапа зависит от того, какое из двух
равновесий может реализоваться на втором этапе. Если игроки считают, что на втором этапе они оба
заберут деньги, то им выгоднее забрать деньги на первом этапе, поскольку v1 , v2 = 1 < 2. Если же
игроки считают, что на втором этапе они оба оставят деньги в банке, то на первом этапе может реали-
зоваться одно из двух равновесий Нэша, поскольку v1 , v2 = 3 > 2: либо оба игрока забирают деньги,
либо оба оставляют. Таким образом, обратная индукция дает три решения. В двух из этих решений
происходит «набег на банк» на первом и втором этапе соответственно. Третье решение соответствует
случаю, когда оба вкладчика дожидаются получения максимального выигрыша (3, 3).
Использование обратной индукции в играх с почти совершенной информацией можно дополнитель-
но обосновать тем, что для них выполнен вариант Теоремы 158.
Теорема 159:
В игре с почти совершенной информацией (и конечным числом ходов) множество решений,
получаемых обратной индукцией, совпадает с множеством совершенных в подыграх равновесий.
В отличие от игр с совершенной информацией, в играх с почти совершенной информацией решения
в чистых стратегиях может не существовать (как, например в игре на Рис. 16.20). Выход из положения
состоит в том, чтобы ввести в поведение игроков элемент рандомизации, по аналогии со смешанными
стратегиями, которые мы рассмотрели в случае статических игр.

1-й
?1
1-й ?1

2-й


0 0
1 1
1 1

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

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

ОГЛАВЛЕНИЕ

Следующая >>