Идеальное байесовское равновесие - Perfect Bayesian equilibrium

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

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

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

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

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

PBE всегда является сетевым элементом, но не может быть подигра идеальное равновесие (SPE).

PBE в сигнальных играх

А сигнальная игра это простейший вид динамической байесовской игры. Есть два игрока, один из них («получатель») имеет только один возможный тип, а другой («отправитель») - несколько возможных типов. Сначала играет отправитель, затем получатель.

Чтобы рассчитать PBE в сигнальной игре, мы рассматриваем два типа равновесия: разделяющее равновесие и балансирующее равновесие. В разделяющем равновесии каждый тип отправителя выполняет свое действие, поэтому действие отправителя дает информацию получателю; в равновесии объединения все типы отправителей выполняют одно и то же действие, поэтому действие отправителя не дает информации получателю.

Подарочная игра 1

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

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

Чтобы проанализировать PBE в этой игре, давайте сначала рассмотрим следующий потенциал разделение равновесий:

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

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

Теперь давайте посмотрим на следующие потенциальные равновесия объединения:

Стратегия отправителя: всегда отдавать. Убеждения получателя не обновляются: они по-прежнему верят в априорную вероятность, что отправитель с вероятностью друг ${ displaystyle p}$ и враг с вероятностью ${ displaystyle 1-p}$ . Их выигрыш от принятия составляет ${ displaystyle 2p-1}$ , поэтому они принимают, если и только если ${ displaystyle p geq 1/2}$ . Итак, это PBE (лучший ответ как для отправителя, так и для получателя), если и только если априорная вероятность быть другом удовлетворяет ${ displaystyle p geq 1/2}$ .
Стратегия отправителя: никогда не отдавать. Здесь убеждения получателя при получении подарка могут быть произвольными, поскольку получение подарка - это событие с вероятностью 0, поэтому правило Байеса не применяется. Например, предположим, что при получении подарка получатель считает, что отправитель является другом с вероятностью 0,2 (или любым другим числом меньше 0,5). Стратегия получателя: отклонить. Это PBE независимо от априорной вероятности. И отправитель, и получатель получают ожидаемую выплату 0, и ни один из них не может улучшить ожидаемую выплату отклонением.

Подвести итоги:

Если ${ displaystyle p geq 1/2}$ , то есть два PBE: либо отправитель всегда дает, а получатель всегда принимает, либо отправитель всегда не дает, а получатель всегда отклоняет.
Если ${ displaystyle p <1/2}$ , то есть только один PBE: отправитель всегда не дает, а получатель всегда отклоняет. Этот PBE не Парето эффективный, но это неизбежно, поскольку отправитель не может достоверно указать свой тип.

Подарочная игра 2

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

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

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

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

Стратегия отправителя: всегда отдавать. Убеждения получателя не обновляются: они по-прежнему верят в априорную вероятность, что отправитель с вероятностью друг ${ displaystyle p}$ и враг с вероятностью ${ displaystyle 1-p}$ . Их выигрыш от принятия всегда выше, чем от отказа, поэтому они соглашаются (независимо от значения ${ displaystyle p}$ ). Это PBE - это лучший ответ как для отправителя, так и для получателя.
Стратегия отправителя: никогда не отдавать. Предположим, что при получении подарка получатель верит, что отправитель - друг с вероятностью ${ displaystyle q}$ , где ${ displaystyle q}$ любое число в ${ displaystyle [0,1]}$ . Вне зависимости от ${ displaystyle q}$ , оптимальная стратегия получателя: принять. Это НЕ PBE, поскольку отправитель может повысить свой выигрыш с 0 до 1, сделав подарок.
Стратегия отправителя: никогда не отдавать, а стратегия получателя: отклонять. Это НЕ 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. Обозначим через ${ displaystyle { hat {c}}}$ пороговая стоимость обоих игроков в день 1 (так что в день 1 каждый игрок строит, если и только если их стоимость не превышает ${ displaystyle { hat {c}}}$ ). Вычислять ${ displaystyle { hat {c}}}$ , мы работаем в обратном направлении и анализируем действия игроков в день 2. Их действия зависят от истории (= два действия в день 1), и есть три варианта:

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

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

Прыжковые торги

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

Смотрите также

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

использованная литература

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

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

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

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

[1]

[2]

[3]

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