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.
🎲 Normal Form Games and Nash Equilibrium
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.
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
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.
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
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.
🌍 Evolution, Auctions, and Mechanism Design
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.
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 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.
🎯 Practice — Check Your Game Theory Intuition
These puzzles build game theory intuition — think strategically.
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.
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.
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.