Every finite game has an equilibrium point.

— John Nash, Non-Cooperative Games, doctoral thesis (1950)

Some games have no equilibrium at all if each player picks a fixed move. The simplest is odds and evens. Ana calls “evens”, Bruno calls “odds”, and each shows one or two fingers. If the sum is even, Ana wins a point; if it is odd, Bruno wins. Reducing each choice to “one” or “two” fingers, the payoffs are:

Ana / Bruno 1 finger 2 fingers
1 finger (1, −1) (−1, 1)
2 fingers (−1, 1) (1, −1)

Test the four combinations: in each one, whoever lost would gain by switching their move. There is no equilibrium in fixed moves. It makes sense: whoever always plays the same thing is beaten as soon as the other notices.

Randomising is the best strategy

The way out is to mix: to choose at random, with certain probabilities. A mixed strategy is a probability distribution over the moves. Suppose Ana shows 1 finger with probability $p$ and Bruno with probability $q$, drawn independently.

If Ana shows 1 finger, her expected payoff is $q\cdot1+(1-q)\cdot(-1)=2q-1$. If she shows 2 fingers, it is $q\cdot(-1)+(1-q)\cdot1=1-2q$. Ana is only willing to mix the two moves if they give her the same payoff, that is, if Bruno leaves her indifferent:

$$2q-1=1-2q\quad\Longrightarrow\quad q=\frac12.$$

By the same reasoning, Bruno only mixes if $p=\frac12$. The only equilibrium is each player showing 1 or 2 fingers with a 50% chance. Against this mix, no strategy, pure or mixed, gives the other player an expected payoff above zero.

Nash’s theorem

This is the great result of the 1950 thesis: every game with a finite number of players and moves has at least one Nash equilibrium, if mixed strategies are allowed.

The proof uses a fixed-point theorem. For each combination of mixed strategies, build another one, in which each player shifts their mix a little towards the moves that would give them a higher payoff. This defines a continuous function from the set of combinations to itself. That set is like a ball without holes, and Brouwer’s theorem guarantees that every continuous function from a ball to itself has a fixed point: a combination the function does not move. A point that does not move is exactly a combination in which nobody wants to change: an equilibrium.

The theorem guarantees that the equilibrium exists, but does not say it is unique, nor that it is easy to compute. Today we know that, in large games, finding a Nash equilibrium can be an extremely hard computational problem.

The penalty kick

The most famous example of a mixed strategy happens in stadiums. In a penalty, the kicker chooses a corner, and the goalkeeper must dive before seeing the ball. For a right-footed kicker, the natural corner is their left, which is the goalkeeper’s right. Suppose the chances of a goal are these:

Kicker / Goalkeeper Keeper dives to the natural corner Keeper dives to the other corner
Shoots to the natural corner 60% 95%
Shoots to the other corner 90% 70%

The numbers are rounded, but close to real data from European football: the kicker almost never misses when the goalkeeper dives the wrong way, and the natural corner is the most comfortable to shoot at, but also the one the goalkeeper defends best when he guesses the side.

If the kicker shoots to the natural corner with probability $p$, the goalkeeper is indifferent when both dives give the same chance of a goal:

$$0.60p+0.90(1-p)=0.95p+0.70(1-p)\quad\Longrightarrow\quad0.20=0.55p\quad\Longrightarrow\quad p\approx0.36.$$

And if the goalkeeper dives to the natural corner with probability $q$, the kicker is indifferent when

$$0.60q+0.95(1-q)=0.90q+0.70(1-q)\quad\Longrightarrow\quad0.25=0.55q\quad\Longrightarrow\quad q\approx0.45.$$

In equilibrium, the kicker shoots to the natural corner only 36% of the time, and the goalkeeper dives there 45% of the time. The chance of a goal is about 79%. The explanation: when the goalkeeper guesses the side, the natural corner is the easier one to defend, 60% goals against 70%, and the kicker compensates by using the other corner more. But he cannot use it all the time, or the goalkeeper would start diving only that way.

Exercise: in odds and evens, if Bruno shows 1 finger with probability 0.8, what is Ana's best response?

Showing 1 finger, Ana wins on average $2(0.8)-1=0.6$. Showing 2, she wins $-0.6$. She should always show 1 finger. Any mix other than 50% can be exploited.

Exercise: in rock, paper, scissors, what is the Nash equilibrium?

By symmetry, each player chooses each of the three options with probability $\frac13$. Against this mix, any choice wins, draws and loses with the same chance, $\frac13$, and the expected payoff is zero. If a player played rock more than $\frac13$ of the time, the other would start playing more paper.

Sources: John F. Nash, “Non-cooperative games”, Annals of Mathematics 54 (1951) · Ignacio Palacios-Huerta, “Professionals play minimax”, The Review of Economic Studies 70 (2003) · Avinash Dixit and Barry Nalebuff, The Art of Strategy (Norton, 2008).

All topics on John Nash · ← The Nash equilibrium: nobody does better alone · The Nash bargaining solution →

Image credits.