Nash Equilibrium

What you’re seeing

Best responses

Fix what everyone else does, a_−i. Player i’s best responses are the actions that give the highest payoff against it. Osborne writes the set of them as a function:

It is a set because there can be ties. In a payoff matrix, Row’s best responses to a column are the rows with the largest gold number in that column; that is exactly what underlining finds.

Nash equilibrium

One useful way to read it: no regrets. After the game, each player learns what the others did and asks, “Could I have done better?” At a Nash equilibrium the answer is no, for everyone. Another way: it is a self-enforcing agreement. If the players agreed beforehand to play a*, nobody would want to break the agreement alone, even with no one to enforce it.

Many equilibria, or none

Unlike dominance, Nash equilibrium nearly always says something, but often it says “one of these.” Three shapes show up again and again.

Coordination games have equilibria the players rank the same way, yet they can still fail to coordinate if each expects the other to go elsewhere. Bach or Stravinsky adds conflict: both want to coordinate, but they disagree about where. Chicken (Osborne calls a version of it hawk–dove) has two equilibria in which one player backs down, and each prefers the one where the other does. Matching pennies has none: whatever cell you are in, the loser wants to switch.

The stag hunt: better versus safer

The philosopher Jean-Jacques Rousseau described hunters who can catch a stag only if all of them stay at their posts, while any one of them can catch a hare alone. With payoffs Stag–Stag 4, Hare 3 whatever the other does, and Stag alone 0:

Both (Stag, Stag) and (Hare, Hare) are equilibria. (Stag, Stag) is Pareto-dominant: better for both. But (Hare, Hare) is risk-dominant, a term from John Harsanyi and Reinhard Selten’s 1988 book on equilibrium selection: deviating from it costs less. If you hunt stag and your partner doesn’t, you lose 3 (from 3 to 0); if you hunt hare and your partner hunts stag, you lose only 1 (from 4 to 3). For two-by-two games like this one, the risk-dominant equilibrium compares the products of these losses, (3 − 0) × (3 − 0) = 9 against (4 − 3) × (4 − 3) = 1.

Does an equilibrium always exist?

Not in pure actions, as matching pennies shows. But Nash’s theorem (1950) guarantees that once players may randomize: every strategic game with finitely many players, each with finitely many actions, has at least one Nash equilibrium in mixed strategies. Nash proved it with a fixed-point theorem: the best-response map, which sends each strategy profile to the profiles of best responses to it, must leave some profile where it is. Chapter 4 shows how to compute these mixed equilibria.

Focal points: choosing among equilibria

When a game has several equilibria, how do people pick one? Thomas Schelling noticed that they often succeed far better than chance by choosing what stands out: a focal point. Try a few coordination puzzles. Your partners are simulated; where Schelling reported his students’ answers, the simulation follows them.

Every one of these puzzles has many equilibria: if both of you name tails, that works just as well as heads. Nothing in the payoffs favors one equilibrium. What breaks the tie is shared culture, convention and imagination. Schelling put it this way in The Strategy of Conflict: people can often concert their intentions or expectations with others if each knows that the other is trying to do the same. Splitting $100 shows the same force in bargaining: any pair of claims adding up to $100 is an equilibrium, and 50–50 wins because it is the obvious one.

What equilibrium does and doesn’t predict

A Nash equilibrium is a steady state: if everyone expects it, nobody wants to change. Osborne’s favorite reading is a population of players who meet again and again, each with experience of how others behave: once behavior settles, it must be an equilibrium, since anyone who could do better would eventually notice. That reading explains why equilibrium predicts well in familiar, repeated situations (which side of the road to drive on, prices in a mature market) and less well in brand-new games played once by beginners, such as the guessing game of Chapter 1.

An equilibrium says nothing about which equilibrium will happen when there are several, nothing about how players get there, and nothing about whether the outcome is good. Equilibria can be terrible for everyone, as in the prisoner’s dilemma. Choosing among equilibria takes extra ideas: Pareto ranking, risk dominance, focal points, history, and in later chapters the timing of moves (Chapter 6) and repetition (Chapter 7).

A short history

Antoine Augustin Cournot found the equilibrium of a duopoly in 1838 (Chapter 5), but the general idea is John Forbes Nash Jr.’s. As a 21-year-old Princeton graduate student, he published a one-page proof of existence in the Proceedings of the National Academy of Sciences (1950), using Kakutani’s fixed-point theorem, then a fuller version with a proof based on Brouwer’s fixed-point theorem in the Annals of Mathematics (1951). Von Neumann and Morgenstern’s theory had handled zero-sum games and coalitions; Nash’s equilibrium worked for any game in which players act independently. He shared the 1994 Nobel prize in economics with John Harsanyi and Reinhard Selten. His life, including decades of mental illness and recovery, is told in Sylvia Nasar’s biography A Beautiful Mind (1998).

Thomas Schelling introduced focal points in The Strategy of Conflict (1960) and shared the 2005 prize with Robert Aumann. John Harsanyi and Reinhard Selten developed a full theory of equilibrium selection, including risk dominance, in A General Theory of Equilibrium Selection in Games (1988).

Where you see it

• Business standards: which video format, charging plug or software platform to back is a coordination game: what matters most is choosing what others choose. When Toshiba stopped making HD DVD players in 2008, the industry settled on Blu-ray. Platform battles in phones worked the same way (see the case Nokia and the Burning Platform).
• Entry and capacity: a market with room for one new store, one new plant or one new airline route is a game of chicken. Firms announce plans early to claim the favorable equilibrium.
• Policy: on 3 September 1967 Sweden switched from driving on the left to driving on the right. Both are equilibria; moving a whole country from one to the other took years of preparation and a single coordinated morning. Bank runs are coordination failures too: if everyone expects a run, withdrawing early is each depositor’s best response.
• Sports: a soccer back line stepping up together to catch attackers offside is a coordination game: it works only if every defender moves at the same moment, and one defender who hangs back ruins it for all.
• Daily life: two people walking toward each other on a sidewalk, both stepping to the same side; a group choosing a meeting time without a chat thread; everyone leaving a stadium through the same gate. Conventions are equilibria that have become habits.

Practice

1. Find the equilibria. Find every pure-strategy Nash equilibrium.

   	Column
   Row	L	C	R
   T	1, 2	3, 1	0, 0
   M	2, 1	2, 3	2, 0
   B	0, 0	1, 1	3, 2

   Show the answer

   Row’s best responses: against L, M (2); against C, T (3); against R, B (3). Column’s: against T, L (2); against M, C (3); against B, R (2). The only cell with both marks is (B, R), with payoffs (3, 2). (M, C) looks good for Column, but against C Row prefers T (3 > 2).

2. No pure equilibrium. Show that this game has no pure-strategy Nash equilibrium by checking each cell for a profitable deviation.

   	Column
   Row	Left	Right
   Up	5, 1	1, 4
   Down	4, 3	2, 2

   Show the answer

   (Up, Left): Column switches to Right (4 > 1). (Up, Right): Row switches to Down (2 > 1). (Down, Right): Column switches to Left (3 > 2). (Down, Left): Row switches to Up (5 > 4). Every cell has someone who wants to move, like matching pennies. (In Chapter 4 you’ll find its mixed equilibrium: Row plays Up with probability 1/4, Column plays Left with probability 1/2.)

3. Risk dominance. In a stag hunt, change the hare payoff from 3 to 2 (so Hare gives 2 whatever the other does). Which equilibrium is risk-dominant now? How sure of your partner must you be to hunt stag?

   Show the answer

   Losses from deviating: at (Stag, Stag), 4 − 2 = 2 for each player, product 4. At (Hare, Hare), 2 − 0 = 2 for each, product 4. It’s a tie: neither is risk-dominant. You hunt stag if 4q ≥ 2, that is q ≥ 1/2. Lower the hare payoff further and Stag becomes both the better and the safer equilibrium.

4. Dominance and equilibrium. Explain why, if every player has a strictly dominant action, the profile of those actions is the game’s only Nash equilibrium.

   Show the answer

   A strictly dominant action is the unique best response to every profile of the others’ actions. So in any Nash equilibrium each player must be playing it, which leaves only one candidate; and that candidate is an equilibrium because each action is a best response to the others.

5. A best-response function. Two partners each choose an effort level e_i ≥ 0. Partner i’s payoff is u_i = e_i(2 + e_j) − e_i², where j is the other partner: effort is more productive when the other works hard too. Find B_i(e_j) and the Nash equilibrium.

   Show the answer

   Setting the derivative with respect to e_i to zero: 2 + e_j − 2e_i = 0, so B_i(e_j) = (2 + e_j)/2 = 1 + e_j/2 (the second derivative, −2, confirms a maximum). In equilibrium each is a best response to the other: e = 1 + e/2, so e* = 2 for both, with payoffs 2 × 4 − 4 = 4 each. (Both would be better off at higher effort, for example 3 each gives 3 × 5 − 9 = 6: each partner ignores the boost their effort gives the other.)

6. Risk dominance and 50–50 beliefs. In a symmetric 2×2 game with actions S and H, payoffs a = u(S, S), b = u(S, H), c = u(H, S), d = u(H, H), with a > c and d > b (two strict equilibria). Show that (S, S) is risk-dominant exactly when S is the best response to a partner who is equally likely to play S or H.

   Show the answer

   Risk dominance compares (a − c)² with (d − b)², so (S, S) is risk-dominant when a − c > d − b (both differences are positive). Against a 50–50 partner, S pays (a + b)/2 and H pays (c + d)/2. S is better when a + b > c + d, which rearranges to a − c > d − b. The same condition.

How the interactive works

Equilibria. For every column the program finds the rows with the highest row payoff (Row’s best responses, ties included), and for every row the columns with the highest column payoff. Pure-strategy Nash equilibria are the cells in both lists. A deviation arrow from a cell points to the best alternative for a player who is not already best responding there. Selection in 2×2 games compares the two equilibria’s payoffs (Pareto) and the products of each player’s loss from deviating (risk dominance).

Random games draw each payoff uniformly from 0 to 9. About 85% of the time the generator keeps drawing until the game has at least one pure equilibrium, so that “no equilibrium” comes up now and then rather than one game in eight.

Focal points. Your partner is drawn at random from fixed weights. For heads or tails, splitting $100, meeting in New York and the meeting time, the weights follow the answers Schelling reported; for the grid of squares and “name a number” they are a guess about what people find salient, and the puzzle says so.

Checks (node). On 3,000 random games of size 2×2 to 4×4, the equilibria found by best responses matched a brute-force search for cells with no profitable deviation, and the cells with both underlines were exactly the equilibria. Among 5,000 random 3×3 games, 12% had no pure equilibrium, 49% had one, 31% had two and 8% had three or more. In the stag hunt the program reports (Stag, Stag) as Pareto-dominant and (Hare, Hare) as risk-dominant (products 1 and 9), with the stag threshold at q = 3/4.

Check yourself

1. An action profile is a Nash equilibrium when …

   • it gives the highest total payoff
   • no player can do better by changing only their own action
   • every player is playing a dominant action
   Show the answer

   Each action must be a best response to the others’ actions. Dominant actions are one way to get there, but most equilibria don’t involve them.

2. In a payoff matrix, a cell is a pure-strategy Nash equilibrium when …

   • its two payoffs are equal
   • its row payoff is the largest number in the whole matrix
   • its row payoff is the largest in its column and its column payoff is the largest in its row
   Show the answer

   That is the underline method: Row can’t gain by moving within the column, and Column can’t gain by moving within the row.

3. In the stag hunt above, (Hare, Hare) is risk-dominant because …

   • hunting hare protects you if your partner doesn’t cooperate: the loss from a partner’s deviation is smaller
   • it gives higher payoffs to both
   • it is not really an equilibrium
   Show the answer

   (Stag, Stag) pays more, but it is fragile: you need to be at least 75% sure of your partner. Hare pays 3 whatever happens.

4. What does Nash’s theorem guarantee?

   • Every game has a pure-strategy equilibrium
   • Every finite game has at least one equilibrium, possibly in mixed strategies
   • Every game has exactly one equilibrium
   Show the answer

   Matching pennies has no pure equilibrium, and coordination games have several. Existence is guaranteed only once randomizing is allowed.

5. Two people must meet in a city without communicating and both go to the main train station at noon. Game theory calls the station at noon …

   • a dominant strategy
   • the only Nash equilibrium
   • a focal point: one equilibrium among many that stands out
   Show the answer

   Meeting anywhere at any shared time is an equilibrium. The station at noon is Schelling’s focal point: it is chosen because each expects the other to choose it.

Sources

• M. J. Osborne, An Introduction to Game Theory (Oxford University Press, 2004), chapter 2 (Nash equilibrium, best response functions, the stag hunt, hawk–dove) and chapter 4 (mixed strategy equilibrium).
• J. F. Nash, “Equilibrium points in n-person games”, Proceedings of the National Academy of Sciences 36(1), 1950, 48–49; “Non-cooperative games”, Annals of Mathematics 54(2), 1951, 286–295.
• T. C. Schelling, The Strategy of Conflict (Harvard University Press, 1960), chapter 3. The survey numbers are as summarized in Focal point (game theory) (Wikipedia).
• J. C. Harsanyi and R. Selten, A General Theory of Equilibrium Selection in Games (MIT Press, 1988).
• J. Mehta, C. Starmer and R. Sugden, “The nature of salience: an experimental investigation of pure coordination games”, American Economic Review 84(3), 1994, 658–673.
• Ben Polak, Yale ECON 159, Lecture 6: Nash Equilibrium: Dating and Cournot.
• MIT OpenCourseWare 14.12, Lecture notes, Chapter 6: Nash Equilibrium.
• “Game Theory”, Stanford Encyclopedia of Philosophy.