Photo: © 2001 Imagine Entertainment

Game Theory

The Nash equilibrium, explained

Jørgen Veisdal
Oct 20 · 10 min read

If we all go for the blonde and block each other, not a single one of us is going to get her. So then we go for her friends, but they will all give us the cold shoulder because no on likes to be second choice. But what if none of us goes for the blonde? We won’t get in each other’s way and we won’t insult the other girls. It’s the only way to win. It’s the only way we all get laid.”

If we are to believe the movie, this is how the character John Nash from A Beautiful Mind (2001) first explained his brilliant new discovery of “governing dynamics” to his friends. In reality of course, this is not how the real John Forbes Nash Jr. came upon the idea, nor would it have been how he would have described the concept of his discovery. The purpose of this article is to provide a more accurate and complete narration of how the Nash equilibrium came about, and what it means.

Estimated reading time is 10 minutes. Spotify mood music by James Horner. Happy reading

What is a Nash equilibrium?

A Nash equilibrium is a solution concept for non-cooperative games involving two or more players in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only their own strategy (Osborne et al, 1994). Informally, the theorem states:

A strategy profile is a Nash equilibrium if no player can do better by unilaterally changing his or her strategy.

That is, in a two-person game, a pair of strategies constitute a Nash equilibrium if player A’s choice is optimal, given player B’s choice, and B’s choice is optimal given player A’s choice. No player can singlehandedly change their strategy in order to obtain a more optimal result. Crucially, neither player knows what strategy the other will choose, but acts solely on the basis of their own interests, given their knowledge of other players’ interests. The finding generalizes to n players. Formally:

Proof of the Nash Equilibrium

Nash’s thesis proof (1950c) used the Brouwer’s fixed-point theorem. Awarding credit to David Gale, Nash later published a simpler proof of the same result, using the Kakutani fixed-point theorem:

Examples

A formal game typically consists of three elements: players, strategy sets and payoff functions for each player. The payoff functions represent each players’ preferences over the strategy sets, where a strategy set is a list of strategies for each player in the game. We can illustrate the three elements in an example figure called a payoff matrix for games of two players, featuring two strategies for each:

In each of the games, both players can choose between two strategies, labeled A and B.

Pure-strategy Nash equilibrium

In game 1, if they choose different strategies (A,B) or (B,A), both get payoffs of 0. If they both choose strategies A, they both get a payoff 2. If they choose strategies B, they both get a payoff 1. The strategy sets (A,A) and (B,B) hence result in Nash equilibria, as deviation of a single player would result in a lower payoff for that player. In game 2, if they choose different strategies (A,B) or (B,A), player 1 gets a payoff of -1 and player 2 a payoff of 1. If they both choose A or both choose B, player 1 gets the payoff of 1 and player 2 the payoff of -1. There are no pure-strategy Nash equilibria in this game, because in each strategy set, one of the players stands to gain from deviating.

Mixed-strategy Nash equilibrium

One of Nash’s results was to show that there must exist at least one Nash equilibrium point in all finite games. Since no pure-strategy Nash equilibrium exists for game 2, there must exist one in mixed strategies:

In cases such as game 2, instead of choosing a single strategy, players can instead choose probability distributions over the set of strategies available to them. In equilibrium, each player’s probability distribution makes all others indifferent between their pure strategies. For instance, as player 1 we can play A half the time and B half the time, and let the flipping of a coin decide when we play which. Player 2’s only rational response will have to be to do the same. As such, a mixed-strategy Nash equilibrium in the matching pennies game exists if both play A and B with equal probability simultaneously.

Interpretations

Nash in his thesis proposed two ways of thinking about his equilibrium concept:

  • One based on rationality and
  • One based on statistical populations.

In the rationality interpretation, players are perceived as rational and they have complete information about the structure of the game, including all of the players’ preferences regarding possible outcomes, where this information is common knowledge. Since all players have complete information about each others’ strategic alternatives and preferences, they can also compute each other’s optimal choice of strategy for each set of expectations. If all of the players expect the same Nash equilibrium, and the game is played only once, then there are no incentives for anyone to change their strategies.

In the interpretation according to statistical populations, Nash states that “[i]t is unnecessary to assume that the participants have full knowledge of the total structure of the game, or the ability and inclination to go through any complex reasoning processes”. This because “What is assumed is that there is a population of participants for each position in the game, which will be played throughout time by participants drawn at random from the different populations. If there is a stable average frequency with which each pure strategy is employed by the average member of the appropriate population, then this stable average frequency constitutes a mixed strategy Nash equilibrium.” (Nash, 1950c).

As Harold Kuhn would later write:

Discovery

Rather than what was depicted in the movie, as his biographer Sylvia Nasar writes, Nash came upon the idea when he was an graduate student at Princeton University, researching the mathematical modeling of games of strategy and bargaining between economic actors. As Nasar writes,

The conversation between Nash and David Gale was recounted by Gale himself to Nasar in 1995. Nash was at the time working on the so-called ‘bargaining problem’ where two individuals have the opportunity for mutual benefit, but no action taken by one of the individuals unilaterally (without consent) can affect the well-being of the other. Think of the classic “divide and choose protocol” of two people trying to divide a cake evenly, where one carves and the other chooses which piece he or she wants, providing a so-called envy-free cake-cutting procedure.

Characteristically, as Nasar writes, Gale was less enchanted by the possible applications of Nash’s new result than the mathematics, stating in 1995 that “The mathematics was so beautiful. It was so right mathematically.”

Gale also helped Nash claim credit for the result as soon as possible by drafting a note to the National Academy of Sciences. Solomon Lefschetz submitted the note on their behalf, and the result appeared in less than a single page entitled Equilibrium points in N-person games in the 36th volume of the Proceedings of the National Academy of Sciences in January of 1950.

Epilogue

Nash’s thesis would eventually spawn three journal papers and a Nobel Prize in Economics (1994).

Journal papers

The three articles contain three different proofs of the existence of Nash equilibria. The first, entitled Equilibrium Points in N-person Games (1950b) is the note Nash and Gale drafted for the Proceedings of the National Academy of Sciences. The second, called Non-Cooperative games (1951) was published in the Annals of Mathematics Vol. 54 (2). In Two-person cooperative games (1953), published in Econometrica 21, Nash extended his work on the bargaining problem (Nash, 1950a) to a wider class of situations in which threats can a play a role (Kuhn et al, 2002).

Nobel Prize

Several weeks before the 1994 Nobel prize in economics was announced on Oct. 11, two mathematicians — Harold W. Kuhn and John Forbes Nash Jr. — visited their old teacher, Albert W. Tucker, now almost 90 and bedridden, at Meadow Lakes, a nursing home near here. Mr. Nash hadn’t spoken with his mentor in several years. Their hour-long conversation, from which Mr. Kuhn excused himself, concerned number theory.

When Mr. Nash stepped out of the room, Mr. Kuhn returned to tell Mr. Tucker a stunning secret: Unbeknownst to Mr. Nash, the Royal Swedish Academy intended to grant Mr. Nash a Nobel Prize for work he had done as the old man’s student in 1949, work that turned out to have revolutionary implications for economics. The award was a miracle. — Nasar, 1994.

On the 11th of October 1994, Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel announced that the 1994 Nobel Prize in Economics would be awarded to Dr. John Forbes Nash, Jr. for his pioneering analysis of equilibria in the theory of non-cooperative games:


This essay is part of a series of stories on math-related topics, published in Cantor’s Paradise, a weekly Medium publication. Thank you for reading!

Cantor’s Paradise

Medium’s #1 Math Publication!

Jørgen Veisdal

Written by

Editor-in-Chief at Cantor’s Paradise. Research fellow at the Norwegian University of Science and Technology. Co-founder at Moon Labs

Cantor’s Paradise

Medium’s #1 Math Publication!

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade