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

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

В теории игр идеальное байесовское равновесие (PBE) — это решение с байесовской вероятностью для пошаговой игры с неполной информацией. Точнее, это концепция равновесия , которая использует байесовское обновление для описания поведения игрока в динамических играх с неполной информацией . Совершенное байесовское равновесие используется для определения исхода игр, в которых игроки ходят по очереди, но не уверены в «типе» своего противника, что происходит, когда игроки не знают предпочтений своего противника между отдельными ходами. Классическим примером динамической игры с типами является военная игра, в которой игрок не уверен, является ли его противник рисковым типом « ястреб » или пацифистским типом « голубь ». Совершенные байесовские равновесия — это уточнение байесовского равновесия Нэша (BNE), которое представляет собой концепцию решения с байесовской вероятностью для непошаговых игр.

Любое идеальное байесовское равновесие состоит из двух компонентов – стратегии и убеждений :

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

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

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

Совершенное байесовское равновесие всегда является равновесием Нэша.

равновесия

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

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

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

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

Равновесие 1. Отправитель: Не давать , независимо от того, относятся ли они к типу друга или врага. Получатель: Не принимать , полагая, что Вероятность(Друг|Не давать) = p и Вероятность(Друг|Отдать) = x, выбирая значение $x\leq .5.$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Еще примеры

Дополнительные примеры см. в разделе «сигнализация game#Examples» . См. также дополнительные примеры. Лориенте и Диес (2023) недавно применили эту концепцию в покере.

PBE в многоэтапных играх

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

Повторяющаяся игра на общественное благо

	Строить	Не
Строить	1-С1, 1-С2	1-С1, 1
Не	1, 1-С2	0,0
Игра «Общественное благо»

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

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

Теперь предположим, что эта игра повторяется два раза. Эти две игры независимы, т. е. каждый день игроки одновременно решают, строить ли общественное благо в этот день, получать выигрыш 1, если товар построен в этот день, и оплачивать его стоимость, если они построили в этот день. Единственная связь между играми заключается в том, что, играя в первый день, игроки могут раскрыть некоторую информацию о своих расходах, и эта информация может повлиять на игру во второй день.

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

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

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

Скачки ставок

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

См. также

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