Perfect Bayesian equilibrium

Last updated
Perfect Bayesian Equilibrium
Solution concept in game theory
Relationship
Subset of Bayesian Nash equilibrium
Significance
Proposed byCho and Kreps[ citation needed ]
Used forDynamic Bayesian games
Example signaling game

In game theory, a Perfect Bayesian Equilibrium (PBE) is a solution with Bayesian probability to a turn-based game with incomplete information. More specifically, it is an equilibrium concept that uses Bayesian updating to describe player behavior in dynamic games with incomplete information. Perfect Bayesian equilibria are used to solve the outcome of games where players take turns but are unsure of the "type" of their opponent, which occurs when players don't know their opponent's preference between individual moves. A classic example of a dynamic game with types is a war game where the player is unsure whether their opponent is a risk-taking "hawk" type or a pacifistic "dove" type. Perfect Bayesian Equilibria are a refinement of Bayesian Nash equilibrium (BNE), which is a solution concept with Bayesian probability for non-turn-based games.

Contents

Any perfect Bayesian equilibrium has two components -- strategies and beliefs:

The strategies and beliefs also must satisfy the following conditions:

A perfect Bayesian equilibrium is always a Nash equilibrium.

Examples of perfect Bayesian equilibria

Gift game 1

Consider the following game:

For any value of Equilibrium 1 exists, a pooling equilibrium in which both types of sender choose the same action:

Equilibrium 1. Sender: Not give, whether they are the friend type or the enemy type. Receiver: Do not accept, with the beliefs that Prob(Friend|Not Give) = p and Prob(Friend|Give) = x, choosing a value

The sender prefers the payoff of 0 from not giving to the payoff of -1 from sending and not being accepted. Thus, Give has zero probability in equilibrium and Bayes's Rule does not restrict the belief Prob(Friend|Give) at all. That belief must be pessimistic enough that the receiver prefers the payoff of 0 from rejecting a gift to the expected payoff of from accepting, so the requirement that the receiver's strategy maximize his expected payoff given his beliefs necessitates that Prob(Friend|Give) On the other hand, Prob(Friend|Not give) = p is required by Bayes's Rule, since both types take that action and it is uninformative about the sender's type.

If , a second pooling equilibrium exists as well as Equilibrium 1, based on different beliefs:

Equilibrium 2. Sender: Give, whether they are the friend type or the enemy type. Receiver: Accept, with the beliefs that Prob(Friend|Give) = p and Prob(Friend|Not give) = x, choosing any value for

The sender prefers the payoff of 1 from giving to the payoff of 0 from not giving, expecting that his gift will be accepted. In equilibrium, Bayes's Rule requires the receiver to have the belief Prob(Friend|Give) = p, since both types take that action and it is uninformative about the sender's type in this equilibrium. The out-of-equilibrium belief does not matter, since the sender would not want to deviate to Not give no matter what response the receiver would have.

Equilibrium 1 is perverse if The game could have so the sender is very likely a friend, but the receiver still would refuse any gift because he thinks enemies are much more likely than friends to give gifts. This shows how pessimistic beliefs can result in an equilibrium bad for both players, one that is not Pareto efficient. These beliefs seem unrealistic, though, and game theorists are often willing to reject some perfect Bayesian equilibria as implausible.

Equilibria 1 and 2 are the only equilibria that might exist, but we can also check for the two potential separating equilibria, in which the two types of sender choose different actions, and see why they do not exist as perfect Bayesian equilibria:

  1. Suppose the sender's strategy is: Give if a friend, Do not give if an enemy. The receiver's beliefs are updated accordingly: if he receives a gift, he believes the sender is a friend; otherwise, he believes the sender is an enemy. Thus, the receiver will respond with Accept. If the receiver chooses Accept, though, the enemy sender will deviate to  Give, to increase his payoff from 0 to 1, so this cannot be an equilibrium.
  2. Suppose the sender's strategy is: Do not give if a friend, Give if an enemy. The receiver's beliefs are updated accordingly: if he receives a gift, he believes the sender is an enemy; otherwise, he believes the sender is a friend. The receiver's best-response strategy is Reject. If the receiver chooses Reject, though, the enemy sender will deviate to  Do not give, to increase his payoff from -1 to 0, so this cannot be an equilibrium.

We conclude that in this game, there is no separating equilibrium.

Gift game 2

In the following example, [1] the set of PBEs is strictly smaller than the set of SPEs and BNEs. It is a variant of the above gift-game, with the following change to the receiver's utility:

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:

  1. 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.
  2. 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.
  3. 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.

More examples

For further examples, see signaling game#Examples. See also [2] for more examples. There is a recent application of this concept in Poker, by Loriente and Diez (2023). [3]

PBE in multi-stage games

A multi-stage game is a sequence of simultaneous games played one after the other. These games may be identical (as in repeated games) or different.

Repeated public-good game

BuildDon't
Build1-C1, 1-C21-C1, 1
Don't1, 1-C20,0
Public good game

The following game [4] :section 6.2 is a simple representation of the free-rider problem. There are two players, each of whom can either build a public good or not build. Each player gains 1 if the public good is built and 0 if not; in addition, if player builds the public good, they have to pay a cost of . The costs are private information - each player knows their own cost but not the other's cost. It is only known that each cost is drawn independently at random from some probability distribution. This makes this game a Bayesian game.

In the one-stage game, each player builds if-and-only-if their cost is smaller than their expected gain from building. The expected gain from building is exactly 1 times the probability that the other player does NOT build. In equilibrium, for every player , there is a threshold cost , such that the player contributes if-and-only-if their cost is less than . This threshold cost can be calculated based on the probability distribution of the players' costs. For example, if the costs are distributed uniformly on , then there is a symmetric equilibrium in which the threshold cost of both players is 2/3. This means that a player whose cost is between 2/3 and 1 will not contribute, even though their cost is below the benefit, because of the possibility that the other player will contribute.

Now, suppose that this game is repeated two times. [4] :section 8.2.3 The two plays are independent, i.e., each day the players decide simultaneously whether to build a public good in that day, get a payoff of 1 if the good is built in that day, and pay their cost if they built in that day. The only connection between the games is that, by playing in the first day, the players may reveal some information about their costs, and this information might affect the play in the second day.

We are looking for a symmetric PBE. Denote by the threshold cost of both players in day 1 (so in day 1, each player builds if-and-only-if their cost is at most ). To calculate , we work backwards and analyze the players' actions in day 2. Their actions depend on the history (= the two actions in day 1), and there are three options:

  1. 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 .
  2. 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 .
  3. 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.

Jump-bidding

In an open-outcry English auction, the bidders can raise the current price in small steps (e.g. in $1 each time). However, often there is jump bidding - some bidders raise the current price much more than the minimal increment. One explanation to this is that it serves as a signal to the other bidders. There is a PBE in which each bidder jumps if-and-only-if their value is above a certain threshold. See Jump bidding#signaling.

See also

Related Research Articles

In game theory, the Nash equilibrium is the most commonly-used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy. The idea of Nash equilibrium dates back to the time of Cournot, who in 1838 applied it to his model of competition in an oligopoly.

<span class="mw-page-title-main">Ultimatum game</span> Game in economic experiments

The ultimatum game is a game that has become a popular instrument of economic experiments. An early description is by Nobel laureate John Harsanyi in 1961. One player, the proposer, is endowed with a sum of money. The proposer is tasked with splitting it with another player, the responder. Once the proposer communicates their decision, the responder may accept it or reject it. If the responder accepts, the money is split per the proposal; if the responder rejects, both players receive nothing. Both players know in advance the consequences of the responder accepting or rejecting the offer.

In game theory, the centipede game, first introduced by Robert Rosenthal in 1981, is an extensive form game in which two players take turns choosing either to take a slightly larger share of an increasing pot, or to pass the pot to the other player. The payoffs are arranged so that if one passes the pot to one's opponent and the opponent takes the pot on the next round, one receives slightly less than if one had taken the pot on this round, but after an additional switch the potential payoff will be higher. Therefore, although at each round a player has an incentive to take the pot, it would be better for them to wait. Although the traditional centipede game had a limit of 100 rounds, any game with this structure but a different number of rounds is called a centipede game.

In game theory, cheap talk is communication between players that does not directly affect the payoffs of the game. Providing and receiving information is free. This is in contrast to signalling, in which sending certain messages may be costly for the sender depending on the state of the world.

<span class="mw-page-title-main">Signaling game</span> Game class in game theory

In game theory, a signaling game is a simple type of a dynamic Bayesian game.

In game theory, a move, action, or play is any one of the options which a player can choose in a setting where the optimal outcome depends not only on their own actions but on the actions of others. The discipline mainly concerns the action of a player in a game affecting the behavior or actions of other players. Some examples of "games" include chess, bridge, poker, monopoly, diplomacy or battleship.

<span class="mw-page-title-main">Solution concept</span> Formal rule for predicting how a game will be played

In game theory, a solution concept is a formal rule for predicting how a game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players and, therefore, the result of the game. The most commonly used solution concepts are equilibrium concepts, most famously Nash equilibrium.

In game theory, an extensive-form game is a specification of a game allowing for the explicit representation of a number of key aspects, like the sequencing of players' possible moves, their choices at every decision point, the information each player has about the other player's moves when they make a decision, and their payoffs for all possible game outcomes. Extensive-form games also allow for the representation of incomplete information in the form of chance events modeled as "moves by nature". Extensive-form representations differ from normal-form in that they provide a more complete description of the game in question, whereas normal-form simply boils down the game into a payoff matrix.

In game theory, a Bayesian game is a strategic decision-making model which assumes players have incomplete information. Players hold private information relevant to the game, meaning that the payoffs are not common knowledge. Bayesian games model the outcome of player interactions using aspects of Bayesian probability. They are notable because they allowed, for the first time in game theory, for the specification of the solutions to games with incomplete information.

Backward induction is the process of determining a sequence of optimal choices by reasoning from the endpoint of a problem or situation back to its beginning using individual events or actions. Backward induction involves examining the final point in a series of decisions and identifying the optimal process or action required to arrive at that point. This process continues backward until the best action for every possible point along the sequence is determined. Backward induction was first utilized in 1875 by Arthur Cayley, who discovered the method while attempting to solve the secretary problem.

In game theory, trembling hand perfect equilibrium is a type of refinement of a Nash equilibrium that was first proposed by Reinhard Selten. A trembling hand perfect equilibrium is an equilibrium that takes the possibility of off-the-equilibrium play into account by assuming that the players, through a "slip of the hand" or tremble, may choose unintended strategies, albeit with negligible probability.

In game theory, folk theorems are a class of theorems describing an abundance of Nash equilibrium payoff profiles in repeated games. The original Folk Theorem concerned the payoffs of all the Nash equilibria of an infinitely repeated game. This result was called the Folk Theorem because it was widely known among game theorists in the 1950s, even though no one had published it. Friedman's (1971) Theorem concerns the payoffs of certain subgame-perfect Nash equilibria (SPE) of an infinitely repeated game, and so strengthens the original Folk Theorem by using a stronger equilibrium concept: subgame-perfect Nash equilibria rather than Nash equilibria.

In game theory, a repeated game is an extensive form game that consists of a number of repetitions of some base game. The stage game is usually one of the well-studied 2-person games. Repeated games capture the idea that a player will have to take into account the impact of their current action on the future actions of other players; this impact is sometimes called their reputation. Single stage game or single shot game are names for non-repeated games.

In game theory, a correlated equilibrium is a solution concept that is more general than the well known Nash equilibrium. It was first discussed by mathematician Robert Aumann in 1974. The idea is that each player chooses their action according to their private observation of the value of the same public signal. A strategy assigns an action to every possible observation a player can make. If no player would want to deviate from their strategy, the distribution from which the signals are drawn is called a correlated equilibrium.

In game theory, the purification theorem was contributed by Nobel laureate John Harsanyi in 1973. The theorem justifies a puzzling aspect of mixed strategy Nash equilibria: each player is wholly indifferent between each of the actions he puts non-zero weight on, yet he mixes them so as to make every other player also indifferent.

Sequential equilibrium is a refinement of Nash equilibrium for extensive form games due to David M. Kreps and Robert Wilson. A sequential equilibrium specifies not only a strategy for each of the players but also a belief for each of the players. A belief gives, for each information set of the game belonging to the player, a probability distribution on the nodes in the information set. A profile of strategies and beliefs is called an assessment for the game. Informally speaking, an assessment is a perfect Bayesian equilibrium if its strategies are sensible given its beliefs and its beliefs are confirmed on the outcome path given by its strategies. The definition of sequential equilibrium further requires that there be arbitrarily small perturbations of beliefs and associated strategies with the same property.

In game theory, a subgame perfect equilibrium is a refinement of a Nash equilibrium used in dynamic games. A strategy profile is a subgame perfect equilibrium if it represents a Nash equilibrium of every subgame of the original game. Informally, this means that at any point in the game, the players' behavior from that point onward should represent a Nash equilibrium of the continuation game, no matter what happened before. Every finite extensive game with perfect recall has a subgame perfect equilibrium. Perfect recall is a term introduced by Harold W. Kuhn in 1953 and "equivalent to the assertion that each player is allowed by the rules of the game to remember everything he knew at previous moves and all of his choices at those moves".

Quantal response equilibrium (QRE) is a solution concept in game theory. First introduced by Richard McKelvey and Thomas Palfrey, it provides an equilibrium notion with bounded rationality. QRE is not an equilibrium refinement, and it can give significantly different results from Nash equilibrium. QRE is only defined for games with discrete strategies, although there are continuous-strategy analogues.

The intuitive criterion is a technique for equilibrium refinement in signaling games. It aims to reduce possible outcome scenarios by restricting the possible sender types to types who could obtain higher utility levels by deviating to off-the-equilibrium messages, and to types for which the off-the-equilibrium message is not equilibrium dominated.

The Divinity Criterion or Divine Equilibrium or Universal Divinity is a refinement of Perfect Bayesian equilibrium in a signaling game proposed by Banks and Sobel (1987). One of the most widely applied refinement is the D1-Criterion.

References

  1. James Peck. "Perfect Bayesian Equilibrium" (PDF). Ohio State University. Retrieved 6 December 2021.
  2. Zack Grossman. "Perfect Bayesian Equilibrium" (PDF). University of California. Retrieved 2 September 2016.
  3. Loriente, Martín Iñaki & Diez, Juan Cruz (2023). "Perfect Bayesian Equilibrium in Kuhn Poker". Universidad de San Andres.
  4. 1 2 Fudenberg, Drew; Tirole, Jean (1991). Game Theory. Cambridge, Massachusetts: MIT Press. ISBN   9780262061414. Book preview.