Идеальное байесовское равновесие

Идеальное байесовское равновесие
Концепции решения в теории игр
Отношение
Подмножество	Байесовское равновесие по Нэшу
Значимость
Предложено	Чо и Крепс ^{[ необходима ссылка ]}
Используется для	Динамические байесовские игры
Пример	сигнальная игра

В теории игр , Идеальное байесовское Равновесие (РОВ) является равновесным понятием актуально для динамичных игр с неполной информацией (последовательная байесовская игрой ). Это уточнение байесовского равновесия по Нэшу (BNE). Идеальное байесовское равновесие состоит из двух компонентов - стратегии и убеждений :

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

Стратегии и убеждения должны удовлетворять следующим условиям:

Последовательная рациональность : каждая стратегия должна быть оптимальной в ожидании, учитывая убеждения.
Последовательность : каждое убеждение должно обновляться в соответствии со стратегиями равновесия, наблюдаемыми действиями и правилом Байеса на каждом пути, достигнутом в равновесии с положительной вероятностью. На путях с нулевой вероятностью, известных как пути вне равновесия , убеждения должны быть указаны, но могут быть произвольными.

Совершенное байесовское равновесие - это всегда равновесие по Нэшу и совершенное равновесие подыгры .

Примеры идеального байесовского равновесия [ править ]

Подарочная игра 1 [ править ]

Рассмотрим следующую игру: ^[1]

У отправителя есть два возможных типа: либо «друг» (с вероятностью ), либо «враг» (с вероятностью ). У каждого типа есть две стратегии: либо дарить, либо не дарить. ${\ displaystyle p}$ ${\ displaystyle 1-p}$
У получателя есть только один тип и две стратегии: либо принять подарок, либо отклонить его.
Полезность отправителя равна 1, если его подарок принят, -1, если его подарок отклонен, и 0, если он не дает никаких подарков.
Полезность получателя зависит от того, кто дарит подарок:
- Если отправитель - друг, то полезность получателя равна 1 (если он принимает) или 0 (если он отклоняет).
- Если отправитель - враг, то полезность получателя равна -1 (если он принимает) или 0 (если он отклоняет).

Для любого значения равновесия 1 существует равновесие объединения, в котором оба типа отправителя выбирают одно и то же действие: ${\ displaystyle p,}$

Равновесие 1. Отправитель: Дайте , будь то типа друга или врага. Получатель: Не принимать , полагая, что Prob (Friend | Not Give) = p и Prob (Friend | Give) = x, выбирая значение

{\ Displaystyle х \ leq .5.}

Отправитель предпочитает выплату 0 вместо отказа от выплаты -1 от отправки и отказа от приема. Таким образом, Give имеет нулевую вероятность в равновесии, а правило Байеса вообще не ограничивает веру Prob (Friend | Give) . Эта вера должна быть пессимист достаточно того, что приемник предпочитает выигрыш 0 от отказа подарка к ожидаемому выигрышу от принятия, поэтому требование о том , что стратегия приемника максимизировать его ожидаемый выигрыш учитывая его убеждение требует , что вероятностная (Friend | Give) На с другой стороны, Prob (Friend | Not give) = p требуется правилом Байеса, поскольку оба типа выполняют это действие, и оно не информативно о типе отправителя. ${\ Displaystyle х (1) + (1-х) (- 1) = 2x-1,}$ ${\ displaystyle \ leq .5.}$

Если существует второе равновесие объединения, а также равновесие 1, основанное на различных убеждениях: ${\ displaystyle p \ geq 1/2}$

Равновесие 2. Отправитель: Не давайте , будь то тип друга или тип врага. Получатель: Принять, полагая, что Prob (Friend | Give) = p и Prob (Friend | Not give) = x , выбирая любое значение для

{\ displaystyle x.}

Отправитель предпочитает выплату 1 вместо выплаты компенсации 0 от отказа, ожидая, что его подарок будет принят. В равновесии правило Байеса требует, чтобы получатель имел веру Prob (Friend | Give) = p , поскольку оба типа предпринимают это действие, и это не информативно о типе отправителя в этом равновесии. Неравновесное убеждение не имеет значения, поскольку отправитель не хотел бы отклоняться от положения « Не давать» независимо от того, какой ответ будет у получателя.

Равновесие 1 является извращенным, если в игре может быть так, что отправитель, скорее всего, является другом, но получатель все равно откажется от любого подарка, потому что считает, что враги дарить подарки гораздо чаще, чем друзья. Это показывает, как пессимистические убеждения могут привести к ухудшению равновесия для обоих игроков, которое не является эффективным по Парето . Однако эти убеждения кажутся нереалистичными, и теоретики игр часто готовы отвергать некоторые идеальные байесовские равновесия как неправдоподобные. ${\ displaystyle p \ geq .5.}$ ${\ displaystyle p = 0,99,}$

Равновесия 1 и 2 являются единственными равновесиями, которые могут существовать, но мы также можем проверить два потенциальных разделяющих равновесия , в которых два типа отправителя выбирают разные действия, и понять, почему они не существуют как идеальные байесовские равновесия:

Предположим, что стратегия отправителя такова: давать другу, не давать врагу. Убеждения получателя соответственно обновляются: если он получает подарок, он считает, что отправитель - друг; в противном случае он считает, что отправитель - враг. Таким образом, получатель ответит Accept . Если получатель выбирает « Принять» , то вражеский отправитель отклоняется в сторону « Раздать» , чтобы увеличить свой выигрыш с 0 до 1, так что это не может быть равновесием.
Предположим, что стратегия отправителя такова: не отдавать, если друг, давать, если враг. Убеждения получателя обновляются соответственно: если он получает подарок, он считает, что отправитель - враг; в противном случае он считает, что отправитель - друг. Стратегия наилучшего ответа получателя - " Отклонить". Однако, если получатель выбирает « Отклонить» , противник-отправитель отклоняется на « Не давать» , чтобы увеличить свой выигрыш с -1 до 0, так что это не может быть равновесием.

Делаем вывод, что в этой игре нет разделяющего равновесия.

Подарочная игра 2 [ править ]

В следующем примере набор PBE строго меньше, чем набор SPE и BNE. Это вариант вышеупомянутой подарочной игры со следующими изменениями в утилите получателя:

Если отправитель - друг, то полезность получателя равна 1 (если они принимают) или 0 (если они отклоняют).
Если отправитель - враг, то полезность получателя равна 0 (если они принимают) или -1 (если они отклоняют).

Обратите внимание, что в этом варианте принятие - слабо доминирующая стратегия для получателя.

Как и в примере 1, разделяющего равновесия нет. Давайте посмотрим на следующие потенциальные равновесия объединения:

Стратегия отправителя: всегда отдавать. Убеждения получателя не обновляются: они все еще верят в априорную вероятность, что отправитель - друг с вероятностью и враг с вероятностью . Их выигрыш от принятия всегда выше, чем от отказа, поэтому они принимают (независимо от значения ). Это PBE - это лучший ответ как для отправителя, так и для получателя. ${\ displaystyle p}$ ${\ displaystyle 1-p}$ ${\ displaystyle p}$
Стратегия отправителя: никогда не отдавать. Предположим, что получатель верит при получении подарка, что отправитель является другом с вероятностью , где любое число в . Независимо от того, оптимальная стратегия получателя: принять. Это НЕ PBE, поскольку отправитель может улучшить свою выплату с 0 до 1, сделав подарок. ${\ displaystyle q}$ ${\ displaystyle q}$ ${\ displaystyle [0,1]}$ ${\ displaystyle q}$
Стратегия отправителя: никогда не отдавать, а стратегия получателя: отвергать. Это НЕ PBE, поскольку для любого мнения получателя отклонение - не лучший ответ.

Обратите внимание, что вариант 3 - это равновесие по Нэшу! Если мы игнорируем убеждения, то отказ может считаться лучшим ответом для получателя, поскольку он не влияет на их вознаграждение (поскольку в любом случае нет подарка). Более того, вариант 3 - это даже SPE, поскольку здесь единственная вспомогательная игра - это вся игра! Такие неправдоподобные равновесия могут возникать также в играх с полной информацией, но их можно устранить, применяя совершенное равновесие по Нэшу в подиграх . Однако байесовские игры часто содержат не одноэлементные информационные наборы, и поскольку подигрыдолжен содержать полные информационные наборы, иногда есть только одна под-игра - вся игра, и поэтому каждое равновесие по Нэшу тривиально является совершенным под-игрой. Даже если игра имеет более одной вспомогательной игры, неспособность совершенствования вспомогательной игры прорезать информационные наборы может привести к тому, что неправдоподобное равновесие не будет устранено.

Подводя итог: в этом варианте подарочной игры есть два SPE: либо отправитель всегда дает, а получатель всегда принимает, либо отправитель всегда не дает, а получатель всегда отклоняет. Из них только первый - PBE; другой - не PBE, поскольку не может поддерживаться какой-либо системой убеждений.

Больше примеров [ править ]

Дополнительные примеры см. В игре «Сигнализация # Примеры» . См. Также ^[2] для получения дополнительных примеров.

PBE в многоступенчатых играх [ править ]

Многоступенчатая игра представляет собой последовательность одновременных игр играла одну за другими. Эти игры могут быть одинаковыми (как в повторяющихся играх ) или разными.

Повторяющаяся общественно-полезная игра [ править ]

	Строить	Не надо
Строить	1-C1, 1-C2	1-C1, 1
Не надо	1, 1-С2	0,0
Общественная хорошая игра

Следующая игра ^[3]^{: раздел 6.2} представляет собой простое представление проблемы безбилетника . Есть два игрока, каждый из которых может либо строить общественное благо, либо не строить. Каждый игрок получает 1, если общественное благо построено, и 0, если нет; кроме того, если игрок строит общественное благо, он должен заплатить стоимость . Стоимость - это личная информация - каждый игрок знает свою цену, но не знает цену другого. Известно только, что каждая стоимость выбирается независимо от некоторого распределения вероятностей. Это делает эту игру байесовской . ${\ displaystyle i}$ ${\ displaystyle C_ {i}}$

В одноэтапной игре каждый игрок строит, если и только если их стоимость меньше, чем их ожидаемый выигрыш от строительства. Ожидаемый выигрыш от строительства ровно в 1 раз превышает вероятность того, что другой игрок НЕ построит. В равновесии для каждого игрока существует пороговая стоимость , так что игрок вносит свой вклад, если и только если его стоимость меньше, чем . Эта пороговая стоимость может быть рассчитана на основе распределения вероятностей затрат игроков. Например, если затраты равномерно распределяются по ${\ displaystyle i}$ ${\ displaystyle C_ {i} ^ {*}}$ ${\ displaystyle C_ {i} ^ {*}}$ ${\ displaystyle [0,2]}$ , то существует симметричное равновесие, в котором пороговая стоимость обоих игроков составляет 2/3. Это означает, что игрок, стоимость которого составляет от 2/3 до 1, не будет вносить свой вклад, даже если его стоимость ниже выгоды, из-за возможности того, что другой игрок внесет свой вклад.

Теперь предположим, что эта игра повторяется два раза. ^[3]^{: раздел 8.2.3} Две игры независимы, то есть каждый день игроки одновременно решают, строить ли общественное благо в этот день, получить выплату 1, если благо построено в этот день, и оплатить свою стоимость. если они построили в тот день. Единственная связь между играми заключается в том, что, играя в первый день, игроки могут раскрыть некоторую информацию о своих расходах, и эта информация может повлиять на игру во второй день.

Ищем симметричный PBE. Обозначьте пороговой стоимостью обоих игроков в день 1 (так, в день 1 каждый игрок строит, если и только если их стоимость не больше ). Для расчета мы работаем в обратном порядке и анализируем действия игроков во второй день. Их действия зависят от истории (= два действия в день 1), и есть три варианта: ${\ displaystyle {\ hat {c}}}$ ${\ displaystyle {\ hat {c}}}$ ${\ displaystyle {\ hat {c}}}$

В день 1 ни одного игрока не построили. Итак, теперь оба игрока знают, что цена их противника выше . Они соответствующим образом обновляют свои убеждения и приходят к выводу, что вероятность того, что их противник построит в день 2, меньше. Следовательно, они увеличивают свою пороговую стоимость, а пороговая стоимость во второй день равна . ${\ displaystyle {\ hat {c}}}$ ${\ displaystyle c ^ {00}> {\ hat {c}}}$
В день 1 оба игрока построили. Итак, теперь оба игрока знают, что цена их оппонента ниже . Они соответствующим образом обновляют свои убеждения и приходят к выводу, что существует большая вероятность того, что их противник построит в день 2. Следовательно, они уменьшают свою пороговую стоимость, а пороговая стоимость во второй день равна . ${\ displaystyle {\ hat {c}}}$ ${\ displaystyle c ^ {11} <{\ hat {c}}}$
В день 1 построился ровно один игрок; предположим, что это игрок 1. Итак, теперь известно, что стоимость игрока 1 ниже, а стоимость игрока 2 выше . Существует равновесие, в котором действия в день 2 идентичны действиям в день 1 - игрок 1 строит, а игрок 2 не строит. ${\ displaystyle {\ hat {c}}}$ ${\ displaystyle {\ hat {c}}}$

Можно рассчитать ожидаемый выигрыш «порогового игрока» (игрока с точной стоимостью ) в каждой из этих ситуаций. Поскольку пороговый игрок должен быть безразличен между внесением вклада и отказом от него, можно рассчитать пороговую стоимость дня 1 . Оказывается, что этот порог ниже , чем - порог в одномоментной игре. Это означает, что в двухэтапной игре игроки меньше хотят строить, чем в одноэтапной. Интуитивно причина в том, что, когда игрок не вносит взнос в первый день, он заставляет другого игрока поверить, что его цена высока, и это заставляет другого игрока более охотно вносить взнос во второй день. ${\ displaystyle {\ hat {c}}}$ ${\ displaystyle {\ hat {c}}}$ ${\ displaystyle c ^ {*}}$

Прыжковые ставки [ править ]

На открытом аукционе на английском языке участники торгов могут повышать текущую цену небольшими шагами (например, каждый раз на 1 доллар). Однако часто бывает скачок ставок - некоторые участники торгов повышают текущую цену намного больше, чем минимальный шаг. Одно из объяснений этого состоит в том, что это служит сигналом для других участников торгов. Существует PBE, в котором каждый участник торгов перепрыгивает, если и только если их значение превышает определенный порог. См. Jump bidding # signaling .

См. Также [ править ]

Последовательное равновесие - уточнение PBE, которое ограничивает убеждения, которые могут быть отнесены к наборам информации вне равновесия, «разумными».
Интуитивный критерий и Божественное равновесие - другие усовершенствования PBE, характерные для сигнальных игр .

Ссылки [ править ]

^ Джеймс Пек. «Идеальное байесовское равновесие» (PDF) . Государственный университет Огайо . Дата обращения 2 сентября 2016 .
^ Зак Гроссман. «Идеальное байесовское равновесие» (PDF) . Калифорнийский университет . Дата обращения 2 сентября 2016 .
^ a b Фуденберг, Дрю ; Тироль, Жан (1991). Теория игр . Кембридж, Массачусетс: MIT Press . ISBN 9780262061414. Предварительный просмотр книги.

[1] Джеймс Пек. «Идеальное байесовское равновесие» (PDF) . Государственный университет Огайо . Дата обращения 2 сентября 2016 .

[2] Зак Гроссман. «Идеальное байесовское равновесие» (PDF) . Калифорнийский университет . Дата обращения 2 сентября 2016 .

[ft91-3] Фуденберг, Дрю ; Тироль, Жан (1991). Теория игр . Кембридж, Массачусетс: MIT Press . ISBN 9780262061414. Предварительный просмотр книги.

[1]

vтеТемы по теории игр
Определения	Кооперативная игра Решительность Эскалация обязательств Игра в расширенной форме Победа первого и второго игрока Сложность игры Графическая игра Иерархия убеждений Информационный набор Игра в нормальной форме Предпочтение Последовательная игра Одновременная игра Выбор одновременного действия Решенная игра Лаконичная игра
Концепции равновесия	равновесие по Нэшу Совершенство подигры Устойчивое равновесие по Мертенсу Байесовское равновесие по Нэшу Идеальное байесовское равновесие Дрожащая рука Правильное равновесие Эпсилон-равновесие Коррелированное равновесие Последовательное равновесие Квази-совершенное равновесие Эволюционно устойчивая стратегия Доминирование риска Основной Значение Шепли Парето эффективность Равновесие Гиббса Квантовое равновесие отклика Самоподтверждающееся равновесие Сильное равновесие по Нэшу Марковское идеальное равновесие
Стратегии	Доминирующие стратегии Чистая стратегия Смешанная стратегия Аргумент кражи стратегии Око за око Мрачный спусковой крючок Сговор Обратная индукция Прямая индукция Марковская стратегия Затенение ставки
Классы игр	Симметричная игра Идеальная информация Повторная игра Сигнальная игра Показ игры Дешевый разговор Игра с нулевой суммой Конструкция механизма Проблема торга Стохастическая игра Средняя игра n -игровая игра Большая игра Пуассона Нетранзитивная игра Глобальная игра Строго определенная игра Возможная игра
Игры	Идти Шахматы Бесконечные шахматы Шашки Крестики-нолики Дилемма заключенного Игра по обмену подарками Необязательная дилемма заключенного Дилемма путешественника Координационная игра Курица Сороконожка игра Дилемма волонтера Долларовый аукцион Битва полов Охота на оленя Соответствующие пенни Ультиматум игра Камень ножницы Бумага Пиратская игра Диктаторская игра Игра в общественные блага Блотто игра Война на истощение Проблема с баром Эль Фарол Справедливое деление Ярмарка нарезки торта Игра Курно Тупик Дилемма закусочной Угадайте 2/3 среднего Покер куна Игра Нэша в торг Индукционные головоломки Доверительная игра Игра принцесс и монстров Проблема рандеву
Теоремы	Теорема о невозможности Эрроу Теорема согласия Ауманна Народная теорема Теорема о минимаксе Теорема Нэша Теорема очищения Принцип откровения Теорема Цермело
Ключевые цифры	Альберт В. Такер Амос Тверски Антуан Огюстен Курно Ариэль Рубинштейн Клод Шеннон Даниэль Канеман Дэвид К. Левин Дэвид М. Крепс Дональд Б. Гиллис Дрю Фуденберг Эрик Маскин Гарольд В. Кун Герберт Саймон Эрве Мулен Жан Тироль Жан-Франсуа Мертенс Дженнифер Тур Чейес Джон Харсаньи Джон Мейнард Смит Джон Нэш Джон фон Нейман Кеннет Эрроу Кеннет Бинмор Леонид Гурвич Ллойд Шепли Мелвин Дрешер Меррилл М. Флуд Ольга Бондарева Оскар Моргенштерн Пол Милгром Пейтон Янг Райнхард Зельтен Роберт Аксельрод Роберт Ауманн Роберт Б. Уилсон Роджер Майерсон Сэмюэл Боулз Сюзанна Скотчмер Томас Шеллинг Уильям Викри
Разное	All-pay аукцион Альфа – бета обрезка Парадокс Бертрана Ограниченная рациональность Комбинаторная теория игр Анализ конфронтации Сотрудничество Эволюционная теория игр Преимущество первого хода в шахматах Игровая механика Глоссарий теории игр Список теоретиков игр Список игр по теории игр Безвыигрышная ситуация Решение шахмат Топологическая игра Трагедия общественного достояния Тирания малых решений