Proving the beauty of a mind

In the previous Theory Lunch talk we introduced the notion of Nash equilibrium for games in normal form. Today, we went through the proof of Nash’s theorem of existence of mixed strategy Nash equilibria for finite games in normal form.

Let us recall the basic notions. In a game in normal form we have:

A set $N$ of players.
A set $S_i$ of strategies for each player.
A collection of utility functions $\{u_i\}_{i \in N}$ which associate to each strategic profile $s \in S = \prod_{i \in N} S_i$ a real number, such that $u_i(s)$ is the utility player $i$ gets from the strategic profile $s$ .

A Nash equilibrium for a game in normal form is a strategic profile $s$ such that, for every player $i$ and every strategy $s'_i$ feasible for player $i$ , it is the case that $u_i(s_i \mid s_{-i}) \geq u_i(s'_i \mid s_{-i})$ . We had seen that not every finite game in normal form admits a pure strategy Nash equilibrium: so, we introduced randomization.

A mixed strategy for player $i$ is a probability distribution $\mu_i : \mathcal{P}(S_i) \to [0,1]$ . If $S_i$ is finite, this is the same as assigning values $p_{i,j} = \mu_i(s_{i,j})$ for $j = 1, \ldots, |S_i|$ . A mixed strategy profile is a collection $\mu = \{\mu_i\}_{i \in N}$ of mixed strategies for each player. A mixed strategy Nash equilibrium is a mixed strategy profile $\mu = \{\mu_i\}_{i \in N}$ such that, for every player $i$ and every mixed strategy $\mu'_i$ feasible for player $i$ ,

$\mathbb{E}(u_i \mid \mu_i, \mu_{-i}) \geq \mathbb{E}(u_i \mid \mu'_i, \mu_{-i})$ .

The idea behind Nash’s proof goes as follows. If the game is finite, then a mixed strategy for player $i$ is identified with a point of

$\Delta_i = \left\{ x \in \mathbb{R}^{|S_i|} \mid x_j \geq 0 \, \forall j \, , \, \sum_{j=1}^{|S_i|} x_j = 1 \right\} \, :$

therefore, mixed strategy profiles can be identified with points of

$\Delta = \prod_{i=1}^{|N|} \Delta_i \subseteq \mathbb{R}^{|S_1| + |S_2| + \ldots + |S_{|N|}|} \, ,$

which is compact and convex as all of its components are. Mixed strategy Nash equilibria are those points of $\Delta$ where each pure strategy $s_{i,j}$ , $i \in N$ , $j = 1, \ldots, |S_i|$ , is used in the most efficient way: by relaxing the condition and allowing a small “slack” with respect to such most efficient way, it is possible to define a continuous transformation of mixed strategy profiles into mixed strategy profiles, which will have a fixed point because of the Brouwer fixed-point theorem. By gradually reducing the slack, a mixed strategy Nash equilibrium is found as a limit point of such approximations.

Suppose player $i$ has available the pure strategies $s_{i,j}$ for $j = 1, \ldots, |S_i|$ . Let $\mu$ be an arbitrary mixed strategy profile and $k \geq 1$ be an arbitrary integer. Consider the following quantities:

$u_{i,j}(\mu) = \mathbb{E}(u_i \mid s_{i,j}, \mu_{-i})$ .
$w_i(\mu) = \max_j u_{i,j}(\mu)$ .
$\Psi_{i,j}(\mu, k) = u_{i,j}(\mu) - w_i(\mu) + \dfrac{1}{k}$ .
$\Psi_{i,j}^+(\mu, k) = \max \left( \Psi_{i,j}(\mu, k), 0 \right)$ .

Given $i \in N$ , the sum $\sum_{j=1}^{|S_i|} \Psi_{i,j}^+ (\mu, k)$ is bounded from below by $\max_{j \in \{1, \ldots, |S_i|\}} \Psi_{i,j}^+ (\mu,k) = 1/k$ , hence the functions

$P_{i,j}(\mu,k) = \dfrac{\Psi_{i,j}^+(\mu, k)}{\sum_{j=1}^{|S_i|} \Psi_{i,j}^+ (\mu, k)}$

are continuous and nonnegative and satisfy $\sum_j P_{i,j}(\mu,k) = 1$ whatever $i \in N$ and $k \geq 1$ are. As a consequence, the functions

$F_k = \lambda (\mu : \Delta) \,.\, (P_{i,j}(\mu,k) \, \mathtt{for} \, j \, \mathtt{in} \, S_i \, \mathtt{for} \, i \, \mathtt{in} \, N) \,,$

that is,

$(F_k(\mu))_i(s_{i,j}) = P_{i,j}(\mu,k) \; \forall i \in N \, \forall j \in \{1, \ldots, |S_i|\} \,,$

are continuous transformations of $\Delta$ into itself. Let $\mu_k$ be a fixed point of $F_k$ , whose existence is ensured by the Brouwer fixed-point theorem: as $\Delta$ is compact, the sequence $\{\mu_k\}_{k \geq 1}$ has a limit point $\overline{\mu}$ .

Suppose, for the sake of contradiction, that $\overline{\mu}$ is not a mixed strategy Nash equilibrium. Then there must be a player $i$ and a mixed strategy $\mu_i$ such that $\mathbb{E}(u_i \mid \mu_i, \overline{\mu}_{-i}) > \mathbb{E}(u_i \mid \overline{\mu})$ . The only way this may happen, is that some pure strategy $s_{i,j}$ is used suboptimally by $\overline{\mu}$ , that is,

$0 < u_{i,j}(\overline{\mu}) < w_i(\overline{\mu}) \,.$

Choose $\varepsilon > 0$ and $k \geq 1$ so that:

$\mu_k$ belongs to a subsequence converging to $\overline{\mu}$ .
$u_{i,j}(\overline{\mu}) - w_i(\overline{\mu}) < -\varepsilon$ .
$\left| \left( u_{i,j}(\mu_k) - w_i(\mu_k) \right) - \left( u_{i,j}(\overline{\mu}) - w_i(\overline{\mu}) \right) \right| < \varepsilon/2$ .
$1/k < \varepsilon/2$ .

Points 2 and 3 tells us that $u_{i,j}(\mu_k) - w_i(\mu_k)$ is strictly smaller than $-\varepsilon/2$ : this, together with point 4, yields $\Psi_{i,j}(\mu_k) < 0$ , thus $\Psi_{i,j}^+(\mu_k) = 0$ . But $\mu_k$ is a fixed point for $F_k$ , so

$u_{i,j}(\mu_k) = u_{i,j}(F_k(\mu_k)) = \dfrac{\Psi_{i,j}^+(\mu_k)}{\sum_{j=1}^{|S_i|} \Psi_{i,j}^+(\mu_k)} = 0$ :

and as $k$ may be taken arbitrarily large and $|\mu_k - \overline{\mu}|$ be made arbitrarily small, we must conclude that $u_{i,j}(\overline{\mu}) = 0$ too. This is a contradiction.