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

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

ОГЛАВЛЕНИЕ

Следующая >>


Для байесовских игр предложена концепция равновесия,258 аналогичная равновесию Нэша
в играх с полной информацией.


Определение 12.



257
Можно задать целевые функции не для типов, а для игроков. В таком случае игрок максимизирует ожи-
даемую полезность, исходя из вероятности того, что он окажется того или иного типа. Оба подхода совпа-
дают при естественном предположении, что вероятность появления любого типа не равна нулю.
258
Концепция байесовского равновесия предложена американским экономистом венгерского происхожде-
ния Джоном Харшаньи. (Harsanyi, J. C. (1967-8), "Games with Incomplete Information Played by 'Bayesian'
Players," Parts I, II and III, Management Science, 14, 159-182, 320-334, 486-502.

673
674
Набор стратегий (s 1(?), ..., -m(?)) является равновесием Нэша-Байеса (байесовским рав-
- s
новесием) в игре с неполной информацией, если для каждого типа ? ? ?i каждого игрока
i действия -i(?) максимизируют его ожидаемую полезность в предположении, что все
s
другие игроки выбрали равновесные стратегии:

Ui(?, -i(?), s–i(?)) = max Ui(?, xi, s–i(?))
- -
s
xi ? Xi



Для того, чтобы введенные определения стали более понятными, проиллюстрируем их на
условном примере.


Игра 10. «b/K%! *%iCu?2a!=»
В игре участвуют два игрока, использующие в работе компьютеры. Каждый игрок может
быть двух типов — предпочитает работать либо на IBM PC, либо на Макинтоше, причем
любители IBM PC попадаются с вероятностью ? (для обоих игроков). Каждый из игроков
выбирает либо IBM PC, либо Макинтош. Лишь после того, как игрок выбрал тип компью-
тера, он узнает, с партнером какого типа ему предстоит работать, и какой тот выбрал себе
компьютер. Каждый из типов каждого из игроков оценивает пользование компьютером
любимой разновидности в 1 у.е., а пользование другим компьютером в 0 у.е. Игроки по-
лучают дополнительный выигрыш в 2 у.е., если выберут компьютеры одной и той же раз-
новидности. (


Игра представлена в Таблице 22.
Мы не будем полностью решать эту игру. Найдем только условия для параметра ?, при
которых набор стратегий «если игрок любит IBM, то оно выбирает IBM; если игрок любит
Mac, то он выбирает Mac», т.е. ((IBM, Mac), (IBM, Mac)), будет равновесием Нэша-
Байеса.
Рассмотрим выбор 1-го игрока, если он предпочитает IBM PC. Если он ожидает, что стра-
тегией 2-го игрока является (IBM, Mac), то его ожидаемая полезность от выбора компью-
теров IBM PC и Макинтош равна соответственно
IBM: ??3 + (1–?)?1,
Mac: ??0 + (1–?)?2.
Первый игрок такого типа выберет IBM PC, если выполнено условие
??3 + (1–?)?1 > ??0 + (1–?)?2
или
? > 1/4.




674
675
Oaaeeoa 22
Игрок 2
Любит IBM Любит Mac
Игрок 1
IBM Mac IBM Mac
0 2 1
3
IBM
Любит 1 3 1
3
[?]
IBM 2 0 3
1
Mac 2 0 2
0
0 2 1
3
IBM
Любит 0 2 0
2
[1–?]
Mac 2 0 3
1
Mac 3 1 3
1
[?] [1–?]


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


Следующий пример не является полноценной игрой, поскольку выбор в нем делает только
один игрок, однако он включает все те компоненты байесовской игры, о которых здесь
говорилось. Этот пример показывает, как можно моделировать то, что один и тот же игрок
может в зависимости от некоторых случайных обстоятельств обладать разным объемом
информации. Размышления над примером позволяет «сломать» некоторые стереотипы,
которые могут сложиться на основе формального определения байесовской игры.


Игра 11. «b=.2a!»
На входе в некоторое учреждение стоит вахтер. В учреждение могут войти посетители
двух типов: «свои» и «чужие» (будем их для краткости обозначать A и B). Некоторые по-
сетители кажутся вахтеру своими, а некоторые — чужими. Таким образом, в данной игре
есть 2 типа вахтера (обозначим их соответственно a и b). Вахтер может проверить у посе-
тителя наличие пропуска. При этом, если посетитель окажется своим, то выигрыш вахтера
составит –1, а если чужим, то 1. (
Oaaeeoa 23
Посетитель

675
676
A B
проверять –1 1
?Aa ?Ba
a
не проверять 0 0
Вахтер
проверять –1 1
?Ab ?Bb
b
не проверять 0 0


Матрица игры приведена в Таблице 23. Вероятность того, что свой посетитель кажется
вахтеру своим обозначена ?Aa и т. д. Заметим, что по смыслу игры, если вахтер достаточно
опытен, то вероятности появления типов не должны быть независимыми.
Условная вероятность того, что посетитель свой, если он кажется своим, равна ?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. «`3*o,%… “ ?= "*=i, " ?=Ca?=2=……/. *%…"a!2=.»
Некий предмет продается с аукциона. Участники аукциона (i = 1, ..., n), подают свои заяв-
ки, pi > 0, в запечатанных конвертах. Побеждает тот, кто предложит самую высокую цену.
(Если самую высокую цену предложат сразу несколько участников, то победитель опре-
деляется жребием.) Победивший участник платит заявленную цену и получает предмет.
Если i-й участник окажется победителем, то его выигрыш составит vi – pi, где vi — цен-
ность для него данного предмета; выигрыш всех остальных участников будет равен нулю.
Известно, что оценки vi распределены равномерно на отрезке [0, 1] и независимы. (


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


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


где мы воспользовались тем, что оценка vj равномерно распределена на [0, 1], и обозначи-
ли через ?(p) функцию, обратную к p0(?). Поскольку по предположению vj распределены
независимо, то события p0(vj) < p независимы, и вероятность того, что i–й игрок выиграет
аукцион, заявив цену p, равна ?(p) . (Здесь мы пользуемся тем, что, поскольку p0(?) —
n-1

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


Условия первого порядка для задачи максимизации ожидаемого выигрыша имеют вид
(n–1)(v – p) ?(p) ??(p) – ?(p)
n-2 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) = n v + vn–1 ,

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

В самом деле, при таких стратегиях других игроков ожидаемый выигрыш игрока с оцен-
кой v,
n ?n–1
? n-1
n – 1? (v – p) p ,
?

677
678
достигает глобального максимума на  + при p = nn 1 v, то есть условия первого порядка да-


ли нам правильное решение. Заметим, что хотя мы нашли равновесие, но не можем быть
уверены, что полученное нами решение единственно.
Если в аукционе участвуют 2 игрока, то в равновесии каждый предложит цену на уровне
половины своей оценки. С ростом количества участников равновесные стратегии все
больше приближаются к «правдивым» стратегиям pi(v) = v.


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

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

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

ОГЛАВЛЕНИЕ

Следующая >>