Введение
Концепция решения в теории игр
В теории игр, совершенное байесовское равновесие (PBE) – это решение с использованием байесовской вероятности для игры с последовательными ходами и неполной информацией. Более конкретно, это концепция равновесия, использующая байесовское обновление для описания поведения игроков в динамических играх с неполной информацией. Совершенные байесовские равновесия используются для определения исхода игр, где игроки делают ходы по очереди, но не уверены в "типе" своего оппонента, что происходит, когда игроки не знают предпочтения оппонента между отдельными ходами. Классическим примером динамической игры с типами является военная игра, где игрок не знает, является ли его противник склонным к риску "ястребом" или пацифистом "голубим". Совершенные байесовские равновесия являются уточнением байесовского равновесия Нэша (BNE), которое представляет собой концепцию решения с использованием байесовской вероятности для игр без последовательных ходов. Любое совершенное байесовское равновесие состоит из двух компонентов: стратегий и убеждений. Стратегия игрока в заданном информационном множестве определяет его выбор действия в этом множестве, который может зависеть от истории (действий, предпринятых ранее в игре). Это аналогично последовательной игре. Убеждение игрока в заданном информационном множестве определяет, какой узел в этом множестве, по его мнению, был достигнут в игре. Убеждение может быть распределением вероятностей по узлам в информационном множестве и, как правило, является распределением вероятностей по возможным типам других игроков. Формально, система убеждений – это назначение вероятностей каждому узлу в игре таким образом, чтобы сумма вероятностей в любом информационном множестве равнялась 1. Стратегии и убеждения также должны удовлетворять следующим условиям: Последовательная рациональность: каждая стратегия должна быть оптимальной в ожидаемом значении, учитывая убеждения. Согласованность: каждое убеждение должно обновляться в соответствии со стратегиями равновесия, наблюдаемыми действиями и правилом Байеса на каждом пути, достигнутом в равновесии с положительной вероятностью. На путях с нулевой вероятностью, известных как внеравновесные пути, убеждения должны быть определены, но могут быть произвольными. Совершенное байесовское равновесие всегда является равновесием Нэша.
The strategy of a player in a given information set specifies his choice of action in that information set, which may depend on the history (on actions taken previously in the game). This is similar to a sequential game. The belief of a player in a given information set determines what node in that information set he believes the game has reached. The belief may be a probability distribution over the nodes in the information set, and is typically a probability distribution over the possible types of the other players. Formally, a belief system is an assignment of probabilities to every node in the game such that the sum of probabilities in any information set is 1. The strategies and beliefs also must satisfy the following conditions:
Sequential rationality: each strategy should be optimal in expectation, given the beliefs. Consistency: each belief should be updated according to the equilibrium strategies, the observed actions, and Bayes' rule on every path reached in equilibrium with positive probability. On paths of zero probability, known as off equilibrium paths, the beliefs must be specified but can be arbitrary. A perfect Bayesian equilibrium is always a Nash equilibrium.
Игра подарков 2
В следующем примере набор ПБЭ строго меньше, чем набор SPE и BNE. Это вариант вышеуказанной игры с дарами, с следующим изменением в полезности получателя: если отправитель – друг, то полезность получателя равна 1 (если он принимает) или 0 (если он отклоняет). Если отправитель – враг, то полезность получателя равна 0 (если он принимает) или 1 (если он отклоняет). Обратите внимание, что в этом варианте принятие является слабо доминирующей стратегией для получателя. Подобно примеру 1, разделяющего равновесия нет. Давайте рассмотрим следующие потенциальные равновесия объединения: стратегия отправителя: всегда дарить. Убеждения получателя не обновляются: они по-прежнему верят в априорную вероятность, что отправитель – друг с вероятностью, а враг – с вероятностью. Их выигрыш от принятия всегда выше, чем от отклонения, поэтому они принимают (независимо от значения). Это ПБЭ – это лучший ответ для обоих, отправителя и получателя. Стратегия отправителя: никогда не дарить. Предположим, что убеждения получателя при получении дара таковы, что отправитель – друг с вероятностью, где – любое число в. Независимо от, оптимальная стратегия получателя: принять. Это НЕ ПБЭ, так как отправитель может увеличить свою отдачу с 0 до 1, даря дар. Стратегия отправителя: никогда не дарить, а стратегия получателя: отклонять. Это НЕ ПБЭ, поскольку для любого убеждения получателя отклонение не является лучшим ответом. Обратите внимание, что вариант 3 – это равновесие Нэша! Если мы игнорируем убеждения, то отклонение можно считать лучшим ответом для получателя, поскольку это не влияет на его выигрыш (поскольку подарка в любом случае нет). Более того, вариант 3 – это даже SPE, так как единственная подигра здесь – это вся игра! Такие маловероятные равновесия могут возникать также в играх с полной информацией, но они могут быть устранены путем применения совершенного подигре равновесия Нэша. Однако, байесовские игры часто содержат не-одиночные информационные множества, и поскольку подигры должны содержать полные информационные множества, иногда есть только одна подигра – вся игра, и поэтому каждое равновесие Нэша является тривиально совершенным подигре. Даже если игра имеет более одной подигры, неспособность совершенства подигры разрезать информационные множества может привести к тому, что маловероятные равновесия не будут устранены. Подводя итог: в этом варианте игры с дарами есть два SPE: либо отправитель всегда дарит, а получатель всегда принимает, либо отправитель всегда не дарит, а получатель всегда отклоняет. Из них только первый является ПБЭ; другой не является ПБЭ, поскольку он не может быть поддержан какой-либо системой убеждений.
If the sender is a friend, then the receiver's utility is 1 (if they accept) or 0 (if they reject). If the sender is an enemy, then the receiver's utility is 0 (if they accept) or 1 (if they reject). Note that in this variant, accepting is a weakly dominant strategy for the receiver. Similarly to example 1, there is no separating equilibrium. Let's look at the following potential pooling equilibria:
The sender's strategy is: always give. The receiver's beliefs are not updated: they still believe in the a priori probability, that the sender is a friend with probability and an enemy with probability Their payoff from accepting is always higher than from rejecting, so they accept (regardless of the value of ). This is a PBE it is a best response for both sender and receiver. The sender's strategy is: never give. Suppose the receiver's beliefs when receiving a gift is that the sender is a friend with probability , where is any number in Regardless of , the receiver's optimal strategy is: accept. This is NOT a PBE, since the sender can improve their payoff from 0 to 1 by giving a gift. The sender's strategy is: never give, and the receiver's strategy is: reject. This is NOT a PBE, since for any belief of the receiver, rejecting is not a best response. Note that option 3 is a Nash equilibrium! If we ignore beliefs, then rejecting can be considered a best response for the receiver, since it does not affect their payoff (since there is no gift anyway). Moreover, option 3 is even a SPE, since the only subgame here is the entire game! Such implausible equilibria might arise also in games with complete information, but they may be eliminated by applying subgame perfect Nash equilibrium. However, Bayesian games often contain non singleton information sets and since subgames must contain complete information sets, sometimes there is only one subgame—the entire game—and so every Nash equilibrium is trivially subgame perfect. Even if a game does have more than one subgame, the inability of subgame perfection to cut through information sets can result in implausible equilibria not being eliminated. To summarize: in this variant of the gift game, there are two SPEs: either the sender always gives and the receiver always accepts, or the sender always does not give and the receiver always rejects. From these, only the first one is a PBE; the other is not a PBE since it cannot be supported by any belief system.
Еще примеры
Для получения дополнительных примеров см. раздел «Игры сигналов»#Примеры. Также см. для получения дополнительных примеров. Недавнее применение этой концепции в покере представлено Лориенте и Диесом (2023).
PBE в многоступенчатых играх
Многоступенчатая игра — это последовательность игр, проводимых одновременно одна за другой. Эти игры могут быть одинаковыми (как в повторяющихся играх) или различными.
Повторная охота на общественное благо
Следующая игра является простым представлением проблемы безбилетника. В игре участвуют два игрока, каждый из которых может построить общественное благо или не строить его. Каждый игрок получает выгоду в 1, если общественное благо построено, и 0, если нет; кроме того, если игрок строит общественное благо, он должен понести затраты в размере . Затраты являются частной информацией – каждый игрок знает свои собственные затраты, но не знает затраты другого игрока. Известно лишь, что каждая из этих затрат выбирается случайным образом и независимо из некоторого распределения вероятностей. Это делает игру байесовской. В одноэтапной игре каждый игрок строит, если и только если его затраты меньше ожидаемой выгоды от строительства. Ожидаемая выгода от строительства равна 1, умноженной на вероятность того, что другой игрок НЕ будет строить. В равновесии для каждого игрока существует пороговая стоимость , такая что игрок вносит вклад, если и только если его затраты меньше . Эта пороговая стоимость может быть рассчитана на основе распределения вероятностей затрат игроков. Например, если затраты распределены равномерно на [0, 1], то существует симметричное равновесие, в котором пороговая стоимость для обоих игроков равна 2/3. Это означает, что игрок, чьи затраты находятся между 2/3 и 1, не будет вносить вклад, даже если его затраты ниже выгоды, из-за возможности того, что другой игрок внесет вклад. Теперь предположим, что эта игра повторяется дважды. Два этапа игры независимы, то есть каждый день игроки одновременно решают, строить ли общественное благо в этот день, получают выигрыш в 1, если благо построено в этот день, и несут свои затраты, если они построили его в этот день. Единственная связь между этапами игры заключается в том, что, играя в первый день, игроки могут раскрыть некоторую информацию о своих затратах, и эта информация может повлиять на игру во второй день. Мы ищем симметричное совершенное подыгровое равновесие (ПИР). Обозначим через пороговую стоимость для обоих игроков в первый день (то есть в первый день каждый игрок строит, если и только если его затраты не превышают ). Чтобы рассчитать , мы действуем в обратном порядке и анализируем действия игроков во второй день. Их действия зависят от истории (= два действия в первый день), и есть три варианта:
В первый день ни один игрок не построил. Теперь оба игрока знают, что затраты их оппонента выше . Они соответствующим образом обновляют свои убеждения и приходят к выводу, что вероятность того, что их оппонент построит во второй день, меньше. Следовательно, они увеличивают свою пороговую стоимость, и пороговая стоимость во второй день равна . В первый день оба игрока построили. Теперь оба игрока знают, что затраты их оппонента ниже . Они соответствующим образом обновляют свои убеждения и приходят к выводу, что вероятность того, что их оппонент построит во второй день, больше. Следовательно, они снижают свою пороговую стоимость, и пороговая стоимость во второй день равна . В первый день построил ровно один игрок; предположим, что это игрок 1. Теперь известно, что затраты игрока 1 ниже , а затраты игрока 2 выше . Существует равновесие, в котором действия во второй день идентичны действиям в первый день: игрок 1 строит, а игрок 2 не строит. Можно рассчитать ожидаемую выгоду "порогового игрока" (игрока с точной стоимостью ) в каждой из этих ситуаций. Поскольку пороговому игроку должно быть безразлично, вносить вклад или нет, можно рассчитать пороговую стоимость для первого дня. Оказывается, что этот порог ниже , чем порог в одноэтапной игре. Это означает, что в двухэтапной игре игроки менее склонны строить, чем в одноэтапной игре. Интуитивно, причина в том, что, когда игрок не вносит вклад в первый день, он заставляет другого игрока поверить, что его затраты высоки, и это делает другого игрока более склонным к внесению вклада во второй день.
In day 1, no player built. So now both players know that their opponent's cost is above They update their belief accordingly, and conclude that there is a smaller chance that their opponent will build in day 2. Therefore, they increase their threshold cost, and the threshold cost in day 2 is In day 1, both players built. So now both players know that their opponent's cost is below They update their belief accordingly, and conclude that there is a larger chance that their opponent will build in day 2. Therefore, they decrease their threshold cost, and the threshold cost in day 2 is In day 1, exactly one player built; suppose it is player 1. So now, it is known that the cost of player 1 is below and the cost of player 2 is above There is an equilibrium in which the actions in day 2 are identical to the actions in day 1 player 1 builds and player 2 does not build. It is possible to calculate the expected payoff of the "threshold player" (a player with cost exactly ) in each of these situations. Since the threshold player should be indifferent between contributing and not contributing, it is possible to calculate the day 1 threshold cost It turns out that this threshold is lower than the threshold in the one stage game. This means that, in a two stage game, the players are less willing to build than in the one stage game. Intuitively, the reason is that, when a player does not contribute in the first day, they make the other player believe their cost is high, and this makes the other player more willing to contribute in the second day.
Приостановка торгов
На открытом аукционе в английском формате участники могут повышать текущую цену небольшими шагами (например, на 1 доллар за раз). Однако часто встречается стратегия повышения ставок с большим шагом – некоторые участники повышают текущую цену значительно больше минимального прироста. Одно из объяснений этого заключается в том, что это служит сигналом для других участников торгов. Существует PBE (последовательная равновесная стратегия), в которой каждый участник делает большой шаг повышения ставки тогда и только тогда, когда его оценка превышает определенный порог. См. Jump bidding#сигнализация.