9 Games of Incomplete Information

9.1 Auctions

Let us consider the (general) problem: How to allocate (discrete) resources among selfish agents in a multi-agent system?

Auctions provide a general solution to this problem. As such, auctions have been heavily used in real life, in consumer, corporate as well as government settings:

eBay, art auctions, wine auctions, etc.
advertising (Google adWords)
governments selling public resources: electromagnetic spectrum, oil leases, etc.
…

Auctions also provide a theoretical framework for understanding resource allocation problems among self-interested agents. Formally, an auction is any protocol that allows agents to indicate their interest in one or more resources and that uses these indications to determine the resource allocation and payments of the agents.

Auctions may be used in various settings depending on the complexity of the resource allocation problem:

Single-item auctions: Here $n$ bidders (players) compete for a single indivisible item that can be allocated to just one of them. Each bidder has his own private value of the item in case he wins (gets zero if he loses). Typically (but not always) the highest bid wins. How much should he pay?
Multiunit auctions: Here a fixed number of identical units of a homogenous commodity are sold. Each bidder submits both a number of units he demands and a unit price he is willing to pay. Here also the highest bidders typically win, but it is unclear how much should they pay (pay-as-bid vs uniform pricing).
Combinatorial auctions: Here bidders compete for a set of distinct goods. Each player has a valuation function that assigns values to subsets of the set (some goods are useful only in groups etc.). Who wins and what he pays?

Tip

We shall mostly concentrate on single-item auctions.

9.1.1 Single-Item Auctions

There are many single-item auctions, but we consider the following well-known versions:

open auctions:
- The English Auction: Often occurs in movies; bidders are sitting in a room (by computer or a phone) and the price of the item goes up as long as someone is willing to bid it higher. Once the last increase is no longer challenged, the last bidder to increase the price wins the auction and pays the price for the item.
- The Dutch Auction: Opposite of the English auction; here, the price starts at a prohibitively high value and the auctioneer gradually drops the price. Once a bidder shouts “buy”, the auction ends and the bidder gets the item at the price.
sealed-bid auctions:
- $k$-th price Sealed-Bid Auction: Each bidder writes down his bid and places it in an envelope; the envelopes are opened simultaneously. The highest bidder wins and then pays the $k$-th maximum bid. (In reverse auction it is the $k$-th minimum). The most prominent special cases are The First-Price Auction and The Second-Price Auction.

Observe that

the English auction is essentially equivalent to the second price auction if the increments in every round are very small.

Note

There exists a “continuous” version, called the Japanese auction, where the price continuously increases. Each bidder may drop out at any time. The last one who stays gets the item for the current price (which is the dropping price of the “second highest bid”).

similarly, the Dutch auction is equivalent to the first price auction. Note that the bidder with the highest bid stops the decrement of the price and buys at the current price which corresponds to his bid.

But now the question arises, which auction (and if any) is better? The goal of the bidder is clear – to get the item at as low a price as possible (i.e. they maximize the difference between their private value and the price they pay). We consider only self-interested non-communicating bidders, that are rational and intelligent. There are also at least two goals that may be pursued by the auctioneer (in various settings):

revenue maximization;
incentive compatibility: we want the bidder to spontaneously bid their true value of the item.

Tip

The incentive compatibility objective means that we do not want it to be possible to strategically manipulate the auction by lying.

9.1.2 Auctions as Games

Consider single-item sealed-bid auctions as strategic-form games: Let $G = (N, (B_i)_{i \in N}, (u_i)_{i \in N})$ be a strategic-form game where

the set of players $N$ is the set of bidders;
$B_i = [0, \infty)$ where each $b_i \in B_i$ corresponds to the bid $b_i$ (we follow the standard notation and use $b_i$ to denote pure strategies (bids)).
to define $u_i$, we assume that each bidder has his own private value $v_i$ of the item, then given bids $\boldsymbol{b} = (b_1, \dots, b_n)$:
- First Price: \[ u_i(\boldsymbol{b}) = \begin{cases} v_i - b_i, & b_i > \max_{j \neq i} b_j, \\ 0, & \text{otherwise}; \end{cases} \]
- Second Price: \[ u_i(\boldsymbol{b}) = \begin{cases} v_i - \max_{j \neq i} b_j, & b_i > \max_{j \neq i} b_j, \\ 0, & \text{otherwise}. \end{cases} \]

Is this model realistic? Not really – usually, the bidders are not perfectly informed about the private values of the other bidders.

Tip

Although imperfect-information extensive-form games would solve this issue, the construction would be awkward, to say the least (and would miss the point of the problem).

9.2 Incomplete-Information Games

Definition 9.1 A (strict) incomplete information game is a tuple $G = (N, (A_i)_{i \in N}, (T_i)_{i \in N}, (u_i)_{i \in N})$ where

$N = \left\{1, \dots, n\right\}$ is a set of players;
each $A_i$ is a set of actions available to player $i$; we denote by $A = \prod_{i = 1}^n A_i$ the set of all possible action profiles $\boldsymbol{a} = (a_1, \dots, a_n)$;
each $T_i$ is the set of all possible types of player $i$ and we denote by $T = \prod_{i = 1}^n T_i$ the set of all possible type profiles $\boldsymbol{t} = (t_1, \dots, t_n)$;
$u_i$ is a type-dependent payoff function \[ u_i: A_1 \times \cdots \times A_n \times T_i \to \mathbb{R}; \] given a profile of actions $\boldsymbol{a} = (a_1, \dots, a_n)$ and a type $t_i \in T_i$, we write $u_i(\boldsymbol{a}; t_i) = u_i(a_1, \dots, a_n; t_i)$ to denote the corresponding payoff.

A pure strategy of player $i$ is a function $s_i : T_i \to A_i$. As before, we denote by $S_i$ the set of all pure strategies of player $i$, and by $S$ the set of all pure strategy profiles $S = \prod_{i = 1}^n S_i$.

9.2.1 Dominance

Definition 9.2 A pure strategy $s_i$ very weakly dominates $s'_i$ if for every $t_i \in T_i$ the following holds: For all $\boldsymbol{a}_{-i}\in A_{-i}$ we have that \[ u_i(s_i(t_i), \boldsymbol{a}_{-i}; t_i) \geq u_i(s'_i(t_i), \boldsymbol{a}_{-i}; t_i). \]

Definition 9.3 A pure strategy $s_i$ weakly dominates $s'_i$ if for every $t_i \in T_i$ the following holds: For all $\boldsymbol{a}_{-i}\in A_{-i}$ we have that \[ u_i(s_i(t_i), \boldsymbol{a}_{-i}; t_i) \geq u_i(s'_i(t_i), \boldsymbol{a}_{-i}; t_i) \] and the inequality is strict for at least one $\boldsymbol{a}_{-i}$.

Tip

Such $\boldsymbol{a}_{-i}$ satisfying the strict inequality may be different for different types $t_i.$

Definition 9.4 A pure strategy $s_i$ strictly dominates $s'_i$ if for every $t_i \in T_i$ the following holds: For all $\boldsymbol{a}_{-i}\in A_{-i}$ we have that \[ u_i(s_i(t_i), \boldsymbol{a}_{-i}; t_i) > u_i(s'_i(t_i), \boldsymbol{a}_{-i}; t_i). \]

Definition 9.5 A pure strategy $s_i$ is (very weakly, weakly, strictly) dominant if it (very weakly, weakly, strictly) dominates all other pure strategies $s'_i \in S_i$.

In order to generalize Nash equilibria to incomplete-information games, we use the following notation: Given a pure strategy profile $\boldsymbol{s} = (s_1, \dots, s_n) \in S$ and a profile of types $\boldsymbol{t} = (t_1, \dots, t_n) \in T$, for every player $i$ we write \[ \boldsymbol{s}_{-i}(\boldsymbol{t}_{-i}) = (s_1(t_1), \dots, s_{i-1}(t_{i-1}), s_{i+1}(t_{i+1}), \dots, s_n(t_n)). \]

Definition 9.6 (Ex-post Nash equilibirium¹) A strategy profile $\boldsymbol{s} = (s_1, \dots, s_n)$ is an ex-post Nash equilibrium if no player can increase their ex-post expected utility $u_i(s_i, \boldsymbol{s}_{-i}; t_i, \boldsymbol{t}_{-i})$ by unilaterally changing their strategy, i.e. for every player $i$ and every type profile $\boldsymbol{t} \in T$ and every strategy $s_i' \in S_i$ of player $i$ it holds that \[ u_i(\boldsymbol{s}; \boldsymbol{t}) \geq u_i(s_i', \boldsymbol{s}_{-i}; \boldsymbol{t}). \]

Note that in the ex-post expected utility, player $i$ knows types of other players!

Warning

In the lectures, it was defined as follows:

A strategy profile $\boldsymbol{s} = (s_1, \dots, s_n)$ is an ex-post Nash equilibrium if for every type profile $\boldsymbol{t} = (t_1, \dots, t_n) \in T$, we have that $\boldsymbol{s}(\boldsymbol{t}) = (s_1(t_1), \dots, s_n(t_n))$ is a Nash equilibrium in the strategic form game defined by the $t_i$’s.

Formally, $\boldsymbol{s} = (s_1, \dots, s_n)$ is an ex-post Nash equilibrium if for all $i \in N$ and all $\boldsymbol{t} = (t_1, \dots, t_n) \in T$ and all $a_i \in A_i$ the following holds \[ u_i(\boldsymbol{s}(\boldsymbol{t}); t_i) \geq u_i(a_i, \boldsymbol{s}_{-i}(\boldsymbol{t}_{-i}); t_i). \]

Example 9.1 Consider single-item sealed-bid auctions as strict incomplete-information games: $G = (N, (B_i)_{i \in N}, (V_i)_{i \in N}, (u_i)_{i \in N})$ where

the set of players $N$ is the set of bidders;
$B_i = [0, \infty)$ where each action $b_i \in B_i$ corresponds to the bid $b_i$;
$V_i = [0, \infty)$ where each type $v_i \in V_i$ corresponds to the private value $v_i$;
let $v_i \in V_i$ be the type of player $i$ (i.e. his private value), then given an action profile $\boldsymbol{b} = (b_1, \dots, b_n)$ (i.e. bids) we define
- First Price \[ u_i(\boldsymbol{b}; v_i) = \begin{cases} v_i - b_i, & b_i > \max_{j \neq i} b_j, \\ 0, & \text{otherwise}, \end{cases} \]
- Second Price \[ u_i(\boldsymbol{b}; v_i) = \begin{cases} v_i - \max_{j \neq i} b_j, & b_i > \max_{j \neq i} b_j, \\ 0, & \text{otherwise}. \end{cases} \]

Are there dominant strategies? Are there ex-post-Nash equilibria?

Note

Note that when there is a tie (i.e. there are $k \neq l$ such that $b_l = b_k = \max_j b_j$), then all players get 0.

9.2.2 Second-Price Auction

For every $i$, we denote by $v_i$ the pure strategy $s_i$ for player $i$ defined by $s_i(v_i) = v_i$.

Tip

Intuitively, such a strategy is truth-telling, which means that the player bids his own private value truthfully.

Theorem 9.1 Assume Second-Price Auction. Then for every player $i$ we have that $v_i$ is a weakly dominant strategy. So $\boldsymbol{v}$ is also an ex-post Nash equilibrium.

Proof. Let us fix the private value $v_i$ and the bid $b_i \in B_i$ of player $i$ such $b_i \neq v_i$. We show that for all bids of opponents $\boldsymbol{b}_{-i}\in B_{-i}$: \[ u_i(v_i, \boldsymbol{b}_{-i}; v_i) \geq u_i(b_i, \boldsymbol{b}_{-i}; v_i) \] with the strict inequality for at least one $\boldsymbol{b}_{-i}$. Intuitively, assume that player $i$ bids $b_i$ against $\boldsymbol{b}_{-i}$ of his opponents and compares his payoff with the payoff he obtains by playing $v_i$ against $\boldsymbol{b}_{-i}$.

There are two cases to consider; $b_i < v_i$ and $b_i > v_i$:

Case $b_i < v_i$: We distinguish three cases depending on $\boldsymbol{b}_{-i}$
1. If $b_i > \max_{j \neq i} b_j$, then \[ u_i(b_i, \boldsymbol{b}_{-i}; v_i) = v_i - \max_{j \neq i} b_j = u_i(v_i, \boldsymbol{b}_{-i}; v_i); \] intuitively, player $i$ wins and pays the price $\max_{j \neq i} b_j < b_i$; however, then bidding $v_i > b_i$, player $i$ still wins and pays $\max_{j \neq i} b_j$ as well;
2. If there is $k \neq i$ such that $b_k > \max_{j \neq k} b_j$, then \[ u_i(b_i, \boldsymbol{b}_{-i}; v_i) = 0 \leq u_i(v_i, \boldsymbol{b}_{-i}; v_i); \] moreover, if $b_i < b_k < v_i$, then we get a strict inequality (required by Definition 9.3) \[ u_i(b_i, \boldsymbol{b}_{-i}; v_i) = 0 < v_i - b_k = u_i(v_i, \boldsymbol{b}_{-i}; v_i); \] intuitively, if another player $k$ wins, then player $i$ gets 0 and increasing $b_i$ to $v_i$ surely does not hurt. Moreover, if $b_i < b_k < v_i$, then increasing $b_i$ to $v_i$ strictly increases the payoff of player $i$;
3. If there are $k \neq l$ such that $b_k = b_l = \max_j b_j$, then \[ u_i(b_i, \boldsymbol{b}_{-i}; v_i) = 0 \leq u_i(v_i, \boldsymbol{b}_{-i}; v_i); \] intuitively, there is a tie in $(b_i, \boldsymbol{b}_{-i})$ and all players get 0.
Case $b_i > v_i$: We distinguish four sub-cases depending on $\boldsymbol{b}_{-i}$
1. If $b_i > \max_{j \neq i} b_j > v_i$, then \[ u_i(b_i, \boldsymbol{b}_{-i}; v_i) = v_i - \max_{j \neq i} b_j < 0 = u_i(v_i, \boldsymbol{b}_{-i}; v_i), \] so in this case, the inequality is strict;
2. If $b_i > v_i \geq \max_{j \neq i} b_j$, then \[ u_i(b_i, \boldsymbol{b}_{-i}; v_i) = v_i - \max_{j \neq i} b_j = u_i(v_i, \boldsymbol{b}_{-i}; v_i); \] note that this case also covers $v_i = \max_{j \neq i} b_j$ where decreasing $b_i$ to $v_i$ causes a tie with zero payoff for player $i$ (and everybody else);
3. If there is $k \neq i$ such that $b_k > \max_{j \neq k} b_j > v_i$, then \[ u_i(b_i, \boldsymbol{b}_{-i}; v_i) = 0 = u_i(v_i, \boldsymbol{b}_{-i}; v_i); \]
4. If there are $k \neq l$ such that $b_k = b_l = \max_j b_j > v_i$, then \[ u_i(b_i, \boldsymbol{b}_{-i}; v_i) = 0 = u_i(v_i, \boldsymbol{b}_{-i}; v_i). \]

9.2.3 First-Price Auction

Consider now the First-Price Auction. Here the highest bidder wins and pays his bid. Let us impose a (reasonable) assumption that no player bids more than his private value. We shall now show that there are no dominant strategies.

Assume the opposite, i.e. that there is a very weakly dominant strategy $s_i$ of player $i$.

Counter-example idea

Intuitively, if player $i$ wins against some bids of his opponents, then his bid is strictly larger than the bids of all his opponents. Hence he can slightly decrease his bid and still win.

Formally, assume that all other players bid 0, i.e. $b_j = 0$ for $j \neq i$, and let $v_i > 0$. If $s_i(v_i) > 0$, then \[ u_i(s_i(v_i), \boldsymbol{b}_{-i}; v_i) = v_i - s_i(v_i) < v_i - \frac 1 2 s_i(v_i) = u_i\left( \frac 1 2 s_i(v_i), \boldsymbol{b}_{-i}; v_i \right). \] On the other hand, if $s_i(v_i) = 0$, then \[ u_i(s_i(v_i), \boldsymbol{b}_{-i}; v_i) = 0 < v_i - \frac 1 2 v_i = u_i\left( \frac 1 2 v_i, \boldsymbol{b}_{-i}; v_i \right). \]

Hence $s_i$ cannot be very weakly dominant (and thus neither weakly, nor strictly). Similarly, we will show, using again a counter-example, that there is no ex-post Nash equilibrium. Therefore, let us assume the pure strategy profile $\boldsymbol{s} = (s_1, \dots, s_n)$ is an ex-post Nash equilibrium. Consider $0 < v_1 < \dots < v_{n-1}$ and define \[ M = \max \left\{s_i(v_i) \vert\; i \in \left\{1, \dots, n-1\right\}\right\}. \] Let $v_n = M + 1$. If player $n$ wins, i.e. $s_n(v_n) > M$, then \[\begin{align*} u_n(s_n(v_n), \boldsymbol{s}_{-i}(\boldsymbol{v}_{-i}); v_n) &= v_n - s_n(v_n) \\ &< v_n - (s_n(v_n) - \varepsilon) \\ &= u_n(s_n(v_n) - \varepsilon, \boldsymbol{s}_{-i}(\boldsymbol{v}_{-i}); v_n) \end{align*}\] for $\varepsilon\in (0, s_n(v_n) - M)$ (i.e. player $n$ may help himself by lowering his bid slightly). If player $n$ does not win, i.e. $s_n(v_n) \leq M < M + 1 = v_n$, then for $\varepsilon\in (0,1)$, e.g. $\varepsilon= \frac 1 2$, we get \[ u_n(s_n(v_n), \boldsymbol{s}_{-i}(\boldsymbol{v}_{-i}); v_n) = 0 < \frac 1 2 = u_n(v_n - \varepsilon, \boldsymbol{s}_{-i}(\boldsymbol{v}_{-i}); v_n), \] i.e. player $n$ may help himself by playing $v_n - \frac 1 2$. This concludes the counter-example.

9.2.4 Summary

To summarize, for Second-Price Auctions, there is an ex-post Nash equilibrium in weakly dominant strategies and it is incentive-compatible (players are self-motivated to bid their private value). On the other hand, for First-Price Auctions, there are no ex-post Nash equilibria or dominant strategies.

9.3 Bayesian Games

Definition 9.7 A Bayesian game $G = (N, (A_i)_{i \in N}, (T_i)_{i \in N}, (u_i)_{i \in N}, P)$ where $(N, (A_i)_{i \in N}, (T_i)_{i \in N}, (u_i)_{i \in N})$ is a strict incomplete-information game and $P$ is distribution on types, i.e.

$N = \left\{1, \dots, n\right\}$ is the set of players;
$A_i$ is a set of actions available to player $i$;
$T_i$ is a set if types available to player $i$ (recall that $T = \prod_{i = 1}^n T_i$ is the set of all type profiles and $A = \prod_{i = 1}^n A_i$ is the set of all action profiles);
$u_i$ is a type-dependent payoff function \[ u_i : A_1 \times \dots \times A_n \times T_i \to \mathbb{R}; \]
$P$ is a (joint) prior distribution over $T$ called common prior.

Note

Formally, $P$ is a probability measure over an appropriate measurable space on $T$. However, for simplicity, we will not go into measure theory and only consider two special cases: finite $T$ (in which case $P : T \to [0,1]$ so that $\sum_{\boldsymbol{t} \in T} P(\boldsymbol{t}) = 1$) and $T_i = \mathbb{R}$ for all $i$ (in which case we assume that $P$ is determined by a (joint) density function $p$ on $\mathbb{R}^n$).

A play then proceeds as follows:

a type profile $\boldsymbol{t} = (t_1, \dots, t_n) \in T$ is randomly chosen according to $P$;
then each player learns his type $t_i$ (and it is common knowledge that every player knows his own type but not the types of other players);
each player $i$ chooses his action based on $t_i$;
each player receives his payoff $u_i(\boldsymbol{a}; t_i)$.

A pure strategy for player $i$ is again a function $s_i : T_i \to A_i$. As before, we use $S$ to denote the set of all pure strategy profiles. We also assume that $u_i$ depends only on $t_i$ and not on $\boldsymbol{t}_{-i}$. This is called the private values model and can be used to model auctions. This model can be extended to common values by using $u_i(\boldsymbol{a}; \boldsymbol{t})$.

Moreover, we assume the common prior $P$. This means that all players have the same beliefs about the type profiles. This assumption is rather strong. More general models allow players to have

their own individual beliefs about types;
… beliefs about beliefs about types;
…. beliefs about beliefs about beliefs about types;
…. (we get an infinite hierarchy).

But there is a general result of Harsanyi saying that this complicated hierarchy is not necessary – it is possible to extend the type space in such a way that each player’s “extended type” describes his original type as well as all of his beliefs.

Example 9.2 Assume that player 1 may suspect that player 2 is angry with him/her but cannot be sure. In other words, there are two types of player 2 giving two different games. So formally, we have Bayesian game $G = (N, (A_i)_{i \in N}, (T_i)_{i \in N}, (u_i)_{i \in N}, P)$ where

$N = \left\{1,2\right\}$;
$A_1 = A_2 = \left\{O, F\right\}$;
$T_1 = \left\{t_1\right\}$ and $T_2 = \left\{t_2^1, t_2^2\right\}$;
the payoffs are given by Table 9.1;
$P(t_1, t_2^1) = P(t_1, t_2^2) = \frac 1 2$.

Table 9.1: Rows are chosen by player 1 with type $t_1$

The corresponding strategic-form game for $t_2 = t_2^1$
	$F$	$O$
$F$	$(2,1)$	$(0,0)$
$O$	$(0,0)$	$(1,2)$

The corresponding strategic-form game for $t_2 = t_2^2$
	$F$	$O$
$F$	$(2,0)$	$(0,2)$
$O$	$(0,1)$	$(1,0)$

Example 9.3 (Bayesian sealed-bid Single-item auction) Consider single-item sealed-bid auctions as Bayesian games: $G = (N, (B_i)_{i \in N}, (V_i)_{i \in N}, (u_i)_{i \in N}, P)$ where

the set of players $N$ is the set of bidders;
$B_i = [0, \infty)$ where each action $b_i \in B_i$ corresponds to the bid $b_i$;
$V_i = [0, \infty)$ where each type $v_i \in V_i$ corresponds to the private value $v_i$;
let $v_i \in V_i$ be the type of player $i$ (i.e. his private value), then given an action profile $\boldsymbol{b} = (b_1, \dots, b_n)$ (i.e. bids) we define
- First Price \[ u_i(\boldsymbol{b}; v_i) = \begin{cases} v_i - b_i, & b_i > \max_{j \neq i} b_j, \\ 0, & \text{otherwise}, \end{cases} \]
- Second Price \[ u_i(\boldsymbol{b}; v_i) = \begin{cases} v_i - \max_{j \neq i} b_j, & b_i > \max_{j \neq i} b_j, \\ 0, & \text{otherwise}; \end{cases} \]
$P$ is a probability distribution of the private values such that $P(\boldsymbol{v} \in [0, \infty)^n) = 1$. For example, we may (and will) assume that $v_i$ is chosen independently and uniformly from $[0, v_{\max}]$, where $v_{\max}$ is a fixed given number. Then $P \sim \mathrm{Unif}([0, v_{\max}]^n)$.

For now, let us assume that each player has only finitely many types, i.e. $T$ is finite. Given a type profile $\boldsymbol{t} = (t_1, \dots, t_n)$ we denote by $P(\boldsymbol{t}_{-i}\vert t_i)$ the conditional probability that the opponents of player $i$ have types $\boldsymbol{t}_{-i}$ conditioned on player $i$ having type $t_i$, i.e. \[ P(\boldsymbol{t}_{-i}\vert t_i) = \frac {P(t_i, \boldsymbol{t}_{-i})} {\sum_{\boldsymbol{t}'_{-i}\in T_{-i}} P(t_i, \boldsymbol{t}'_{-i})}. \]

Tip

Intuitively, $P(\boldsymbol{t}_{-i}\vert t_i)$ is the maximum information player $i$ may squeeze out of $P$ about possible types of others once he learns his own type $t_i$.

Given a pure strategy profile $\boldsymbol{s} = (s_1, \dots, s_n)$ and type $t_i \in T_i$ of player $i$ the expected payoff for player $i$ is \[ u_i(\boldsymbol{s}; t_i) = \sum_{\boldsymbol{t}_{-i}\in T_{-i}} u_i(\boldsymbol{s}(t_i, \boldsymbol{t}_{-i}); t_i) P(\boldsymbol{t}_{-i}\vert t_i). \]

Note

This is the conditional expected value of the measurable function $u_i \circ\boldsymbol{s} \circ(\boldsymbol{t}_{-i}\mapsto (t_i, \boldsymbol{t}_{-i}))$ given the random vector $\mathbf{\mathrm{t}}_{-i}$ from the distribution $P(\cdot \vert t_i)$: \[ u_i(\boldsymbol{s}; t_i) = \mathrm{\mathbb{E}}\left( u_i(\boldsymbol{s}(t_i, \mathbf{\mathrm{t}}_{-i}); t_i) \right). \]

Example 9.4 Let us continue with the Bayesian Battle of Sexes example, see Example 9.2, and recall $P(t_1, t_2^1) = P(t_1, t_2^2) = \frac 1 2$ and

Table 9.2: Rows are chosen by player 1 with type $t_1$

The corresponding strategic-form game for $t_2 = t_2^1$
	$F$	$O$
$F$	$(2,1)$	$(0,0)$
$O$	$(0,0)$	$(1,2)$

The corresponding strategic-form game for $t_2 = t_2^2$
	$F$	$O$
$F$	$(2,0)$	$(0,2)$
$O$	$(0,1)$	$(1,0)$

Consider strategies $s_1$ of player 1 and $s_2$ of player 2 defined by

$s_1(t_1) = F$;
$s_2(t_2^1) = F$ and $s_2(t_2^2) = O$.

Then

$u_1(\boldsymbol{s}; t_1) = \frac 1 2 \cdot 2 + \frac 1 2 \cdot 0 = 1$;
$u_2(\boldsymbol{s}; t_2^1) = 1$ and $u_2(\boldsymbol{s}; t_2^2) = 2$.

Example 9.5 (First-Price auction) Consider the first-price auction as a Bayesian game where the types of players are chosen uniformly and independently from $[0, v_{\max}]$. Consider a pure strategy profile $\boldsymbol{v} = (v_1/2, \dots, v_n/2)$ (i.e. each player $i$ plays $v_i/2$). Then \[\begin{align*} u_i(\boldsymbol{v}; v_i) &= P(\text{player }i\text{ wins}) \cdot v_i/2 + P(\text{player }i\text{ loses}) \cdot 0 \\ &= P(\text{all player except }i\text{ bid less than }v_i) \cdot v_i/2 \\ &\overset{\text{iid}}{=} \left( \frac {v_i} {v_{\max}} \right)^{n-1} \cdot v_i/2 \\ &= \frac {v_i^n}{2v_{\max}^{n-1}}. \end{align*}\]

9.3.1 Risk Aversion

We assume that players maximize their expected payoff. Such players are called risk neutral. In general, there are three kinds of players that can be described using the following experiment. A player can choose between two possibilities: either get 50$ surely, or get 100$ with probability $\frac 1 2$ and 0 with probability $\frac 1 2$, then

a risk-neutral player has no preference;
a risk-averse player prefers the first alternative;
a risk-seeking player prefers the second alternative.

9.3.2 Dominance and Nash Equilibria

A pure strategy $s_i$ weakly dominates $s_i' \neq s_i$ if for every $t_i \in T_i$ satisfying $s_i(t_i) \neq s_i'(t_i)$ and every $\boldsymbol{s}_{-i}\in S_{-i}$ it holds that \[ u_i(s_i, \boldsymbol{s}_{-i}; t_i) \geq u_i(s'_i, \boldsymbol{s}_{-i}; t_i) \] and there exists at least one $\boldsymbol{s}_{-i}$ such that the inequality is strict.

Tip

The other modes of dominance are defined analogously. Dominant strategies are, too, defined as usual.

Definition 9.8 A pure strategy profile $\boldsymbol{s} = (s_1, \dots, s_n) \in S$ in the Bayesian game is a pure strategy Bayesian Nash equilibrium (BNE) if for each player $i$ and each type $t_i \in T_i$ of player $i$ and every strategy $s_i' \in S_i$ we have that \[ u_i(\boldsymbol{s}; t_i) \geq u_i(s_i', \boldsymbol{s}_{-i}; t_i). \]

Example 9.6 Let us return to the Battle of Sexes as a Bayesian game, i.e. $P(t_1, t_2^1) = P(t_1, t_2^2) = \frac 1 2$ and

Table 9.3: Rows are chosen by player 1 with type $t_1$

The corresponding strategic-form game for $t_2 = t_2^1$
	$F$	$O$
$F$	$(2,1)$	$(0,0)$
$O$	$(0,0)$	$(1,2)$

The corresponding strategic-form game for $t_2 = t_2^2$
	$F$	$O$
$F$	$(2,0)$	$(0,2)$
$O$	$(0,1)$	$(1,0)$

We will use the following notation in this example: $(X, (Y,Z))$ means that player 1 players $X \in \left\{F,O\right\}$, and player 2 plays $Y \in \left\{F, O\right\}$ if their type is $t_2^1$ and $Z \in \left\{F,O\right\}$ otherwise. It is easy to check that $(F, (F,O))$ is a pure strategy Bayesian Nash equilibrium (BNE). Even though $O$ is preferred by player 2, the outcome $(O,O)$ cannot occur with a positive probability in any BNE, as

to ever meet at the opera, player 1 needs to play $O$;
the unique best response of player 2 to $O$ is $(O,F)$;
but $(O,(O,F))$ is not a Bayesian Nash equilibrium, because
- the excepted payoff of player 1 at $(O,(O,F))$ is $\frac 1 2$;
- on the other hand, the expected payoff of player 1 at $(F, (F,O))$ is 1.

9.3.3 Auctions as Bayesian Games

Consider the second-price sealed-bid auction as a Bayesian game where the types of players are chosen according to an arbitrary distribution.

Theorem 9.2 In a second-price sealed-bid auction, with any probability distribution $P$, the truth revealing profile of bids, i.e. $\boldsymbol{v} = (v_1, \dots, v_n)$, is a weakly dominant strategy profile.

Proof. The same exact proof as for the strict incomplete-information games can be repeated, as we did not assume the players to have a common prior.

Now consider the first-price sealed-bid auction as a Bayesian game with some prior distribution $P$. Note that bidding truthfully does not have to be a dominant strategy. For example, if player $i$ knows that (with high probability) his value $v_i$ is much larger than $\max_{j \neq i} v_j$, he will not waste money and bid less than $v_i$. So is there a pure strategy Bayesian Nash equilibrium?

Theorem 9.3 Assume that for all players $i$ the type of player $i$ is chosen independently and uniformly from $[0, v_{\max}]$. Consider a pure strategy profile $\boldsymbol{s} = (s_1, \dots, s_n) \in S$ where $s_i(v_i) = \frac {n-1} n v_i$ for every player $i$ and every private value $v_i$. Then $\boldsymbol{s}$ is a Bayesian Nash equilibrium.

Hence we can see that there are, in some sense, “optimal” strategies for players in both types of auctions, but then a question arises which one is better for the auctioneer (in terms of expected revenue)?

Consider the first and second price sealed-bid auctions. For simplicity, assume that the type (their private value) of each player is chosen independently and uniformly from $[0,1]$, then

in the first-price auction, players bid $\frac {n-1} n v_i$ Thus the probability distribution (the cumulative distribution function) of the revenue is \[ F(x) = P\left( \max_j \frac {n - 1} n v_j \leq x \right) = P\left( \max_j v_j \leq \frac {nx}{n-1} \right) = \left( \frac{nx}{n-1} \right)^n. \] It is then straightforward to show that the expected maximum bid in the first-price auction (i.e. the revenue) is $\frac {n-1} {n+1}$;
in the second-price auction, players bid $v_i$. However, the revenue is the expected second-largest value. Thus the distribution of the revenue² is \[ F(x) = \underbrace{P\left( \max_j v_j \leq x \right)}_{\text{tie or too small bids}} + \underbrace{\sum_{i = 1}^n P\left( v_i > x \; \land \; \forall j \neq i : v_j \leq x \right)}_{\text{one of the players bids enough}}. \] Amazingly, this also gives the expectation $\frac {n-1} {n+1}$.

This result is a special case of a rather general revenue equivalence theorem, first proven by Vickrey (1961) and then generalized by Myerson (1981).

Note

Both Vickrey and Myerson were awarded Nobel Price in economics for their contribution to the auction theory.

Theorem 9.4 (Revenue Equivalence) Assume that each of $n$ risk-neutral players has independent private values drawn from a common cumulative distribution function $F(x)$ which is continuous and strictly increasing on an interval $[v_{\min}, v_{\max}]$ (the probability $v_i \notin [v_{\min}, v_{\max}]$ is zero). Then any efficient auction mechanism in which any player with value $v_{\min}$ has expected payoff zero yields the same expected revenue.

Here efficient means that the auction has a symmetric and increasing Bayesian Nash equilibrium in each of $v_i$ and always allocates the item to the player with the highest bid.

Note

The Theorem 9.4 is not necessary for the exam.

	\(F\)	\(O\)
\(F\)	\((2,1)\)	\((0,0)\)
\(O\)	\((0,0)\)	\((1,2)\)

	\(F\)	\(O\)
\(F\)	\((2,0)\)	\((0,2)\)
\(O\)	\((0,1)\)	\((1,0)\)

	\(F\)	\(O\)
\(F\)	\((2,1)\)	\((0,0)\)
\(O\)	\((0,0)\)	\((1,2)\)

	\(F\)	\(O\)
\(F\)	\((2,0)\)	\((0,2)\)
\(O\)	\((0,1)\)	\((1,0)\)

	\(F\)	\(O\)
\(F\)	\((2,1)\)	\((0,0)\)
\(O\)	\((0,0)\)	\((1,2)\)