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

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

ОГЛАВЛЕНИЕ

Следующая >>

? · 3 + (1 ? ?) · 1,
IBM:
? · 0 + (1 ? ?) · 2.
Mac:

32
Концепция байесовского равновесия предложена американским экономистом венгерского происхождения
Джоном Харшаньи. (J. C. Harsanyi: Games with Incomplete Information Played by ‘Bayesian’ Players (parts I,
II and III), Management Science 14 (1967-1968): 159–182, 320–334, 486–502).
16.5. Статические игры с неполной информацией 666
Таблица 16.17.

Игрок 2
Любит IBM Любит Mac
IBM Mac IBM Mac
Игрок 1
3 0 2 1
IBM 3 1 3 1
[?]
1 2 0 3
Любит IBM
Mac 0 2 0 2
3 0 2 1
IBM 2 0 2 0
[1 ? ?]
1 2 0 3
Любит Mac
Mac 1 3 1 3
[1 ? ?]
[?]


Первый игрок такого типа выберет IBM PC, если выполнено условие

? · 3 + (1 ? ?) · 1 ? · 0 + (1 ? ?) · 2

или
? 1/4.
Рассмотрим теперь выбор 1-го игрока, если он предпочитает Макинтош. Поскольку в равновесии
он ожидает, что стратегией 2-го игрока является (IBM, Mac), то его ожидаемая полезность от выбора
компьютеров IBM PC и Макинтош равна соответственно

? · 2 + (1 ? ?) · 0,
IBM:
? · 1 + (1 ? ?) · 3.
Mac:

Первый игрок такого типа выберет Макинтош, если выполнено условие

? · 2 + (1 ? ?) · 0 ? · 1 + (1 ? ?) · 3

или
? 3/4.
Для второго игрока рассуждения аналогичные и приводят к тем же условиям, поскольку игроки
одинаковы. Таким образом, условие
1/4 ? 3/4
гарантирует, что набор стратегий ((IBM, Mac), (IBM, Mac)) будет байесовским равновесием.
Следующий пример не является полноценной игрой, поскольку выбор в нем делает только один
игрок, однако он включает все те компоненты байесовской игры, о которых здесь говорилось. Этот
пример показывает, как можно моделировать то, что один и тот же игрок может в зависимости от
некоторых случайных обстоятельств обладать разным объемом информации. Размышления над при-
мером позволяет «сломать» некоторые стереотипы, которые могут сложиться на основе формального
определения байесовской игры.
Игра 11. «Вахтер»
На входе в некоторое учреждение стоит вахтер. В учреждение могут войти посетители двух типов:
«свои» и «чужие» (будем их для краткости обозначать A и B ). Некоторые посетители кажутся вах-
теру своими, а некоторые — чужими. Таким образом, в данной игре есть 2 типа вахтера (обозначим
их соответственно a и b ). Вахтер может проверить у посетителя наличие пропуска. При этом, если
посетитель окажется своим, то выигрыш вахтера составит ?1 , а если чужим, то 1 .

Матрица игры приведена в Таблице 16.18. Вероятность того, что свой посетитель кажется вахте-
ру своим обозначена ?Aa и т. д. Заметим, что по смыслу игры, если вахтер достаточно опытен, то
вероятности появления типов не должны быть независимыми.
16.5. Статические игры с неполной информацией 667
Таблица 16.18.

Посетитель
A B
?1 1
проверять
[?Aa ] [?Ba ]
a
0 0
не проверять
?1 1
проверять
Вахтер
[?Ab ] [?Bb ]
b
0 0
не проверять


Условная вероятность того, что посетитель свой, если он кажется своим, равна ?Aa /(?Aa + ?Ba ),
а условная вероятность того, что посетитель чужой, если он кажется своим, равна ?Ba /(?Aa + ?Ba ).
Таким образом, ожидаемый выигрыш вахтера типа a, если он проверяет документы, равен
?Aa ?Ba
· (?1) + · 1,
?Aa + ?Ba ?Aa + ?Ba
а если не проверяет, то 0 . Аналогично, ожидаемый выигрыш вахтера типа b, если он проверяет доку-
менты, равен
?Ab ?Bb
· (?1) + · 1,
?Ab + ?Bb ?Ab + ?Bb
а если не проверяет, то 0 .
Если вахтер опытен, то вероятность ?Aa велика по сравнению с вероятностью ?Ba , а вероятность
?Ab велика по сравнению с вероятностью ?Bb , и естественно ожидать, что вахтер будет проверять
документы у тех, кто ему кажется чужими и не будет проверять документы у тех, кто ему кажется
своими.
Разберем также пример, в котором множества типов являются континуумами.
Игра 12. «Аукцион с заявками в запечатанных конвертах»
Некий предмет продается с аукциона. Участники аукциона (i = 1, . . . , n ), подают свои заявки, pi 0,
в запечатанных конвертах. Побеждает тот, кто предложит самую высокую цену. (Если самую высо-
кую цену предложат сразу несколько участников, то победитель определяется жребием.) Победивший
участник платит заявленную цену и получает предмет. Если i-й участник окажется победителем, то
его выигрыш составит vi ? pi , где vi — ценность для него данного предмета; выигрыш всех остальных
участников будет равен нулю. Известно, что оценки vi распределены равномерно на отрезке [0, 1] и
независимы.

В данном случае можно считать, что множество типов каждого игрока совпадает с отрезком [0, 1].
Удобно рассматривать стратегию i-го игрока как функцию, ставящую в соответствие типу v цену,
которую он предложит, pi (v):
pi (·) : [0, 1] > R+ .
Решить эту задачу непосредственно затруднительно. Можно предложить следующий путь решения:
предположить, что равновесные стратегии обладают некоторыми естественными свойствами, затем
вычислить, исходя из этого, равновесные стратегии и показать, что на самом деле найдено равновесие.
По смыслу задачи естественно искать симметричное равновесие, то есть такое равновесие, в котором
игроки выбирают одинаковые стратегии:

pi (v) ? p0 (v) ?i,

Кроме того, предположим, что одинаковая для всех стратегия p0 (·) является возрастающей диф-
ференцируемой функцией. Найдем, исходя из этих предположений, оптимальный отклик i-го игрока.
Если этот игрок выберет цену p , то вероятность того, что другой игрок, j , предложил более низкую
цену равна
Pr(p0 (vj ) < p) = Pr(vj < p?1 (p)) = p?1 (p) = ?(p),
0 0

где мы воспользовались тем, что оценка vj равномерно распределена на [0, 1], и обозначили через ?(p)
функцию, обратную к p0 (·). Поскольку по предположению vj распределены независимо, то события
16.5. Статические игры с неполной информацией 668

p0 (vj ) < p независимы, и вероятность того, что i-й игрок выиграет аукцион, заявив цену p , равна
?(p)n?1 . (Здесь мы пользуемся тем, что, поскольку p0 (·) — возрастающая функция, то вероятность
события p0 (vj ) = p равна нулю.) Таким образом, ожидаемый выигрыш i-го игрока с оценкой v ,
предложившего цену p , в предположении, что все остальные игроки выбрали стратегии p0 (·), равен

?(p)n?1 · (v ? p) + (1 ? ?(p)n?1 ) · 0 = (v ? p)?(p)n?1 .

Условия первого порядка для задачи максимизации ожидаемого выигрыша имеют вид

(n ? 1)(v ? p)?(p)n?2 ? (p) ? ?(p)n?1 = 0

или
(n ? 1)(v ? p)? (p) ? ?(p) = 0.
В равновесии игрок, имеющий оценку v , должен предлагать цену p = p0 (v). Подставив это в
условия первого порядка, получаем:

(n ? 1)(v ? p0 (v))? (p0 (v)) ? ?(p0 (v)) = 0.

Поскольку ?(·) — функция, обратная к p0 (·), то
1
?(p0 (v)) = v и ? (p0 (v)) = .
p0 (v)

Получим дифференциальное уравнение

(n ? 1)[v ? p0 (v)] ? p0 (v)v = 0.

Решением этого уравнения, как несложно проверить, является
n?1 C
p0 (v) = v + n?1 ,
n v
где C — константа интегрирования. Найдем эту константу. По смыслу игры p0 (v) не должна пре-
вышать v . С другой стороны, по условию заявленная цена не может быть отрицательной. Поэтому
должно выполняться граничное условие p0 (0) = 0, откуда C = 0. Таким образом, наши рассуждения
приводят к стратегиям вида
n?1
p0 (v) = v.
n
В самом деле, при таких стратегиях других игроков ожидаемый выигрыш игрока с оценкой v ,
(n?1
)
n
(v ? p)pn?1 ,
n?1

достигает глобального максимума на R+ при p = n?1 v , то есть условия первого порядка дали нам пра-
n
вильное решение. Заметим, что хотя мы нашли равновесие, но не можем быть уверены, что полученное
нами решение единственно.
Если в аукционе участвуют 2 игрока, то в равновесии каждый предложит цену на уровне половины
своей оценки. С ростом количества участников равновесные стратегии все больше приближаются к
«правдивым» стратегиям pi (v) = v .
Выше уже упоминалось, что равновесие в смешанных стратегиях в играх с полной информацией
можно представить как байесовское равновесие (в чистых стратегиях) в играх с неполной информаци-
ей. Рассмотрим в качестве примера Игру 16.2.5 «Инспекция».
С помощью байесовского равновесия можно имитировать эффект смешанных стратегий при ис-
пользовании только чистых стратегий. Рассмотрим, как это можно сделать на примере Игры 16.2.5
«Инспекция» (с. 636). Предположим, что оба игрока могут быть разных типов. Для упрощения пред-
положим, что множество типов у каждого из игроков — отрезок [0, 1]. При этом предполагаем, что
разные типы одного и того же игрока имеют одинаковые предпочтения (те, что заданны Таблицей 16.9).
Несложно проверить, что следующий набор стратегий является байесовским равновесием расширен-
ной игры: налогоплательщик платит налог, если его тип удовлетворяет условию ?1 1/2 , в противном
16.6. Динамические байесовские игры 669

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

Задачи
 705. Как представить Игру 16.2.1 (с. 625) в виде байесовской игры?
 706. Богатство отца составляет $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 ].
(A) Рассмотрим следующую игру. Каждый из братьев решает, разделить ли деньги, находящиеся
в конвертах. Таким образом каждый из братьев говорит «Да» или «Нет» (одновременно). Если оба
говорят «Да», они делят деньги поровну. Если хотя бы один из братьев говорит «Нет», то они остаются
с деньгами, находящимися в их собственных конвертах.
(i) Каждый брат знает только количество денег в его собственном конверте. Таким образом тип
каждого брата — это элемент множества {1, 2, 4, 8, . . .}. Каково распределение вероятностей по типам?
(ii) Опишите эту ситуацию формально как игру с неполной информацией.
(iii) Опишите равновесие (Нэша — Байеса) в чистых стратегиях, в котором братья делят деньги.
Проверьте, что это действительно равновесие. Существует ли в этой игре другое равновесие?
(B) Предположите теперь, что отец объявил, что ни в одном из конвертов не может находиться
больше чем $3 ? 2K (для некоторого K 1 ). Охарактеризуйте равновесия Нэша — Байеса в чистых
стратегиях получившейся в результате игры.
 707. В Таблице 16.19 показана «возмущенная» игра «Инспекция» (см. Игру 16.2.5). В ней ?1 и
?2 — случайные возмущения, соответствующие типу 1-го и 2-го игрока соответственно, причем ?1 и
?2 равномерно распределены на отрезке [0, ?] (? > 0 ) и независимы между собой33 . Найдите байесов-
ское равновесие (в чистых стратегиях) в этой игре. Докажите, что при ? > 0 найденное байесовское
равновесие стремится к равновесию в смешанных стратегиях исходной игры (Игра 16.2.5 на с. 636).
[Указание: Подскажем, равновесие какого вида здесь искать. Каждый игрок выбирает некоторый
пороговый уровень, ?i . Равновесные стратегии выглядят следующим образом: если ?1 < ?1 , то первый
? ?
игрок выбирает стратегию «нарушать», а если ?1 > ?1 — то стратегию «не нарушать» (вероятность
?
того, что ?1 = ?1 равна нулю, поэтому этот случай можно не рассматривать); аналогичным образом
?
второй игрок выбирает стратегию «проверять», если ?2 < ?2 и стратегию «не проверять», если ?2 > ?2 .]
? ?



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

Инспектор
проверять не проверять

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

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

ОГЛАВЛЕНИЕ

Следующая >>