An equilibrium point is an n-tuple such that each player’s mixed strategy maximizes his payoff if the strategies of the others are held fixed.

— John Nash, Proceedings of the National Academy of Sciences (1950)

In 1944 John von Neumann and the economist Oskar Morgenstern published Theory of Games and Economic Behavior, a huge book that turned strategic decisions into mathematics: card games, wars, markets. Von Neumann’s great result applied to two-player zero-sum games, in which what one wins the other loses, like chess or poker. But most of life is not like that: in a trade deal, a negotiation or traffic, both sides can win together, or lose together.

In 1949 a 21-year-old student found the idea that worked for any game, with any number of players.

The idea

In a game, each player chooses a strategy, and each one’s outcome depends on everyone’s choices. A Nash equilibrium is a combination of strategies in which no player can do better by changing strategy alone, with the others keeping theirs.

In symbols: if $s_i^*$ is the strategy of player $i$, $s_{-i}^*$ collects those of the others, and $u_i$ is the payoff of player $i$, then

$$\boxed{u_i(s_i^*,s_{-i}^*)\geq u_i(s_i,s_{-i}^*)\quad\text{for every player }i\text{ and every strategy }s_i.}$$

In an equilibrium, each player is doing the best they can, given what the others are doing. Nobody regrets their own choice.

The square or the café?

Ana and Bruno agreed to meet in the afternoon, but forgot to say where, and they have no phones. Each can go to the square or to the café. Both prefer the café, but what matters most is meeting. The payoffs, first Ana’s and then Bruno’s, are:

Ana / Bruno Square Café
Square (2, 2) (0, 0)
Café (0, 0) (3, 3)

Test each combination. At (Café, Café), if Ana switches alone to the square, she goes from 3 to 0; the same holds for Bruno. Nobody wants to change: it is an equilibrium. At (Square, Square), switching alone takes each from 2 to 0: also an equilibrium! But at (Square, Café), Ana would gain by going to the café, so it is not an equilibrium.

The game has two equilibria, and one is better than the other for both. Nash’s concept says which combinations are stable, but not which of them will happen. In practice, convention decides: custom, the place the two usually go.

The prisoner’s dilemma

In 1950, the same year as Nash’s thesis, two researchers at the RAND Corporation, Merrill Flood and Melvin Dresher, invented a game to test the idea, and the mathematician Albert Tucker told it as a story of two prisoners. The police arrest two accomplices and question them in separate rooms. Each can stay silent or betray the other. The sentences, in years in prison, are:

A / B Silent Betray
Silent (1, 1) (10, 0)
Betray (0, 10) (5, 5)

Think like prisoner A. If B stays silent, A gets 1 year by staying silent and 0 by betraying: better to betray. If B betrays, A gets 10 by staying silent and 5 by betraying: better to betray. Whatever B chooses, betraying is better for A. The same reasoning holds for B. The only Nash equilibrium is (Betray, Betray), with 5 years each.

But if both stayed silent, they would get only 1 year each! The equilibrium is bad for both, and neither can leave it alone. It is the dilemma of many real situations: the arms race, overfishing, deforestation, pollution. Each person, acting in their own interest, produces an outcome nobody wants.

Exercise: in the meeting table, if Ana is at the square and Bruno at the café, who has an incentive to change?

Both. Ana, switching alone to the café, goes from 0 to 3; Bruno, switching alone to the square, goes from 0 to 2. But if both change at the same time, they still miss each other. The equilibrium test always looks at one player changing at a time.

Exercise: in the prisoner's dilemma, change the sentence of the one who stays silent alone from 10 to 3 years. Does the equilibrium change?

Now, if B betrays, A gets 3 by staying silent and 5 by betraying: better to stay silent. If B stays silent, A gets 1 by staying silent and 0 by betraying: better to betray. Betraying is no longer always better. The pure-strategy equilibria become (Silent, Betray) and (Betray, Silent): each prefers to do the opposite of the other. The outcome of a game depends heavily on the numbers in the table.

Sources: John F. Nash, “Equilibrium points in n-person games”, Proceedings of the National Academy of Sciences 36 (1950), doi:10.1073/pnas.36.1.48 · William Poundstone, Prisoner’s Dilemma (Doubleday, 1992) · 1994 Nobel Prize in Economics, Nobel Foundation.

All topics on John Nash · ← The game of Hex: why the first player wins · Mixed strategies: the penalty kick and odds and evens →

Image credits.