Game Theory Guide: Strategic Decision Making
Introduction
Game theory studies strategic interactions where the outcome for each participant depends on the choices of all participants. Unlike optimization theory, where a single decision maker controls all variables, game theory analyzes situations involving multiple decision makers with potentially conflicting interests. Each player’s optimal choice depends on what others choose.
The field originated with John von Neumann and Oskar Morgenstern’s 1944 book Theory of Games and Economic Behavior. Since then, game theory has transformed economics, political science, biology, and computer science. It explains price competition between firms, voting behavior in elections, animal signaling in evolution, and protocol design in computer networks.
Normal Form Games
Normal form games specify players, strategies, and payoffs. Each player chooses a strategy simultaneously, and the combination of strategies determines each player’s payoff. The payoff matrix summarizes the game for two players with finite strategy sets.
Representing Normal Form Games
A normal form game is represented by a payoff matrix. For two players with m and n strategies, the payoff matrix has dimensions m×n, with each cell containing the payoffs for both players. The row player chooses a row; the column player chooses a column. The first number in each cell is the row player’s payoff; the second is the column player’s payoff.
The prisoner’s dilemma has the following structure: both players choosing cooperate yields moderate payoffs for both (say 3 each). A defector facing a cooperator gets a high payoff (5) while the cooperator gets nothing (0). Mutual defection yields low payoffs for both (1 each). This structure captures situations where individual incentives conflict with group welfare.
Dominant Strategies
A dominant strategy is optimal regardless of what the other player does. If a player has a dominant strategy, the decision is straightforward — choose it. In the prisoner’s dilemma, defecting is a dominant strategy for both players, yet both would be better off if both cooperated. This tension defines the dilemma.
The prisoner’s dilemma models many real situations: price competition between firms (both would profit from high prices, but each is tempted to undercut), arms races (both prefer disarmament, but each fears the other cheating), and climate agreements (all benefit from cooperation, but each benefits more by free-riding).
Nash Equilibrium
A Nash equilibrium is a strategy profile where no player can benefit by unilaterally changing their strategy. Each player’s strategy is a best response to the others’ strategies. Nash equilibrium is the central solution concept in game theory, capturing the idea of strategic stability.
The prisoner’s dilemma has a unique Nash equilibrium where both defect. The coordination game (choosing sides of the road) has two Nash equilibria: both drive on the left or both on the right. The battle of the sexes has three: both attend boxing, both attend ballet, or a mixed strategy where each randomizes.
Mixed Strategies
In some games, no pure strategy Nash equilibrium exists. Matching pennies — where one player wins if both match, the other wins if they differ — has no pure strategy equilibrium. The mixed strategy equilibrium randomizes between strategies with specific probabilities.
Mixed strategies describe bluffing in poker, randomization in penalty kicks, and inspection games. The equilibrium probabilities balance the payoffs so that each player is indifferent between their pure strategies, making exploitation impossible.
Extensive Form Games
Extensive form games add sequential structure. Players move in sequence, with later players knowing the earlier choices. Game trees represent these games, with branches for each possible action and payoffs at the terminal nodes.
Subgame Perfect Equilibrium
Subgame perfect equilibrium requires that strategies constitute a Nash equilibrium in every subgame. This refinement eliminates noncredible threats — promises or warnings that a rational player would not carry out. Backward induction computes subgame perfect equilibria by solving from the terminal nodes backward.
The entry deterrence game illustrates the concept: an incumbent firm threatens to fight if a potential entrant enters the market. Fighting is costly for both, so the threat is not credible. Subgame perfection recognizes this and predicts entry occurs. The incumbent’s optimal response is to accommodate rather than fight.
Sequential Games and Backward Induction
In sequential games, players observe previous moves before acting. The extensive form represents these games with game trees, where each node belongs to a player and branches represent available actions. Terminal nodes carry payoff vectors.
Backward induction solves sequential games by analyzing from the end backward. At each decision node, the player chooses the action leading to the highest payoff, assuming all future players will also act optimally. The resulting strategy profile is a subgame perfect equilibrium — a Nash equilibrium in every subgame of the original game.
The centipede game illustrates the sometimes counterintuitive results of backward induction. Two players alternate taking increasing shares of a growing pot. Backward induction predicts the first player takes the pot immediately, even though both would be better off if they could cooperate. This paradox highlights the tension between rational individual behavior and collective optimality.
Repeated Games
Repeated play enables cooperation even in games like the prisoner’s dilemma. The shadow of the future — the possibility of future punishment for current defection — can sustain cooperation indefinitely. The folk theorem characterizes the set of payoffs achievable in repeated games with sufficiently patient players.
Tit-for-tat (cooperate on the first move, then copy the opponent’s previous move) is a remarkably successful strategy in repeated prisoner’s dilemma tournaments. It is nice (never defects first), retaliatory (punishes defection), forgiving (returns to cooperation), and clear (easy to understand).
Zero-Sum Games
In zero-sum games, one player’s gain is exactly the other’s loss. Total payoff sums to zero across players. Poker, chess, and many board games are zero-sum. The minimax theorem states that in any finite zero-sum game with mixed strategies, the value exists: max_{p} min_{q} u(p,q) = min_{q} max_{p} u(p,q).
The optimal strategy in zero-sum games is a mixed strategy that makes the opponent indifferent among their actions. This principle determines optimal bluffing frequencies in poker and optimal serve placement in tennis.
Evolutionary Game Theory
Evolutionary game theory applies game theory to biological populations. Strategies are inherited behaviors, payoffs are reproductive fitness, and equilibrium corresponds to evolutionarily stable strategies (ESS). An ESS is a strategy such that if the entire population uses it, no mutant strategy can invade.
Hawk-Dove Game
The Hawk-Dove game models animal conflicts over resources. Hawks escalate fights to the point of injury; Doves display but retreat. Pure hawk and pure dove are not evolutionarily stable. The ESS mixes hawks and doves in proportions determined by the costs and benefits of fighting.
The Hawk-Dove game explains why ritualized displays (rather than escalated fights) are common in nature — the costs of injury make pure aggression evolutionarily unstable. It also models human behaviors like queuing versus pushing.
Replicator Dynamics
Replicator dynamics describes how strategy frequencies change over time. Strategies with above-average fitness increase in frequency; those with below-average fitness decline. Fixed points of replicator dynamics correspond to Nash equilibria of the underlying game. Stable fixed points correspond to evolutionarily stable strategies.
The replicator equation dxi/dt = xi(f_i − φ) governs the frequency xi of strategy i, where f_i is the fitness of strategy i and φ is the average population fitness. The equation captures the essence of natural selection: strategies that outperform the average grow at the expense of underperforming strategies.
Signaling and Cheap Talk
Signaling games model communication between informed and uninformed parties. In the classic job market signaling model, workers choose education levels to signal their productivity to employers. Education is costly, but the cost is lower for high-productivity workers, creating a separating equilibrium where education accurately signals ability.
Cheap talk models communication without direct costs. The sender can send any message at no cost, so the message is credible only if the sender has no incentive to lie. Crawford and Sobel’s model shows that cheap talk can convey information when the sender’s and receiver’s interests are sufficiently aligned, with the amount of information increasing as preferences align more closely.
Applications
Game theory illuminates auction design. The Vickrey auction (second-price sealed-bid) induces truthful bidding as a dominant strategy. The English auction (ascending price) achieves efficient allocation. Spectrum auctions designed by game theorists have generated billions in government revenue.
Political science uses game theory to analyze voting behavior, legislative bargaining, and international relations. The median voter theorem predicts that two-candidate elections converge to the preferences of the median voter. Bargaining models analyze how legislative coalitions form and divide resources.
Computer science uses game theory for mechanism design — creating systems where self-interested participants produce socially desirable outcomes. Cryptocurrency protocols, peer-to-peer file sharing, and ad auctions all rely on game-theoretic principles.
Algorithmic game theory studies computational aspects of games. Computing Nash equilibria is PPAD-complete — believed to be computationally intractable in the worst case. However, learning dynamics like fictitious play and regret minimization converge to equilibria in many settings, and approximation algorithms find near-equilibrium solutions efficiently.
What is the prisoner’s dilemma? Two suspects are interrogated separately. Each can either confess (defect) or remain silent (cooperate). Defecting is a dominant strategy for both, but mutual defection is worse for both than mutual cooperation. The dilemma captures the tension between individual and collective rationality.
What makes a Nash equilibrium stable? A Nash equilibrium is stable if no player has an incentive to deviate unilaterally. Refinements like subgame perfection and evolutionary stability impose additional conditions that ensure deeper stability.
How does repetition enable cooperation? Repetition allows players to punish defection in future rounds. As long as the future matters enough (players are sufficiently patient), the threat of punishment sustains cooperation even in games where one-shot interaction produces defection.
What is an evolutionarily stable strategy? An ESS is a strategy that, if adopted by an entire population, cannot be invaded by any alternative strategy. It is the biological analog of a Nash equilibrium with additional stability against mutation.
Optimization Theory — Mathematical Modeling — Probability Theory Guide