Nash Equilibrium — Mathematics Knowledge System

Overview

A Nash equilibrium (NE) is a profile of strategies — one for each player in a game — such that no player can increase their expected payoff by unilaterally deviating to a different strategy, given the strategies of all other players. Named after John Nash who proved in 1950 that every finite game possesses at least one Nash equilibrium in mixed strategies, the concept is the dominant solution concept in non-cooperative game theory and underlies a vast literature in economics, computer science, and evolutionary biology.

Intuition

A Nash equilibrium is a stable resting point of strategic interaction: if all players are playing their NE strategies and each one contemplates deviating, they find no profitable deviation. It is not necessarily the best outcome for society (cf. Prisoner's Dilemma), nor is it necessarily unique. It is simply the strongest form of stability under individual rationality.

Formal Definition

Definition

In a normal-form game G = (N, (Sᵢ), (uᵢ)), a mixed strategy profile σ* is a Nash equilibrium if each player is best-responding to the others.

\sigma^* = (\sigma_1^*, \ldots, \sigma_n^*) \text{ is a Nash equilibrium if for all } i \in N:

Nash equilibrium definition

U_i(\sigma_i^*, \sigma_{-i}^*) \geq U_i(\sigma_i, \sigma_{-i}^*) \quad \forall\, \sigma_i \in \Delta(S_i)

Best-response condition

\sigma_{-i} = (\sigma_1, \ldots, \sigma_{i-1}, \sigma_{i+1}, \ldots, \sigma_n)

Strategy profile of all players except i

\text{BR}_i(\sigma_{-i}) = \arg\max_{\sigma_i \in \Delta(S_i)} U_i(\sigma_i, \sigma_{-i})

Best-response correspondence

\sigma^* \text{ is NE} \iff \sigma_i^* \in \text{BR}_i(\sigma_{-i}^*) \quad \forall\, i \in N

Fixed-point characterisation

Notation

Notation	Meaning
$\sigma^*$	Nash equilibrium strategy profile
$\sigma_{-i}$	Strategies of all players other than i
$\text{BR}_i$	Best-response correspondence of player i
$U_i(\sigma)$	Expected payoff of player i under mixed profile σ

Theorems

Theorem 1: Nash Existence Theorem (1950)

\text{Every finite normal-form game has at least one Nash equilibrium in mixed strategies}

Theorem 2: Support Characterisation

\sigma_i^* \text{ assigns positive probability only to strategies in } \arg\max_{s_i} U_i(s_i, \sigma_{-i}^*)

Theorem 3: PPAD-Completeness of Nash

\text{Computing a Nash equilibrium of a two-player game is PPAD-complete}

Worked Examples

1
Check (D, D): if player 1 deviates to C, payoff goes from 1 to 0 — worse. Player 2 similarly. So (D, D) is NE.
$u_1(D, D) = 1 > 0 = u_1(C, D)$
2
Check (C, C): player 1 can deviate to D and get 3 instead of 2 — profitable deviation. Not NE.
$u_1(D, C) = 3 > 2 = u_1(C, C)$
3
Check (D, C) and (C, D): in each, one player has a profitable deviation.
$u_2(C, C) = 2 > 0 = u_2(C, D)$

✓ Answer

(D, D) is the unique pure NE. No mixed NE exists because D strictly dominates C.

Practice Problems

Mediumproof writing

Prove that in a finite two-player zero-sum game, σ* is a Nash equilibrium iff σ* is a minimax strategy profile.

Common Mistakes

Common Mistake

Nash equilibrium is always unique

Games can have multiple NE. The Hawk-Dove game has two pure NE and one mixed NE. Coordination games like Battle of the Sexes also have multiple equilibria.

Common Mistake

Nash equilibrium is Pareto optimal

The Prisoner's Dilemma (D,D) NE is Pareto dominated by (C,C). Individual rationality and collective optimality can conflict.

Quiz

Which theorem guarantees the existence of a Nash equilibrium in every finite game?

Brouwer's fixed-point theoremKakutani's fixed-point theorem applied to the best-response correspondenceThe minimax theoremFarkas' lemma

In a mixed-strategy Nash equilibrium, a player is indifferent among:

All strategies in their strategy setThe strategies they assign positive probability to (support)The strategies they assign zero probability toAll opponents' strategies

Historical Background

John Nash introduced the equilibrium concept bearing his name in a two-page paper in the Proceedings of the National Academy of Sciences in 1950, and expanded it in his 1951 Annals of Mathematics paper. His proof used Kakutani's fixed-point theorem. The concept unified and generalised von Neumann's minimax solution for zero-sum games. Nash's contribution, along with Harsanyi and Selten's refinements, earned the 1994 Nobel Memorial Prize in Economic Sciences.

1950
Nash's two-page PNAS note 'Equilibrium Points in n-Person Games' introduces Nash equilibrium
John Nash
1951
Nash's Annals of Mathematics paper provides the full fixed-point proof
John Nash
1965
Selten introduces subgame perfect equilibrium as a refinement
Reinhard Selten
1994
Nash, Harsanyi, Selten awarded Nobel Prize in Economics
John Nash, John Harsanyi, Reinhard Selten
2009
Daskalakis, Goldberg, Papadimitriou prove computing NE is PPAD-complete
Constantinos Daskalakis, Paul Goldberg, Christos Papadimitriou

Summary

A Nash equilibrium is a strategy profile where each player's strategy is a best response to all others' strategies.
Equivalently, σ* is NE iff σᵢ* ∈ BRᵢ(σ*₋ᵢ) for all i — a fixed point of the best-response correspondence.
Every finite game has at least one Nash equilibrium (possibly in mixed strategies) by Kakutani's theorem.
Pure strategy NE are found by checking mutual best responses; mixed NE by indifference conditions.
Computing a Nash equilibrium is PPAD-complete, making it computationally hard in the worst case.

References

BookNash, J.F. — Equilibrium Points in n-Person Games, PNAS 36(1), 1950, pp. 48–49
BookNash, J.F. — Non-Cooperative Games, Annals of Mathematics 54(2), 1951, pp. 286–295
BookOsborne, M.J. & Rubinstein, A. — A Course in Game Theory (1994), MIT Press, Chapter 2
WebsiteWikipedia — Nash equilibrium
WebsiteMathWorld — Nash Equilibrium