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:

  1. \mu_k belongs to a subsequence converging to \overline{\mu}.
  2. u_{i,j}(\overline{\mu}) - w_i(\overline{\mu}) < -\varepsilon.
  3. \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.
  4. 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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s