Skip to content
Normal Form GamesNash EquilibriumMixed StrategiesMinimax TheoremSequential GamesBackward InductionEvolutionary GamesAuction TheoryMechanism Design→→→→→Article 21: Strategic Interaction in PolicyNash Equilibrium: no player gains by deviating alonevlymbooq
Game Theory Concept Map Revision Diagram for GS1 Geography — Shows the logical progression from normal‑form games to mechanism design, highlighting equilibrium concepts and solution methods. · Open the full diagram →
🔬 Scientist Pure mathematics — no exam syllabus

Game Theory — The Mathematics of Strategy

Game theory studies strategic decision-making — how rational agents interact when each person's outcome depends on everyone's choices. It began with a poker problem in 1928 (von Neumann's minimax theorem) and grew into a universal language for economics, biology, political science, and artificial intelligence. At its heart is one revolutionary idea: that we can model conflict and cooperation mathematically, and find the stable outcomes that rational players will settle on.

"Game theory is the study of mathematical models of strategic interaction among rational decision-makers."
— John von Neumann & Oskar Morgenstern, Theory of Games and Economic Behavior (1944)

🎲 Normal Form Games and Nash Equilibrium

The Game That Changed Social Science
Two criminals are arrested and interrogated separately. Each can either cooperate (stay silent) or defect (betray the other). If both cooperate, they each get 1 year. If one defects and the other cooperates, the defector goes free and the cooperator gets 5 years. If both defect, they each get 3 years. What should a rational player do? Defecting gives a strictly better outcome regardless of what the other does — it's a dominant strategy. So both defect and get 3 years, even though mutual cooperation (1 year each) would make both better off. This is the tragedy of the prisoner's dilemma: individual rationality leads to collective disaster. It explains arms races, price wars, the tragedy of the commons, and why cooperation is so fragile — and so remarkable when it emerges.
What's rational for each person individually can be terrible for everyone collectively.

Payoff Matrices and Strategy Sets

A game in normal form has three components: players, strategies, and payoffs. For two players, we write a payoff matrix where rows are Player 1's strategies, columns are Player 2's, and each cell contains the payoff pair (u₁, u₂). A strategy s* is a dominant strategy if it gives a strictly higher payoff than any other strategy no matter what the opponent does. A Nash equilibrium is a strategy profile where no player can improve by unilaterally changing their strategy — each player's strategy is a best response to the others'. In the prisoner's dilemma, (Defect, Defect) is the unique Nash equilibrium.

Best Response
BRᵢ(s₋ᵢ) = argmax uᵢ(sᵢ, s₋ᵢ)
Nash Equilibrium
sᵢ ∈ BRᵢ(s₋ᵢ) for all i
Dominant Strategy
sᵢ dominates if uᵢ(sᵢ, t) > uᵢ(rᵢ, t) ∀t
Pareto Optimal
No player can improve without harming another
✨
Solving a 2×2 Coordination Game ▶
Consider two drivers approaching each other. Each can drive on the Left or Right. If both choose the same side, they avoid collision (payoff 1 each). If they choose different sides, they crash (payoff 0 each).

The payoff matrix:
       L    R
L: (1,1) (0,0)
R: (0,0) (1,1)

There are two pure Nash equilibria: (L,L) and (R,R). There's also a mixed equilibrium where each player randomizes 50-50 — but that gives expected payoff 0.5, worse than the pure equilibria. This is why societies converge on one convention (drive on the left in the UK, on the right in the US) — coordination problems have multiple solutions, and history decides which one we pick.

Elimination of Dominated Strategies

Not every game has a dominant strategy. But we can often simplify games by iterated elimination of strictly dominated strategies (IESDS). A strategy is strictly dominated if there's another strategy that always does better. Removing dominated strategies may reveal new dominated ones. This process converges to a set of rationalizable strategies — those that survive common knowledge of rationality. In some games, this uniquely identifies the outcome; in others (like coordination games), it doesn't narrow things down much.

🎰 Mixed Strategies and the Minimax Theorem

Why Poker Players Bluff — and Why It's Mathematical
Not every game has a pure-strategy Nash equilibrium. Consider Rock-Paper-Scissors: whatever you pick, your opponent can counter it. The only stable strategy is to randomize uniformly — play each option with probability 1/3. This is a mixed strategy. Von Neumann's minimax theorem (1928) showed that in any two-player zero-sum game (one player's gain equals the other's loss), there exists a value V such that Player 1 can guarantee at least V and Player 2 can guarantee at most V. The optimal strategies are mixed, and the value V is unique. This is the birth of game theory — von Neumann proved it before he even knew what to call the field. Today, the minimax theorem underlies adversarial training in AI (GANs), security games, and poker-solving algorithms.
When every pure strategy can be beaten, randomization is the rational choice.

Mixed Strategy Nash Equilibrium

A mixed strategy is a probability distribution over pure strategies. A mixed strategy Nash equilibrium exists when each player's mixed strategy makes the other players indifferent among their pure strategies (so they're willing to randomize too). Nash's existence theorem (1950) proved that every finite game has at least one Nash equilibrium (possibly in mixed strategies). This result — proved in Nash's 27-page PhD thesis — earned him the Nobel Prize and became the foundation of modern game theory. To find a mixed equilibrium, solve for probabilities where each player's expected payoff is equal across all pure strategies they play with positive probability.

Nash's Existence Theorem
Every finite game has at least one Nash equilibrium
A brilliant application of Kakutani's fixed-point theorem to economics. Nash's proof took just two pages and changed the world.
✨
Computing Mixed Equilibrium in Matching Pennies ▶
Two players each show a coin. Player 1 wins if both match (both Heads or both Tails). Player 2 wins if they differ.

Payoff matrix (P1 payoff shown, P2 gets the opposite in this zero-sum game):
     H     T
H:   +1   −1
T:   −1   +1

No pure Nash equilibrium exists. For mixed: let p = P1's probability of Heads, q = P2's probability of Heads.
P1's expected payoff given q: if H → q(1) + (1−q)(−1) = 2q−1. If T → q(−1) + (1−q)(1) = 1−2q.
For P1 to be indifferent: 2q−1 = 1−2q → q = 1/2. Similarly, p = 1/2.

The mixed equilibrium: both play Heads with probability 1/2. Expected value of the game = 0.

🌳 Sequential Games and Backward Induction

Backward Induction — Solving Games by Thinking Backward
In extensive form games, players move in sequence, and later players know what earlier players did. These are represented as game trees. The solution concept is subgame perfect equilibrium — found by backward induction: start at the terminal nodes, determine the optimal choice at each decision node, and work backward. Consider a game where you can either take $1 now or let me take $0.50 and give you $2 tomorrow. If I'm rational, I'll take the $0.50 and you get $2 — but if you don't trust me, you take the $1. The ultimatum game shows this beautifully: one player proposes a split of $10, the other accepts or rejects (both get nothing if rejected). Standard theory says the proposer offers $0.01 and the responder accepts (something > nothing). But in real life, people reject unfair offers — because humans care about fairness, not just money.
Backward induction assumes perfect rationality and perfect trust. Real humans are more complex — and more interesting.

Subgame Perfect Equilibrium

A subgame perfect equilibrium (SPE) is a strategy profile that induces a Nash equilibrium in every subgame of the original game. It eliminates non-credible threats — promises to punish that wouldn't actually be carried out. Backward induction finds SPE in finite perfect-information games. The centipede game illustrates a paradox: backward induction says the first player should defect immediately, but if both players are even slightly altruistic, they can cooperate for many rounds and both come out ahead.

Repeated Games and the Folk Theorem

When the same game is played repeatedly, cooperation can emerge even in the prisoner's dilemma. The Folk theorem says that in infinitely repeated games, any feasible payoff vector that's better for each player than their minimax value can be sustained as a Nash equilibrium — provided players are patient enough. Tit-for-tat (cooperate on the first move, then copy the opponent's previous move) is remarkably effective: it's nice, retaliatory, forgiving, and clear. In Axelrod's tournaments, tit-for-tat won against far more complex strategies.

The Folk Theorem
Any feasible, individually rational payoff can be sustained in an infinitely repeated game with sufficiently patient players
The "folk" part comes from it being common knowledge among game theorists before anyone formally proved it. It shows that repetition enables cooperation.
Tit-for-Tat in the Prisoner's Dilemma
In a repeated prisoner's dilemma with tit-for-tat, both players start by cooperating. If one defects, the other defects next round — punishment is immediate but reversible. This creates a stable cooperative equilibrium as long as players care enough about future payoffs (formalized by the discount factor δ > 1/2 for typical payoffs).

🌍 Evolution, Auctions, and Mechanism Design

Evolutionary Game Theory — Survival of the Fittest Strategy
John Maynard Smith realized that game theory applies not just to rational humans but to evolving populations. An evolutionarily stable strategy (ESS) is a strategy such that if the whole population uses it, no mutant strategy can invade. The classic example: in a population of aggressive Hawks and peaceful Doves, the ESS is a mix where the payoff for playing Hawk equals the payoff for playing Dove. This explains why animals don't always fight to the death — ritualized displays (Dove behavior) persist because they're evolutionarily stable. The Hawk-Dove game models territorial disputes, mate competition, and even corporate pricing strategies. Evolutionary game theory replaces rationality with selection — strategies that do well proliferate; those that do poorly die out.
Rationality isn't required for strategic behavior — evolution finds the equilibrium through trial and error over generations.

Auction Theory — The Winner's Curse

Auctions are games with rules designed by the seller. In a first-price sealed-bid auction, the highest bidder pays their bid. In a second-price auction (Vickrey), the highest bidder pays the second-highest bid — which makes truthful bidding a dominant strategy (you should bid exactly what the item is worth to you). The revenue equivalence theorem says that under certain conditions, all standard auction formats yield the same expected revenue. The winner's curse occurs in common-value auctions (like oil drilling rights): the winner tends to be the one who overestimated the value, so winning the auction is bad news. Sophisticated bidders shade their bids downward to avoid this — but that's a strategic choice, and getting it wrong can bankrupt you.

Vickrey Auction
Truthful bidding is dominant
Revenue Equivalence
All standard auctions give same expected revenue
ESS Condition
u(x,x) ≥ u(y,x) for all y
Minimax Value
V = max_{p} min_{q} u(p,q)

Mechanism Design — Reverse Game Theory

In mechanism design, you design the rules of the game to achieve a desired outcome, assuming players will act strategically. The revelation principle says any outcome achievable by some mechanism can also be achieved by a direct revelation mechanism where players truthfully report their private information. The Vickrey-Clarke-Groves (VCG) mechanism generalizes the Vickrey auction to any social choice problem — it makes truthful reporting a dominant strategy and achieves efficient outcomes. VCG mechanisms are used in spectrum auctions, keyword advertising auctions (Google AdWords), and even kidney exchange programs. The challenge: VCG can run deficits, and designing budget-balanced mechanisms that are also strategy-proof is the subject of active research.

✨
Nash's Nobel — A Life of Genius and Struggle ▶
John Nash proved the existence of equilibrium in 1950 when he was just 21 years old. His proof used Kakutani's fixed-point theorem — a deep result from topology — to show that in any finite game, there's a set of strategies where no player wants to deviate.

Nash later developed a severe mental illness (paranoid schizophrenia) and spent decades in and out of hospitals. He recovered remarkably in the 1990s and won the Nobel Prize in Economics in 1994. His life was portrayed in the film "A Beautiful Mind" (2001).

Tragically, Nash and his wife died in a car crash in 2015, returning from Norway where he'd just received the Abel Prize — mathematics' highest honor.
"The best way to predict the future is to design it — mechanism design gives us the tools to build games that align individual incentives with social good."
— Inspired by Roger Myerson and Eric Maskin

🎯 Practice — Check Your Game Theory Intuition

These puzzles build game theory intuition — think strategically.

← Back to Math Map

Bayesian Games and Incomplete Information

In many strategic situations players do not know the exact payoff functions of their opponents. A Bayesian game models this by introducing a set of types for each player, a common prior probability distribution over type profiles, and payoff functions that depend on both actions and types. Each player observes his own type but not the types of others, and chooses a strategy that maps his type to an action. A Bayesian Nash equilibrium (BNE) is a profile of type‑contingent strategies such that each player's strategy maximizes his expected payoff given the strategies of the others and the prior.

Key components

  • Type space Θᵢ for each player i, finite or continuous.
  • Prior μ over Θ = ×ᵢ Θᵢ, common knowledge.
  • Action sets Aᵢ.
  • Payoff uᵢ(a, θ) where a ∈ ×ᵢ Aᵢ and θ ∈ Θ.

Existence and computation

Harsanyi (1967‑68) showed that any Bayesian game can be transformed into an equivalent normal‑form game with incomplete information by expanding the strategy space to functions from types to actions. By applying Kakutani’s fixed‑point theorem to this expanded game, a BNE exists in mixed strategies whenever type and action spaces are finite. Computing a BNE often reduces to solving a system of best‑response correspondences; for two‑player zero‑sum Bayesian games the minimax theorem extends, yielding a value that can be found by linear programming.

Applications

Auction theory (private‑value vs common‑value models), mechanism design with private information, and signaling games (Spence’s job‑market model) are all framed as Bayesian games. In a first‑price sealed‑bid auction with independent private values, the symmetric BNE bidding function is derived from the first‑order condition of expected utility maximization.

Correlated Equilibrium and Communication

A correlated equilibrium (Aumann, 1974) relaxes the independence requirement of mixed‑strategy Nash equilibrium by allowing a correlation device — a public random signal — to recommend actions to players. Formally, a probability distribution σ over action profiles a ∈ A is a correlated equilibrium if for every player i and every pair of actions aᵢ, aᵢ′ with σ(aᵢ) > 0, the conditional expected payoff from obeying the recommendation aᵢ is at least as high as deviating to aᵢ′, given the recommendation. Every Nash equilibrium (mixed or pure) is a correlated equilibrium, but the converse need not hold; correlated equilibria can achieve higher total welfare.

Characterization via linear inequalities

The set of correlated equilibria of a finite game is a convex polytope described by linear incentive constraints: for all i, aᵢ, aᵢ′, Σa₋ᵢ σ(aᵢ, a₋ᵢ)[uᵢ(aᵢ, a₋ᵢ) − uᵢ(aᵢ′, a₋ᵢ)] ≥ 0. This polytope can be computed in polynomial time using the ellipsoid method or interior‑point algorithms, whereas finding a Nash equilibrium is PPAD‑complete.

Communication and cheap talk

When players can exchange costless messages before playing (cheap talk), the set of equilibrium outcomes expands to the communication equilibrium (Forges, 1986). In games with common interests, cheap talk can implement any correlated equilibrium; with conflicting interests, only a subset is achievable. The classic “Battle of the Sexes” with a public coin toss illustrates how a correlation device yields the fair (½,½) payoff, which is not a Nash equilibrium of the base game.

Worked Example: Correlated Equilibrium in Chicken
Consider the Chicken game with payoff matrix (Row, Column):
Swerve‑Swerve (0,0), Swerve‑Straight (−1,1), Straight‑Swerve (1,−1), Straight‑Straight (−10,−10).
Find a correlated equilibrium that yields higher expected payoff than any mixed‑strategy Nash equilibrium.
The mixed‑strategy Nash equilibrium has each player play Straight with probability 1/11, giving expected payoff −10/11 ≈ −0.91. Define a correlation device that recommends (Swerve, Straight) with probability ½ and (Straight, Swerve) with probability ½. If a player receives “Swerve”, the conditional distribution of the opponent’s action is Straight with probability 1, so deviating to Straight yields −10 < 0; obeying yields 0. If a player receives “Straight”, the opponent plays Swerve with probability 1, so deviating to Swerve yields 0 < 1; obeying yields 1. Both incentive constraints hold, so this distribution is a correlated equilibrium. Expected payoff for each player = ½·0 + ½·1 = 0.5, strictly higher than the Nash payoff.
Exam‑Day Strategy
When a question asks for “an equilibrium that improves on Nash”, check whether a public correlation device is allowed. Write down the linear incentive constraints; a simple symmetric recommendation often suffices. Remember that every Nash equilibrium is a correlated equilibrium, so the set of correlated equilibria is never empty.

Cooperative Game Theory and the Shapley Value

Cooperative game theory studies how groups of players (coalitions) can share the total surplus they generate. A transferable‑utility (TU) game is a pair (N, v) where N = {1,…,n} is the player set and v: 2ᴺ → ℝ with v(∅)=0 assigns a worth to each coalition. The central solution concepts are the core, the Shapley value, and the nucleolus.

The core

An allocation x ∈ ℝⁿ (with Σᵢ xᵢ = v(N)) belongs to the core if for every coalition S ⊆ N, Σᵢ∈S xᵢ ≥ v(S). The core is the set of imputations that no coalition can improve upon. The Bondareva‑Shapley theorem states that the core is non‑empty iff the game is balanced (every balanced collection of coalitions has weights summing to at most v(N)). Many market games (e.g., assignment games) have non‑empty cores.

The Shapley value

The Shapley value φ(v) distributes v(N) according to each player’s average marginal contribution over all possible orders of coalition formation: φᵢ(v) = Σ_{S⊆N{i}} (|S|! (n−|S|−1)! / n!) [v(S∪{i}) − v(S)]. It satisfies four axioms: efficiency, symmetry, dummy player, and additivity. The Shapley value is unique with these properties and lies in the core whenever the core is non‑empty and the game is convex (supermodular).

Applications

Cost‑sharing in airport runway construction, voting power indices (Shapley‑Shubik index), and profit allocation in joint ventures. In a three‑player airport game with costs c₁ ≤ c₂ ≤ c₃, the Shapley value allocates incremental costs proportionally to the order in which players “arrive”.

Stochastic Games and Markov Perfect Equilibrium

A stochastic game (Shapley, 1953) extends repeated games by allowing the stage‑game payoff and the transition to the next state to depend on the current state and the action profile. Formally, a stochastic game consists of a finite state space Ω, action sets Aᵢ for each player, stage payoffs uᵢ(ω, a), and transition probabilities p(ω′ | ω, a). Players discount future payoffs with factor δ ∈ (0,1). A Markov perfect equilibrium (MPE) is a profile of strategies that depend only on the current state (not on the full history) and form a subgame‑perfect equilibrium in every state.

Existence and computation

For finite stochastic games with discounted payoffs, an MPE in stationary strategies exists (Fink, 1964). The equilibrium conditions reduce to a system of Bellman optimality equations: for each state ω, the value vector V(ω) satisfies Vᵢ(ω) = maxaᵢ mina₋ᵢ [uᵢ(ω, a) + δ Σω′ p(ω′|ω,a) Vᵢ(ω′)] for zero‑sum games, and a set of coupled best‑response conditions for general‑sum games. Numerical methods (value iteration, policy iteration, linear programming for zero‑sum) compute MPEs.

Applications

Dynamic oligopoly with capacity investment, natural resource extraction, and Markov decision processes in reinforcement learning. In a duopoly where firms choose capacities and the market state is total capacity, MPE captures the strategic effect of today’s investment on tomorrow’s competition.

Network Games and Strategic Complementarities

Network games model situations where each player’s payoff depends on his own action and the actions of his neighbors in a fixed graph G = (N, E). A common specification is the linear‑quadratic payoff: uᵢ(x) = a xᵢ − ½ b xᵢ² + Σj∈Nᵢ c xᵢ xⱼ, where Nᵢ are i’s neighbors, a,b > 0, and c captures strategic interaction. If c > 0 the game exhibits strategic complementarities (higher neighbor actions raise marginal returns); if c < 0 it exhibits strategic substitutes.

Equilibrium characterization

When the best‑response functions are linear, the Nash equilibrium solves (I − (c/b) A) x = (a/b) 1, where A is the adjacency matrix. A unique interior equilibrium exists iff the spectral radius ρ((c/b) A) < 1. The equilibrium action of player i is proportional to his Bonacich centrality in the network, linking network position to strategic influence.

Policy implications

In crime networks, removing a high‑centrality node reduces aggregate activity more than removing a peripheral node. In technology adoption with complementarities, seeding early adopters at central positions maximizes diffusion. The framework extends to incomplete information (Bayesian network games) and to dynamic settings where the network evolves.

  • Confusing Bayesian Nash equilibrium with perfect Bayesian equilibrium — the latter requires sequential rationality and consistent beliefs at every information set.
  • Assuming every correlated equilibrium can be implemented by cheap talk — only communication equilibria are reachable without a mediator.
  • Treating the Shapley value as always in the core — it lies in the core only for convex games.
  • Neglecting the spectral radius condition in network games — without ρ < 1 the linear system has no finite solution.
  • Overlooking the stationarity requirement in Markov perfect equilibrium — history‑dependent strategies are not MPE.
  • Misapplying the revenue equivalence theorem to common‑value auctions — it holds only under independent private values and risk neutrality.
  • Confusing the core with the set of Pareto‑efficient allocations — the core also requires coalitional stability.

These advanced concepts deepen the strategic toolkit and appear frequently in higher‑level quantitative and analytical questions.