How Nash proved the existence of Nash Equilibrium in mixed strategies

In just one page, Nash proved one of the most important results in Game Theory

Nash equilibrium is usually defined as a strategy profile in which each player’s strategy is optimal given the strategies chosen by the others. In some games, however, no such profile exists if players are restricted to pure strategies, that is, to choosing a single action with probability one. A standard example is Matching Pennies. Two players simultaneously choose either Heads or Tails. If the choices match, Player 1 wins; if they differ, Player 2 wins. The names Heads and Tails are only labels for actions: the players are not required to toss coins. Consider each of the four possible pure-strategy profiles.

If both players choose the same action, Player 2 can switch to the opposite action and improve their payoff. If they choose different actions, Player 1 can switch to match Player 2's action and improve their payoff. Consequently, from every pure-strategy profile at least one player has a profitable unilateral deviation. Since a Nash equilibrium is a strategy profile from which no player wishes to deviate unilaterally, no pure-strategy Nash equilibrium exists.

Nash’s contribution was to make the strategy space bigger. Instead of choosing only Heads or only Tails, he introduced the possibility that a player chooses a probability distribution over the available actions: for example, Heads with probability (p) and Tails with probability (1-p). These probability distributions are called mixed strategies. Nash proved that when every player in a finite game is allowed to use mixed strategies, an equilibrium always exists. In this article, I will try to explain his one page proof. It’s a great example that a impact is not necessarily correlated with length.

The proof

The proof can be summarised, explaining each concept he uses, as follows:

The essence of Nash’s argument is to transform the problem of finding an equilibrium into a fixed-point problem. Rather than attempting to construct an equilibrium directly, he studies the geometry of the mixed-strategy space and the mathematical properties of the best-response correspondence. Once these objects are shown to satisfy the hypotheses of Kakutani’s Fixed Point Theorem, the existence of a fixed point follows. This fixed point has a natural game-theoretic interpretation: it is a strategy profile in which every player’s chosen mixed strategy is a best response to the strategies of the others. Consequently, no player can unilaterally increase their expected payoff by deviating, which is precisely the definition of a Nash equilibrium. Notice that the proof is an existence argument, it does not provide any guess or computation about what must be the equilibrium(s).

References

Nash, J. F. (1950). Equilibrium points in n-person games. Proceedings of the National Academy of Sciences of the United States of America, 36(1), 48–49. http://www.jstor.org/stable/88031