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

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

ОГЛАВЛЕНИЕ

Следующая >>

зок [0, 1]. При этом предполагаем, что разные типы одного и того же игрока имеют одина-
ковые предпочтения (те, что заданны Таблицей 12). Несложно проверить, что следующий
набор стратегий является байесовским равновесием расширенной игры: налогоплатель-
щик платит налог, если его тип удовлетворяет условию ?1 < 1/2, в противном случае он
налог не платит; аналогично налоговый инспектор проверяет, если его тип удовлетворяет
условию ?2 < 1/2. Это байесовское равновесие полностью воспроизводит равновесие в
смешанных стратегиях исходной игры: в половине случаев налогоплательщик платит на-
лог, и в половине случаев налоговый инспектор проверяет налогоплательщика. Рандоми-
зирует при этом не игрок, а природа, когда выбирает тот или иной тип игрока.
Конечно, в расширенной игре существует не одно, а бесконечно много байесовских рав-
новесий. Для получения другого байесовского равновесия требуется только произволь-
ным образом разбить множество типов каждого игрока на две части, вероятности попада-
ния в которые равны вероятностям использования чистых стратегий в исходном равнове-
сии в смешанных стратегиях.
Можно также имитировать равновесие в смешанных стратегиях с помощью слегка изме-
ненной игры, в которой к выигрышам добавляются малые случайные возмущения, зави-
сящие от типов игроков. Такой подход позволяет избавится от множественности байесов-
ских равновесий, о котором только что говорилось. При этом равновесие в смешанных
стратегиях будет пределом байесовских равновесий в «возмущенных» играх. (См. Задачу
41).

Задачи


39. Как представить Игру 2 (стр. 629) в виде байесовской игры?


40. Богатство отца составляет $3 с вероятностью 1/5, $6 с вероятностью 1/5?4/5, $12 с
вероятностью 1/5?(4/5)2, и т.д. (то есть, $3?2k с вероятностью 1/5?(4/5)k для каждого k >
0). В один конверт он кладет две трети своего богатства, в другой — одну треть. Он дает
по конверту каждому из двух сыновей (каждый из сыновей с одинаковой вероятностью
получит любой конверт). Каждый из сыновей видит, сколько денег в его собственном
конверте, но не знает, сколько денег в конверте брата. Каждый из сыновей имеет функцию
полезности от богатства ln(w). [ Подсказка: 39 > 214].

678
679
(A) Рассмотрим следующую игру. Каждый из братьев решает, разделить ли деньги, нахо-
дящиеся в конвертах. Таким образом каждый из братьев говорит «Да» или «Нет» (одно-
временно). Если оба говорят «Да», они делят деньги поровну. Если хотя бы один из брать-
ев говорит «Нет», то они остаются с деньгами, находящимися в их собственных конвер-
тах.
(i) Каждый брат знает только количество денег в его собственном конверте. Таким обра-
зом тип каждого брата — это элемент множества {1; 2; 4; 8; ...}. Каково распределение
вероятностей по типам?
(ii) Опишите эту ситуацию формально как игру с неполной информацией.
(iii) Опишите равновесие (Байеса-Нэша) в чистых стратегиях, в котором братья делят
деньги. Проверьте, что это действительно равновесие. Существует ли в этой игре другое
равновесие?
(B) Предположите теперь, что отец объявил, что ни в одном из конвертов не может нахо-
диться больше чем $3?2K (для некоторого K > 1). Охарактеризуйте равновесия Байеса-
Нэша в чистых стратегиях получившейся в результате игры.


41. В Таблице 24 показана «возмущенная» игра «Инспекция». В ней ?1 и ?2 — случайные

Oaaeeoa 24
Инспектор
Не
проверять
проверять
0
1+?2
нарушать –1 1+?1
Проверяемый
не –1 0
нарушать 0 0

возмущения, соответствующие типу 1-го и 2-го игрока соответственно, причем ?1 и ?2 рав-
номерно распределены на отрезке [0, ?] (? > 0) и независимы между собой.259 Найдите бай-
есовское равновесие (в чистых стратегиях) в этой игре. Докажите, что при ? > 0 найден-
ное байесовское равновесие стремится к равновесию в смешанных стратегиях исходной
игры (Игра 6 на стр. 641).
[Указание: Подскажем, равновесие какого вида здесь искать. Каждый игрок выбирает не-
?
который пороговый уровень, -i. Равновесные стратегии выглядят следующим образом:
если ?1 < -1, то первый игрок выбирает стратегию «нарушать», а если ?1 > -1 — то страте-
? ?
гию «не нарушать» (вероятность того, что ?1 = -1 равна нулю, поэтому этот случай можно
?
не рассматривать); аналогичным образом второй игрок выбирает стратегию «проверять»,
если ?2< -2 и стратегию «не проверять», если ?2 > -2.]
? ?

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

259
Равномерное распределение выбрано нами только из соображений удобства. В данном случае подошло
бы любое разумное непрерывное распределение.

679
680
В качестве примера динамической байесовской игры рассмотрим модификацию Игры 7
«Террорист» (стр. 653).


Игра 13. «Sa!!%!,“2»
Ситуация в данной игре такая же, как в Игре 7, однако террорист может быть двух типов:
«нормальный» и «сумасшедший». Нормальный террорист так же, как и в Игре 7, получает
выигрыш –100 в случае, если взорвет бомбу в Нью-Йорке. Сумасшедший же террорист
получает в этом случае выигрыш 0. Вероятность того, что террорист окажется сумасшед-
шим, равна ?. Пилот не знает, с террористом какого типа он имеет дело, но сам террорист
знает свой тип. (


Игра схематически показана на Рисунке 172. В игру был добавлен дополнительный фик-
тивный игрок, природа.260 Это сделано для того, чтобы показать на схеме случайный вы-
бор типа террориста. Природа не имеет никакой целевой функции, поэтому на схеме пока-
заны только выигрыши двух исходных игроков.
Природа

нормальный
сумасшедший

F
[?] [1–?]
Пилот

Нью-Йорк Куба Нью-Йорк
Куба
? –1 ? Террорист
Террорист ?1?
? –1 ? взорвать
?1? не взрывать
не взрывать
взорвать
? –100 ? ?1?
?1?
A ? –100 ?
? –100 ? ? –1 ?
? –1 ?
?0?

?enoiie 172. Ea?a «Oa??i?eno»
Первый ход делает природа. С вероятностью ? природа создает сумасшедшего террориста
и с вероятностью 1 – ? — нормального. Пунктирной рамкой показано информационное
множество пилота, соответствующее условию, что он не знает типа террориста.
Решение этой игры можно найти, применяя обратную индукцию. Сначала нужно рассмот-
реть поведение террористов обоих типов. Нормальный террорист, как мы видели раньше в
Игре 7, не будет взрывать бомбу в Нью-Йорке. Сумасшедший же террорист, наоборот,
предпочтет взорвать бомбу (так как 0 больше –1). В результате этих рассуждений (кото-
рые, как предполагается, должен проводить рациональный пилот) получим свернутую
игру, которая показана на Рисунке 173.




260
Отметим, что можно рассматривать байесовские игры (игры с неполной информацией) как игры с несо-
вершенной информацией, в которых одним из игроков является природа.

680
681
Природа

нормальный
сумасшедший

F
[?] [1–?]
Пилот

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

? –1 ? ? –100 ? ?1?
? –1 ?
?1? ?0? ? –1 ?
?1?

?enoiie 173.
Если пилот выберет Кубу, то в любом случае поучит –1. Если же пилот выберет Нью-
Йорк, то с вероятностью ? он получит –100, а с вероятностью 1 – ? получит 1, то есть его
ожидаемый выигрыш составит
??(–100) + (1 – ?)?1 = 1 – 101?.
Пилот должен сравнить выигрыш –1 с выигрышем 1 – 101? и выбрать максимальный. Та-
ким образом, вид решения будет зависеть от параметра ?. Если вероятность встретить су-
масшедшего террориста мала, т.е. ? < 2/101, то пилот полетит в Нью-Йорк, а если эта ве-
роятность велика, т.е. ? > 2/101, то он предпочтет полететь на Кубу. При ? = 2/101 пилоту
все равно, куда лететь.


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

681
682
2) Выбранная стратегия последовательно оптимальна при данных ожиданиях, то есть вы-
бор в каждом информационном множестве должен быть таким, чтобы максимизировать
ожидаемый выигрыш в предположении, что после этого информационного множества
e
игра будет идти в соответствии с набором стратегий (si, s–i).
e
3) Ожидаемые стратегии совпадают с фактически выбранными стратегиями: s–i = s–i.
Первое условие требует специального пояснения. Поясним сначала это условие для слу-
чая чистых стратегий. Рассмотрим некоторого игрока i и информационное множество, в
котором этому игроку принадлежит ход. Какими должны быть его ожидания в данном
информационном множестве? Предположим, что траектория, соответствующая набору
e
стратегий (si, s–i) и выходящая из начальной вершины, проходит через одну из вершин
данного информационного множества. В таком случае, если игрок рационален, то он дол-
жен ожидать, что будет находиться именно в этой вершине, коль скоро игра достигнет
данного информационного множества и ему придется делать в нем выбор.
1-й
В качестве примера рассмотрим статическую игру, изображенную на Рис.
174. Если второй игрок ожидает, что первый игрок выберет правую стра- 2-й
тегию, то он должен ожидать также, что будет находиться в правой вер-
шине своего информационного множества. Следует отметить, что если
второй игрок будет исходить из сформированных таким способом ожида- ?enoiie 174
ний, то, выбирая свои действия оптимальным образом, он повторит ту
функцию отклика, которую мы рассматривали при анализе равновесия
Нэша.
В случае смешанных стратегий общего вида рассуждения должны быть похожими. Сле-
дует вычислить, с какой вероятностью будет достигаться каждая из вершин некоторого
информационного множества в процессе игры, если игра будет происходить в соответст-
e
вии с набором стратегий (si, s–i). Тогда ожидаемая вероятность того, что игрок может на-
ходиться в некоторой вершине рассматриваемого информационного множества, равна
вероятности достижения этой вершины деленной на сумму вероятностей достижения
вершин рассматриваемого информационного множества. Указанная сумма вероятностей
есть просто вероятность достижения рассматриваемого информационного множества, ес-
e
ли игра будет происходить в соответствии с набором стратегий (si, s–i). Понятно, что эта
вероятность не должна быть равна нулю, чтобы можно было произвести деление. (Если
же вероятность равна нулю, т.е. данное информационное множество не может быть дос-
тигнуто, то указанное правило не применимо.) Описанный способ вычисления вероятно-
стей соответствует классическому правилу Байеса для условных вероятностей.
Напомним, что правило Байеса применимо к событиям A и Bj (j = 1, ..., m), таким что:
(1) Bj (j = 1, ..., m) — несовместные события, т.е.
Bj ] Bk = ?, ?j, k = 1, ..., m;
(2) тот факт, что произошло одно из событий Bj гарантирует, что произошло так-
же событие A, т.е.
m
A ? [ Bj .
j=1

При этом верна следующая формула Байеса:
P{Bj }P{A | Bj} P{Bj }P{A | Bj}
.

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

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

ОГЛАВЛЕНИЕ

Следующая >>