Лекция 18. Игры с неполной информацией

 

Игра с наблюдениями. Является ли понятие коррелированного равно­весия чем-то принципиально новым по сравнению с равновесием Нэша? Нет, просто мы заменяем исходную игру некоторой ее модификацией. Сначала ход делает природа (£) с предписанными вероятностями, затем наблюдения де­лают игроки (видят £i). Наконец, разыгрывается первоначальная игра G. А уже в этой новой, видоизмененной с помощью информационной системы £. игре G(£) рассматриваются равновесия Нэша. Конечно, нужно помнить, что стратегии игрока теперь Si могут зависеть от наблюдаемого значения ^, т.е. являются функциями .%•; : Ei —> Si.

Стоит, быть может, привести понятие информационной системы. Это объ­ект, состоящий из: множества О состояний природы, отображений О —> (информация, получаемая г-м игроком) и приора (вероятности) v £ А (О). Если перенести вероятность вперед, то можно ограничиться более частным понятием информационной системы: это множество-произведение Н = с вероятностной мерой v на нем.

В случае игры с посредником множества совпадали с Sf7 более того, наблюдаемое значение было просто подсказкой игроку - как играть. Корре­лированное равновесие тогда - это "послушное", тождественное равновесие в

"расширенной", оснащенной игре. Казалось бы, выше было предложено го­раздо более общее понятие. Оказывается, что по существу мы не получаем ничего нового. Любая игра с наблюдениями сводится к коррелированному равновесию. Здесь впервые проявляет себя довольно общий и простой прин­цип выявления (the revelation principle). Он состоит в том, что любое равнове­сие в любой игре с наблюдениями сводится (эквивалентно в каком-то смысле) к коррелированному равновесию, т.е. к игре с прямыми указаниями о том, что делать.

Объясним, в чем тут дело. Пусть s*(-) - равновесные стратегии в игре G(£) со случайной величиной £ £ А(х^Н^). Рассмотрим тогда отображение s* : Ндг —у S, перенесем с его помощью вероятностную меру с Ед- ни S и обозначим маргинал как ц. Ясно, что при этом получится коррелированное равновесие. В самом деле, если игрок / найдет для себя выгодным использо­вать другую (нетождественную) стратегию Si : St —>> Sh то и в игре G(£) ему было бы выгоднее применять стратегию Si(s*)7 что противоречило бы Нэшевости s*.

Уже это простое соображение помогает описать множество всех платежей, достижимых равновесиями в играх с наблюдениями. Так как они совпадают с коррелированными равновесиями, это указанный выше многогранник.

Явный учет сообщений. Выше мы позволили игрокам что-то наблюдать. Чтобы замоделировать переговоры, мы должны включить в картину и сообщения, посылаемые участниками другим участникам. Рассмотрим одну из возможных моделей.

Представим, что игрок г имеет множество Щ посланий, которые он может отправить (куда? в систему сообщений), и пусть Л/( - множество сообщений, которые он может по­лучить. Система сообщений (коммуникаций) перерабатывает посылаемые сообщения в получаемые. Если R = х ,•/>',-. а Л/ = х( Л/(. то работу системы без помех можно изобразить отображением 7 : R —У Л/. Однако полезно сразу же допустить возможность случайных помех, и тогда система коммуникаций - это отображение 7 : R —У А (Л /).

Стратегическое множество игрока г превращается теперь в

П; = {(,:,)). г е /,',. ,):.\/;—►>',-}.

Т.е. участник решает, какое сообщение ему послать, и как отреагировать на полученное сообщение. Выигрыши Щ также легко выписываются: это

Y2j(rn\r)ui((Si(rni)).

т

Более наглядно это можно понимать так. Для каждого участника / и его "стратегии реа­гирования" S{ мы имеем отображения

R -1+ MM) ^ A (Mi) A A(Si).

Теперь, если дан профиль стратегий ((г^,^)), можно образовать г е Д и его образ в

ХгД(б'г) (ИЛИ В Д(Хг^)). Последнее МНОЖ6СТВО ВЫПУКЛО, ПОЭТОМУ ДЛЯ Любой СМ6СИ Профи­лей можно смешать образы и получить элемент из Д (>!?), т.е. коррелированную стратегию. Теперь можно перейти к полезностям.

Таким образом, коммуникационная система 7 : К —У Д (Л /) порождает новую комму­никационную игру С(7) со стратегиями и выигрышами \]\. И можно начинать анали­зировать равновесия в игре С?(7), сравнивать их со старыми и т.п. Например, если множе­ство К вырождено (из одной точки), коммуникационная система превращается в элемент Д (Л /). т.е. в информационную систему. Да и в общем случае, после того как все послания г( отправлены (зафиксированы), мы получаем информационную систему. Поэтому не удиви­тельно, что каждое равновесие в С (7) также эквивалентно некоторому коррелированному равновесию в исходной игре С Это снова проявление принципа выявления.

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

Как же анализировать такие ситуации? Начнем с простого примера.

Пример. Дуополия Курно с асимметричной информацией. Дуополия Курно, рыночный спрос задается ценами Р(0) = М — (}. где Q = ql + q2 -суммарный выпуск двух фирм. Издержки (удельные) первой фирмы извест­ны всем и равны с. Издержки (тоже удельные) второй фирмы равны либо с', либо с" (с' < с"), с вероятностями в и 1 — в соответственно. Вторая фирма знает точно свои издержки, но первая знает только вероятности в.

Естественно, что вторая фирма будет вести себя по разному при боль­ших или малых издержках. Обозначим эти количества д' и д"; выпуск первой фирмы обозначим ql.

Вторая фирма при низких издержках с' решает задачу

q(M — q — ql — с') —> шах. и решение ее (как функция от ql) равно

4 = (М - д1 - с')/2.

Аналогично,

д" = (М - д1 - с")/2.

Первая фирма не может различать эти случаи и должна выбирать единое д1; ее задача

дгЩМ -д1-д' - с)/2 + (1 - в)(М - дг - д" - с)/2] —у шах,и решение

ді = (М - с - д(( - (1 - %")/2.

(мы всюду предполагаем решение внутренним). Ответ для первой фирмы такой:

Й = [М - 2с - вс' - (1 - в)с"]/3,

и похожие ответы для второй фирмы ((М — 2с' + с)/3 минус некоторый до­бавок в случае низких издержек и (М — 2с" + с)/3 плюс некоторый добавок в случае высоких издержек). То есть выпуск второй фирмы больше при вы­соких издержках по сравнению со случаем полной информированности. (По­чему? Потому что первая фирма из-за незнания снижает свой выпуск (ибо могло бы случиться, что у второй низкие издержки и она предложит больше на рынок), а поэтому вторая фирма может немного увеличить свой выпуск.)

Посмотрите, что мы сделали. Мы представили ситуацию с неполной ин­формацией игрой в развернутой форме, где неполнота информации 1-й фир­мы о типе 2-й фирмы выражается как несовершенство информации 1-ым игроком относительно хода природы. Несовершенство информации фирм от­носительно ходов друг друга отражается как обычно.

 

Развернутая игровая форма для дуополии. Выигрыши не указаны.

Байесовы игры. Харшаньи (1967-68) предложил общий способ представ­ления игр с неполной информацией. Личная информация отражается при этом типом игрока, который включает в себя полезности, информирован­ность и представления об остальных. Такое представление называется Байе-совой игрой. Байесовы игры почти столь же просты, как и игры в нормальной форме.

Для задания Байесовой игры нужно указать множество игроков И, и для каждого игрока г £ N задать множество его возможных действий А^. Это все было раньше. Новым является задание для каждого игрока г множества возможных типов 7] этого игрока. Тип игрока отражает его полезности (вы­игрыши) и его информацию. Это делается с помощью функций полезности щ : Адг х Тдг —у К. (часто полезность щ зависит только от типа игрока г) и с помощью его вер    : 7] —у А(Т_^).

Поясним две последние вещи. С полезностями все ясно. Выигрыш игрока г зависит не только от выбора действий адг (это было и раньше), но и от типа г (и, быть может, от типов остальных). Перед началом игры каждый игрок зна­ет свой тип; что касается типов остальных игроков, то он имеет о них лишь вероятностные представления (веры). Представление (знание, вера) игрока типа 1{ о типах остальных задается как вероятностная мерар^(^) = (Рг(^-г|^г)) на = у.^ф{Гу Например, эта вера может быть его субъективным пред­ставлением, никак не связанным с реальным типом его партнера. Однако на практике обычно считается, что имеется некоторое априорное распределение вероятности Р на Тдг. И тогда индивидуальные вероятности р-, формируются как условные вероятности, т.е.р^-^и) = Р{^)/{^2ГР^-ъ-, и) Для всевоз­можных Ь = и г. Эти данные (Т^и^р^) считаются известными всем и даже предполагаются общим знанием.

Как же мыслится развитие игры? Сначала природа (руководствуясь веро­ятностью Р) выбирает тип ^. Затем каждый игрок узнает свой собственный тип и поэтому свою полезность и свои веры. После этого он должен выбрать свои действия (зависящие от его информации, то есть от типа 1^). Поэтому стратегией называют отображение 5^ : 7] —у А^ из типов в действия.

Могло бы показаться странным - зачем игроку нужно фиксировать весь свой набор действий при всевозможных его типах, когда он знает свой текущий тип и ему нужно выбрать соответствующее действие. Дело в том, что другие не знают его тип; чтобы им найти наилучший ответ, им нужно знать его действия во всех ситуациях. В примере с асимметричной дуаполией Курно первая фирма, чтобы найти оптимальный ответ, должна знать и     и д".

Байесовы равновесия. Что же считать равновесием в Байесовой игре (./V, (А(: 7], щ:р(: г £ Как обычно, взаимно наилучшие ответы. Пусть

игроки выбрали по стратегии : 7] —у А^. Каков их выигрыш, точнее, каков выигрыш игрока г, имеющего тип £ Т(1 Еще более точно, как оценивает свой выигрыш такой игрок, зная стратегии в^? Представим на минуту, что он знает типы остальных игроков. Тогда он знает их действия в^(^), и может посчитать свой выигрыш как м^(в^(^), в^(^); Однако он незнает в точности а знает только вероятности р^-^и). Поэтому он может посчитать ожидаемое значение своего выигрыша

Теперь равновесием (Байесовым) будет такой набор стратегий вдг, что для любого г, любого ^ £ 7] и любой другой стратегии : 7] —у выполняются неравенства

Аналогично определяются равновесия в смешанных стратегиях.

Фактически мы превратили Байесову игру в обычную игру в нормальной форме и использовали в ней понятие равновесия Нэша. Более точно, мы ввели вместо каждого игрока г множество 7] его типов, так что число игроков резко увеличилось. Однако у каждого такого игрока стратегии старые - Л/. Есть другой, по существу эквивалентный способ образовать игру в нормальной форме. В ней множество игроков остается старым, но каждый игрок может действовать в зависимости от приходящей к нему информации (о его "типе", так что его стратегии - это отображения из 7] в А^); выигрыш же он усредняет по всему множеству 7дг. Тут полезно вспомнить об играх с сообщениями (или наблюдениями); единственное новшество здесь в том, что выигрыш может зависеть от типа (или наблюдения).

Аукционы. Понятие Байесова равновесия незаменимо при анализе аук­ционов. Начнем с простейшего примера.

Два покупателя (биддера) хотят купить некий предмет. Оценка предмета V для каждого равномерно распределена на отрезке [0,1]. Действует аукцион первой цены (то есть предмет достается тому, кто предложит наибольший бид, и он платит предложенную цену; проигравший ничего не получает и не платит). Биддеры нейтральны к риску.

Чтобы сделать это Байесовой игрой, нужно уточнить действия, типы, ве­ры и выигрыши. Тут все ясно. Стратегии - отображения отрезка в (неявно это означает, что полезность предмета для продавца равна 0). Для упрощения будем искать равновесие в аффинных стратегиях; то есть 61 (г^) = а\ + с\у\, где с\ > 0, и аналогично для второго. (Конечно, выбирать оптимальную стратегию они могут как угодно, мы просто ищем равновесие такого специ­ального вида.) Мы обнаружим, что в равновесии б^(^) = То есть агенты называют половину своей оценки.

Итак, пусть игрок у применяет стратегию Ь^[у^) = + При данном у. выигрыш игрока г равен

Ясно, что Ь{ нужно назначать на отрезке + с?], и что для таких

РгоЬ(6^ > + срф) = {Ь{ — аф)1су Отсюда легко понять (максимизируя квадратичную по    функцию), что наилучший ответ

&$(^$) = {vi + %)/2, если VI >      и =    в противном случае.

Мы видим отсюда, что с; = 1/2, и что а/ = (1]/'2. Так как симметрично с^- = 1/2 и с^- = щ/2, то    = а^- = 0.

Конечно, если распределение оценок неравномерное, нужно искать реше­ние в нелинейных стратегиях.

Более общий пример. Пусть и игроков борются за один (неделимый) предмет. Каж­дый знает, насколько предмет ценен для него; что же касается остальных, то ценности распределены на интервале [0, М] с кумулятивным распределением /• (/•' дифференциру­емая неубывающая функция). Игроки делают предложения (запечатанные биды) Ь{ > 0; действует аукцион первой цены.

Будем искать симметричное равновесие в соответствии с некоторой возрастающей функ­цией /3 (от его истиной оценки у). Пусть при истиной ценности у игрок делает вид, что ценит в из. Тогда его ожидаемый выигрыш равен

так как Р(из)п 1 - это вероятность того, что все остальные ценят предмет меньше из и наш игрок побеждает на аукционе. Условие первого порядка дает соотношение

для оптимального ги. По определению, из должно совпадать с V, причем при всех V. По­этому мы получаем дифференциальное уравнение для функции /3:

(уі - 6і)РгоЬ(6і > СЬу + СуУу).

(V - (3(из))Г(из)

п-1

(и-/3(ад))(п- 1)^'(ад) = /З'(ад)

/З» = (п-1)(ь-Р(ь))Ґ(ь).

Решая это уравнение, получаем

р(х) = Г(х)1-п(п - 1) / іГ(і)п-2Г'(і)<ІЇ.

 

В случае равномерного распределения это дает функцию

= (1 - 1/п)и на [0,М].

В случае п = 2 мы приходим к старому ответу: предлагать половину стоимости.

Более подробно про аукционы можно почитать у Майерсона или Бинмора.

Сравнение аукционов. Сравним рассмотренный выше аукцион первой цены (для простоты - с двумя участниками и равномерным распределением ценности на отрезке [0,1]) с аукционом второй цены. А именно, посмотрим, сколько в среднем получает про­давец предмета при аукционе первой цены. Мы видели, что при ценностях (Г|. г-,), когда Г| > г... продавец получает Г| /2. Поэтому его ожидаемый выигрыш в этой ситуации зада­ется интегралом

Вторая половина ситуации (когда у\ < г^) дает еще столько же, так что полный (ожидае­мый) выигрыш продавца равен 1/3.

При аукционе второй цены, когда у\ > У2, предмет достается первому игроку, и он платит г2- Поэтому выигрыш продавца при таких условиях задается интегралом

Вторая половина (когда у\ < г^) дает столько же, и продавец снова получает 1/3.

Мы видим, что два таких разных аукциона дают в среднем один и тот же выигрыш продавцу (и покупателям, если проделать аналогичные вычисления). И это не случайное совпадение. Знаменитая теорема об эквивалентности аукционов утверждает, что, грубо го­воря, любые аукционы (с любым числом симметричных покупателей) эквивалентны в том смысле, что ожидаемый выигрыш любого участника не зависит от выбранного аукциона.

 

1/2 • 1/3 = 1/6.