Nash Equilibrium: Why Nobody Wants to Move First

Game Theory, Part 5 of 9

Princeton, 1949. John Nash, a 21-year-old graduate student, arranges a meeting with John von Neumann — one of the most famous mathematicians in the world and the author of the minimax theorem. Nash wants to show him an idea he has been working on.

According to Nash's biographer Sylvia Nasar, von Neumann cut him off almost at once: "That's trivial, you know. That's just a fixed point theorem."

Nash did not drop the idea. In November 1949 his short note was submitted to the Proceedings of the National Academy of Sciences. It ran to two pages. In 1950 Nash defended a doctoral thesis on the same subject, and in 1994 it earned him the Nobel Prize in Economic Sciences, shared with John Harsanyi and Reinhard Selten.

So what was in that "trivial" idea?

One question

You can test for a Nash equilibrium with a single question, put to each player in turn:

"Knowing what the others did, would you change your choice?"

If nobody wants to change their choice on their own, it's an equilibrium. If even one player does, it isn't.

Let's put this question to the table from the previous part, the one about two prisoners.

Both stay silent. Does anyone want to change? Yes: if your accomplice stays silent, confessing gets you freedom instead of a year. Not an equilibrium.

Both confess. Does anyone want to change? No: if your accomplice has confessed, staying silent gets you ten years instead of five. An equilibrium.

Here's the key thing to remember: an equilibrium is not the same as the best outcome. A year each is better than five each. But everyone wants to escape the "best" outcome, while nobody wants to leave the bad one. An equilibrium describes not what is good, but what is stable.

For any two-player table, there's a quick way to find the equilibria without long reasoning. Go through each column and mark the cell where your result is best: that's your best reply to that move by your opponent. Then go through each row and mark the cell that's best for your opponent.

Cells with two marks are the equilibria. If there are none, an equilibrium exists only with random moves — but more on that later.

What Nash actually proved

In Part 3 we met von Neumann's theorem: a two-player zero-sum game has a value. But most real situations are different: there are often more than two players, and their interests aren't always opposed.

Nash proved that an equilibrium exists in any finite game, with any number of players and any payoffs. There is one condition: sometimes players have to choose their moves at random with certain probabilities, as in rock-paper-scissors. Those mixed strategies are the subject of Part 7.

For chess, nothing changes. In zero-sum games a Nash equilibrium is the same thing as minimax: neither side can improve the result by changing only its own play. So the "perfect play" from Part 2 of the series is a Nash equilibrium too.

When there is more than one

Here is a game millions of people play every day. Two drivers are heading towards each other. Each chooses which side of the road to keep to (payoffs illustrative):

There are two equilibria here: "both left" and "both right". Neither is better than the other. All that matters is that everyone chooses the same.

But leaving the equilibrium everyone is in is very hard. A driver who decides to be the first to drive on the right in a left-driving country changes nothing — except causing an accident.

That was exactly Sweden's trap. The country drove on the left, even though its Nordic neighbours and most of mainland Europe drove on the right. In a 1955 referendum, 82.9% of voters rejected a change. But in 1963 parliament approved the reform anyway.

The switch was set for Sunday, 3 September 1967. At 4:50 a.m. all traffic stopped. At 5:00 it started again — on the right.

In game-theory terms, this was a move from one equilibrium to another. Nobody would have made it alone. So everyone's behaviour had to change, all at once.

How people choose an equilibrium

If there are several equilibria, how do players settle on one without talking?

In his 1960 book, the economist Thomas Schelling described a question he put to students: you have to meet a stranger in New York, but you haven't agreed on a place or a time. Where and when do you go? The most common answer: at noon, at the information booth in Grand Central Terminal.

In theory, any place and any hour is an equilibrium: if both of you go there, neither gains by going elsewhere. But people choose what stands out — what each expects the others to expect. Schelling called this a focal point. In the road game, the focal point is habit, the law, or what the neighbours do.

The mistake in A Beautiful Mind

In the film A Beautiful Mind (2001), there's a scene in which the young Nash supposedly discovers his idea. A group of friends is sitting in a bar. They have all noticed the same young woman and are about to approach her.

Nash explains: if they all go for her, they'll get in each other's way. And then her friends will turn them down too, because nobody wants to be second choice. So nobody should approach her, and they should all approach her friends instead.

It's a good scene, but it isn't a Nash equilibrium. Ask our question. Everyone has gone to the friends.

Does anyone want to change? Yes: each of them, alone, would now rather approach the woman nobody has approached. The plan holds only because of an agreement.

The equilibrium in this story is different: exactly one of them approaches her, and the rest go to her friends. Then nobody gains by changing their choice. The mathematician José-Manuel Rey pointed this out back in 2008 in Plus magazine.

The irony is that the film's scene shows something closer to a collective agreement. Agreements like that — coalitions — are exactly what Nash deliberately left out in his 1951 paper. His theory is about players who each decide for themselves.

What to take away

Nash's question is useful far beyond tables.

• Stable doesn't mean good. If everyone is unhappy but nobody changes their behaviour, you are probably looking at a bad equilibrium. Telling one person to "just act differently" isn't enough: on their own, it doesn't pay.
• You leave an equilibrium together. As in Sweden, it takes a change of rules, an agreement or a shared signal after which the new behaviour pays for everyone.
• When there are several equilibria, what everyone notices decides. Habit, tradition, an obvious landmark. Whoever sets the focal point often decides where the group ends up.

At the chessboard, the same question is the basis of reviewing a game. As you go through it, check: knowing how your opponent replied, would you change your move? The moves where the answer is "yes" are the places where your play wasn't an equilibrium.

Exercise

1. Two friends have agreed to spend the evening together, but they've lost contact. One would rather go to the cinema, the other to a concert. But both most want to be together. Payoffs: both at the cinema — 2 and 1; both at the concert — 1 and 2; different places — 0 and 0. Find all the equilibria.
2. Back to the film scene. Is it an equilibrium if two of the friends approach the same woman?

Answers are at the end.

Questions for discussion

• Name a bad equilibrium from your life or work that nobody wants to be the first to leave. What could be its "Dagen H" — Sweden's switch day?
• Has a focal point ever helped you find someone, or reach an agreement without words?
• Von Neumann called Nash's idea trivial. Has an "obvious" thought of yours ever turned out to be valuable to others?

Next in the series: "An Eye for an Eye, but with Forgiveness", on Robert Axelrod's tournaments, in which computer programs played the prisoner's dilemma against each other again and again — and on which strategy won.

Answers. 1) There are two equilibria: both at the cinema and both at the concert. In either case, whoever goes somewhere else alone gets 0 instead of 1 or 2. There is also a third, mixed equilibrium, where each chooses at random. We'll come back to it in Part 7. 2) No. Both of them get turned down, because they get in each other's way. So either of them would do better going to the friends. The equilibrium is when exactly one approaches her.

Discuss below