Read 3 of 5

Nash equilibrium

What can we predict when nobody has a dominant strategy?

Dominant and dominated strategies don't always exist. In most games, a player's best choice depends on what the other player does.

This reading introduces the tool for those games. We define best responses and Nash equilibrium, find the equilibria of several classic games, and ask what we can predict when a game has more than one equilibrium, or none.

3.1

Best responses

Alice and Bob are deciding where to spend the evening. Alice prefers the ballet and Bob the opera, but both would rather be together than apart. They choose separately, without being able to talk first.

Being together at your favorite is worth 3, together at the other's favorite 1, and apart 0.

Start with dominance

Question 1 of 1

Does either player have a dominant strategy or a dominated strategy in this game?

Choose one answer.

Neither has a dominant strategy. If Bob goes to the ballet, Alice should too; if Bob goes to the opera, Alice should too. Nothing is dominated either, so dominance can't help.

We need a weaker idea. A is a strategy that gives a player the highest payoff against a particular choice of the others. Ballet is Alice's best response to Bob's Ballet, and Opera is her best response to Bob's Opera. Dominance asks whether a strategy is best against everything the rival might do. A best response only has to be best against one thing.

Best responses are easy to find in a matrix. For the row player, go column by column and underline the highest red payoff in each column. For the column player, go row by row and underline the highest blue payoff in each row.

3.2

Nash equilibrium

A is a combination of strategies, one for each player, in which every player's strategy is a best response to the others'. Given what everyone else is doing, no player can do better by changing its own strategy. Each player can say, "Given what you're doing, I'm doing the best I can."

The idea is named after the mathematician John NashJohn Forbes Nash Jr. (1928–2015) was an American mathematician at Princeton. His 1950 doctoral thesis, 28 pages long, defined the equilibrium that now carries his name. He shared the 1994 Nobel Memorial Prize in Economic Sciences with John Harsanyi and Reinhard Selten for their work on game theory. His life is the subject of the book and film A Beautiful Mind.Photo: Peter Badge / Typos1, Wikimedia Commons, CC BY-SA 3.0, who showed in 1950 that equilibria of this kind exist in a very wide class of games.

There are several ways to read a Nash equilibrium, and each is useful in a different situation.

  • No regrets. Once the choices are revealed, no player looks back and wishes it had chosen differently, given what the others actually did.
  • A self-enforcing agreement. Think of an equilibrium as an unwritten handshake deal. There's no court or referee to enforce it, so it survives only if keeping it is in each player's own interest. In a Nash equilibrium it is: as long as the others keep the deal, breaking it hurts the player who breaks it.
  • A resting point. Players may not know the equilibrium in advance. But suppose they adjust by trial and error, each changing its choice whenever it can do better. They stop changing only at a Nash equilibrium, and once they're there, nothing pushes them away.
  • A self-fulfilling convention. If everyone expects everyone else to behave in a certain way, and that behavior is a best response to those expectations, the expectations confirm themselves. Australians drive on the left because they expect everyone else to, and everyone else does.

In a matrix, a Nash equilibrium is a cell in which both payoffs are underlined. In the ballet game there are two: (Ballet, Ballet) and (Opera, Opera). In the cafés' game there is one, ($4, $4).

The cafés' game, with each café's best responses shaded in its color. The cell where both are best responses is the Nash equilibrium.

How does this relate to the tools of Reading 2?

Dominance and Nash equilibrium

Question 1 of 2

Suppose every player has a dominant strategy and plays it. Is the outcome a Nash equilibrium?

Choose one answer.

The same holds for iterated elimination. If it leaves one cell, that cell is the only Nash equilibrium of the game.

Three things a Nash equilibrium doesn't claim are worth spelling out, because each is a common mistake.

It needn't be good for the players. An equilibrium is stable, not desirable. In the cafés' game both cafés earn 200 at ($4, $4). Both would earn 300 at ($6, $6), but that cell isn't an equilibrium: if Café B charges $6, Café A earns 400 by switching to $4. So the outcome both prefer doesn't last on its own, and the outcome that lasts is worse for both. The next section comes back to this.

It needn't be unique. A game can have more than one equilibrium. The ballet game has two, (Ballet, Ballet) and (Opera, Opera), and in each of them neither player wants to switch alone. The definition tells us which outcomes are stable, but not which of them will happen. Section 3.4 asks what decides that.

It doesn't explain how the players got there. The definition is a test we apply to a combination of choices: is each player doing its best, given what the others do? It says nothing about the process that led there. The players may have reasoned their way to it, learned it over time or simply agreed on it. They needn't even know that it's an equilibrium. The definition only says that once they're there, nobody wants to leave.

Compare the competitive equilibrium of Week 3. There, no buyer or seller wanted to change their plans at the market price. Here, no player wants to change its strategy, given the others' strategies. Both are states that nobody wants to leave.

Find the equilibria

Go back to Alice and Bob's 4 × 5 game from Reading 1. Click a payoff to mark it as a best response: Alice's best payoff in each column and Bob's best payoff in each row. Then press Check.

Question 1 of 1

Which cells are Nash equilibria?

Choose one answer.

3.3

The cafés: a prisoner's dilemma

Go back to the cafés. In Reading 2 we saw that $4 is a dominant strategy for each café, so the only Nash equilibrium is ($4, $4). Look at where that leaves them: 200 each, when they could have had 300 each by both charging $6. Nobody made a mistake. Each café did what was best for itself, whatever the other did, and the result is worse for both.

A game with this structure is called a . The name comes from the original story. Two suspects are questioned separately. Each is better off confessing, whatever the other does, but if both stay silent they both get a lighter sentence than if both confess.

The game was first designed in 1950 by the mathematicians Merrill FloodMerrill M. Flood (1908–1991) was an American mathematician and one of the pioneers of operations research. At RAND he worked on the traveling salesman problem and, with Melvin Dresher, ran the first experiment with the prisoner's dilemma in January 1950: two RAND researchers played the game 100 times in a row.Reference: M. M. Flood (1958), “Some experimental games,” Management Science 5(1), 5–26. and Melvin DresherMelvin Dresher (1911–1992) was a Polish-born American mathematician at RAND, where he worked on game theory and its military applications. He wrote Games of Strategy: Theory and Applications (1961).Reference: M. Dresher (1961), Games of Strategy: Theory and Applications, Prentice-Hall. at the RAND Corporation. Soon after, the Princeton mathematician Albert W. TuckerAlbert W. Tucker (1905–1995) was a Canadian-born mathematician at Princeton. He supervised John Nash's doctoral thesis, and the Karush–Kuhn–Tucker conditions in optimization carry his name. In 1950 he presented Flood and Dresher's game to a group of psychologists at Stanford and needed a story to explain it, so he invented the two prisoners.Reference: A. W. Tucker (1983), “The mathematics of Tucker: a sampler,” Two-Year College Mathematics Journal 14(3), 228–232, which reprints his 1950 note “A two-person dilemma.” formalized it, told the story of the two prisoners and gave the game its name. The Stanford Encyclopedia of Philosophy has more on its history.

The structure shows up wherever individually sensible moves add up to a collectively bad outcome: fare wars between airlines, rival firms escalating their advertising, and price cuts that each firm makes to win customers from the other.

What can the cafés do about it? Asking the other café to keep its price at $6 doesn't help. Even if Café B promises, Café A knows that B still earns more by charging $4, whatever A does, and a promise that goes against the promiser's interest isn't believed. The way out is to change the payoffs, so that undercutting no longer pays. There are three broad ways to do that.

Repetition. In the game above the cafés meet once. In reality they set prices every day. A café that undercuts today earns 400 instead of 300, a gain of 100. But its rival can respond by charging $4 from tomorrow on, and then the undercutter earns 200 a day instead of 300 for as long as that lasts. If the future matters enough, the gain today isn't worth the loss later, and both cafés can keep charging $6. Reading 5 works out when that happens.

Commitment. A café can change its own payoffs in advance. Suppose Café A promises its customers to match any lower price in the street. Now if Café B cuts to $4, A's price falls to $4 too, so B doesn't take every customer. It only splits them at a lower price, 200 instead of 300, and undercutting stops paying. The weekly challenge, Hats, asks when a price-matching promise like this works and when it doesn't.

Changing the game. The cafés are in a dilemma because their coffee is the same, so the cheaper café takes every customer. If they make their products different, say one focuses on specialty pour-over and the other on quick takeaway, a lower price no longer wins all the customers, and the gain from undercutting shrinks. Week 7 studies competition between firms whose products differ.

3.4

Several equilibria

Three classic games each have two equilibria, for different reasons.

Chicken. Two drivers race toward each other on a narrow road, and each can swerve or stay on course. If one swerves and the other doesn't, the one who swerves is the “chicken” and loses face, with a payoff of \(-1\), while the one who stays wins, with 1. If both swerve, nobody wins or loses, and both get 0. If neither swerves, they crash, the worst outcome for both, at \(-10\) each.

If Alice swerves, Bob's best response is to stay, 1 against 0. If Alice stays, Bob's best response is to swerve, \(-1\) against \(-10\). The same holds for Alice, so there are two equilibria, (Swerve, Stay) and (Stay, Swerve). Each player prefers the one in which the other swerves.

Chicken is a game of nerve. Each driver wants the other to back down, and the worst outcome is that neither does. The same structure appears whenever two parties each hope the other will give way: two firms that each want the other to leave a market too small for both, a union and a management heading for a strike, or two countries in a standoff. In chicken, credibility is everything. A driver who could convince the other that it will never swerve, for example by visibly throwing its steering wheel out of the window, would win.

Pure coordination. Alice and Bob want to meet tonight, either at their usual café or at the cinema in their neighborhood. Their phones are dead, so they can't call each other. Neither cares which place it is. What matters is being at the same place: each gets 2 if they meet and 0 if they don't.

If Bob goes to the café, Alice's best response is the café, and if Bob goes to the cinema, it's the cinema. The same holds for Bob. So both (Café, Café) and (Cinema, Cinema) are equilibria, and both players rank them the same way. This is a : there's no conflict at all, only the need to match. What can go wrong is beliefs. Alice goes to the café because she expects Bob to be there, and Bob goes to the cinema for the same reason. Firms face the same problem when they need to agree on a common file format or a meeting place for a trade fair.

The battle of the sexes. This is the ballet game from the start of this reading. Alice prefers the ballet, Bob prefers the opera, and both prefer being together to being apart. Again there are two equilibria, (Ballet, Ballet) and (Opera, Opera). But unlike in pure coordination, the players rank them differently: Alice gets 3 at the ballet and 1 at the opera, and Bob the reverse. They agree that they want to coordinate, and they disagree about where. Two firms that both gain from a common standard, but each prefer the one built around their own technology, are in this game.

When a game has several equilibria, the model narrows the prediction but can't tell us which equilibrium will happen. What decides it depends on the kind of game, and that matters for a manager. In pure coordination the problem is only beliefs: each needs to expect the other to go to the same place. Anything that makes one equilibrium obvious solves it, such as a habit, a convention or a quick message. In chicken and the battle of the sexes, communication alone isn't enough, because each would like to steer toward its own favorite. There, what decides the outcome is often who can commit first, which is where Reading 4 begins.

So it pays to diagnose which kind of game you're in. Firms often spend on building trust when the real problem is who gets the better deal, and on negotiating when the real problem is that nobody wants to move first.

3.5

No equilibrium in pure strategies

In matching pennies, Alice and Bob each hold a coin. Each secretly turns it to heads or tails, and then both reveal their coins at the same time. If the coins match, both heads or both tails, Alice wins and Bob pays her $1. If they don't match, Bob wins and Alice pays him $1. Whatever one player gains, the other loses, so this is a zero-sum game.

No cell has both payoffs shaded. Start anywhere and follow the best responses. Suppose Alice plays Heads. Bob wants the coins not to match, so he plays Tails. Against Tails, Alice wants a match, so she switches to Tails. Against that, Bob switches to Heads, and then Alice switches back to Heads. We're back where we started. In every cell, one of the two players would rather switch. So the game has no Nash equilibrium in pure strategies, that is, with each player choosing one action for sure.

This is not a curiosity. A penalty taker and a goalkeeper, a tax auditor and a taxpayer, and a store choosing which week to run a promotion are all in games like this, and in all of them being predictable is costly. Players do best by keeping the other side guessing. If we allow players to randomize, choosing each action with some probability, an equilibrium exists again. We won't compute those equilibria in this course, but the lesson is useful on its own: when a rival can exploit any pattern in what you do, don't have one.

Name the game

For each matrix, find the pure-strategy Nash equilibria and decide which kind of game it is.

Question 1 of 4

Two firms each choose a technical standard, Old or New. Both earn 9 if both choose New, 5 if both choose Old and 0 if they choose differently.

Choose one answer.

Summary

A best response is the best strategy against a particular choice of the others. A Nash equilibrium is a combination of strategies in which each player's strategy is a best response to the others', so nobody wants to change alone. In a matrix, it is a cell with both payoffs underlined. An equilibrium can be bad for everyone, as in the cafés' prisoner's dilemma. Chicken, coordination and the battle of the sexes have two equilibria each, and the model can't say which happens. Matching pennies has none in pure strategies.

Concept atlas