| $\mathsf{FF}$ | $\mathsf{FO}$ | $\mathsf{OF}$ | $\mathsf{OO}$ | |||||
| $\mathsf{F}$ | $2$ | $\frac{1}{2}$ | $1$ | $\frac{2}{3}$ | $1$ | $0$ | $1$ | $1$ |
| $\mathsf{O}$ | $0$ | $\frac{1}{2}$ | $\frac{1}{2}$ | $0$ | $\frac{1}{2}$ | $\frac{3}{2}$ | $1$ | $1$ |
8 Bayesian Games
So far, we have restricted attention to simultaneous move games where players have perfect knowledge of the utility functions of other players. This is not always true in practice. In this section, we will consider games where players have uncertainty about the utility functions of other players, and this uncertainty may be different for different players. Such games are called games with incomplete information. We will focus on the special case when players have a subject probability distribution on the uncertainty. Such games are called Bayesian Games.
8.1 An illustrative example
To iilustrate such games, let’s consider a variation of battle of sexes, where player 2 may either want to meet player 1 or may want to avoid it. For simplicity we assume that player 1 is the same as before. We will model it by saying that there are two types of player 2; the type of the player is determined by events in nature, and that each player has a probability distribution on the events in nature (for simplicity, we will assume that this probability distribution is common knowledge between the players, but it is possible to model Bayesian games where each player has a different subjective probability on the events in nature).
More formally, we assume that there are two states in nature, modelled by \[ Ω = \{ ω_1, ω_2 \}. \] In state \(ω_1\), player 2 wants to meet player 1 while in state \(ω_2\), player 2 wants to avoid player 1. Furthermore, there is a prior belief \(p\) on \(Ω\) which we will assume is given by \[ p(ω_1) = \tfrac 12 \quad\text{and}\quad p(ω_2) = \tfrac 12. \]
Each player has a type, which we will denote by \(t_i\) for player \(i\) (there is a slight notational conflict as we had sometimes used \(t_i\) to denote alternative strategies for players). The set of types of player \(i\) is denoted by \(\ALPHABET T_i\). In the above example, \[ \ALPHABET T_1 = \{1\} \quad\text{and}\quad \ALPHABET T_2 = \{1, 2\}. \]
The important aspect of modeling such games is the information structure, i.e., who knows what about the states of nature. The information structure is modelled by a signal \(τ_i\) from the state of nature to player’s type. For this example, we will assume that \[ τ_1(ω_1) = τ_1(ω_2) = 1 \quad\text{and}\quad τ_2(ω_1) = 1, τ_2(ω_2) = 2. \] Thus, player 2 knows the state of nature (i.e., it knows whether it wants to meet with player 1 or not), while player 1 does not know the tate of nature (i.e., she doesn’t know if player 2 wants to meet with her or not).
Thus, effectively the type \(t_i = τ_i(ω)\) of the player is a random variable and the information structure can be thought of as the collection of partition generated by the types of each player, i.e., \(σ(t_1)\) and \(α(t_2)\) (where \(σ(⋅)\) means the sigma algebra generated by a random variable). Thus, for the above example, we can visualize the information structure as shown in Figure 8.1
We will use a slightly different terminology and call the moves of the players as actions (and denote them by \(a_i \in \ALPHABET A_i\). The pure strategy of a player is defined as a map from its type to its actions, i.e., \[ s_i \colon \ALPHABET T_i \to \ALPHABET A_i. \] This means that in the above example player 2 of type 1 (the one who wants to meet with player 1) may choose actions differently from player 2 of type 2 (the one who wants to avoid player 1).
Note that player 1 has two pure strategies: \[ 1 \mapsto \mathsf{F}, \quad \text{and} \quad 1 \mapsto \mathsf{O} \] while player 2 has four pure strategies: \[ 1 \mapsto \mathsf{F}, 2 \mapsto \mathsf{F}, \quad 1 \mapsto \mathsf{F}, 2 \mapsto \mathsf{O}, \quad 1 \mapsto \mathsf{O}, 2 \mapsto \mathsf{F}, \quad 1 \mapsto \mathsf{O}, 2 \mapsto \mathsf{O}. \] For simplicity of notation, we will simply denote them as follows: \[ \ALPHABET S_1 = \{ \mathsf{F}, \mathsf{O} \} \quad\text{and}\quad \ALPHABET S_2 = \{ \mathsf{FF}, \mathsf{FO}, \mathsf{OF}, \mathsf{OO} \}. \]
As was the case in games with complete information, a mixed strategy \(σ_i\) is a probability distribution over a set of pure strategies.
There are two ways to model the utility function of the players. Utilities could be either modelled as a function of events in nature and strategy profile of players or as a function of type profile of players and strategy profile of players. For this example, we will take the former approach. Thus, \[ u_i \colon Ω × \ALPHABET S \to \reals, \quad i \in \ALPHABET N. \]
For two player finite games, a compact way to write the utility function is to draw the bimatrix representation for each \(ω \in Ω\). For instance, in the above example, we may consider
| $\mathsf{F}$ | $\mathsf{O}$ | |||
| $\mathsf{F}$ | $2$ | $1$ | $0$ | $0$ |
| $\mathsf{O}$ | $0$ | $0$ | $1$ | $2$ |
| $\mathsf{F}$ | $\mathsf{O}$ | |||
| $\mathsf{F}$ | $2$ | $0$ | $0$ | $2$ |
| $\mathsf{O}$ | $0$ | $1$ | $1$ | $0$ |
Given a pure strategy profile \((s_1, s_2)\), the utility of player \(i\) is \[ U_i(s_1, s_2) = \sum_{ω \in Ω} \sum_{t_1 \in \ALPHABET T_1} \sum_{t_2 \in \ALPHABET T_2} p(ω) u_i(ω, s_1( t_1(ω) ) s_2( t_2(ω) ) ). \] The payoff of a mixed strategy profile \((σ_1, σ_2)\) is defined as \[ U_i(σ_1, σ_2) = \sum_{s_1 \in \ALPHABET S_1} \sum_{s_2 \in \ALPHABET S_2} σ_1(s_1) σ_2(s_2) U_i(s_1, s_2). \]
The equilibrium of a Bayesian game is called Bayesian equilibrium (abbreviated as BNE). There are two equivalent methods to define and compute BNE of Bayesian game. We describe both of them below.
Method 1: Ex-ante view
According to the ex-ante view, we view the game before nature has played. A strategy profile \((s_1, s_2)\) is a (pure strategy) BNE if \[ U_i(s_i, s_{-i}) \ge U_i(s'_{i}, s_{-i}), \quad \forall i \in \ALPHABET N, s'_i \in \ALPHABET S_i. \] Note that the definition BNE is similar to that of NE; the difference is in how the utility function \(U_i\) is defined. A mixed strategy BNE is defined in a similar manner.
Thus, if we compute the utility function \(U_i(s_1, s_2)\) for all pure strategy profiles, we can easily find the BNE. For instance, for the above game, the utility function \(U_i(s_1, s_2)\) can be computed as follows: \[\begin{align*} U(\mathsf{F}, \mathsf{FF}) &= p(ω_1) u(ω_1, \mathsf{F}, \mathsf{F}) + p(ω_2) u(ω_2, \mathsf{F}, \mathsf{F}) = \tfrac 12 (2,1) + \tfrac 12 (2,0) = (2, \tfrac 12) \\ U(\mathsf{F}, \mathsf{FO}) &= p(ω_1) u(ω_1, \mathsf{F}, \mathsf{F}) + p(ω_2) u(ω_2, \mathsf{F}, \mathsf{O}) = \tfrac 12 (2,1) + \tfrac 12 (0,2) = (1, \tfrac 32) \\ \cdots &= \cdots \end{align*}\]
We can write such an normal-form reduction of the game as a bimatrix game:
We can then identify a BNE of the orginal game by identifying the NE of its normal-form rediction. Although this approach is simple, it is not very attractive because the normal-form reduction has large strategy spaces (exponential in the number of types) and we have already seen that it difficult to compute NE of games with large strategy spaces.
Method 2: Interim view
According to the interim view, we view the game after nature has played; so each player knows its type. We can consider each player of each time (i.e., each \((i,t_i)\) as a separete player. Thus, the game has \(\prod_{i \in \ALPHABET N} |\ALPHABET T_i|\) players.
For a two player game, given an action \(a_i\) of player~\(i\) and a pure ss_{-i}$ of the player other than~\(i\), the utility of player \(i\) of type \(t_i\) is given by \[ U_{i.t_i}(a_i, s_{-i}) = \sum_{ω \in Ω} \sum_{t_{-i} \in \ALPHABET T_{-i}} p(ω | t_i) u_i(ω, a_i, s_{-i}(t_{-i}(ω))). \] Note that the payoff depends on the belief of player \(i.t_i\) which is given by \(p(ω | t_i)\).
When player \(-i\) is playing a mixed strategy \(σ_{-i}\), then the expected utility is given by \[ U_{i.t_i}(a_i, σ_{-i}) = \sum_{s_{-i} \in \ALPHABET S_{-i}} σ_{-i}(s_{-i}) U_{i.t_i}(a_i, s_{-i}). \]
In this formulation, a strategy profile \(σ^*\) is a Bayesian Nash equilibrium if for every player \(i\) and every type \(t_i \in \ALPHABET T_i\), we have \[ U_{i.t_i}( σ_i(t_i), σ_{-i}) \ge U_{i.t_i}( a_i, σ_{-i}), \quad \forall a_i \in \ALPHABET A_i. \]
A key result in Bayesian games is that the two definitions of BNE (one for the ex-ante view and the other for the interim view) are equivalent (provided the model is parscimonious, i.e., \(p(ω) > 0\) for all \(ω\)). In particular, when players are playing BNE, no player has a profitable deviation after knowing his type if and only if he has no profitable deviation before knowing his type.
Combing back to our example, we can write the utility function of all the players as follows:
| $\mathsf{FF}$ | $\mathsf{FO}$ | $\mathsf{OF}$ | $\mathsf{OO}$ | |
| $\mathsf{F}$ | $2$ | $1$ | $1$ | $0$ |
| $\mathsf{O}$ | $0$ | $\frac{1}{2}$ | $\frac{1}{2}$ | $1$ |
| $\mathsf{F}$ | $\mathsf{O}$ | |
| $\mathsf{F}$ | $1$ | $0$ |
| $\mathsf{O}$ | $0$ | $2$ |
| $\mathsf{F}$ | $\mathsf{O}$ | |
| $\mathsf{F}$ | $0$ | $2$ |
| $\mathsf{O}$ | $1$ | $0$ |
Note that player 2.1 does not care what player 2.2 does. But player 1.1’s strategy depends on both player 2.1 and player 2.2, which indirectly couples the two players.
We now show how to find the BNE via the interim strategy.
First we check for all pure strategy BNE by trying to find a fixed point of BR maps.
- If P1.1 plays \(\mathsf{F}\), BR of P2.1 is \(\mathsf{F}\) and BR of P2.2 is \(\mathsf{O}\).
- If P2 is playing \(\mathsf{FO}\), BR of P1.1 is \(\mathsf{F}\). Thus, \((\mathsf{F}, \mathsf{FO})\) is BNE.
- If P1.1 plays \(\mathsf{O}\), BR of P2.1 is \(\mathsf{O}\) and BR of P2.2 is \(\mathsf{F}\).
- If P2 is playing \(\mathsf{FO}\), BR of P1.1 is \(\mathsf{F}\). Thus, \((\mathsf{O}, \mathsf{OF})\) is not BNE.
Now we consider mixed strategy BNE. We have two possibilities:
Case 1 P1 is playing a pure strategy. Then P2.1 and P2.2 will also play pure strategies because their BR are unique. We have already compute the NE in pure strategies.
Case 2 P2 is playing a mixed strategy \(σ_1 = (p, 1-p)\). Consider mixed strategies \[ σ_{2.1} = (q_1, 1-q_1) \quad\text{and}\quad σ_{2.2} = (q_2, 1-q_2) \] of player 2. Note that we have assumed that \(p \in (0,1)\) but \(q_1, q_2 \in [0, 1]\).
- if \(q_1 \in (0,1)\), then by the invariance principle, \[ U_{2.1}(σ_1, \mathsf{F}) = U_{2.1}(σ_1, \mathsf{O}) \implies p = 2 (1-p) \implies p = \frac 23. \]
- if \(q_2 \in (0,1)\), then by the invariance principle, \[ U_{2.2}(σ_1, \mathsf{F}) = U_{2.1}(σ_1, \mathsf{O}) \implies (1-p) = 2p \implies p = \frac 13. \]
But \(p\) must take a single value so only one of them can be true. Thus, either
- \(q_1 \in (0, 1)\) and \(q_2 \in \{0, 1\}\), or
- \(q_2 \in (0, 1)\) and \(q_1 \in \{0, 1\}\).
We consider both these cases separately.
Case 2.1 \(p \in (0,1)\), \(q_1 \in (0,1)\), and \(q_2 \in \{0, 1\}\).
As argued before, in this case \(p = \tfrac 23\). We consider the two values of \(q_2\) separately.
\(q_2 = 0\). In this case, the mixed strategy of P2 is \[ σ_2 = (0, q_1, 0, 1-q_1). \] By the invariance principle, for P1 to play a mixed strategy, it must be that \[ U_1(\mathsf{F}, σ_2) = U_1(\mathsf{O}, σ_2) \implies q_1 = \tfrac 12 q_1 + (1 - q_1) \implies q_1 = \tfrac 23. \] We also need to check that P2.2 is playing her BR, i.e., \[ U_{2.2}(σ_1, \mathsf{F}) \le U_{2.2}(σ_1, \mathsf{O}) \iff \tfrac 13 \le \tfrac 43 \] which is true. Hence, the following is a mixed strategy NE. \[ \bbox[5pt,border: 1px solid]{ σ_1 = (\tfrac 23, \tfrac 13), \quad σ_{2.1} = (\tfrac 23, \tfrac 13), \quad σ_{2.2} = (0, 1). } \]
\(q_2 = 1\). In this case, the mixed strategy of P2 is \[ σ_2 = (q_1, 0, 1-q_1, 0). \] By the invariance principle, for P1 to play a mixed strategy, it must be that \[ U_1(\mathsf{F}, σ_2) = U_1(\mathsf{O}, σ_2) \implies 2 q_1 + (1 - q_1) = \tfrac 12 (1 -q_1) \implies q_1 = -\tfrac 13. \] Thus, there is no feasible solution in this case.
Case 2.2 \(p \in (0,1)\), \(q_2 \in (0,1)\), and \(q_1 \in \{0, 1\}\).
As argued before, in this case \(p = \tfrac 13\). Just to show the possibility, we solve this case differently from Case 2.1
Since we know the strategy of P1, we compute the BR of P2.1. We know that \[ U_{2.1}(σ_1, \mathsf{F}) = \tfrac 13 \quad\text{and}\quad U_{2.1}(σ_1, \mathsf{O}) = \tfrac 43 \] Since \(U_{2.1}(σ_1, \mathsf{F}) < U_{2.1}(σ_1, \mathsf{O})\), player 2.1 plays \(\mathsf{O}\). Thus, from the point of view of P1, P2 is playing the mixed strategy \[ σ_2 = (0, 0, q_2, 1-q_2). \] Unlike Case 2.1, we don’t need to consider the other possibility because we have established that P2.1 plays \(\mathsf{O}\)
By the invariance principle, for P1 to play a mixed strategy, it must be that \[ U_1(\mathsf{F}, σ_2) = U_1(\mathsf{O}, σ_2) \implies q_2 = \tfrac 12 q_2 + (1-q_2) \implies q_2 = \tfrac 23. \] Hence, the following is a mixed strategy NE. \[ \bbox[5pt,border: 1px solid]{ σ_1 = (\tfrac 13, \tfrac 23), \quad σ_{2.1} = (1, 0). \quad σ_{2.2} = (\tfrac 23, \tfrac 13), } \]
Example 8.1 Using the normal form reduction of Figure 8.3, verify that the following are mixed strategy NE:
- \(σ_1 = (\tfrac 23, \tfrac 13)\) and \(σ_2 = (0, \tfrac 23, 0, \tfrac 13)\).
- \(σ_1 = (\tfrac 13, \tfrac 23)\) and \(σ_2 = (0, 0, \tfrac 23, \tfrac 13)\).
8.2 Some examples
We now present some examples to highlight salient features of Bayesian Nash equilibirum
Example 8.2 (More information can hurt) Consider the following Bayesian game
| $\mathsf{L}$ | $\mathsf{M}$ | $\mathsf{R}$ | ||||
| $\mathsf{T}$ | $1$ | $2$ | $1$ | $0$ | $1$ | $3$ |
| $\mathsf{B}$ | $4$ | $4$ | $0$ | $0$ | $0$ | $5$ |
| $\mathsf{L}$ | $\mathsf{M}$ | $\mathsf{R}$ | ||||
| $\mathsf{T}$ | $1$ | $2$ | $1$ | $3$ | $1$ | $0$ |
| $\mathsf{B}$ | $4$ | $4$ | $0$ | $5$ | $0$ | $0$ |
where \[ p(ω_1) = p(ω_2) = \tfrac 12 \]
Consider two information structures shown in Figure 8.5 and Figure 8.6
Compute the BNE for both cases.
Note that in the first information structure no player has any information about the state of the nature, while in the second information structure, player 2 has full knowledge of the state of nature. The solution will demonstrate that for each information structure the game has a unique BNE under dominant strategies, but the payoff to both players in the second case are worse than in the first case. Thus more information can hurt! A celebrated example of this phenomenon is :Braess’s paradox
Solution
Case 1. In this case, no player has any information. The normal form reduction of the game is given as follows.
| $\mathsf{L}$ | $\mathsf{M}$ | $\mathsf{R}$ | ||||
| $\mathsf{T}$ | $1$ | $2.0$ | $1$ | $1.5$ | $1$ | $1.5$ |
| $\mathsf{B}$ | $4$ | $4.0$ | $0$ | $2.5$ | $0$ | $2.5$ |
Note that for player 2, \(\mathsf{L}\) dominates \(\mathsf{M}\) and \(\mathsf{R}\). Thus, the reduced game is
| $\mathsf{L}$ | ||
| $\mathsf{T}$ | $1$ | $2$ |
| $\mathsf{B}$ | $4$ | $4$ |
In this reduced game, for player 1 \(\mathsf{B}\) dominates \(\mathsf{T}\). Thus, the unique BNE of the game is \((\mathsf{B}, \mathsf{L})\) which gives a payoff of \((4, 4)\).
Case 2. In this case, player 2 knows the state of nature. For \(ω_1\), action \(\mathsf{R}\) is the dominant action, so all other actions can be eliminated. Similarly, for \(ω_1\), action \(\mathsf{M}\) is the dominant action, so all other actions can be eliminated. The reduced game is given by
| $\mathsf{R}$ | ||
| $\mathsf{T}$ | $1$ | $3$ |
| $\mathsf{B}$ | $0$ | $5$ |
| $\mathsf{M}$ | ||
| $\mathsf{T}$ | $1$ | $3$ |
| $\mathsf{B}$ | $0$ | $5$ |
In this reduced game, for player 1, action \(\mathsf{T}\) dominates \(\mathsf{B}\). Thus, the unique BNE is \((\mathsf{T}, \mathsf{RM})\) with a payoff of \((1, (3, 3))\).
Thus both players are worse off with the additional information.
In the examples considered so far, the information structure is trivial: each player either knows everything or knows nothing. We now consider an example where the information structure is non-trivial. Computing the BNE using the interim approach in this general case requires computing posterior probabilities
Example 8.3 (Inflection) Consider the following Bayesian game
| $\mathsf{L}$ | $\mathsf{R}$ | |||
| $\mathsf{T}$ | $2$ | $2$ | $0$ | $0$ |
| $\mathsf{B}$ | $3$ | $0$ | $1$ | $1$ |
| $\mathsf{L}$ | $\mathsf{R}$ | |||
| $\mathsf{T}$ | $2$ | $2$ | $0$ | $0$ |
| $\mathsf{B}$ | $0$ | $0$ | $1$ | $1$ |
| $\mathsf{L}$ | $\mathsf{R}$ | |||
| $\mathsf{T}$ | $2$ | $2$ | $0$ | $0$ |
| $\mathsf{B}$ | $0$ | $0$ | $1$ | $1$ |
where \[ p(ω_1) = \frac{9}{13}, \quad p(ω_2) = \frac{3}{13}, \quad p(ω_3) = \frac{1}{13} \] and the information structure is
The information structure implies that
- At \(ω_1\): P1 knows the payoffs. P2 does not know. P1 knows that P2 does not know.
- At \(ω_2\): P1 knows the payoffs. P2 does not know. P1 does know whether P2 knows.
- At \(ω_3\): Both players know the payoffs. P2 knows that P1 knows. P1 does not know that P2 knows.
Find the Bayesian Nash equilibrium of this game.
Solution
We will follow the interim approach. Observe that the posterior probabilities of \(Ω\) for each player is given as follows: \[\begin{align*} \PR_{1.1}(ω) &= (1, 0, 0), & \PR_{1.2}(ω) &= (0, \tfrac 34, \tfrac 14), \\ \PR_{2.1}(ω) &= (\tfrac 34, \tfrac 14, 0), & \PR_{2.2}(ω) &= (0, 0, 1). \end{align*}\]
where the notation \(\PR_{i.j}\) means the posterior probability of “player \(i\) of type \(j\)”. Based on these posterior probabilities, we can write the interim utility function for each player:
| $\mathsf{LL}$ | $\mathsf{LR}$ | $\mathsf{RL}$ | $\mathsf{RR}$ | |
| $\mathsf{T}$ | $2$ | $2$ | $2$ | $0$ |
| $\mathsf{B}$ | $3$ | $3$ | $1$ | $1$ |
| $\mathsf{LL}$ | $\mathsf{LR}$ | $\mathsf{RL}$ | $\mathsf{RR}$ | |
| $\mathsf{T}$ | $2$ | $\frac{3}{2}$ | $\frac{1}{2}$ | $0$ |
| $\mathsf{B}$ | $0$ | $\frac{1}{4}$ | $\frac{3}{4}$ | $1$ |
| $\mathsf{L}$ | $\mathsf{R}$ | |
| $\mathsf{TT}$ | $2$ | $0$ |
| $\mathsf{TB}$ | $\frac{3}{2}$ | $\frac{1}{4}$ |
| $\mathsf{BT}$ | $\frac{1}{2}$ | $\frac{3}{4}$ |
| $\mathsf{BB}$ | $0$ | $1$ |
| $\mathsf{L}$ | $\mathsf{R}$ | |
| $\mathsf{TT}$ | $2$ | $0$ |
| $\mathsf{TB}$ | $0$ | $1$ |
| $\mathsf{BT}$ | $2$ | $0$ |
| $\mathsf{BB}$ | $0$ | $1$ |
This game can be simplified using IEDS as follows.
Step 1: For P1.1, \(\mathsf{B}\) dominates \(\mathsf{T}\). Removing \(\mathsf{T}\) for P1.1, also eliminates \(\mathsf{TT}\) and \(\mathsf{TB}\) for P2.1 and P2.2. The resulting simplified game is as follows:
| $\mathsf{LL}$ | $\mathsf{LR}$ | $\mathsf{RL}$ | $\mathsf{RR}$ | |
| $\mathsf{B}$ | $3$ | $3$ | $1$ | $1$ |
| $\mathsf{LL}$ | $\mathsf{LR}$ | $\mathsf{RL}$ | $\mathsf{RR}$ | |
| $\mathsf{T}$ | $2$ | $\frac{3}{2}$ | $\frac{1}{2}$ | $0$ |
| $\mathsf{B}$ | $0$ | $\frac{1}{4}$ | $\frac{3}{4}$ | $1$ |
| $\mathsf{L}$ | $\mathsf{R}$ | |
| $\mathsf{BT}$ | $\frac{1}{2}$ | $\frac{3}{4}$ |
| $\mathsf{BB}$ | $0$ | $1$ |
| $\mathsf{L}$ | $\mathsf{R}$ | |
| $\mathsf{BT}$ | $2$ | $0$ |
| $\mathsf{BB}$ | $0$ | $1$ |
Step 2: In this reduced game, for P2.1, \(\mathsf{L}\) dominates \(\mathsf{R}\). Removing \(\mathsf{R}\) for P2.1 also eliminates \(\mathsf{RL}\) and \(\mathsf{RR}\) for P1.1 and P1.2. The resulting simplified game is as follows:
| $\mathsf{RL}$ | $\mathsf{RR}$ | |
| $\mathsf{B}$ | $1$ | $1$ |
| $\mathsf{RL}$ | $\mathsf{RR}$ | |
| $\mathsf{T}$ | $\frac{1}{2}$ | $0$ |
| $\mathsf{B}$ | $\frac{3}{4}$ | $1$ |
| $\mathsf{R}$ | |
| $\mathsf{BT}$ | $\frac{3}{4}$ |
| $\mathsf{BB}$ | $1$ |
| $\mathsf{L}$ | $\mathsf{R}$ | |
| $\mathsf{BT}$ | $2$ | $0$ |
| $\mathsf{BB}$ | $0$ | $1$ |
Step 3: In this reduced game, for P1.2, \(\mathsf{B}\) dominates \(\mathsf{T}\). Removing \(\mathsf{T}\) for P1.2, also eliminates \(\mathsf{BT}\) for P2.1 and P2.2. The resulting simplified game is as follows:
| $\mathsf{RL}$ | $\mathsf{RR}$ | |
| $\mathsf{B}$ | $1$ | $1$ |
| $\mathsf{RL}$ | $\mathsf{RR}$ | |
| $\mathsf{B}$ | $\frac{3}{4}$ | $1$ |
| $\mathsf{R}$ | |
| $\mathsf{BB}$ | $1$ |
| $\mathsf{L}$ | $\mathsf{R}$ | |
| $\mathsf{BB}$ | $0$ | $1$ |
Step 4: In this reduced game, for P2.2, \(\mathsf{R}\) dominates \(\mathsf{L}\). Removing \(\mathsf{R}\) for P2.2 also eliminates \(\mathsf{RR}\) for P1.1 and P1.2. The resulting simplified game is:
| $\mathsf{RL}$ | |
| $\mathsf{B}$ | $1$ |
| $\mathsf{RL}$ | |
| $\mathsf{B}$ | $\frac{3}{4}$ |
| $\mathsf{R}$ | |
| $\mathsf{BB}$ | $1$ |
| $\mathsf{R}$ | |
| $\mathsf{BB}$ | $1$ |
Thus, the unique BNE is: P1.1 plays \(\mathsf{B}\); P1.2 plays \(\mathsf{B}\), P2.1 plays \(\mathsf{R}\) and P2.2 plays \(\mathsf{R}\).
[Observe that for \(ω = ω_3\), both plays know the game, but the good outcome \((\mathsf{T}, \mathsf{L})\), which is also the NE of the game corresponding to \(ω_3\) has been ruled out!
Example 8.4 Consider the following Bayesian game
| $\mathsf{L}$ | $\mathsf{R}$ | |||
| $\mathsf{T}$ | $2$ | $0$ | $0$ | $3$ |
| $\mathsf{B}$ | $0$ | $4$ | $1$ | $0$ |
| $\mathsf{L}$ | $\mathsf{R}$ | |||
| $\mathsf{T}$ | $0$ | $3$ | $3$ | $1$ |
| $\mathsf{B}$ | $2$ | $0$ | $0$ | $1$ |
where \[ p(ω_1) = \tfrac 13 \quad\text{and}\quad p(ω_2) = \tfrac 23 \] and the information structure is
- Write the interim form of the game.
- Using the interim form, find all the pure strategy BNE of the game.
- Using the interim form, find all the mixed strategy BNE of the game.
Solution
The interim games from the point of player 1.1 and 1.2 are the same as the games corresponding to \(ω_1\) and \(ω_2\). So, we only need to compute the interim game corresponding to player 2.1.
| $\mathsf{L}$ | $\mathsf{R}$ | |
| $\mathsf{T}$ | $2$ | $0$ |
| $\mathsf{B}$ | $0$ | $1$ |
| $\mathsf{L}$ | $\mathsf{R}$ | |
| $\mathsf{T}$ | $0$ | $3$ |
| $\mathsf{B}$ | $2$ | $0$ |
| $\mathsf{L}$ | $\mathsf{R}$ | |
| $\mathsf{TT}$ | $2$ | $\frac{5}{3}$ |
| $\mathsf{TB}$ | $0$ | $\frac{5}{3}$ |
| $\mathsf{BT}$ | $\frac{10}{3}$ | $\frac{2}{3}$ |
| $\mathsf{BB}$ | $\frac{4}{3}$ | $\frac{2}{3}$ |
Pure strategy BNE
- IF P2 plays \(\mathsf{L}\), BR of P1.1 is $ and BR of P1.2 is \(\mathsf{B}\).
- If P1 is playing \(\mathsf{TB}\), then BR of P2.1 is \(\mathsf{R}\). Thus, \((\mathsf{TB}, \mathsf{L})\) is not BNE.
- IF P2 plays \(\mathsf{R}\), BR of P1.1 is $ and BR of P1.2 is \(\mathsf{T}\).
- If P1 is playing \(\mathsf{BT}\), then BR of P2.1 is \(\mathsf{L}\). Thus, \((\mathsf{BT}, \mathsf{R})\) is not BNE.
Thus, there is no pure strategy BNE.
Mixed strategy BNE Let \(σ_{1.1} = (p_1, 1 - p_1)\), \(σ_{1.2} = (p_2, 1 - p_2)\) and \(σ_{2.1} = (q, 1-q)\) be a mixed strategy NE.
If \(p_1 \in (0, 1)\), then by the indifference principle, we must have \[ U_{1.1}(\mathsf{T}, σ_2) = U_{1.1}(\mathsf{B}, σ_2) \implies 2q = 1 - q \implies q = \frac 13. \]
If \(p_2 \in (0, 1)\), then by the indifference principle, we must have \[ U_{1.2}(\mathsf{T}, σ_2) = U_{1.2}(\mathsf{B}, σ_2) \implies 3(1 - q) = 2 q \implies q = \frac 35. \]
But \(q\) must take a single value so only one of them can be true. Thus, either
- \(p_1 \in (0,1)\) and \(p_2 \in \{0, 1\}\), or
- \(p_2 \in (0,1)\) and \(p_1 \in \{0, 1\}\).
We consider both these cases separately.
Case 1. \(p_1 \in (0, 1)\). In this case, we have already computed that \(q = \frac 13\). Thus, \[ U_{1.2}(\mathsf{T}, σ_2) = 2, \quad U_{1.2}(\mathsf{B}, σ_2) = \frac {2}{3}. \] Thus, the BR of P1.2 is \(\mathsf{T}\). Hence \(p_2 = 1\). Consequently, the strategy of P1 as viewed by P2.1 is \[ σ_1 = (p_1, 0, 1-p_1, 0). \] Now, by the indifference principle, we must have \[ U_{2.1}(σ_1, \mathsf{L}) = U_{2.1}(σ_1, \mathsf{R}) \implies 2 p_1 + \frac{10}{3}(1-p_1) = \frac{5}{3}p_1 + \frac{2}{3}(1-p_1) \implies p_1 = \frac{8}{7}. \] Since \(p_1 \not\in [0, 1]\), this is not a valid probability distribution and hence not a BNE.
Case 2. \(p_2 \in (0,1)\). In this case, we have already computed that \(q = \frac{3}{5}\). Thus, \[ U_{1.1}(\mathsf{T}, σ_2) = \frac{6}{5}, \quad U_{1.1}(\mathsf{B}, σ_2) = \frac {2}{5}. \] Thus, the BR of P1.1 is \(\mathsf{T}\). Hence \(p_1 = 1\). Consequently, the strategy of P1 as viewed by P2.1 is \[ σ_1 = (p_2, 1-p_2, 0, 0). \] Now, by the indifference principle, we must have \[ U_{2.1}(σ_1, \mathsf{L}) = U_{2.1}(σ_1, \mathsf{R}) \implies 2 p_2 = \frac{5}{3} \implies p_2 = \frac{5}{6}. \] Since \(p_2 \in [0, 1]\), this is a valid probability distribution. Hence, the mixed strategy BNE is \[ \bbox[5pt,border: 1px solid]{ σ_{1.1} = (1, 0), \quad σ_{1.2} = (\tfrac{5}{6}, \tfrac{1}{6}), \quad σ_2 = (\tfrac{3}{5}, \tfrac{2}{5}). } \]
8.3 Bayesian games with continuous actions
In this section, we provide some examples of Bayesian games with continuous actions. For such games it is difficult to specify the space of all pure strategies of a player. Therefore, we typically restrict attention to a parameteric family of strategies. In particular, we follow the interim approach and proceed as follows:
Consider the game from from the point of view of player \(i\) of type \(t_i\).
Assume that all players other than player \(i\) are using a parameteric strategy and write the expression for the expected utility of player \(i\) of type \(t_i\) as a function of its action and other players’ strategies.
By the BR of player \(i\) of type \(t_i\) (typically by differentiatting its expected utility w.r.t. its action and setting it to zero).
The hope is that this BR will belong to the same parametric class. If so, by repeating the argument for all players, we get a system of equations between the parameters of the strategies. Solving them gives a BNE strategy.
Note that there is no guarantee that we will be able to find a BNE within any parameteric class; and identifying the appropriate parameteric class is bit of an art.
In the examples that we provide below, we will typically look at BNE within the class of linear or affine strategies.
Example 8.5 (First price sealed bid auctions) Consider a game where two players present a sealed bid for an object. Let \(v_i\) denote the player \(i\)’s valuation of the object, which is private information to the player.
We will model this as a Bayesian game with a probability space with \(Ω = [0,1]^2\) and \(\PR\) being uniform distribution on \(Ω\). Let \(ω = (v_1, v_2) \in Ω\) denote the state of the world. The signal received by player \(i\) is \(v_1\) and the signal received by player 2 is \(v_2\).
Upon seeing their signals, each player chooses a bid \(b_i\). In first price autions, the person with the highest bid gets the object and pays the amount equal to his bid. Thus, the utility of the players is: \[ u_i(v_i, v_{-j}, b_{i}, b_{-i}) = \begin{cases} v_i - b_i, & \text{if } b_i > b_j \\ \frac{1}{2}(v_i - b_i), & \text{if } b_i = b_j \\ 0, & \text{if } b_i < b_j. \end{cases} \]
Find the BNE of the game within the class of linear strategies, i.e., strategies of the form \[ s_i(v_i) = α_i v_i. \]
Solution
We first compute the interim expected utility of player \(i\) of type \(v_i\). For that matter, observe that posterior belief of player \(i\) about the type of player \(j\) is given by: \[ f(v_j|v_i) = 1, \quad v_j \in [0, 1]. \] Thus, the interim expected utility is given by \[\begin{align*} U_{i.v_i}(b_i, s_j) &= \int_{0}^{1} u_i(v_i, v_j, b_i, s_j(v_j) f(v_j|v_i) dv_j \\ &= \int_{0}^{(b_i/α_j)^{-}} (v_i - b_i) d v_j + \int_{(b_i/α_j)^{-}}^{(b_i/α_j)^{+}} \tfrac 12 (v_i - b_i) d v_j + \int_{(b_i/α_j)^{+}}^1 0 dv_j \\ &= (v_i - b_i) \frac{b_i}{α_j} \end{align*}\] which is concave in \(b_i\). Thus, the interim BR is given by \[ \frac{∂}{∂b_i} U_{i.v_i}(b_i, s_j) = 0 \implies \bbox[5pt,border: 1px solid]{b_i = \frac{v_i}{2}.} \]
By a similar argument, we can show that in \(n\)-player first price auctions, the BNE is to bid \[ b_i = \left(1 - \frac{1}{n}\right) v_i. \] Thus, the players shade their bids below their valuation, to balance the profit when the win against the risk of not winning. THe more the players in the auction, thje less they can affort to shade their bid.
Earlier we had consider second price auctions (?sec-2nd-price) but we assumed that the valuations of all players were common knowledge. Now we consider the case where the player only knows his own valuation.
Example 8.6 (Second price sealed bid auctions) Consider the setup of Example 8.5 but with the valuation function \[ u_i(v_i, v_{-j}, b_{i}, b_{-i}) = \begin{cases} v_i - b_j, & \text{if } b_i > b_j \\ \frac{1}{2}(v_i - b_j), & \text{if } b_i = b_j \\ 0, & \text{if } b_i < b_j. \end{cases} \] Find the BNE of the game within the class of linear strategies, i.e., strategies of the form \[ s_i(v_i) = α_i v_i. \]
Solution
As before, we note that posterior belief of player \(i\) about the type of player \(j\) is given by: \[ f(v_j|v_i) = 1, \quad v_j \in [0, 1]. \] Thus, the interim expected utility of player \(i\) of type \(v_i\) is given by \[\begin{align*} U_{i.v_i}(b_i, s_j) &= \int_{0}^{1} u_i(v_i, v_j, b_i, s_j(v_j) f(v_j|v_i) dv_j \\ &= \int_{0}^{(b_i/α_j)^{-}} (v_i - α_j v_j ) d v_j + \int_{(b_i/α_j)^{-}}^{(b_i/α_j)^{+}} \tfrac 12 (v_i - α_j v_j ) d v_j + \int_{(b_i/α_j)^{+}}^1 0 dv_j \\ &= v_i \frac{b_i}{α_j} - \frac {1}{2} α_j \frac{b_i^2}{α_j^2} \\ &= \frac{v_i b_i}{α_j} - \frac{b_i^2}{2 α_j} \end{align*}\] which is concave in \(b_i\). Thus, the interim BR is given by \[ \frac{∂}{∂b_i} U_{i.v_i}(b_i, s_j) = 0 \implies \bbox[5pt,border: 1px solid]{b_i = v_i.} \]
The above method is analytic. If one has a good guess about the BNE, an alternative method is to argue, as we did earlier in the course, that truthful bidding is a weakly dominant strategy for each player.
Example 8.7 (First price sealed bid auctions with common value) Consider a variation of the first-price auction where the players observe \(v_1\) and \(v_2\) as before, but the value of the object is \(v_1 + v_2\). Thus, the utility function of the players is \[ u_i(v_i, v_{-j}, b_{i}, b_{-i}) = \begin{cases} v_1 + v_2 - b_i, & \text{if } b_i > b_j \\ \frac{1}{2}(v_1 + v_2 - b_i), & \text{if } b_i = b_j \\ 0, & \text{if } b_i < b_j. \end{cases} \]
Find the BNE of the game within the class of linear strategies, i.e., strategies of the form \[ s_i(v_i) = α_i v_i. \]
Solution
As before, we compute \[\begin{align*} U_{i.v_i}(b_i, s_j) &= \int_{0}^1 u_i(v_i, v_j, b_i, s_j(v_j)) f(v_j \mid v_i) dv_j \\ &= \int_{0}^{(b_i/α_j)} (v_i + v_j - b_i) d v_j \\ &= (v_i - b_i) \frac{b_i}{α_j} + \frac{1}{2} \frac{b_i^2}{α_j^2} \end{align*}\] which is concave in \(b_i\). Thus, the interim BR is given by \[ \frac{∂}{∂b_i} U_{i.v_i}(b_i, s_j) = 0 \implies \bbox[5pt,border: 1px solid]{b_i = \frac{α_j}{2 α_j - 1} v_i} \]
By symmetry, we get \[ b_j = \frac{α_i}{2 α_i - 1 } v_j. \] But, we started by assuming that \(b_i = α_i v_i\) and \(b_j = α_j v_j\). Thus, we must have \[ α_1 = \frac{α_2}{2 α_2 - 1} \quad\text{and}\quad α_2 = \frac{α_1}{2 α_1 - 1}. \] Thus, we must have \[ α_1 + α_2 = 2 α_1 α_2. \]
If we look for symmetric solutions, then we have \(α_1 = α_2\), which implies \(α_1 = α_2 = 1\). Thus, the BNE bidding strategy is \[ \bbox[5pt,border: 1px solid]{b_i = v_i.} \]
8.4 Bayesian games with common information
Exercises
Exercise 8.1 Consider the following Bayesian game
| $\mathsf{L}$ | $\mathsf{R}$ | |||
| $\mathsf{T}$ | $1$ | $1$ | $0$ | $2$ |
| $\mathsf{B}$ | $0$ | $2$ | $1$ | $1$ |
| $\mathsf{L}$ | $\mathsf{R}$ | |||
| $\mathsf{T}$ | $2$ | $2$ | $0$ | $1$ |
| $\mathsf{B}$ | $4$ | $4$ | $2$ | $3$ |
where \[ p(ω_1) = p(ω_2) = \tfrac 12 \] and the information structure is
Write the normal form reduction of the game and use it to find all pure strategy BNE.
Write the interim form of the game and use it to find all pure strategy BNE.
Exercise 8.2 Consider the following Bayesian game
| $\mathsf{L}$ | $\mathsf{R}$ | |||
| $\mathsf{T}$ | $2$ | $4$ | $0$ | $0$ |
| $\mathsf{B}$ | $0$ | $0$ | $4$ | $-10$ |
| $\mathsf{L}$ | $\mathsf{R}$ | |||
| $\mathsf{T}$ | $4$ | $-10$ | $0$ | $0$ |
| $\mathsf{B}$ | $0$ | $0$ | $4$ | $4$ |
where \[ p(ω_1) = \tfrac 35 \quad\text{and}\quad p(ω_2) = \tfrac 25 \] and the information structure is
Write the normal form reduction of the game and use it to find all mixed strategy BNE.
Write the interim form of the game and use it to find all mixed strategy BNE.
Exercise 8.3 Consider first price auctions with \(3\) players. In particular, each player have a private value \(v_i\), which is uniformly distributed in \([0,1]\). The values \(v_1\), \(v_2\), and \(v_3\) of the players are independent. Each player places a bid \(b_i = s_i(v_i)\).
The player with the higest bid wins the object. In case of a tie, the object is given at random to one of the players with the highest bid. The winning player pays the amount that he bid to the seller and receives the object.
Find the BNE of the game within the class of linear strategies, i.e., strategies of the form \[ s_i(v_i) = α_i v_i. \]
Exercise 8.4 (Cournot Duopoly with incomplete information) Consider the Cournot competition where two firms produce the same product and competes for the same market of potential customers. The firms simultaneously select production quantity and the price depending on aggregate production.
Let \(a_i \in [0, ∞)\) denote the quantity produced by firm \(i\). The total quantity of products in the market is \(a_1 + a_2\) and we assume that the price is \[ p(a_1, a_2) = \max\{2 - a_1 - a_2, 0 \}. \] The per-item production cost for firm 1 is \(c_1 = 1\) and is common knowledge among the two firms. The production cost of firm 2 is either \(c_L = \frac 34\) (low cost) with probability \(\frac 12\) or is \(c_H = \frac 54\) (high cost) with probability \(\frac 12\). Firm 2 knows its production cost but firm 1 does not.
Model the system as a Bayesian game and identify the Bayesian Nash equilibrium.
Compute the expected equilibrium payoff of each player of each type. Compare this with the payoff obtained when firm 2 does not know its production cost (and therefore assumes that expected production cost of \(c_2 = \frac 12 c_L + \frac 12 c_H = 1\), which is the same model as the Cournot duopoly model considered earlier).