Game Theory — Strategy, Competition & Cooperation

🔬 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)

Part 1

🎲 Normal Form Games and Nash Equilibrium

The Prisoner's Dilemma

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.

Part 2

🎰 Mixed Strategies and the Minimax Theorem

Randomize to Win

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.

Part 3

🌳 Sequential Games and Backward Induction

The Power of Commitment

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).

Part 4

🌍 Evolution, Auctions, and Mechanism Design

Darwin's Game

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