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 in 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 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 nplayers. Formally:

Formal definition of a Nash equilibrium
Let (S,f) be a game with u players Sᵢ is the set of strategies for player i, S = S₁ x S₂ x ... x Sᵤ is the set of strategy profiles and f(x) = (f₁(x),...,fᵤ(x)) is its payoff function evaluated at x ∈ S. Let xᵢ be a strategy profile of player i and x₋ᵢ be a strategy profile of all players except player i.When each player i ∈ {1,...,u} chooses a strategy xᵢ, resulting in a strategy profile x = (x₁,...,xᵤ) then player i obtains payoff fᵢ(x). Note that the payoff depends on the strategy profile chosen, i.e. on the strategy chosen by player i as well as the strategies chosen by all the other players.A strategy profile x* ∈ S is a Nash equilibrium if no unilateral definition in strategy by any single player is profitable for that player, that is∀i,xᵢ ∈ Sᵢ : fᵢ(x*ᵢ, x*₋ᵢ) ≥ fᵢ(xᵢ,x*₋ᵢ)

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:

Proof of the existence of Nash Equilibria using the Kakutani fixed-point theorem (Nash, 1951)
To prove the existence of a Nash Equilibrium (NE), let rᵢ(σ₋ᵢ) be the best response of player i to the strategies of all other players.

rᵢ(σ₋ᵢ) = arg max uᵢ(σᵢ, σ₋ᵢ)

Here, σ ∈ Σ where Σᵢ x Σ₋ᵢ is a mixed strategy profile in the set of all mixed strategies and uᵢ is the payoff function for player i. Define a set valued function r: Σ → 2^Σ such that r = (rᵢ(σ₋ᵢ), r₋ᵢ(σ₋ᵢ). Proving the existence of a Nash equilibrium is equivalent to showing that r has a fixed point.

Kakutani's fixed point theorem guarentees the existence of a fixed point if the following four conditions are satisfied:

1. Σ is compact, convex and non-empty
2. r(σ) is nonempty
3. r(σ) is upper hemicontinuous
4. r(σ) is convex

Condition 1 is satisfied from the fact that Σ is a simplex and thus compact. Convexity follows from players' abilities to mix strategies. Σ is non-empty as long as players have strategies.

Condition 2. and 3. are satisfied by way of Berge's maximum theorem. Because uᵢ is continuous and compact, r(σ) is non-empty and upper hemicontinuous.

Condition 4 is satisfied as a result of mixed strategies. Suppose σᵢ, σᵢ' ∈ r(σ₋ᵢ), then λσᵢ + (1 - λ)σᵢ' ∈ r(σ₋ᵢ), i.e. if two strategies maximize payoffs, then a mix between two strategies will yield the same payoff.

Therefore, there exists a fixed point in r and a Nash equilibrium.

Examples

A formal game typically consists of three elements: players, strategy sets and payoff functions for each player. The payoff functions represent each players’ preferencesover 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

A pure-strategy Nash equilibrium is a strategy set with the property that no single player can obtain a higher expected payoff by deviating unilaterally and playing an alternate strategy

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:

A mixed-strategy Nash equilibrium is a strategy set with the property that at least one player is playing a randomized strategy and no player can obtain a higher expected payoff by deviating unilaterally and playing an alternate strategy

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:

"The Nobel selection committee apparently took the two interpretations that are contained in the thesis seriously. The rational interpretation could have been argued by Cournot, but the statistical interpretation, which is so important for biological games, is wholly original. Although the nature of non-cooperative games is explained in all three of these papers, only the thesis contains an exposition of these two interpretations. When asked at the Nobel seminar why the interpretations were not included in the Annals paper. Nash responded, "I don't know whether it was just pruned down in style for the Annals of Mathematics." - Excerpt, "The Essential John Nash" by Kuhn et al (2002)

Discovery

Rather than what was depicted in the movie, as his biographer Sylvia Nasarwrites, 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,

“A few days after the disastrous meeting with von Neumann, Nash accosted David Gale. “I think I’ve found a way to generalize von Neumann’s min-max theorem,” he blurted out. “The fundamental idea is that in a two-person zero-sum solution, the best strategy for both is … The whole theory is built on it. And it works with any number of people and doesn’t have to be a zero-sum game!”- Excerpt, "A Beautiful Mind" by Sylvia Nasar (1998)

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 realized that Nash’s idea applied to a far broader class of real-world situations than von Neumann’s notion of zero-sum games. “He had a concept that generalized to disarmament”- Excerpt, "A Beautiful Mind" by Sylvia Nasar (1998)

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:

John F. Nash introduced the distinction between cooperative games, in which binding agreements can be made, and non-cooperative games, where binding agreements are not feasible. Nash developed an equilibrium concept for non-cooperative games that later came to be called Nash equilibrium.