Game theory — Nash equilibrium and strategic interaction

Intuition Beginner

Game theory studies situations where several decision-makers choose at once and each one's best move depends on what the others pick. A firm setting its price cares what rivals charge. A bidder at an auction cares what others bid. A country weighing tariffs cares how trading partners retaliate. In every case the right choice is not fixed — it is conditional on someone else's choice.

This is what separates game theory from the price-taking world of 52.01.01. In a competitive market a single buyer or seller is small enough that prices feel fixed from outside. In a strategic setting each actor is large enough, or the group small enough, that one player's move shifts the outcome everyone else faces. Choice becomes interdependent.

The central question follows at once: what counts as a sensible choice when everyone is reasoning this way at the same time? The answer game theory proposes is the Nash equilibrium — a list of choices, one per player, such that no one can do better by switching unilaterally. It is a resting point of mutual best-responding, not a guarantee of a good outcome.

Visual Beginner

The natural picture is the payoff matrix. Rows are one player's options, columns the other's, and each cell holds a pair of numbers — the payoff to each player if that pair of choices is played.

	Column plays C	Column plays D
Row plays C	(3, 3)	(0, 5)
Row plays D	(5, 0)	(1, 1)

The first number in each pair is Row's payoff; the second is Column's. Scan a row to compare Row's options; scan a column to compare Column's.

Worked example Beginner

Two suspects are held separately. Each picks C (stay silent) or D (confess). Their payoffs are the matrix above: bigger is better. What will rational suspects do?

Step 1. Fix what Column does and compare Row's options. If Column plays C, Row gets 3 from C but 5 from D, so D is better. If Column plays D, Row gets 0 from C but 1 from D, so D is better again. Whichever Column does, Row prefers D.

Step 2. The matrix is symmetric, so the same reasoning applies to Column: whatever Row does, Column prefers D.

Step 3. Both pick D, landing in the cell (1, 1). From there, if Row alone switched to C, Row's payoff would fall from 1 to 0; the same holds for Column. Neither wants to move.

So the Nash equilibrium is (D, D), giving each a payoff of 1. Yet (C, C) would have given each 3. This is the prisoner's dilemma: individual rationality produces a joint outcome worse for everyone than cooperation would have. The lesson is that an equilibrium need not be efficient — a result that reappears throughout economics.

Check your understanding Beginner

Formal definition Intermediate+

A game in normal (strategic) form is a tuple $G=⟨N,(S_i{)}_{i\in N},(u_i{)}_{i\in N}⟩$ where $N=\{1,\dots ,n\}$ is the finite set of players, $S_i$ is player $i$'s finite set of pure strategies, and $u_i:S\to \mathbb{R}$ with $S={\prod }_i{S}_i$ is $i$'s payoff function ^{[Osborne 2003]}. A mixed strategy for $i$ is a probability distribution ${\sigma }_i\in \Delta (S_i)$ over pure strategies; the set of mixed strategies is the simplex $\Delta (S_i)=\{{\sigma }_i\ge 0:{\sum }_{s_i\in S_i}{\sigma }_i(s_i)=1\}$. A mixed-strategy profile $\sigma =({\sigma }_1,\dots ,{\sigma }_n)$ induces an expected payoff

$$u_i(\sigma )=\sum _{s\in S}\left(\prod _{j\in N}{\sigma }_j(s_j)\right)u_i(s),$$

which is multilinear in the players' mixed strategies. Write ${\sigma }_{-i}$ for the profile of all players except $i$.

Player $i$'s best-response correspondence is

$${\mathrm{BR}}_i({\sigma }_{-i})=\arg \underset{{\tau }_i\in \Delta (S_i)}{\max }{u}_i({\tau }_i,{\sigma }_{-i}).$$

A mixed-strategy profile ${\sigma }^{\ast }$ is a Nash equilibrium if every player best-responds:

$$\forall i\in N,{\sigma }_i^{\ast }\in {\mathrm{BR}}_i({\sigma }_{-i}^{\ast }).$$

Equivalently, no player can raise expected payoff by deviating alone: $u_i({\sigma }^{\ast })\ge u_i({\tau }_i,{\sigma }_{-i}^{\ast })$ for every ${\tau }_i\in \Delta (S_i)$ and every $i$ ^{[Tadelis 2013]}.

A pure strategy $s_i$ is strictly dominated by ${\tau }_i$ if $u_i({\tau }_i,s_{-i})>u_i(s_i,s_{-i})$ for every $s_{-i}\in S_{-i}$. A rational player never plays a strictly dominated strategy, so the procedure of iterated elimination of strictly dominated strategies (IESDS) deletes such strategies in turn; whatever survives remains a candidate for equilibrium analysis.

Counterexamples to common slips

• Equilibrium is not efficiency. The prisoner's dilemma has a unique Nash equilibrium that is Pareto-dominated by mutual cooperation; the two notions are logically independent.
• Equilibrium need not be unique, and need not be pure. Matching pennies has no pure-strategy equilibrium; its only equilibrium is mixed.
• Mixed strategies are not "random for its own sake." A mixed equilibrium is a statement about beliefs: each player must be indifferent among the pure strategies they play with positive probability, and the mix pins down the opponent's indifference.

Economic theory Intermediate+

The discipline's central result is an existence theorem: a solution concept is only useful if equilibria actually exist.

Theorem (Nash, 1950). Every finite normal-form game possesses at least one mixed-strategy Nash equilibrium ^{[Nash 1950]}.

Argument sketch. Embed each player's mixed strategies in the compact convex simplex ${\Sigma }_i=\Delta (S_i)$ and form $\Sigma ={\prod }_i{\Sigma }_i$. The best-response map $\mathrm{BR}(\sigma )={\prod }_i{\mathrm{BR}}_i({\sigma }_{-i})$ sends each profile to a set of profiles. Because $u_i$ is linear in ${\tau }_i$, the set ${\mathrm{BR}}_i({\sigma }_{-i})$ is non-empty (a continuous function on a compact set attains its maximum) and convex (the argmax of a linear functional over a convex set is convex). The map has a closed graph by continuity of the payoffs. These are exactly the hypotheses of the Kakutani fixed-point theorem, which yields a profile ${\sigma }^{\ast }$ with ${\sigma }^{\ast }\in \mathrm{BR}({\sigma }^{\ast })$ — that is, a Nash equilibrium. $\square$

The full Kakutani verification appears in the Master proof set. Two refinements make the theorem operational. First, strict dominance and Nash equilibrium agree: any strategy played with positive probability in a Nash equilibrium survives IESDS, so elimination never discards an equilibrium (proof below). Second, for the special case of two-player zero-sum games, von Neumann's minimax theorem (1928) strengthens existence to a value: the equilibrium payoffs are ${\max }_{{\sigma }_1}{\min }_{{\sigma }_2}{u}_1$ and ${\min }_{{\sigma }_2}{\max }_{{\sigma }_1}{u}_1$, and these extrema coincide ^{[von Neumann Morgenstern 1944]}.

Bridge. This existence theorem builds toward the dynamic and informational extensions of the Master tier — subgame-perfect equilibrium, repeated games, and Bayesian mechanism design — and appears again in 52.01.01, where the competitive equilibrium is reinterpreted as the Nash equilibrium of a continuum-player game in which no single agent can move the price. The foundational reason Nash equilibrium carries the theory is that it is the weakest self-consistent requirement on beliefs: each player's action is optimal given correct expectations of the others. This is exactly the bridge from individual optimisation (the Lagrangian machinery of 44.02.01) to mutually consistent interaction, the pattern generalises from one-shot to repeated and incomplete-information settings, and putting these together the same fixed-point reasoning recurs whenever rational agents must agree on each other's behaviour.

Exercises Intermediate+

Lean formalization Intermediate+

lean_status: none. Game theory's correctness gate is its fixed-point existence proof together with model consistency, not executable code. The Kakutani/Brouwer fixed-point machinery and the convex-analysis lemmas the proof needs are drawn from the optimisation and convex-analysis chapter 44.02.03; Mathlib's coverage of these ingredients is partial, as recorded in Mathlib gap analysis above, so a faithful formalisation is deferred until that gap closes.

Advanced results Master

The one-shot, complete-information model generalises in three directions: dynamic play, repetition, and incomplete information.

Dynamic games and subgame-perfect equilibrium. When players move sequentially the normal form is replaced by the extensive form — a game tree with decision nodes, chance moves, and terminal payoffs. Nash equilibrium in a tree can be supported by non-credible threats: punishments a rational player would never carry out once called upon to do so. Selten's subgame-perfect equilibrium (SPE) ^{[Selten 1965]} tightens the concept by requiring equilibrium in every subgame. For finite-horizon games of perfect information SPE is characterised by backward induction: solve the last decision node first, replace it with its equilibrium payoff, and recurse to the root. This is exactly the dynamic-programming principle of optimality 44.08.01 applied to strategic settings.

Repeated games and the folk theorem. When a stage game is played over and over with observed history, cooperation can be sustained by the threat of future punishment. The folk theorem states that under sufficiently patient players (discount factor close to one), essentially any feasible and individually rational payoff vector can be supported as a subgame-perfect equilibrium of the repeated game. The result explains how non-cooperative interaction sustains cooperative outcomes — cartels, collusion, social norms — without an external enforcer, at the cost of equilibrium multiplicity.

Bayesian games and mechanism design. When players have private information (their "type"), the static model becomes a Bayesian game: each player knows their own type and holds a common prior over others' types. Equilibrium becomes Bayes–Nash equilibrium, where strategies are type-contingent and best responses are taken in expectation over types. Mechanism design inverts the question: given desired outcomes, what game should the planner design? Myerson's revelation principle ^{[Myerson 1981]} shows that any equilibrium outcome of any mechanism can be replicated by a direct, truthful mechanism in which types are reported honestly, reducing mechanism design to the study of incentive-compatible direct mechanisms. The Vickrey (second-price) auction is the canonical example: truth-telling is a dominant strategy and the efficient allocation results. Optimal auction design (Myerson 1981) characterises the revenue-maximising auction for a single good under independent private values.

Synthesis. Game theory is the analytical engine of strategic economics, and its four pillars — equilibrium existence, dynamic consistency, repeated interaction, and incentive-compatible design under private information — form a single coherent structure: the existence result builds toward the dynamic and Bayesian extensions by supplying the fixed-point reasoning each requires, the foundational reason the revelation principle works is that incentive compatibility is itself an equilibrium constraint, this is exactly the sense in which mechanism design is "inverse game theory," the central insight is dual to the welfare theorems of 52.01.01 (designing the game so that self-interest implements the desired allocation rather than letting an arbitrary game produce whatever it may), the bridge is that the same best-response logic runs from the one-shot normal form through subgame perfection and the folk theorem to Bayesian implementation, and the pattern generalises to the stochastic and partially observed settings of 44.08.03; putting these together, game theory supplies the micro-foundations for every setting where price-taking fails and strategic interaction governs outcomes.

Full proof set Master

Proposition (Nash existence via Kakutani). Every finite normal-form game $G=⟨N,(S_i),(u_i)⟩$ admits a mixed-strategy Nash equilibrium.

Proof. Let ${\Sigma }_i=\Delta (S_i)$ be player $i$'s mixed-strategy simplex and $\Sigma ={\prod }_{i\in N}{\Sigma }_i$. Each ${\Sigma }_i$ is non-empty, compact, and convex (a standard simplex), so $\Sigma$ is as well. Define the best-response correspondence $\mathrm{BR}:\Sigma \rightrightarrows \Sigma$ by

$$\mathrm{BR}(\sigma )=\prod _{i\in N}{\mathrm{BR}}_i({\sigma }_{-i}),{\mathrm{BR}}_i({\sigma }_{-i})=\arg \underset{{\tau }_i\in {\Sigma }_i}{\max }{u}_i({\tau }_i,{\sigma }_{-i}).$$

We verify the four hypotheses of the Kakutani fixed-point theorem.

Non-empty, compact, convex domain. $\Sigma$ is a product of simplices, each non-empty, compact, and convex; the product inherits these properties.

Non-empty values. For each $\sigma$ and each $i$, the map ${\tau }_i\mapsto u_i({\tau }_i,{\sigma }_{-i})$ is linear, hence continuous, on the compact set ${\Sigma }_i$. By the extreme value theorem it attains its maximum, so ${\mathrm{BR}}_i({\sigma }_{-i})\ne \varnothing$.

Convex values. Fix $\sigma$ and $i$, and let ${\tau }_i,{\tau }_i^{\prime }\in {\mathrm{BR}}_i({\sigma }_{-i})$ share the maximal value $m$. For $\lambda \in [0,1]$,

$$u_i(\lambda {\tau }_i+(1-\lambda ){\tau }_i^{\prime },{\sigma }_{-i})=\lambda u_i({\tau }_i,{\sigma }_{-i})+(1-\lambda )u_i({\tau }_i^{\prime },{\sigma }_{-i})=m,$$

by linearity of $u_i$ in $i$'s own strategy, so $\lambda {\tau }_i+(1-\lambda ){\tau }_i^{\prime }\in {\mathrm{BR}}_i({\sigma }_{-i})$. Hence ${\mathrm{BR}}_i({\sigma }_{-i})$ is convex, and so is the product $\mathrm{BR}(\sigma )$.

Closed graph. Suppose ${\sigma }^k\to \sigma$ in $\Sigma$ and ${\tau }^k\in \mathrm{BR}({\sigma }^k)$ with ${\tau }^k\to \tau$. For each $i$ and every ${\rho }_i\in {\Sigma }_i$, optimality of ${\tau }_i^k$ gives $u_i({\tau }_i^k,{\sigma }_{-i}^k)\ge u_i({\rho }_i,{\sigma }_{-i}^k)$. The map $u_i$ is continuous (multilinear on a compact domain), so passing to the limit yields $u_i({\tau }_i,{\sigma }_{-i})\ge u_i({\rho }_i,{\sigma }_{-i})$ for every ${\rho }_i$, whence ${\tau }_i\in {\mathrm{BR}}_i({\sigma }_{-i})$. Thus $\tau \in \mathrm{BR}(\sigma )$ and the graph of $\mathrm{BR}$ is closed.

By the Kakutani fixed-point theorem there exists ${\sigma }^{\ast }\in \Sigma$ with ${\sigma }^{\ast }\in \mathrm{BR}({\sigma }^{\ast })$, which is precisely the definition of a mixed-strategy Nash equilibrium. $\square$

Proposition (IESDS preserves Nash equilibria). Let $G$ be a finite game, ${\sigma }^{\ast }$ a Nash equilibrium, and let $s_i$ be a pure strategy strictly dominated by some (possibly mixed) ${\tau }_i$. Then ${\sigma }_i^{\ast }(s_i)=0$. Consequently, iterated elimination of strictly dominated strategies removes no Nash equilibrium and introduces none.

Proof. Suppose for contradiction that ${\sigma }_i^{\ast }(s_i)>0$. Build ${\sigma }_i^{\prime }$ by shifting the mass ${\sigma }_i^{\ast }(s_i)$ from $s_i$ onto ${\tau }_i$ and renormalising over the remaining support. By strict dominance and linearity of expected payoff in $i$'s own mix,

$$u_i({\sigma }_i^{\prime },{\sigma }_{-i}^{\ast })>u_i({\sigma }_i^{\ast },{\sigma }_{-i}^{\ast }),$$

contradicting that ${\sigma }_i^{\ast }$ is a best response to ${\sigma }_{-i}^{\ast }$. Hence every strictly dominated strategy receives zero mass in every Nash equilibrium. Since IESDS deletes only strictly dominated strategies, every Nash equilibrium of the original game induces a Nash equilibrium of the reduced game, and conversely any equilibrium of the reduced game is an equilibrium of the original. $\square$

Proposition (mixed equilibrium of matching pennies). The matching-pennies game has a unique Nash equilibrium in which both players randomise uniformly, and the value of the game is zero.

Proof. With Row playing Heads with probability $p$ and Column with probability $q$, Row's payoff from Heads is $2q-1$ and from Tails is $1-2q$. In any equilibrium in which Row mixes, Row must be indifferent, so $2q-1=1-2q$, giving $q=\frac{1}{2}$. The same argument for Column (whose payoffs are negated and who therefore wants to make Row indifferent) gives $p=\frac{1}{2}$. No pure-strategy equilibrium exists because at any pure profile the losing player can profitably deviate. Thus the uniform mix is the unique equilibrium, and the value is $2\cdot \frac{1}{2}-1=0$. $\square$

Connections Master

• Microeconomics 52.01.01. The competitive equilibrium of a large market is the limiting case of a Nash equilibrium in which no single player's deviation moves the price; the welfare theorems are re-derived once strategic interaction is reintroduced through externalities or market power.

• Convex analysis and duality 44.02.03. Nash's existence proof runs on convex machinery — the mixed-strategy simplex, convexity of the best-response argmax for linear payoffs, and the Kakutani fixed-point theorem — that is the formal subject of the convex-analysis chapter.

• Markov decision processes and dynamic programming 44.08.03. Subgame-perfect equilibrium solved by backward induction is the strategic counterpart of Bellman's principle of optimality; repeated and stochastic games are game-theoretic MDPs with multiple controllers.

• Decision theory and Bayesian reasoning 49.06.01. Bayesian games extend single-agent expected-utility maximisation to settings where each player's payoff-relevant type is private, so equilibrium analysis fuses game theory with the decision-theoretic treatment of beliefs and priors.

• Computational complexity 47.02.01. While Nash's theorem guarantees existence, computing an equilibrium is hard: the class PPAD captures the complexity of finding mixed Nash equilibria, so the existence proof and algorithmic tractability are sharply different questions.

Historical & philosophical context Master

Game theory's mathematical birth is John von Neumann's 1928 paper proving the minimax theorem for two-player zero-sum games: every such game has a value, and optimal mixed strategies exist for both players ^{[von Neumann 1928]}. Von Neumann and Oskar Morgenstern's Theory of Games and Economic Behavior (1944) expanded this into a research programme, embedding the expected-utility axioms that let payoffs be treated as numbers and setting zero-sum, cooperative, and extensive-form analysis on a common foundation ^{[von Neumann Morgenstern 1944]}.

The decisive conceptual break came with John Nash's 1950 papers, which generalised the equilibrium notion beyond the zero-sum special case. Where von Neumann and Morgenstern had relied on the bilateral, antagonistic structure of zero-sum play, Nash defined equilibrium for any finite game and proved existence via the fixed-point argument reproduced above ^{[Nash 1950]}. This single concept — a profile of mutually consistent best responses — became the organising idea of non-cooperative game theory.

Reinhard Selten's 1965 introduction of subgame-perfect equilibrium tamed dynamic games by ruling out non-credible threats ^{[Selten 1965]}, and the later development of trembling-hand perfection and Bayesian equilibrium handled strategic uncertainty and private information. John Harsanyi's model of Bayesian games (1967–68) made incomplete information tractable, and Roger Myerson's revelation principle (1981) turned mechanism design into a systematic theory by showing any implementable outcome can be implemented truthfully ^{[Myerson 1981]}. Nash, Harsanyi, and Selten shared the 1994 Nobel Memorial Prize; Myerson, Hurwicz, and Maskin shared the 2007 prize for mechanism design.

Philosophically, game theory reframes Adam Smith's invisible hand: self-interest need not coordinate toward efficiency, as the prisoner's dilemma shows, but well-designed rules — auctions, treaties, contracts — can make self-interest implement desirable outcomes. This is the bridge from the positive analysis of markets in 52.01.01 to the normative engineering of institutions.

Bibliography Master

@book{vonNeumannMorgenstern1944,
  author = {von Neumann, John and Morgenstern, Oskar},
  title = {Theory of Games and Economic Behavior},
  publisher = {Princeton University Press},
  year = {1944},
}

@article{vonNeumann1928,
  author = {von Neumann, John},
  title = {Zur Theorie der Gesellschaftsspiele},
  journal = {Mathematische Annalen},
  volume = {100},
  pages = {295--320},
  year = {1928},
}

@article{Nash1950,
  author = {Nash, John F.},
  title = {Equilibrium Points in $n$-Person Games},
  journal = {Proceedings of the National Academy of Sciences},
  volume = {36},
  number = {1},
  pages = {48--49},
  year = {1950},
}

@article{Selten1965,
  author = {Selten, Reinhard},
  title = {Spieltheoretische Behandlung eines Oligopolmodells mit Nachfragetr{\"a}gheit},
  journal = {Zeitschrift f{\"u}r die gesamte Staatswissenschaft},
  volume = {121},
  pages = {301--324 and 667--689},
  year = {1965},
}

@article{Myerson1981,
  author = {Myerson, Roger B.},
  title = {Optimal Auction Design},
  journal = {Mathematics of Operations Research},
  volume = {6},
  number = {1},
  pages = {58--73},
  year = {1981},
}

@book{FudenbergTirole1991,
  author = {Fudenberg, Drew and Tirole, Jean},
  title = {Game Theory},
  publisher = {MIT Press},
  year = {1991},
}

@book{Myerson1991,
  author = {Myerson, Roger B.},
  title = {Game Theory: Analysis of Conflict},
  publisher = {Harvard University Press},
  year = {1991},
}

@book{Osborne2003,
  author = {Osborne, Martin J.},
  title = {An Introduction to Game Theory},
  publisher = {Oxford University Press},
  year = {2003},
}

@book{Tadelis2013,
  author = {Tadelis, Steven},
  title = {Game Theory: An Introduction},
  publisher = {Princeton University Press},
  year = {2013},
}