Game Theory: The Mathematics of Strategic Interaction

1. Normal Form Games

A normal form (or strategic form) game is the most fundamental representation in game theory. It captures a situation where players choose strategies simultaneously without observing the choices of others.

Formal Definition

A normal form game consists of three components: a finite set of players N (often N = 1, 2, ..., n), a strategy set S_i for each player i in N, and a payoff function u_i mapping strategy profiles to real numbers for each player i. A strategy profile is a tuple (s_1, s_2, ..., s_n) where each s_i is drawn from S_i.

Payoff Matrices

For two-player games, payoffs are conveniently represented as a matrix. Player 1 (the row player) chooses a row, Player 2 (the column player) chooses a column, and each cell contains the payoff pair (u_1, u_2). The convention is to list the row player's payoff first.

Dominant Strategies

Strategy s_i strictly dominates strategy t_i if u_i of (s_i, s_-i) is greater than u_i of (t_i, s_-i) for every strategy profile s_-i of the other players. A rational player will never play a strictly dominated strategy. Weak dominance allows equality in some profiles.

Iterated Elimination of Dominated Strategies (IEDS)

IEDS is a solution procedure that repeatedly removes dominated strategies. In each round, any strictly dominated strategy is eliminated for any player. The process continues until no further elimination is possible. The surviving strategies are called rationalizable. If IEDS yields a unique outcome, the game is said to be dominance-solvable.

Order of elimination does not matter for strict dominance: the set of strategies surviving IEDS is the same regardless of which dominated strategies are removed first. This order-independence fails for weak dominance.

2. Nash Equilibrium

Nash equilibrium is the central solution concept of non-cooperative game theory. Named after John Nash, who proved its existence in 1950, it describes a stable state of a game from which no player has a unilateral incentive to deviate.

Definition

A strategy profile s* = (s*_1, ..., s*_n) is a Nash equilibrium if for every player i and every alternative strategy t_i in S_i, the payoff of player i from the equilibrium strategy is at least as large as from any deviation:

Best Response Correspondence

The best response of player i to the strategy profile s_-i of others is the set of strategies that maximize u_i given s_-i. A Nash equilibrium is precisely a profile where every player is playing a best response to the others simultaneously. The best response correspondence BR_i maps S_-i to subsets of S_i.

Nash's Existence Theorem (1950)

Nash proved that every finite game has at least one Nash equilibrium, possibly in mixed strategies. The proof uses the Kakutani fixed-point theorem applied to the product of best-response correspondences. The key steps are:

1. Extend strategies to mixed strategies (probability distributions over pure strategies)
2. Show the expected payoff is linear (hence continuous) in each player's own mixing probabilities
3. Show best responses form a convex-valued, upper hemicontinuous correspondence
4. Apply Kakutani's theorem to guarantee a fixed point
5. The fixed point is a Nash equilibrium in mixed strategies

Pure vs. Mixed Strategy Nash Equilibria

3. Classic Games and Their Equilibria

Several canonical games have become essential benchmarks in game theory because they distill fundamental strategic tensions. Understanding these games builds intuition for equilibrium analysis.

The Prisoner's Dilemma

Two suspects are interrogated separately. Each can Cooperate (stay silent) or Defect (betray the other). The payoff structure creates a situation where individual rationality leads to mutual harm.

Defect is a strictly dominant strategy for both players: regardless of the opponent's choice, defecting yields a better outcome. The unique Nash equilibrium (Defect, Defect) is Pareto inferior — both players are worse off than if they had both cooperated. This tension between individual and collective rationality is the central message of the game.

Battle of the Sexes

A couple must decide between two activities — say, Opera (preferred by Player 1) and Football (preferred by Player 2) — but both prefer being together over being apart. This is a coordination game with two pure strategy Nash equilibria.

Stag Hunt

Two hunters can cooperate to hunt a stag (large payoff requiring coordination) or individually hunt a hare (smaller but guaranteed payoff). The Stag Hunt models trust and social cooperation: the cooperative outcome is Pareto superior but requires mutual trust.

Matching Pennies

Matching Pennies is the canonical zero-sum game. Player 1 wins if both pennies match; Player 2 wins if they differ. There is no pure strategy Nash equilibrium: whatever pure strategy one player uses, the other can exploit it. The unique Nash equilibrium is fully mixed.

4. Mixed Strategy Nash Equilibrium

A mixed strategy assigns a probability distribution over the pure strategies of a player. Mixed strategy Nash equilibria arise naturally in games without pure strategy equilibria and in games where players benefit from being unpredictable.

The Indifference Condition

The key to computing mixed strategy Nash equilibria is the indifference principle: a player will mix over a set of strategies only if all strategies in their mixing support yield the same expected payoff. If one strategy were strictly better, the player would deviate to playing it with probability 1.

Computing Mixed Strategy NE: Step-by-Step

Consider Battle of the Sexes. Let Player 1 play Opera with probability p and Player 2 play Opera with probability q.

Interpretation of Mixed Strategies

Mixed strategies can be interpreted in several ways. The literal interpretation is that players actually randomize. A more compelling interpretation for one-shot games is epistemic: the mixing probability represents the opponent's beliefs about what the player will do, and the player is indifferent over what to play given those beliefs. In repeated games, mixing can represent the empirical frequency of play across repetitions.

5. Extensive Form Games and Subgame Perfect Equilibrium

Extensive form games capture sequential decision-making by representing the game as a tree. Players move in some order, and later players may or may not observe earlier actions. This representation is essential for modeling negotiations, auctions, and dynamic interactions.

Game Trees

An extensive form game consists of a tree of nodes. Each non-terminal node is a decision node belonging to some player (or to Nature for random events). Edges represent possible actions. Terminal nodes carry payoff vectors for all players. The game begins at the root node.

Information Sets and Perfect vs. Imperfect Information

An information set groups decision nodes that a player cannot tell apart when it is their turn to move. In a perfect information game, each information set contains exactly one node — every player knows the full history of play. In imperfect information games, some information sets have multiple nodes, meaning the player cannot observe some prior actions.

A strategy in an extensive form game specifies an action at every information set of a player — even those information sets that would not be reached under the prescribed strategy. This is important: a strategy is a complete contingent plan, not just a plan for what is likely to happen on the equilibrium path.

Subgame Perfect Equilibrium

A subgame of an extensive form game is a subtree that starts at a single decision node and includes all of its successors, with the requirement that any information set is either entirely in the subgame or entirely outside it. A subgame perfect equilibrium (SPE) is a Nash equilibrium that induces a Nash equilibrium in every subgame.

Backward Induction

Backward induction is the algorithm for computing SPE in finite games of perfect information. Starting from the terminal nodes, determine the optimal action at every final decision node. Then fold back: replace each subtree with the payoff the player at the root of that subtree would achieve under optimal play. Continue until the entire tree is reduced to a single payoff vector at the root.

Ultimatum and Bargaining Games

In the Ultimatum Game, Player 1 proposes a split of a dollar; Player 2 accepts or rejects. Rejection gives both players zero. Backward induction predicts Player 1 offers the smallest positive amount and Player 2 accepts. Experimentally, offers below 30% are frequently rejected, demonstrating that real agents have preferences over fairness, not just money. The Rubinstein bargaining model extends this to alternating offers with discounting and obtains a unique SPE with an explicit formula for the equilibrium split as a function of the discount factors.

6. Repeated Games and the Folk Theorem

Repeated games model long-run interactions where a stage game is played multiple times by the same players. The shadow of future play can sustain cooperation that would be impossible in a one-shot game.

Finitely vs. Infinitely Repeated Games

In a finitely repeated game, backward induction applies: in the last period, no future punishment is possible, so players play the stage-game NE. Working backward, if the stage game has a unique NE, it is played in every period. This means cooperation cannot be sustained in the finitely repeated Prisoner's Dilemma by purely rational players — a sobering result called the end-game problem.

In an infinitely repeated game (or a game that ends with some probability each period), the future always matters. Players discount future payoffs by a factor delta in (0, 1) per period. High delta (patient players) makes cooperation sustainable.

Trigger Strategies

A trigger strategy specifies: cooperate as long as all players have cooperated in every prior period; if anyone has ever defected, defect forever. This is the grim trigger strategy. Under a grim trigger, the value of cooperating today must exceed the temptation gain from defecting plus the cost of permanent future defection.

The Folk Theorem

The Folk Theorem is a family of results stating that essentially any individually rational and feasible payoff can be sustained as an SPE of the infinitely repeated game when players are sufficiently patient.

The Folk Theorem explains why long-term relationships sustain cooperation in markets, cartels, international agreements, and social norms. It also shows that repeated game theory has strong predictive power only when combined with equilibrium selection criteria, since the Folk Theorem admits a vast multiplicity of equilibria.

7. Bayesian Games and Incomplete Information

Bayesian games model situations where players have private information — their own characteristics (types) are known to themselves but not fully observed by others. Harsanyi's framework converts games of incomplete information into games of imperfect information by introducing a prior distribution over types.

Types and Beliefs

Each player i has a type theta_i drawn from a type space Theta_i. Types encode all private information — valuations, costs, capabilities. The joint type distribution P over all types is common knowledge (the prior). Player i knows only their own type and updates beliefs about others' types using Bayes' rule.

Bayesian Nash Equilibrium

A Bayesian Nash equilibrium (BNE) is a strategy profile sigma* such that for each player i and each type theta_i, the strategy sigma*_i(theta_i) maximizes player i's expected payoff, taking expectations over the types of the other players and using their equilibrium strategies.

Signaling Games

Signaling games are a class of Bayesian games where one player (the Sender) has private information and can send a costly signal to another player (the Receiver) who then takes an action. The canonical example is Spence's education model (Nobel Prize 2001): workers have unobservable productivity; education is a costly signal that can separate high-productivity from low-productivity workers even if education has no direct effect on productivity.

Equilibria in signaling games can be separating (different types send different signals) or pooling (all types send the same signal). The Receiver updates beliefs using Bayes' rule after observing the signal and responds optimally. The Perfect Bayesian Equilibrium (PBE) solution concept requires consistent beliefs and sequential rationality at every information set.

8. Mechanism Design and Auction Theory

Mechanism design is sometimes called reverse game theory: instead of analyzing the equilibria of a given game, the designer chooses the rules of the game to achieve a desired outcome. The designer must account for the fact that agents have private information about their preferences (types) and will behave strategically.

Mechanisms and Revelation Principle

A mechanism is a message space M_i for each agent and an outcome function g mapping messages to outcomes. The Revelation Principle states that any outcome achievable by any mechanism can also be achieved by a direct revelation mechanism — where agents report their types directly — in which truth-telling is a dominant strategy (or at least a Bayesian Nash equilibrium). This dramatically simplifies mechanism design: we only need to consider incentive-compatible mechanisms.

VCG Mechanism

The Vickrey-Clarke-Groves (VCG) mechanism is the canonical dominant-strategy incentive-compatible mechanism for social welfare maximization. It selects the outcome maximizing total social welfare and charges each agent the externality they impose on others — the reduction in others' welfare caused by the agent's presence.

Auction Theory: First-Price vs. Second-Price

Auctions are a primary application of mechanism design. In a single-item auction with independent private values, two common formats are:

9. Cooperative Game Theory

Cooperative game theory studies how groups of players can coordinate to achieve better outcomes, and how the resulting gains should be distributed among coalition members. Unlike non-cooperative theory, it takes coalition formation as a primitive and asks what outcomes are stable and fair.

Characteristic Function and Coalitions

A cooperative game in characteristic function form consists of a player set N and a characteristic function v assigning a value v(S) to every coalition S (any subset of N). The value v(S) represents the total payoff the coalition S can guarantee its members, regardless of what players outside S do.

The Core

The core of a cooperative game is the set of payoff allocations x = (x_1, ..., x_n) satisfying two conditions: efficiency (the sum of all x_i equals v(N)) and coalitional rationality (for every coalition S, the sum of x_i for members of S is at least v(S)). An allocation in the core cannot be blocked by any coalition that can do better on its own.

The core may be empty (no stable allocation exists), a single point, or an entire region. Convex games always have a non-empty core. Many matching markets and competitive equilibria correspond to core allocations.

The Shapley Value

The Shapley value is a unique allocation satisfying four axioms that together characterize a fair division of the coalition's surplus. It assigns each player their expected marginal contribution averaged over all possible orderings in which players join the grand coalition.

The Shapley value appears in many applications beyond game theory. SHAP values in machine learning interpret the contribution of each feature to a model's prediction using the Shapley axioms. In political science, the Shapley-Shubik index measures voting power. In cost sharing, the Shapley value distributes joint costs fairly according to the marginal contribution principle.

10. Evolutionary Game Theory

Evolutionary game theory, developed by Maynard Smith and Price in the 1970s, applies game-theoretic concepts to biological populations. Rather than assuming rational optimization, it asks which strategies survive the selection pressure of repeated interaction in a population.

Evolutionarily Stable Strategies (ESS)

A strategy s* is evolutionarily stable if a population playing s* cannot be invaded by a small group of mutants playing any alternative strategy m. Formally, s* is an ESS if for all m not equal to s*:

Hawk-Dove Game

The Hawk-Dove game models competition over a resource of value V against the cost C of injury from fighting. Hawks always fight; Doves always display and retreat when faced with a Hawk. When V is less than C, there is no pure ESS — the stable equilibrium is a mixed population with fraction V/C playing Hawk.

Replicator Dynamics

Replicator dynamics describe how the frequency of strategies evolves over time in a large population. Strategies with above-average fitness grow in frequency; strategies with below-average fitness decline. The replicator equation is:

Replicator dynamics connect evolutionary game theory to dynamical systems. In the Hawk-Dove game with V less than C, the mixed ESS is a globally stable fixed point: any interior initial condition converges to the V/C mixing frequency. In the Prisoner's Dilemma, Defect is a globally stable fixed point under replicator dynamics — cooperation is washed out without additional mechanisms like kin selection, reciprocity, or spatial structure.

11. Zero-Sum Games and the Minimax Theorem

A zero-sum game is one where the payoffs sum to zero in every outcome: one player's gain is exactly the other's loss. Von Neumann's minimax theorem (1928) was the first major theorem in game theory, predating Nash by over two decades.

Minimax and Maximin

In a two-player zero-sum game, Player 1 (the maximizer) wants to maximize their payoff while Player 2 (the minimizer) wants to minimize it. Each player's cautious strategy is to optimize against the worst case:

Saddle Points

A pure strategy Nash equilibrium in a zero-sum game corresponds to a saddle point of the payoff matrix: an entry that is simultaneously the minimum of its row (Player 2 cannot do better by switching columns) and the maximum of its column (Player 1 cannot do better by switching rows). Saddle points exist only in some games; when they do, no mixing is needed in equilibrium.

Linear Programming Duality

Finding the minimax strategy in a zero-sum game is equivalent to solving a linear program. The minimax theorem is equivalent to the LP duality theorem: the primal and dual programs have the same optimal value. This connection enables efficient computation of equilibria in zero-sum games via LP solvers, even for very large strategy spaces. Every Nash equilibrium in a two-player zero-sum game can be found by solving the corresponding LP.

12. Applications Across Disciplines

Game theory has transformed how researchers model strategic behavior across economics, political science, biology, and computer science. Below is a survey of major application domains.

Economics: Oligopoly and Industrial Organization

The Cournot and Bertrand models are the two canonical oligopoly games. In Cournot competition, firms simultaneously choose quantities; the Nash equilibrium price exceeds marginal cost, yielding supracompetitive profits that decline as the number of firms grows. In Bertrand competition, firms simultaneously choose prices; the Nash equilibrium drives prices to marginal cost even with only two firms — the Bertrand paradox. Differentiated products, capacity constraints, and repeated interaction modify these stark predictions.

Political Science: Voting and Elections

The median voter theorem (Hotelling-Downs model) shows that in a one-dimensional policy space with majority rule, both candidates converge to the position of the median voter as a Nash equilibrium. Arrow's Impossibility Theorem shows that no voting rule satisfies all of a small set of desirable axioms simultaneously (Pareto efficiency, non-dictatorship, independence of irrelevant alternatives). The Gibbard-Satterthwaite theorem shows that any deterministic voting rule satisfying mild conditions is subject to strategic manipulation.

Biology: Cooperation and Evolution

Game theory explains altruism and cooperation in biological populations through several mechanisms: kin selection (Hamilton's rule — cooperation evolves when relatedness r times benefit B exceeds cost C), reciprocal altruism (tit-for-tat in repeated interactions), group selection, and network reciprocity (spatial structure allowing cooperators to cluster). The evolution of cooperation in the Prisoner's Dilemma remains an active research area linking game theory, evolutionary biology, and complex systems.

Computer Science: Network Design and AI

Algorithmic game theory studies the computational aspects of strategic interaction. The price of anarchy measures the efficiency loss from selfish routing in networks: the ratio of worst-case Nash equilibrium social cost to optimal social cost. In Braess's paradox, adding a road to a network can increase everyone's travel time. Mechanism design underlies internet advertising auctions (Google, Facebook), spectrum auctions, and matching platforms (residency matching, school choice). In AI, multi-agent reinforcement learning, adversarial training of neural networks, and game-solving algorithms (AlphaGo, Libratus for poker) all apply game-theoretic principles.

13. Practice Problems with Solutions

Work through these problems to master game theory concepts. Click each problem to reveal the solution.

Quick Reference: Key Concepts and Formulas

Further Reading and Resources