Game Theory

Normal form and dominance

A representation of a game as a table of payoffs indexed by each player's strategy choice, plus the reasoning that follows from comparing payoffs directly.

List players, strategies, and payoffs. A strategy dominates another if it yields higher payoff against every opponent combination. Eliminate dominated strategies iteratively.

Dominance requires no assumption about what opponents will do. A strictly dominated strategy is never a best response, so rational players avoid it.

The big idea

Finite simultaneous-move games. Most games have no dominant strategy, so dominance alone rarely determines the outcome.

When a strategic problem is still just a list of options and payoffs, sometimes the table itself rules out a move. Normal form puts that table in front of you, and dominance asks whether one row or column is worse no matter what the other side does. If such a move exists, it can be discarded without forecasting the opponent; if none exists, the analysis has to move on to mutual best response.

What a normal-form game is

A game in normal form is three objects: a set of players, a set of strategies available to each, and a payoff function assigning each player a number for every combination of strategies. The payoff numbers are von Neumann-Morgenstern utilities, so they already fold in each player’s attitude toward risk and can be averaged under a probability, which is what makes a mixed strategy well defined. For two players with finite strategy sets the entire game is a pair of payoff matrices, and everything the theory concludes about it is a statement about those numbers. A strategy in this representation is a complete plan of action rather than a single move, so even a game that unfolds over several stages can be flattened into one simultaneous choice among plans.

The representation buys its simplicity by erasing time. It records who can do what and how each combination pays, and it says nothing about the order of moves or about what a player has seen when the moment to choose arrives. Games where that sequence carries the meaning, a threat that becomes credible only once it can be observed, need the extensive form introduced later on this page. Normal form is the right tool when the choices are effectively simultaneous and the whole strategic content sits in the payoff table.

Common knowledge

What is assumed to be common knowledge is the strongest assumption in the theory: every player knows the full structure, knows that every other player knows it, knows that they know that they know it, and so on without limit. Common knowledge is an infinite conjunction, not a shared fact, and results derived under it fail when the recursion breaks at any level.

Dominance and elimination

A strategy strictly dominates another if it yields a higher payoff against every possible combination of opponent strategies, and weakly dominates if it is at least as good everywhere and strictly better somewhere.

Iterated elimination of weakly dominated strategies is order-dependent. Two analysts applying the same procedure can reach different answers, and the procedure can delete a strategy that appears in a legitimate equilibrium.

Prisoner’s dilemma structure

The prisoner’s dilemma is the shape of a capability race. Each player prefers to defect regardless of the other’s choice, so defection is strictly dominant and mutual defection is the unique equilibrium, while mutual cooperation would have made both better off.

The escapes are structural rather than exhortative:

• Change the payoffs through enforceable agreement
• Change the horizon so the game repeats and reputation binds
• Change the information so commitments become observable

When dominance fails

Dominance solves very few real games. In most games no strategy dominates any other, because what is best depends on what the opponent does. When dominance fails, the analysis needs a concept of mutual consistency rather than individual optimality, and that concept is equilibrium.

Nash equilibrium

A strategy profile where no player gains by unilaterally changing strategy, given what everyone else is doing.

For each player, check whether their strategy is a best response to the others. A profile is a Nash equilibrium if all players are simultaneously best-responding.

If any player could improve by deviating, they would, so the profile would not persist. The fixed-point condition captures mutual consistency.

The big idea

Any finite game has at least one equilibrium in mixed strategies. The concept is silent on efficiency, fairness, and selection among multiple equilibria.

A product standard, a traffic convention, or a pricing pattern can persist even when nobody likes it very much, as long as every participant would do worse by being the only one to move. Nash equilibrium names that mutual lock. It turns strategic prediction from a single player’s choice into the set of choices that can all survive each other. The payoff is stability as a test, and the limitation is immediate: stability does not choose among multiple locked outcomes or make them good.

$$u_i(s_i^{*}, s_{-i}^{*}) \;\ge\; u_i(s_i, s_{-i}^{*}) \quad \forall i, \; \forall s_i$$

Every player is already doing the best they can given what everyone else is doing. It does not say the outcome is good, efficient, fair, or unique.

symbol	meaning
$u_i$	payoff to player i
$s_i^*$	the equilibrium strategy of player i
$s_{-i}^*$	the equilibrium strategies of everyone except i
$s_i$	any alternative strategy available to i

Fixed-point framing

A Nash equilibrium is a strategy profile in which no player can improve their payoff by unilaterally changing strategy. It is a fixed point of the best-response correspondence: an equilibrium is a profile mapped to a set containing itself.

Nash’s existence theorem states that every finite game has at least one equilibrium in mixed strategies. The proof applies Kakutani’s fixed-point theorem to the best-response correspondence over the simplex of mixed strategies; existence is a topological fact about the shape of the strategy space, and the proof supplies no way to find the equilibrium it guarantees.

Multiplicity and selection

Many games have several equilibria and the concept selects nothing among them. A coordination game where both players prefer to match has two pure equilibria and one mixed. Standards adoption, protocol choice, and market conventions are coordination problems with multiple equilibria, and the interesting question in every one of them is which equilibrium gets selected.

Equilibrium need not be efficient. The unique equilibrium of the prisoner’s dilemma is Pareto dominated, meaning another outcome makes every player better off. Equilibrium is a stability condition and carries no welfare guarantee.

Computational hardness

Computing an equilibrium is PPAD-complete even with two players, the 2006 result of Chen and Deng building on Daskalakis, Goldberg, and Papadimitriou. Above two players the completeness result is for an approximate equilibrium, since the exact one can require irrational probabilities. No polynomial algorithm is known and one is not expected. Computation defines the class and explains why a problem whose answer is guaranteed to exist is hard in a different way than SAT.

The equilibrium concept is usually justified by a story about players learning their way to it. If finding one is computationally intractable, that story fails: bounded agents cannot compute what no efficient algorithm computes.

Practical responses

The practical responses are approximate equilibria, where an $\epsilon$-equilibrium allows each player a small improvement, or correlated equilibrium, which is computable by linear programming.

Bounded rationality and suboptimal play

Models for play when opponents do not compute exact best responses and exact Nash behavior is a poor behavioral forecast.

Replace perfect optimization with bounded search, approximate incentives, finite reasoning depth, or noisy best response.

Latency, information, and compute budgets change the strategy that pays most against the opponent actually present.

The big idea

One-shot games, human opponents, deployed agents with inference budgets, and markets where the safe equilibrium strategy leaves exploitable mistakes unpunished.

Herbert Simon’s 1955 bounded rationality argument replaces maximization with satisficing under a computational and informational budget. The claim is not that agents are irrational in a loose sense. It is that computing the optimum has a cost, and the cost can exceed the value of the improvement. That makes the model directly relevant to any agent whose policy must answer within a latency budget, memory budget, or inference-cost limit.

An $\epsilon$-equilibrium is a strategy profile $s^*$ such that no player can gain more than $\epsilon$ by unilateral deviation:

$$u_i(s_i^{*}, s_{-i}^{*}) \;\ge\; u_i(s_i, s_{-i}^{*}) - \epsilon \quad \forall i, \; \forall s_i$$

The parameter is in payoff units and sets the tolerance that iterative and learning methods can reach in bounded time. Exact equilibria can be computationally intractable while approximate equilibria can be reachable by search, learning, or sampling. The surprise is topological rather than numerical: a profile can be close to equilibrium in payoff and still far from every exact equilibrium in strategy space. Payoff flatness, nearly duplicated actions, or small payoff scaling can make a large strategic move worth less than $\epsilon$.

Stahl and Wilson’s 1995 level models and Camerer, Ho, and Chong’s 2004 cognitive hierarchy model replace infinite mutual best response with finite reasoning depth. A level-0 player follows a non-strategic rule. A level-1 player best-responds to level 0. A level-2 player best-responds to level 1, and so on. Cognitive hierarchy mixes several levels in the population, so a player responds to a distribution of lower-level opponents rather than to a single representative type.

Rosemarie Nagel’s 1995 beauty-contest guessing game is the canonical demonstration. In a $p$-beauty contest, each participant names a number, and the winner is closest to $p$ times the group average. Iterated deletion drives the unique Nash prediction to zero when $0 < p < 1$, but Nagel observed choices clustered at finite reasoning depths instead of at the fixed point. The experiment is evidence about one-shot reasoning, not about what repeated feedback would eventually teach.

McKelvey and Palfrey’s 1995 quantal response equilibrium keeps the equilibrium fixed point but softens best response. Players choose better responses with higher probability rather than choosing the best response with certainty. In the logit version, a precision parameter controls how sharply probability concentrates on high-payoff actions. As precision rises, quantal response approaches Nash; at lower precision, it fits systematic experimental deviations that exact Nash assigns probability zero.

The operational consequence is a trade. Against a suboptimal opponent, the equilibrium strategy is safe because it limits exploitation by a best responder, but it is not maximally profitable against the mistakes actually being made. The exploitative strategy that wins more from those mistakes is itself exploitable once the opponent adapts or is replaced by a sharper one. Poker makes the cost concrete: solver play and exploitative play differ because one protects the floor and the other attacks a measured leak.

Minimax and zero-sum games

Games where one player's gain is exactly the other's loss, which have a unique value that both players can guarantee.

Each player chooses a mixed strategy. The row player maximizes the minimum payoff; the column player minimizes the maximum. The minimax theorem says these coincide.

Randomization removes exploitable patterns. Against any pure strategy, the opponent can best-respond; against the optimal mix, no response beats expectation.

The big idea

Two-player games with strictly opposed interests. Nearly every practical strategic situation is non-zero-sum and inherits none of these properties.

Sometimes the opponent’s interests really are exact opposites: every point one side gains is a point the other side loses. In that setting, choosing a favorite pure action invites the other side to aim directly at it. Minimax reasoning asks what payoff can be guaranteed after both players are allowed to randomize. The gain is a security level, a value the opponent cannot push below, and in the zero-sum case the two players’ security levels meet at a single number. That coincidence is what disappears as soon as both sides can gain or lose together.

No-regret self-play converges in average to the value, and minimax strategies guarantee that value regardless of the opponent’s behavior.

$$\max_{p} \min_{q} \; p^{\top} A q \;=\; \min_{q} \max_{p} \; p^{\top} A q$$

It does not matter who is forced to commit first: the value of a zero-sum game is the same either way. This equality fails the moment the game stops being zero-sum, and almost nothing inherits it.

symbol	meaning
$p, q$	mixed strategies, probability distributions over each side’s actions
$A$	the payoff matrix from the row player’s perspective

Minimax theorem

Von Neumann’s minimax theorem, proved in 1928, states that in a finite two-player zero-sum game, $\max_{x} \min_{y} x^\top A y = \min_{y} \max_{x} x^\top A y$. The equality of the two orders of optimization is the entire content: moving first and being exploited should be worse than moving second with full knowledge, and in general it is; the theorem says that with randomization allowed and interests exactly opposed, it is not.

The common value is the value of the game, every equilibrium achieves it, and all equilibria are interchangeable. Zero-sum games have none of the multiplicity problems described above.

Security level and unexploitability

The security level is the payoff a player can guarantee regardless of what the opponent does. Against a fully informed opponent who knows your mixed strategy and best-responds to it, the optimal mix still guarantees the value.

Randomization is unexploitable rather than cautious. In matching pennies the equal mix guarantees zero against any opponent including one who has read your code. This is the precise sense in which a poker solver’s strategy is optimal: not that it wins the most against a given opponent, but that it cannot be beaten in expectation by any opponent.

Linear programming duality

Linear programming duality is the same theorem in different clothes. Solving a zero-sum game reduces to a linear program, and strong duality (the optimal values of a linear program and its dual coincide) is exactly the minimax equality.

Minimax in machine learning

Application	Structure	Pathology without care
Self-play	Two-player zero-sum	Well-defined; converges to value
GANs	Generator vs. discriminator minimax	Mode collapse, oscillation
Adversarial training	Inner max over perturbations, outer min over weights	Guarantee only as good as attack used

Generative adversarial networks were formulated as a minimax game, and training pathologies occur when a minimax problem is attacked with simultaneous gradient descent, which does not converge to a saddle point in general.

Contrast with non-zero-sum

Property	Zero-sum	Non-zero-sum
Value of game	Exists	Does not exist
Equilibria interchangeable	Yes	No
Efficiency	Trivial, the sum is constant	Not guaranteed
Learning dynamics	Time averages converge	Need not converge at all
Computation	Linear programming, polynomial	PPAD-complete

Nearly every strategic situation of practical interest, including pricing, capability racing, contracting, and platform competition, is non-zero-sum.

A saddle point

Expected payoff to the row player of a two by three zero sum game, against the probability p that the row player picks their first strategy. Three straight lines give the payoff against each of the column player's pure strategies. The lower envelope of those lines is what the row player can guarantee, and it peaks at p equal to 0.6 with a value of 1. The column player, mixing their first two strategies equally, holds the row player to the same 1 from above.

1. row's best mixture, p = 0.6
2. value of the game, 1

Each player is optimizing against the other's worst response. The two paths meet because randomization removes exploitable pure choices, turning a tactical table into a single value neither side can improve unilaterally.

Extensive form and subgame perfection

Games represented as trees of sequential moves, with information sets grouping nodes a player cannot distinguish.

Draw a tree: nodes are decision points, edges are actions, leaves are payoffs. Solve by backward induction, starting at leaves and working up.

Sequential structure lets players condition on history. Subgame perfection rules out threats that would be irrational to execute if the subgame were actually reached.

The big idea

Games with observable order of moves. Perfect information games (chess, Go) are solvable by backward induction; imperfect information games (poker) require different methods.

A payoff table hides the order in which choices happen, and that order can be the whole strategic problem. Extensive form keeps the sequence visible by drawing the game as a tree, including what each player can observe before acting. Once time is explicit, promises and threats can be checked at the moment they would have to be carried out. Subgame perfection keeps only the plans that stay optimal inside every subgame, including the ones equilibrium play never reaches.

Perfect versus imperfect information

Extensive form represents a game as a tree: nodes are decision points, edges are actions, leaves carry payoffs. Information sets group nodes a player cannot distinguish when choosing.

Information	Definition	Solvable by	Example
Perfect	Every information set is a single node	Backward induction	Chess, Go
Imperfect	Some information set contains several nodes	Counterfactual regret	Poker, sealed-bid auctions

Poker resisted superhuman play for about two decades after search beat the world chess champion in 1997.

Backward induction and subgame perfection

Backward induction solves a finite perfect-information game by starting at the leaves and working up: at each node, the player to move picks the action leading to their best outcome given that subsequent play is already determined.

Subgame perfect equilibrium is a strategy profile that constitutes a Nash equilibrium in every subgame, including subgames never reached in actual play. It imposes rationality off the equilibrium path as well as on it.

Non-credible threats

Consider an incumbent facing potential entry, announcing that any entrant will be met with a price war destroying both firms. If the threat is believed, the entrant stays out and this is a Nash equilibrium. Subgame perfection rules it out: in the subgame following entry, fighting is worse for the incumbent than accommodating.

Nash equilibrium permits threats that would be irrational to execute, because it only requires optimality against what actually happens. Subgame perfection requires optimality at every node whether it is reached or not.

Commitment

The commitment advantage is the flip side. If the incumbent can make the threat credible by changing the payoffs (signing a supply contract with a penalty for raising prices, building capacity only economic at high volume, publishing a pricing policy costly to reverse), then fighting becomes optimal in the subgame.

Repeated games and the folk theorem

Games played multiple times between the same players, where current choices affect future interactions.

Define a stage game and a discount factor. Use trigger strategies: cooperate until defection, then punish. The threat of future punishment sustains cooperation.

When the future matters enough, the long-run cost of punishment exceeds the short-run gain from defection, making cooperation self-enforcing.

The big idea

Indefinitely repeated interactions where players are patient and deviations are observable. Cooperation collapses when a known final round exists.

A one-shot prisoner’s dilemma makes defection look unavoidable, because tomorrow carries no penalty. Put the same players back together again with observable behavior and the calculation changes. Repeated games make current payoffs compete with the value of future cooperation, so a threat to punish deviation can support outcomes that fail in the stage game. The folk theorem gives the broad version: many payoff profiles can be sustained when players are patient enough.

Folk theorem

The folk theorem states that in an infinitely repeated game with patient enough players, any feasible payoff profile giving each player more than their minmax value can be sustained as an equilibrium. Repetition transforms the strategic situation completely: outcomes impossible in a single play, including full cooperation in the prisoner’s dilemma, become sustainable when the interaction continues.

Trigger strategies

Trigger strategies prove the result. A grim trigger cooperates until any deviation and then defects forever. The condition for cooperation is:

$$\delta \geq \frac{g}{g + l}$$

symbol	meaning
$\delta$	per-period discount factor
$g$	one-period gain from deviating
$l$	per-period loss once punishment begins

Tit for tat is softer: cooperate first, then copy the opponent’s last move. Grim trigger sustains more outcomes; tit for tat is more robust to error.

Finite versus infinite horizons

When the stage game has a unique equilibrium, as the prisoner’s dilemma does, cooperation collapses in a known finite horizon. In the last period there is no future to protect, so both defect; the unraveling runs all the way back. The result holds for a thousand repetitions as firmly as for two.

Cooperation survives an uncertain horizon because there is no last period to start the induction from. What sustains cooperation is not the expected number of interactions but the absence of a commonly known endpoint. Announcing a final round of a negotiation changes behavior in it.

Application to capability races

A race among a small number of identified participants who expect to keep interacting is a repeated game. The folk theorem says restraint is sustainable in principle if participants are patient, deviations are observable, and punishment is credible.

Unobservable deviation is the binding constraint: a participant who cannot verify whether rivals slowed down cannot condition on it. This is the formal argument for verification regimes: they are the mechanism that makes the agreement an equilibrium, not bureaucratic overhead.

Focal points and equilibrium selection

Focal points are how a specific equilibrium gets selected without communication. Round numbers, prominent dates, existing precedent, natural boundaries and the status quo all serve as focal points. Two parties splitting a sum converge on half because both expect the other to expect it.

Equilibrium selection is the unsolved half of the theory. The folk theorem says a continuum of outcomes is sustainable and says nothing about which one occurs.

Bayesian games

Games where players hold private information, modeled by giving each player a type drawn from a commonly known distribution.

Harsanyi transformation: nature draws types, each player observes only their own, then all choose simultaneously. Equilibrium requires each type to best-respond given the prior over others.

The common prior lets players form beliefs about others. Strategies map types to actions, and equilibrium is mutual consistency of these mappings.

The big idea

Any strategic setting with asymmetric information: auctions, negotiations, signaling. The common prior assumption is strong and often false.

In many negotiations and auctions, the hard part is that each participant knows something the others do not: a valuation, a cost, or an outside option. Bayesian games make that private information part of the game by assigning each player a type and a prior over everyone else’s type. Strategies then have to say what each type would do. The benefit is a way to analyze signaling, bidding, and screening without pretending the information is symmetric.

Harsanyi transformation

A Bayesian game handles private information by giving each player a type, drawn from a distribution, that determines their payoffs and is known only to them. A bidder’s type is their valuation, a firm’s type is its cost, a counterparty’s type is their outside option.

The Harsanyi transformation makes this tractable: introduce a fictitious initial move by nature that draws every player’s type according to a commonly known prior. The game of incomplete information becomes a game of imperfect information. The price is the assumption of a common prior, meaning every player agrees on the distribution types are drawn from.

Bayes-Nash equilibrium

A strategy is a map from types to actions, so it specifies what a player does for every type they might be. Equilibrium requires that for each type, the prescribed action maximizes expected payoff given the prior over other players’ types and their equilibrium strategies.

Signaling and screening

Mechanism	Who moves first	Structure
Signaling	Informed party	Costly action whose cost differs by type
Screening	Uninformed party	Menu designed so each type self-selects

In signaling, Spence’s education model is canonical: education need not be productive, only cheaper for the more capable. A separating equilibrium is one where types choose different actions; a pooling equilibrium is one where they choose the same.

In screening, the uninformed party offers a menu: insurance with a deductible choice, service tiers with different rate limits, contracts trading price against commitment length.

Design constraint

The design constraint is that the action must be differentially costly by type. A signal equally cheap for everyone conveys nothing.

Correlated equilibrium

An equilibrium where a shared random signal coordinates play, and no player wants to ignore their private recommendation.

A device samples a joint distribution over action profiles and privately tells each player their recommended action. Equilibrium holds if no player gains by deviating from the recommendation.

The recommendation is informative about what others were told. Deviating loses the benefit of that information, not just the coordination.

The big idea

Any game. The set of correlated equilibria contains all Nash equilibria, often strictly, and is computable by linear programming.

Independent randomization can leave players missing each other even when coordination would help them both. A shared signal changes the problem because each recommendation carries information about the recommendations others received. Correlated equilibrium describes the joint distribution where every player prefers to follow their private recommendation after seeing it. The reward is a larger, easier-to-compute equilibrium set than Nash, provided the signal device is available.

Concept

A correlated equilibrium is defined with respect to a shared random signal. A device draws an outcome from a known joint distribution and privately recommends to each player a strategy. The distribution is a correlated equilibrium if no player can improve their expected payoff by deviating from the recommendation.

The conditioning is the whole idea: receiving a recommendation is informative about what others were told, and a player who deviates loses the benefit of that information.

Relationship to Nash

Property	Nash	Correlated
Containment	Subset	Superset
Can Pareto dominate	N/A	Yes
Computation	PPAD-complete	Linear programming

Any Nash equilibrium is a correlated equilibrium whose signal distribution is the product of independent mixed strategies. Allowing correlation can strictly enlarge the set, as it does in chicken, and in some games, such as Shapley’s three-strategy game, the additional points Pareto dominate every Nash equilibrium.

Allowing players to condition their choices on a shared signal gives a larger set that a linear program can find in polynomial time. Using correlation requires a trusted device or signal, which may not exist.

Convergence via no-regret learning

If every player runs a no-regret learning algorithm (such as multiplicative weights update), the empirical distribution of joint play converges to the set of coarse correlated equilibria. The equilibrium emerges from independent adaptive behavior without coordination, communication, or knowledge of the payoff structure.

Minimizing external regret buys the coarse set, where a player commits before seeing the signal. Correlated equilibrium proper requires the stronger no-swap-regret condition, which is achievable but by a different and more expensive algorithm. Either guarantee concerns the average of play over many rounds, not the strategies at any single round, where the dynamics can cycle indefinitely.

Traffic lights as intuition

At an intersection, the two pure equilibria are one direction going and the other stopping, both unfair. Independent randomization risks collision. A light is a public signal that recommends going to one direction and stopping to the other, and given the recommendation neither driver wants to deviate.

The equilibrium is enforced by information rather than by penalty. Shared randomness is a coordination resource.

Evolutionary game theory

A framework where strategies spread through a population in proportion to their payoff, without requiring rational calculation.

The replicator dynamic: a strategy's frequency grows when its payoff exceeds the population average and shrinks when it falls below.

Successful strategies leave more copies. The selection pressure mimics optimization without anyone optimizing.

The big idea

Large populations with heritable strategies. Dynamics can cycle or exhibit chaos; convergence to equilibrium is not guaranteed.

A population can adapt even when no individual solves an optimization problem. Strategies that earn higher payoffs leave more copies, so their frequencies rise, while worse performers fade. Evolutionary game theory studies that selection process directly. The useful shift is behavioral humility: a game may have an equilibrium, but the population path generated by payoff-based reproduction can cycle or become chaotic instead of settling there.

Replicator dynamic

Evolutionary game theory replaces the rational optimizer with a population. Strategies have frequencies, payoffs determine growth rates, and successful strategies spread. The replicator dynamic is:

$$\dot{x}_i = x_i \left( f_i(x) - \bar{f}(x) \right)$$

symbol	meaning
$x_i$	frequency of strategy $i$
$f_i(x)$	expected payoff against current population
$\bar{f}(x)$	population average payoff

A strategy grows when it does better than average and shrinks when it does worse. No player computes anything.

Evolutionarily stable strategies

An evolutionarily stable strategy (ESS) is one that, once dominant, cannot be invaded by a small group playing anything else. Every ESS is a Nash equilibrium; not every Nash equilibrium is evolutionarily stable.

Cycling and chaos

The intuitive picture of evolution converging to a stable outcome is often wrong. In rock-paper-scissors under the replicator dynamic, the interior equilibrium is not attracting and trajectories cycle indefinitely.

With four or more strategies and general payoffs, replicator dynamics can produce limit cycles and chaotic trajectories; with three, the flow is planar, so it can cycle around an equilibrium or along a heteroclinic loop but cannot be chaotic. A game can have a well-defined equilibrium that adaptive dynamics never reach.

Population-based training

Methods that maintain a population of agents and reproduce the successful ones are implementing a replicator dynamic. In a non-transitive game where strategy A beats B, B beats C and C beats A, self-play against the current best opponent can chase its own tail indefinitely.

The standard fix is to evaluate against a maintained league of past opponents, which is what the strongest self-play systems in real-time strategy games did.

Shapley value

The unique allocation of a coalition's total value to its members that satisfies efficiency, symmetry, null-player, and additivity axioms.

Average each player's marginal contribution across all possible orders in which the coalition could have formed. The sum is taken over all 2^(n-1) subsets.

The axioms pin down a unique allocation: shares must sum to total value, identical contributors get identical shares, zero contributors get zero, and combined games add.

The big idea

Any cooperative game with transferable utility. Computation is exponential in player count; approximations use random orderings.

A team, coalition, or feature set can create value jointly while leaving no obvious receipt for who produced which part. The Shapley value answers by averaging each participant’s marginal contribution over every order in which the group could have formed. That averaging makes the allocation satisfy the fairness axioms listed below, but it also creates the computational burden: exact calculation has to consider exponentially many possible coalitions.

$$\phi_i = \sum_{S \subseteq N \setminus \{i\}} \frac{|S|!\,(n-|S|-1)!}{n!}\left[v(S \cup \{i\}) - v(S)\right]$$

symbol	meaning
$\phi_i$	the value assigned to player or feature $i$
$v(S)$	the worth of coalition $S$ on its own
$N$	the set of all players, of size $n$
$n$	total number of players
$S$	a coalition not containing $i$

Average how much player i adds to a coalition, over every possible order in which the coalition could have formed.

Four axioms

Axiom	Requirement
Efficiency	Shares sum to total value
Symmetry	Equal contributors receive equal shares
Null player	Zero contribution receives zero share
Additivity	Value of combined games is sum of values

Shapley proved in 1953 that exactly one allocation satisfies all four.

Computational cost

The sum runs over all $2^{n-1}$ subsets, which is 524,288 for twenty players.

Approximation	Method
Monte Carlo	Random orderings, average marginal contributions
Kernel methods	Weighted least-squares over coalition evaluations

SHAP for feature attribution

SHAP applies this construction to features, treating a prediction as the value created by a coalition of feature values. The axioms give its main selling point: attributions sum exactly to the difference between prediction and baseline.

When features are correlated, evaluating $v(S)$ samples feature combinations that never occur in practice. The model is queried far off the data manifold and the attribution reflects behavior on inputs it will never see.

Core

The core asks which divisions are stable against defection: no coalition could do better by leaving. The core can be empty, and when it is, no stable division exists.

The Shapley value always exists and may lie outside the core. One guarantees fair division by axiomatic standards; the other guarantees stability. In general you cannot have both.

Bargaining

The problem of how two parties split a surplus when both can walk away, taking their outside options with them.

Nash bargaining maximizes the product of gains above each party's disagreement payoff. Rubinstein's model has alternating offers with delay costs and a unique equilibrium.

The disagreement point anchors the split because it determines what each party sacrifices by agreeing. Patience matters because delay destroys value.

The big idea

Any negotiation where both sides have outside options. Improving your outside option shifts the split more than improving your argument.

When two parties can both walk away, the persuasive story each tells is usually less decisive than the payoff each keeps by refusing. Bargaining theory starts from that disagreement point and asks how the remaining surplus gets divided. Models differ in what they treat as decisive, some appealing to axioms the split ought to satisfy, others to the cost of waiting through rounds of offers. The practical consequence is blunt: outside options and patience move the split.

Nash bargaining solution

The Nash bargaining solution selects the split that maximizes the product of the parties’ gains:

$$\max (u_1 - d_1)(u_2 - d_2)$$

symbol	meaning
$u_i$	party i’s payoff from agreement
$d_i$	party i’s payoff from disagreement

Four axioms (Pareto efficiency, symmetry, invariance to affine utility transformations, independence of irrelevant alternatives) pin it down uniquely.

Disagreement point

Improving your outside option is worth more than improving your argument. The argument enters through the feasible set; the outside option enters through the reference point that determines how the surplus is divided.

A party negotiating a supply contract improves its position more by qualifying a second supplier than by preparing a better case for why it deserves a discount.

Rubinstein’s alternating-offers model

Two parties alternate proposing a division; each rejection costs delay. The unique equilibrium has the first mover receiving:

$$\frac{1 - \delta_2}{1 - \delta_1 \delta_2}$$

Two features:

• Agreement is immediate because both parties can compute the outcome
• The share depends on relative patience: the party who loses less from delay gets more

Application to compute contracts

Factor	Effect on bargaining position
Workload portability	Improves buyer’s disagreement point
Hard deadline	Makes deadline-holder the impatient party
Unsold capacity	Makes seller the impatient party

Portability is a pricing instrument rather than an engineering nicety.

Matching theory

The study of markets where price does not clear and both sides must choose each other, with stability as the solution concept.

A matching is stable if no pair would both prefer each other to their current partners. Gale-Shapley deferred acceptance finds a stable matching in polynomial time.

Without stability, a blocking pair forms and the matching unravels. Stability is a minimum requirement for a matching to persist.

The big idea

Two-sided markets: labor markets, school assignment, organ exchange. No stable mechanism can be strategy-proof for both sides at once.

Some markets cannot be cleared by posting one price, because both sides care about exactly whom they get. A hospital cannot hire every resident who applies, and a school assignment only works if families and schools are paired under preferences. Matching theory studies these pairings through stability: no unmatched pair should both prefer each other to their assignments. The payoff is persistence, since a blocking pair has a reason to break the arrangement.

$$\nexists \; (m, w) : \; w \succ_m \mu(m) \;\wedge\; m \succ_w \mu(w)$$

A matching is stable when no pair would both rather have each other than their assigned partners.

symbol	meaning
$\mu$	the matching, assigning each agent a partner
$\succ_m$	the preference ordering of agent m
$(m, w)$	a candidate blocking pair

Gale-Shapley deferred acceptance

The algorithm proves stable matchings always exist. The proposing side proposes to their most preferred; the receiving side tentatively holds the best offer and rejects the rest; rejected proposers move to their next choice. It terminates in at most $n^2$ rounds.

Outcome for proposing side	Outcome for receiving side
Best stable matching	Worst stable matching

Which side proposes is a design decision with predictable distributional consequence.

Strategy-proofness

No member of the proposing side can gain by misreporting preferences. Members of the receiving side can sometimes gain by strategically rejecting acceptable offers. No stable matching mechanism can be strategy-proof for both sides at once.

One-sided matching and kidney exchange

Top trading cycles assigns objects to agents where only agents have preferences. Kidney exchange is the application that made it consequential: incompatible donor-recipient pairs can be matched with other pairs for a swap. In the United States, paired exchange facilitated about one in five living donor kidney transplants in 2021.

Market unraveling

Without a clearinghouse, participants make offers earlier than rivals until offers are made long before the information needed exists. Medical residency matching unraveled to positions offered two years before graduation. The fix is a centralized clearinghouse running at a fixed time with a stable algorithm.

Social choice and Arrow theorem

The problem of aggregating individual preferences into a collective ranking, and Arrow's proof that no rule satisfies four reasonable conditions at once.

Arrow showed that with three or more alternatives, every aggregation rule violates at least one of: unrestricted domain, unanimity, independence of irrelevant alternatives, non-dictatorship.

Preferences can cycle. Three voters ranking A over B over C, B over C over A, and C over A over B produce an intransitive majority preference.

The big idea

Any preference aggregation: voting, RLHF, constitutional AI. No neutral procedure exists; every scheme embeds choices about whose preferences count how much.

A group can contain perfectly consistent individuals and still fail to produce a consistent collective ranking. Majority comparisons can cycle, and changing the voting rule only moves the failure into a different assumption. Social choice theory studies that aggregation problem, and Arrow’s theorem is its central warning. The consequence worth carrying is that no voting rule is neutral machinery: every one of them encodes a choice about which fairness condition to give up.

Arrow’s impossibility theorem

Arrow’s theorem, proved in his 1950 paper and developed in the 1951 monograph Social Choice and Individual Values, states that with three or more alternatives, no aggregation rule satisfies four conditions at once:

• Unrestricted domain. The rule accepts any profile of individual rankings.
• Unanimity. If everyone prefers A to B, so does the social ranking.
• Independence of irrelevant alternatives. The social ranking of A against B depends only on individuals’ rankings of A against B.
• Non-dictatorship. No single individual’s ranking determines the outcome regardless of everyone else’s.

Every voting rule violates at least one.

Strategic manipulation

Gibbard and Satterthwaite proved that every deterministic, non-dictatorial voting rule that can select at least three outcomes is manipulable: some voter in some situation gains by misreporting.

With three or more possible outcomes, no reasonable rule makes truthful voting a dominant strategy for every voter in every situation. Observed votes are strategic reports rather than preferences.

Condorcet cycles

With three voters and three alternatives, majority rule can produce cycles: A beats B, B beats C, and C beats A. The social preference is intransitive and no alternative beats all others.

Bearing on alignment

Any scheme that aggregates human preferences into a single objective inherits these limits: RLHF, constitutional approaches, and any procedure that fits a reward model from comparisons. What follows is not that alignment is impossible; it is that no aggregation procedure is neutral.

Escape routes

Escape	Cost
Cardinal utility (range voting)	Intensities not observable, not comparable, manipulable
Domain restriction (single-peaked)	Must actually hold; fails on multidimensional issues
Randomization	Lottery over outcomes few would accept

Every published escape pays one of these three costs.

Price of anarchy

The ratio of social cost at the worst equilibrium to social cost at the optimal allocation, measuring how much selfishness costs.

Compute the cost of the worst Nash equilibrium and the cost of the socially optimal outcome. The ratio is the price of anarchy.

Selfish agents ignore externalities. Each driver taking the fastest route for themselves may congest the system worse than coordinated routing would.

The big idea

Congestion games, routing, load balancing. A ratio near one means decentralized behavior is nearly optimal; unbounded ratios mean coordination is essential.

Decentralized choices can settle into equilibrium and still waste capacity because each participant optimizes their own route, queue, or machine assignment. The price of anarchy measures that waste by comparing the worst equilibrium cost with the best coordinated cost. A small ratio says selfish behavior nearly matches central planning; an unbounded ratio says the rules need assignment, pricing, or admission control before the system should be left to individual incentives.

$$\mathrm{PoA} = \frac{\max_{s \in \mathrm{Eq}} \mathrm{cost}(s)}{\min_{s} \mathrm{cost}(s)}$$

The worst equilibrium divided by the best achievable outcome. A price of anarchy near one means decentralized behavior costs almost nothing.

symbol	meaning
$Eq$	the set of equilibria of the game
$cost(s)$	total social cost of strategy profile s

Known bounds

The price of anarchy depends on the class of game and the shape of the cost functions. For some classes the ratio is a small constant, and for others it grows without bound as the network scales.

Game class	Price of anarchy
Atomic congestion, affine cost	2.5
Load balancing, identical machines	Constant for pure equilibria; grows as log m / log log m for mixed
Selfish routing, affine latency	4/3
Selfish routing, arbitrary nondecreasing	Unbounded

Braess paradox

In a network where traffic splits between two routes, adding a fast connecting link can make every driver slower at equilibrium. The new link is individually attractive, so drivers take it, congesting shared segments.

In a system with self-interested routing, capacity added at the wrong place does not just fail to help; it can hurt.

Design responses

Response	Mechanism
Central assignment	Load balancers, join-shortest-queue
Pricing	Marginal cost tolls, priority pricing
Admission control	Cap load below nonlinear latency regime

All three are ways of not playing the game.

Stackelberg competition

A sequential game where a leader commits to a strategy first and a follower observes and responds.

Solve by backward induction: compute the follower's best response as a function of the leader's choice, substitute into the leader's payoff, and maximize.

By moving first and being observed, the leader changes the follower's problem. The follower must treat the leader's action as fixed.

The big idea

When commitment is observable and irreversible. A commitment nobody sees or one that can be quietly reversed provides no advantage.

Moving first only helps if the second mover has to take that move seriously. A public capacity choice, pricing policy, or randomized defense plan can change the follower’s best response before they act. Stackelberg competition captures this leader-follower structure. Solving it means looking ahead to the follower’s response and choosing the commitment that performs best against that response, so hidden or reversible moves lose the advantage.

Commitment advantage

Stackelberg competition is a sequential game: the leader moves first, the follower observes and responds. The leader advantage comes from commitment: by moving first and being seen to move, the leader changes the follower’s problem.

The advantage requires being observed. A commitment nobody sees is not a commitment, and neither is one that can be reversed. The mechanisms that create it include sunk capacity and irreversible infrastructure investments, published pricing policies with reputational cost, contractual penalties, public capability disclosure schedules, and binding external audits. They function differently from internal intentions with the same content.

Solving the game

The game is solved by backward induction through the follower’s best-response function: compute the follower’s optimal action as a function of the leader’s move, substitute into the leader’s payoff, and maximize.

The leader substitutes the follower’s best response rather than guessing at it because of subgame perfection: the follower will optimize once the leader’s move is fixed, so any leader plan that counts on a different reaction is not credible. Optimizing along the follower’s reaction curve is what separates the Stackelberg outcome from the simultaneous-move one. In quantity competition the leader commits to a large output, the follower answers with less, and the leader earns more than it would if both chose at once while the follower earns less. The whole advantage comes from moving first and being believed; let the follower commit in turn, or hide the leader’s move, and the reaction-curve calculation no longer describes the game.

Security games

Security games are the standard application where the leader commits to randomization rather than to an action. A defender allocates limited resources across targets; an attacker observes the allocation policy, not the realized draw.

Committing to a deterministic allocation is exploitable. The correct allocation is randomized with coverage weighted by target value. Publishing the policy while randomizing the instance is what a well-designed audit regime does.

Mechanism design

The problem of designing game rules so that self-interested players reveal private information or take desired actions.

Specify what outcome you want, then work backward to find rules making that outcome an equilibrium. The revelation principle lets you search over direct truthful mechanisms.

Incentive compatibility aligns individual interest with the designer's goal. Participants act selfishly, but the rules channel selfishness toward the intended outcome.

The big idea

Auctions, matching markets, voting, resource allocation. Myerson-Satterthwaite shows that some efficient outcomes are impossible to achieve.

Sometimes the strategic problem is not choosing a move inside the game, but choosing the rules everyone else will face. Mechanism design starts with the desired outcome and works backward to rules that make self-interested behavior produce it. The key constraint is incentive compatibility: participants must find it best to reveal or act as needed. The limit is just as important, since some efficient trades remain impossible under the usual participation and budget constraints.

Inversion

Mechanism design inverts game theory. Instead of analyzing the outcome of a given game, it asks what game to build so that self-interested play produces a desired outcome. Two constraints bound every design:

• Incentive compatibility. Each participant’s best action is the one the designer wants.
• Individual rationality. Participating is at least as good as staying out.

Revelation principle

Anything achievable by any mechanism is achievable by a direct mechanism in which participants report their private information truthfully. This collapses an unmanageable search over all possible rules into a search over truthful direct mechanisms.

Myerson-Satterthwaite theorem

Consider a single buyer and a single seller with private valuations drawn from overlapping distributions. No mechanism can be simultaneously:

• Incentive compatible
• Individually rational
• Budget balanced
• Efficient (trade happens exactly when buyer values more than seller)

Some trades that should occur will not, in any mechanism whatsoever.

Escapes from the impossibility

Escape	Mechanism
Outside subsidy	Platform underwrites market, relaxes budget balance
Many participants	Exchanges work where bilateral negotiation does not
Mandatory participation	Regulator relaxes individual rationality

Auction theory

The study of how goods are allocated when the seller does not know buyers' valuations, with revenue and efficiency as objectives.

Design a format (sealed-bid, ascending, descending) and allocation rule. Equilibrium bidding depends on information structure: private values versus common values.

Competition among bidders extracts surplus. Second-price and ascending formats make truthful bidding optimal; first-price formats require strategic shading.

The big idea

Single-item sales with private independent values satisfy revenue equivalence. The winner's curse arises in common-value settings where the highest estimate is biased.

A seller often knows the object but not what each buyer would pay, while buyers may know their own values or only noisy estimates of a shared value. Auction theory studies how the format turns that information structure into bids, allocation, and revenue. The same object can call for truthful bidding, strategic shading, or a winner’s-curse correction depending on the rules and information. The payoff is a way to design the sale rather than treating bids as raw demand.

Format comparison

Format	Behavior	Strategic property
First-price sealed-bid	Bid below value (shading)	Strategy depends on beliefs
Second-price sealed-bid	Bid true value	Truthful as dominant strategy
Ascending open	Equivalent to second-price	Under private values
Descending open	Equivalent to first-price	Under any value structure

Revenue equivalence

Under risk neutrality, private independent values, symmetric bidders, no budget constraints, no collusion, and a single indivisible item, all four formats yield the same expected revenue.

When two formats collect different revenue, one of these assumptions is failing.

Common-value settings and the winner’s curse

The item is worth the same to everyone and bidders hold noisy private estimates. The winner is the bidder with the highest estimate, and the highest of several noisy estimates is systematically above the value.

Bidding one’s unbiased estimate loses money on average conditional on winning. The estimate is unbiased unconditionally and biased conditional on the event that determines whether you pay.

Long-term compute capacity contracting has this structure: the buyer who wins a competitive capacity auction is disproportionately the one who forecast demand most optimistically.

The same winner’s-curse problem occurs in spectrum auctions, drilling rights, and acquisitions.

General defense

Every defense against the winner’s curse comes from a single observation: winning is bad news about your own estimate. If you took the item, your bid topped a field of noisy guesses, so your guess was probably on the high side, and the fix is to bid the value you would assign conditional on winning rather than your value in the abstract. That correction grows with the number of rivals, because the maximum of many independent estimates sits further above the truth the more of them there are, and with the noise in those estimates.

Concretely: make the shading explicit, treat competing bidders as a parameter increasing required conservatism, and be suspicious of a win that came at a price no rival was willing to match. In a common-value auction the equilibrium bid already embeds this discount, so the real failure is behavioral, a bidder who reasons from the unconditional estimate and forgets what winning implies. None of it transfers to a pure private-value sale, where your valuation does not move with anyone else’s information and losing teaches you nothing about your own number.