Back

ⓘ Bayesian game




                                     

ⓘ Bayesian game

In game theory, a Bayesian game is a game in which players have incomplete information about the other players. For example, a player may not know the exact payoff functions of the other players, but instead have beliefs about these payoff functions. These beliefs are represented by a probability distribution over the possible payoff functions.

John C. Harsanyi describes a Bayesian game in the following way. Each player in the game is associated with a set of types, with each type in the set corresponding to a possible payoff function for that player. In addition to the actual players in the game, there is a special player called Nature. Nature randomly chooses a type for each player according to a probability distribution across the players type spaces. This probability distribution is known by all players the "common prior assumption". This modeling approach transforms games of incomplete information into games of imperfect information in which the history of play within the game is not known to all players.

Incompleteness of information means that at least one player is unsure of the type and therefore the payoff function of another player. Such games are called Bayesian because players are typically assumed to update their beliefs according to Bayes rule. In particular, the belief a player holds about another players type might change according to his own type.

                                     

1. Specification of games

In a Bayesian game, one has to specify type spaces, strategy spaces, payoff functions and prior beliefs. A strategy for a player is a complete plan of action that covers every contingency that might arise for every type that player might be. A type space for a player is just the set of all possible types of that player. The beliefs of a player describe the uncertainty of that player about the types of the other players. Each belief is the probability of the other players having particular types, given the type of the player with that belief. A payoff function is a function of strategy profiles and types.

Formally, such a game is given by: G = ⟨ N, Ω, p, ⟨ A i, u i, T i, τ i ⟩ i ∈ N ⟩ {\displaystyle G=\langle N,\Omega,p,\langle A_{i},u_{i},T_{i},\tau _{i}\rangle _{i\in N}\rangle }, where

  • T i {\displaystyle T_{i}} is the set of types for player i {\displaystyle i}. Given the state, the type of player i {\displaystyle i} is given by the function τ i: Ω → T i {\displaystyle \tau _{i}\colon \Omega \rightarrow T_{i}}. So, for each state of nature, the game will have different types of players.
  • Ω {\displaystyle \Omega } is the set of states of nature.
  • A i {\displaystyle A_{i}} is the set of actions for player i {\displaystyle i}. Let A = A 1 × A 2 × ⋯ × A N {\displaystyle A=A_{1}\times A_{2}\times \dotsb \times A_{N}}.
  • u i: T i × A → R {\displaystyle u_{i}\colon T_{i}\times A\rightarrow \mathbb {R} } is the payoff function for player i {\displaystyle i}.
  • p {\displaystyle p} is the prior probability distribution over Ω {\displaystyle \Omega }.
  • N {\displaystyle N} is the set of players.

A pure strategy for player i {\displaystyle i} is a function s i: T i → A i {\displaystyle s_{i}\colon T_{i}\rightarrow A_{i}}. A mixed strategy for player i {\displaystyle i} is a function σ i: T i → Δ A i {\displaystyle \sigma _{i}\colon T_{i}\rightarrow \Delta A_{i}}, where Δ A i {\displaystyle \Delta A_{i}} is the set of all probability distributions on A i {\displaystyle A_{i}}. Note that a strategy for any given player only depends on his own type.

A strategy profile σ {\displaystyle \sigma } is a strategy for each player. A strategy profile determines expected payoffs for each player, where the expectation is taken over both the set of states of nature and hence profiles of types with respect to beliefs p {\displaystyle p}, and the randomization over actions implied by any mixed strategies in the profile σ {\displaystyle \sigma }.

                                     

2. Bayesian Nash equilibrium

In a non-Bayesian game, a strategy profile is a Nash equilibrium if every strategy in that profile is a best response to every other strategy in the profile; i.e., there is no strategy that a player could play that would yield a higher payoff, given all the strategies played by the other players.

An analogous concept can be defined for a Bayesian game, the difference being that every players strategy maximizes his expected payoff given his beliefs about the state of nature. A players beliefs about the state of nature are formed by conditioning the prior probabilities p {\displaystyle p} on his own type according to Bayes rule.

A Bayesian Nash equilibrium is defined as a strategy profile that maximizes the expected payoff for each player given their beliefs and given the strategies played by the other players. That is, a strategy profile σ {\displaystyle \sigma } is a Bayesian Nash equilibrium if and only if for every player i, {\displaystyle i,} keeping the strategies of every other player fixed, strategy σ i {\displaystyle \sigma _{i}} maximizes the expected payoff of player i {\displaystyle i} according to his beliefs.

                                     

3.1. Variants of Bayesian equilibrium Perfect Bayesian equilibrium

Bayesian Nash equilibrium can result in implausible equilibria in dynamic games, where players move sequentially rather than simultaneously. As in games of complete information, these can arise via non-credible strategies off the equilibrium path. In games of incomplete information there is also the additional possibility of non-credible beliefs.

To deal with these issues, Perfect Bayesian equilibrium, in the spirit of subgame perfect equilibrium requires that, starting from any information set, subsequent play be optimal. Furthermore, it requires that beliefs be updated consistently with Bayes rule on every path of play that occurs with positive probability.

                                     

3.2. Variants of Bayesian equilibrium Stochastic Bayesian games

The definition of Bayesian games has been combined with stochastic games to allow for environment states e.g. physical world states and stochastic transitions between states. The resulting "stochastic Bayesian game" model is solved via a recursive combination of the Bayesian Nash equilibrium and the Bellman optimality equation.

                                     

3.3. Variants of Bayesian equilibrium Incomplete information over collective agency

The definition of Bayesian games and Bayesian equilibrium has been extended to deal with collective agency. One approach is to continue to treat individual players as reasoning in isolation, but to allow them, with some probability, to reason from the perspective of a collective. Another approach is to assume that players within any collective agent know that the agent exists, but that other players do not know this, although they suspect it with some probability. For example, Alice and Bob may sometimes optimize as individuals and sometimes collude as a team, depending on the state of nature, but other players may not know which of these is the case.

                                     

4.1. Example Sheriffs Dilemma

A sheriff faces an armed suspect. Both must simultaneously decide whether to shoot the other or not.

The suspect can either be of type "criminal" or type "civilian". The sheriff has only one type. The suspect knows its type and the Sheriffs type, but the Sheriff does not know the suspects type. Thus, there is incomplete information because the suspect has private information, making it a Bayesian game. There is a probability p that the suspect is a criminal, and a probability 1-p that the suspect is a civilian; both players are aware of this probability common prior assumption, which can be converted into a complete-information game with imperfect information.

The sheriff would rather defend himself and shoot if the suspect shoots, or not shoot if the suspect does not even if the suspect is a criminal. The suspect would rather shoot if he is a criminal, even if the sheriff does not shoot, but would rather not shoot if he is a civilian, even if the sheriff shoots. Thus, the payoff matrix of this Normal-form game for both players depends on the type of the suspect. It is assumed that payoffs are given as follows:

If both players are rational and both know that both players are rational and everything that is known by any player is known to be known by every player i.e. player 1 knows player 2 knows that player 1 is rational and player 2 knows this, etc. ad infinitum – common knowledge, play in the game will be as follows according to perfect Bayesian equilibrium:

When the type is "civilian", the dominant strategy for the suspect is not to shoot, and when the type is "criminal", the dominant strategy for the suspect is to shoot; alternative strictly dominated strategy can thus be removed. Given this, if the sheriff shoots, he will have a payoff of 0 with probability p and a payoff of -1 with probability 1-p, i.e. an expected payoff of p-1; if the sheriff does not shoot, he will have a payoff of -2 with probability p and a payoff of 0 with probability 1-p, i.e. an expected payoff of -2p. Thus, the Sheriff will always shoot if p-1 > -2p, i.e. when p > 1/3.



                                     
  • experimental design Bayesian Filtering Library Bayesian game Bayesian inference Bayesian inference in phylogeny Bayesian information criterion Bayesian linear regression
  • Bayesian probability is an interpretation of the concept of probability, in which, instead of frequency or propensity of some phenomenon, probability is
  • In game theory, a Perfect Bayesian Equilibrium PBE is an equilibrium concept relevant for dynamic games with incomplete information sequential Bayesian
  • In game theory, a signaling game is a simple type of a dynamic Bayesian game It is a game with two players, called the sender S and the receiver R
  • In game theory, Bayesian regret is the average difference between the utility of a strategy and an ideal utility where desired outcomes are maximized
  • these solutions turn towards Bayesian Nash Equilibria since games with incomplete information become Bayesian games. In a game of complete information, the
  • In physics and the philosophy of physics, quantum Bayesianism abbreviated QBism, pronounced cubism is an interpretation of quantum mechanics that
  • The Bayesian - Nash revelation - principle says that every social - choice function that can be implemented in Bayesian - Nash equilibrium Bayesian game i.e
  • Bayesian programming is a formalism and a methodology for having a technique to specify probabilistic models and solve problems when less than the necessary
  • Quantum pseudo - telepathy is the fact that in certain Bayesian games with asymmetric information, players who have access to a shared physical system in