Bayesian game

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:[2] ${\displaystyle G=\langle N,\Omega ,p,\langle A_{i},u_{i},T_{i},\tau _{i}\rangle _{i\in N}\rangle }$, where

1. ${\displaystyle N}$ is the set of players.
2. ${\displaystyle \Omega }$ is the set of states of nature.
3. ${\displaystyle A_{i}}$ is the set of actions for player ${\displaystyle i}$. Let ${\displaystyle A=A_{1}\times A_{2}\times \dotsb \times A_{N}}$.
4. ${\displaystyle T_{i}}$ is the set of types for player ${\displaystyle i}$. Given the state, the type of player ${\displaystyle i}$ is given by the function ${\displaystyle \tau _{i}\colon \Omega \rightarrow T_{i}}$. So, for each state of nature, the game will have different types of players.
5. ${\displaystyle u_{i}\colon T_{i}\times A\rightarrow \mathbb {R} }$ is the payoff function for player ${\displaystyle i}$.
6. ${\displaystyle p}$ is the (prior) probability distribution over ${\displaystyle \Omega }$.

A pure strategy for player ${\displaystyle i}$ is a function ${\displaystyle s_{i}\colon T_{i}\rightarrow A_{i}}$. A mixed strategy for player ${\displaystyle i}$ is a function ${\displaystyle \sigma _{i}\colon T_{i}\rightarrow \Delta A_{i}}$, where ${\displaystyle \Delta A_{i}}$ is the set of all probability distributions on ${\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 ${\displaystyle p}$, and the randomization over actions implied by any mixed strategies in the profile ${\displaystyle \sigma }$.

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 player's strategy maximizes his expected payoff given his beliefs about the state of nature. A player's beliefs about the state of nature are formed by conditioning the prior probabilities ${\displaystyle p}$ on his own type according to Bayes' rule.

A Bayesian Nash equilibrium (BNE) 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 ${\displaystyle i,}$ keeping the strategies of every other player fixed, strategy ${\displaystyle \sigma _{i}}$ maximizes the expected payoff of player ${\displaystyle i}$ according to his beliefs.[2]

For finite Bayesian games, i.e., both the action and the type space are finite, there are two equivalent representations. The first is called the agent-form game (see Theorem 9.51 of the Game Theory book[3]) which expands the number of players from ${\displaystyle |N|}$ to ${\textstyle \sum _{i=1}^{|N|}|T_{i}|}$, i.e., every type of each player becomes a player. The second is called the induced normal form (see Section 6.3.3 of Multiagent Systems[4]) which still has ${\displaystyle |N|}$ players yet expands the number of each player i's actions from ${\displaystyle |A_{i}|}$ to ${\textstyle |A_{i}|^{|T_{i}|}}$, i.e., the pure policy is a combination of actions the player should take for different types. We can compute Nash Equilibrium (NE) in these two equivalent representations and then recover the BNE from the NE.

• If we further consider two players with a zero-sum objective function, then we can form a linear program to compute BNE.[5]
• If we further consider two players with a general-sum objective function, then we can form a math program of a bi-linear objective function and linear constrains to compute BNE (see Theorem 1 of the paper[6]). Although no nonlinear solver can guarantee the global optimal, we can check whether a BNE is achieved by looking at the value of the program's objective function, which should equal 0 at a BNE. Thus, the value closer to 0 represents a smaller error, which can serve as a metric of the solution quality.

• Bayesian-optimal mechanism
• Bayesian-optimal pricing
• Bayesian programming
• Bayesian inference

• Gibbons, Robert (1992). Game Theory for Applied Economists. Princeton University Press. pp. 144–52.
• Levin, Jonathan (2002). "Games with Incomplete Information" (PDF). Retrieved 25 August 2016.