Glossary

When your best move depends on what someone else chooses, and their best move depends on yours. The defining feature of a game.

Given a guess about what the other player will do, your best response is the move that pays you most. A different guess can mean a different best move.

A game where cooperation grows the total payoff — both players can win together. Trade, teamwork, and most real-world games have positive-sum elements.

A game where one player's gain is exactly the other's loss — the total payoff is fixed. Splitting a pie is zero-sum; the pie can't grow.

A number representing how good an outcome is for a player. Higher is better. Units don't matter for the analysis — what matters is the comparison.

The average outcome of an uncertain choice — each possible payoff multiplied by its probability, all summed together.

A grid showing what each player gets for every combination of moves. Rows are one player's choices; columns are the other's.

A move that pays you more than any alternative — no matter what the other player does. When you have one, you play it.

A move that pays less than some alternative — no matter what the other player does. A rational player never picks one, so you can throw them away.

Throw away dominated strategies, look at the smaller game, throw away any new dominated strategies, repeat. Sometimes this collapses a game to a single outcome.

A classic game where both players are better off cooperating, but each has a private incentive to defect — and so they often both defect.

A combination of choices where no player can improve their outcome by switching their move alone, given what the others are doing.

A single, definite move — like "play Top" or "choose Hare". The opposite is a mixed strategy (randomizing between moves), which we'll meet later.

A game where both players prefer to match — equilibria are on the diagonal. Stag Hunt and Battle of the Sexes are the canonical examples.

A game where equilibria require players to differ — one yields, the other doesn't. Chicken and Hawk-Dove are the canonical examples.

Solving a sequential or finite-horizon game by reasoning from the end backward. Figure out the last round first, then the second-to-last, and so on. Central to sequential games and finite repeated games.

How much you value the future relative to the present. A high discount factor means the future matters a lot — a long shadow that encourages cooperation today. A low one means impatience, and cooperation falls apart.

A simple strategy for repeated games: cooperate on the first move, then copy whatever your opponent did last round. Famously won Axelrod's tournament.

Rationality limited by what humans can actually compute under real time and cognitive constraints. Herbert Simon's term. Why we use heuristics instead of optimizing every choice.

A framework for how deeply humans reason about each other. Level-0 plays randomly. Level-1 plays best response to level-0. Level-2 plays best response to level-1. Most real players are level-1 or level-2 — almost nobody recurses infinitely.

A simple bargaining game: one player proposes a split of a fixed pie; the other accepts or rejects. If rejected, both get nothing. Rational theory says any positive offer should be accepted; real responders routinely reject low offers, revealing fairness preferences.

A subset of players who agree to act together as a single unit. In a 4-player game there are 16 possible coalitions, from the empty set to the "grand coalition" (everyone). Cooperative game theory studies which coalitions form and how they split joint gains.

The set of allocations to the grand coalition where no smaller coalition has a profitable deviation — every subgroup is content with what they're getting. Core allocations are stable; an empty core means no stable allocation exists at all.

A fair allocation rule: each player's share is their average marginal contribution, averaged over every possible ordering in which the coalition could form. Uniquely satisfies efficiency, symmetry, dummy, and additivity axioms.

When majority preferences over 3+ candidates form a cycle: A beats B, B beats C, C beats A. The group has no consistent "majority winner," even if every individual voter has rational, transitive preferences.

Kenneth Arrow's 1951 result: no ranked voting system with 3+ candidates can simultaneously satisfy universality, non-dictatorship, Pareto, and independence of irrelevant alternatives. Choosing a voting rule means choosing which axiom to sacrifice.

Voting for a candidate other than your true favorite to produce a better outcome. Gibbard-Satterthwaite proves it's unavoidable in any non-trivial voting system: every reasonable rule can be "gamed" in some preference profile.

A strategy that randomizes over pure moves with specific probabilities. A pure strategy is the special case where one move gets probability 1. Mixing matters when your opponent can exploit predictability.

In any mixed-strategy Nash equilibrium, each player's mix must make their opponent indifferent between the moves the opponent is randomizing over. It's the standard tool for solving mixed equilibria in small games.

John Nash proved that every finite game has at least one Nash equilibrium — allowing mixed strategies. Some games have no pure-strategy equilibrium (Matching Pennies), but they always have a mixed one.

A strategy that, when adopted by most of a population, cannot be invaded by any rare alternative strategy — mutants playing the alternative have lower fitness than residents. Every ESS is a Nash equilibrium, but not vice versa.

When a strategy's fitness depends on how common it is in the population. Hawks do well when rare (exploit many Doves) and poorly when common (too many Hawk-vs-Hawk fights). The ESS is the stable frequency where fitnesses balance.

A game in which players move in turns — each player observes the prior moves before choosing their own. Contrasts with simultaneous games where moves are made at the same time. Sequential games are represented as trees.

A diagram of a sequential game showing the sequence of decisions and outcomes. Decision nodes (one per player turn) branch into possible moves; leaves at the bottom show the final payoffs.

A threat the threatener would actually carry out if called on it. Backward induction reveals which threats are credible: if executing the threat would be worst for the threatener at that point, the threat is empty and the other player can ignore it.

The payoff each player receives if bargaining fails — also called the threat point or BATNA (best alternative to a negotiated agreement). A player will never rationally accept a deal that gives them less than their disagreement payoff. Higher disagreement points mean more leverage: the player can credibly walk away from any offer below their outside option, forcing the other side to offer more.

A situation in which two or more parties can jointly create a surplus (a gain available only through agreement), but must negotiate how to divide it. Each party has a disagreement point — what they receive if talks fail — and will only accept outcomes that beat it. Because many splits are mutually preferable to disagreement, standard equilibrium reasoning leaves the outcome indeterminate; additional theory (fairness axioms, dynamic offers, or power asymmetries) is needed to make a unique prediction.

The unique split of a bargaining surplus satisfying John Nash's four axioms: Pareto efficiency, symmetry, scale invariance, and independence of irrelevant alternatives. Formally: choose the outcome (x*, y*) that maximizes the product (x − d₁)(y − d₂), where d₁ and d₂ are the disagreement payoffs. For a fixed-size pie this reduces to giving each player their disagreement payoff plus an equal share of the remaining surplus.

A dynamic bargaining model (Ariel Rubinstein, 1982) in which two players alternate making proposals indefinitely. Both discount the future by factor δ ∈ (0, 1), so delay is costly. Backward induction yields a unique equilibrium: agreement in the first round, with the proposer receiving share 1/(1 + δ) of the surplus (under equal discounting). The model shows that patience is bargaining power: the less impatient player captures a larger share, and as both players become very patient (δ → 1), the split approaches 50/50.

A bargaining or contest situation in which each party holds out hoping the other will concede, but every round of standoff imposes costs on both sides. The surplus shrinks (or disappears entirely) while both parties wait. In a symmetric war of attrition, the equilibrium is mixed: each party concedes with some probability each period, resulting in probabilistic delay and expected surplus destruction. Real-world examples include protracted labor strikes, trade-dispute standoffs, and corporate takeover fights where delay erodes the target's value.

A game has incomplete information when one or more players do not know some payoff-relevant feature of the game — typically the payoffs, preferences, or private values of another player. This is distinct from imperfect information (not knowing past moves) and uncertainty about strategies. Incomplete information is the standard setting for games of private valuations, negotiations over unknown reservation prices, and any market where quality is observable only to one side. John Harsanyi's (1967) type framework transforms incomplete-information games into complete-but-imperfect-information games by introducing a prior distribution over types.

Information held by one player that is payoff-relevant and not directly observable by others. A seller who knows their product's quality has private information; an insurance applicant who knows their health risk has private information; a poker player's hole cards are private information. Private information creates strategic possibilities — concealment, signaling, screening — and inefficiencies — adverse selection, the winner's curse, market unraveling. The central challenge of mechanism design is to create rules that elicit truthful revelation of private information or produce good outcomes despite it.

In Harsanyi's formulation of incomplete-information games, a player's type is a complete description of their private payoff-relevant information — their valuations, costs, preferences, or signal. A seller can be a 'high-quality type' or a 'lemon type'; a buyer can be a 'high-value type' or a 'low-value type.' Each type has its own payoff function. Before play begins, nature draws a type for each player from a commonly known prior distribution. Players observe their own type but not others'. A strategy in a Bayesian game is a mapping from each possible type to an action.

A player's prior belief is their probability distribution over the possible types of another player, formed before observing any actions or signals. In Harsanyi's type framework, the prior is assumed to be common knowledge — both players know the distribution, even though each player's realized type is private. Priors represent background knowledge: the fraction of used cars that are lemons, the distribution of health risks in an insurance pool, the distribution of valuations in an auction. Once a player observes signals or actions during the game, they update their prior to form a posterior — the foundation of Bayesian updating, which appears explicitly in the Signaling unit.

A Bayesian Nash equilibrium (BNE) is a strategy profile in an incomplete-information game where each type of each player plays a best response, given their prior beliefs about the distribution of the opponent's types and the strategies those types will play. It extends Nash equilibrium to settings where payoffs are private: each player maximizes expected payoff by integrating over the probability-weighted strategies of all opponent types. In a BNE, no type of any player can improve their expected payoff by unilaterally deviating. The Bayesian Nash equilibrium is the workhorse solution concept for auctions, mechanism design, and signaling models.

A fact is common knowledge among a group of players if everyone knows it, everyone knows that everyone knows it, everyone knows that everyone knows that everyone knows it — and so on, to arbitrary depth. Common knowledge is strictly stronger than 'mutual knowledge' (everyone knows it). It is the epistemic foundation of Nash equilibrium: players can only be confident their opponents will play equilibrium strategies if they know their opponents know they will, and so on. The failure of common knowledge — when everyone privately knows a fact but no one knows others know it — can prevent coordination even when all the relevant information is 'out there.' Public announcements generate common knowledge where private beliefs cannot.

Cheap talk is communication that is costless to send and costless to fake — a verbal claim, a written statement, or any message whose production costs the sender nothing regardless of its content or their true type. In a game where the sender's interests diverge from the receiver's, cheap talk cannot move a Nash equilibrium: a rational receiver infers that any claim will be made by all sender types (since it is free), and therefore discounts it entirely. Cheap talk can be informative in specific cases — when senders and receivers have perfectly aligned interests, or when the sender's payoff from a false claim is lower than from a true one — but these are special cases, not the general rule. The contrast with costly signaling motivates the rest of the signaling unit: to communicate credibly, senders must take actions, not merely make statements.

In game theory, a signal is a costly, observable action taken by an informed sender (a player who knows their own type) to communicate information to an uninformed receiver. For a signal to be credible — to convey information in equilibrium — it must satisfy the single-crossing condition: the cost or benefit of sending the signal must differ across sender types so that not every type is willing to send it. A signal that is equally costly for all types conveys nothing (everyone sends it). A signal that is differentially costly — expensive for low types, cheap for high types — can sort types in a separating equilibrium. The concept generalizes widely: peacock tails, university degrees, personal investment stakes, luxury consumption, and warranties are all signals in this technical sense.

A costly signal is a specific type of signal whose credibility derives from its cost being borne differentially across sender types. Unlike cheap talk, a costly signal requires the sender to expend real resources — time, money, effort, risk — to transmit information. The mechanism: if the cost is high enough that low types are deterred from sending the signal while high types are not, then only high types send it, and receivers can rationally infer type from the signal's presence. The cost need not be productive; it need only be differentially burdensome. Michael Spence's insight was that education can be a costly signal of ability even if it teaches nothing, because acquiring a degree is harder for low-ability workers than high-ability workers. Amotz Zahavi identified the same logic in biology as the handicap principle.

A signaling game is a two-player sequential game with incomplete information in which an informed sender moves first by choosing an observable action (the signal), and an uninformed receiver observes the signal, updates their beliefs about the sender's type, and responds. The formal structure: (1) Nature draws the sender's type from a commonly known prior; (2) the sender observes their type and chooses a signal; (3) the receiver observes the signal (but not the type) and chooses a response; (4) payoffs are realized. A signaling game is the canonical model for job markets, warranty signaling, animal display, and any setting where an informed party wishes to communicate their private information to an uninformed party whose response affects their payoff. The equilibrium concepts for signaling games extend Bayesian Nash equilibrium; the most refined concept, Perfect Bayesian Equilibrium, specifies beliefs at every information set including those off the equilibrium path.

A separating equilibrium is an equilibrium of a signaling game in which different sender types choose different signal levels, so the receiver can perfectly infer the sender's type from the signal alone. In Spence's job-market model, high-ability workers get degrees and low-ability workers do not — observing whether a worker has a degree perfectly reveals their type. Separating equilibria require the single-crossing condition: the cost of the threshold signal must deter low types but not high types. Separating equilibria can coexist with pooling equilibria in the same game (multiplicity), and multiple separating equilibria can exist at different threshold levels. The least-cost separating equilibrium — where the signal is just sufficient to deter mimicry — minimizes wasteful signaling costs. Separating equilibria are contrasted with pooling equilibria, in which all types send the same signal and the receiver learns nothing.

A pooling equilibrium is an equilibrium of a signaling game in which all sender types choose the same signal level, so the receiver's posterior equals their prior — observing the signal conveys no new information about the sender's type. In a pooling equilibrium, the receiver responds based on the prior's expected type, effectively treating all senders as average. High types receive no wage or price premium for being high-ability; low types avoid the cost of an uninformative signal. Pooling equilibria arise when the separating signal threshold is too costly for high types to justify paying (the wage premium from separation does not cover the signaling cost). Like separating equilibria, pooling equilibria are sensitive to off-path beliefs: what the receiver believes about a sender who deviates from the common signal level determines whether pooling is stable. Pooling is contrasted with separating equilibria, in which types are distinguished.

A bidder's private value is the maximum amount they are personally willing to pay for an item, known only to themselves and independent of other bidders' valuations. In a private-value auction, each bidder has a value that is their own intrinsic preference — a collector's attachment to a painting, a firm's idiosyncratic cost savings from an asset — and the good is worth the same to a bidder regardless of what others would have paid. The private-value assumption contrasts with common-value auctions, where the item has an objective true value shared by all bidders (such as an oil-field lease whose value depends on the quantity of oil underground). Under independent private values, bidders' valuations are drawn independently from a commonly known distribution, providing the foundation for the revenue equivalence theorem. Most auction theory begins with private values as the baseline model before relaxing to interdependent or common values.

An auction is a mechanism for allocating a good or resource through competitive bidding, used when the seller cannot observe individual buyers' valuations. By requiring buyers to submit bids, an auction transfers the task of revealing valuations to the buyers themselves — whoever values the good most will tend to outbid others, achieving an efficient allocation without the seller needing to know who values the good or by how much. Auction formats vary along two key dimensions: whether bids are visible during the process (open vs sealed-bid) and what the winner pays (first-price vs second-price). Common settings include government spectrum license sales, online advertising slot auctions, art and collectibles markets, financial instruments (Treasury bills), and e-commerce platforms. Game theory analyzes auctions as Bayesian games where each bidder's valuation is private information — their type — and optimal bidding constitutes a Bayesian Nash equilibrium.

The revenue equivalence theorem states that under four standard conditions — bidders are symmetric (drawn from the same value distribution), risk-neutral, have independent private values, and the efficient allocation rule holds (highest-value bidder wins) — all auction formats satisfying these conditions yield the same expected revenue to the seller, and each bidder's expected payment is the same across formats. Proved by William Vickrey (1961) and extended by Roger Myerson (1981), revenue equivalence explains why an English auction, a Dutch auction, a sealed-bid first-price auction, and a Vickrey auction all generate the same expected proceeds in theory. The intuition: since all four formats allocate to the same bidder (highest value), the social surplus created is the same; revenue equivalence says the seller-buyer split of that surplus is also the same in expectation, even though payment rules and bidding strategies differ dramatically. Revenue equivalence breaks down when its assumptions are violated: risk aversion favors first-price formats (risk-averse bidders shade less), value interdependence favors open formats (more information revelation), and bidder asymmetry can favor one format over another.

Bid shading is the practice of submitting a bid below one's true private value in a first-price auction (or strategically equivalent Dutch auction) in order to retain positive surplus if one wins. In a first-price auction, a bidder who bids their full value v and wins pays v — earning zero surplus. By shading the bid to some b < v, the bidder earns surplus v − b on a win, at the cost of a reduced probability of winning (since a lower bid is more likely to be beaten by rivals). The optimal shade balances these two effects: the equilibrium bid (n−1)/n × v for n symmetric bidders with uniform private values shades more when competition is weaker (small n) and converges to full value as n → ∞. Bid shading is not irrational or deceptive — it is the equilibrium outcome of first-price auction rules. It contrasts with the second-price (Vickrey) auction, where bidding true value is a dominant strategy because the payment is determined by others, not by one's own bid.

An English auction (also called an ascending-bid or open-outcry auction) is an open auction format in which the price starts low and rises until only one bidder remains. Bidders can observe the current price and, in many variants, which rivals are still active; they drop out when the price exceeds their valuation. The winner pays the price at which the second-last bidder dropped out — effectively the second-highest private value. Under independent private values, the dominant strategy is to remain active until the price reaches your true value: staying in is optimal when the price is below your value (you profit if rivals drop out) and dropping out is optimal when the price exceeds your value (continuing would mean overpaying). The English auction is strategically equivalent to the Vickrey (sealed-bid second-price) auction under independent private values — bidders observe drops in real time, but the strategic problem reduces to the same dominant strategy as in a sealed-bid second-price format. It is the most commonly observed auction format in practice: art auctions at Sotheby's and Christie's, eBay-style online auctions, and many financial auctions use ascending-price formats.

A Dutch auction (also called a descending-bid auction) is an open auction format in which the price starts high and falls until a bidder accepts the current price and wins. The first bidder to call 'yes' wins at the price displayed at that moment. The format is named after its use in Dutch flower markets. Strategically, the Dutch auction is equivalent to a sealed-bid first-price auction: each bidder must decide in advance the price at which they will accept, without observing rivals' behavior (since accepting ends the auction immediately). The equilibrium strategy involves bid shading — calling 'yes' at a price below one's true value to retain surplus — with the optimal shade factor identical to that in sealed-bid first-price auctions. Under the revenue equivalence theorem's assumptions, the Dutch auction generates the same expected seller revenue as the English and Vickrey formats. The term 'Dutch auction' is also used in finance for share buybacks and IPOs where a price is set to sell a target quantity of shares, but this is a different mechanism from the descending-price auction.

In a second-price auction (also called a Vickrey auction), the highest bidder wins but pays the second-highest bid submitted — not their own. This separates the roles of the bid: it determines the winner (cutoff function) but not the payment (determined externally by the runner-up). The consequence is that bidding one's true value is a dominant strategy: overbidding risks winning at a price exceeding one's value (negative surplus), while underbidding risks losing when winning would have been profitable. Neither error can improve outcomes relative to truthful bidding. William Vickrey (1961) proved this rigorously and the format bears his name. The open-bid English (ascending) auction achieves the same payment outcome under independent private values. Second-price auctions are the simplest example of dominant-strategy incentive-compatible (DSIC) mechanisms — designs that make honesty individually rational regardless of others' behavior. They are widely used in internet advertising (Google and Facebook ad auctions use generalized second-price variants) and are the theoretical foundation for VCG mechanisms in multi-item settings.

In a first-price auction, the highest bidder wins and pays exactly the amount they bid. This payment rule creates a strategic tension absent from second-price auctions: a bidder's bid simultaneously determines whether they win and how much they pay if they do win. Rational bidders therefore engage in bid shading — submitting less than their true value to preserve positive surplus on a win. The symmetric Bayesian Nash equilibrium bid function for n bidders with values drawn independently and uniformly from [0, V] is b(v) = (n−1)/n × v: each bidder bids a fixed fraction of their value, with that fraction rising toward 1 as the number of bidders n increases. The Dutch (descending-price) auction is strategically equivalent to the sealed-bid first-price auction: both require the bidder to commit to a threshold price without observing rivals' behavior, and both result in the winner paying their own bid. Under the revenue equivalence theorem's standard assumptions, first-price auctions generate the same expected seller revenue as second-price auctions.

A common-value auction is an auction in which the item has a single true value that is the same for all bidders, but each bidder observes only a private noisy signal of that value rather than the true value itself. Examples include auctions for oil-field leases (the oil is worth what it sells for, regardless of who extracts it), Treasury bill auctions (the bill's true return is the same to all buyers), and corporate takeovers (the target's cash flows are objective facts, not subjective preferences). Common-value auctions contrast with private-value auctions, where each bidder's valuation is idiosyncratic and independent. The common-value structure creates interdependent values: learning that rivals have dropped out is informative, because it reveals their signals were likely low, which should update one's own estimate of the true value downward. Open (English) auctions therefore outperform sealed-bid formats in common-value settings on efficiency grounds — information is revealed during the auction, allowing bidders to update and avoid the winner's curse more effectively. The winner's curse — the tendency to overpay because winning reveals overestimation — is the central strategic challenge in common-value auctions.

The winner's curse is the phenomenon in common-value auctions where the winning bidder tends to have overpaid relative to the item's true value, because winning reveals that the winner had the most optimistic private estimate among all bidders. When estimates are noisy and the true value is uncertain, the bidder with the highest estimate is most likely to have received an upwardly biased signal. Rational bidders anticipate this and shade their bids below their raw estimates by an amount that increases with the number of competitors (more bidders → the highest estimate is more extreme → larger expected upward bias) and with signal noise. Bidders who fail to account for the winner's curse systematically overpay. The winner's curse was first documented empirically in offshore oil-lease auctions (Capen, Clapp, and Campbell, 1971) and has since been observed in corporate takeovers (Roll's hubris hypothesis), IPO subscription, spectrum auctions, and laboratory experiments. The rational response is to ask, when formulating a bid: 'Conditional on my estimate being the highest of n estimates, what is the expected true value?' — which will be lower than the raw estimate.

The Chicken game (also called the Hawk-Dove game) is a two-player simultaneous game in which each player chooses to Escalate or Back Down. If both Escalate, the outcome is catastrophic for both — the worst result. If one Escalates while the other backs down, the escalating player wins and the yielding player loses face but avoids catastrophe. If both Back Down, the outcome is mutually mediocre — neither wins but neither is harmed. The two pure-strategy Nash equilibria are the off-diagonal outcomes where one player escalates and the other yields: (Escalate, Back Down) and (Back Down, Escalate). There is also a mixed-strategy equilibrium. The game is strategically significant because neither player has a dominant strategy — the best response to Escalate is to Back Down, and the best response to Back Down is to Escalate. This anti-coordination structure creates a commitment problem: each player wants to convince the other that they will not yield. The Chicken game models arms races, labor negotiations, political standoffs, and — most famously — the Cuban Missile Crisis. It is the canonical example of a game where credible commitment and the ability to appear irrational are sources of strategic advantage.

The Hawk-Dove game is the evolutionary biology framing of the Chicken game, introduced by John Maynard Smith and George Price (1973). Two animals contest a resource. A Hawk always escalates: it fights until it wins or is injured. A Dove always displays and retreats if the opponent escalates. If two Hawks meet, they fight — the resource is split but both bear injury costs; if costs exceed the resource value, both do poorly. If a Hawk meets a Dove, the Hawk gets the full resource and the Dove retreats unharmed. If two Doves meet, they display until one retreats, splitting the resource without fighting. The evolutionarily stable strategy is a mixed population (or a mixed strategy) that balances Hawk and Dove frequencies based on resource value and injury cost. The Hawk-Dove game is structurally identical to the Chicken game but applied to frequency-dependent selection: in a population of Doves, a Hawk mutant does well; in a population of Hawks, a Dove mutant does well. This frequency-dependence is why neither pure Hawk nor pure Dove is an evolutionarily stable strategy when injury costs are high enough.

Madman theory is the strategic logic, developed by Thomas Schelling, of deliberately appearing irrational, unpredictable, or irrevocably committed in order to make threats credible in commitment games. In games like Chicken, the equilibrium outcome depends on which player is perceived as less likely to back down; a player who appears genuinely willing to accept catastrophe forces the other to yield. The term 'madman' refers not to actual irrationality but to the projected appearance of it — a commitment device that constrains perceived future choices. The Nixon administration's 'madman strategy' in Vietnam (deliberately signaling to North Vietnam and the Soviet Union that Nixon was unpredictable and capable of extreme escalation) is a documented historical application. Schelling formalized the underlying logic in The Strategy of Conflict (1960): the value of commitment comes from the credibility of the constraint, and sometimes the most effective constraint is one that appears beyond rational calculation. Madman theory is a specific instance of the broader Schelling insight that in sequential and commitment games, the ability to limit your own future options is a source of bargaining power, not weakness.

A matching market is a market in which allocation is determined by mutual compatibility or preference, rather than by price. In a matching market, it is not sufficient for one side to be willing to pay — both sides must be willing to be matched. Medical residency programs match doctors to hospitals based on preference rankings submitted by both sides; school choice programs match students to schools; kidney exchanges match donor-recipient pairs by biological compatibility; job markets match candidates to firms. Matching markets arise when price-clearing is impractical (as in school choice, where selling school slots would be considered unjust) or illegal (as in organ markets in most countries), or when mutual acceptability is essential for the match to function. The game-theoretic challenge in matching markets is stability: an allocation is stable if no unmatched pair would mutually prefer to be matched with each other rather than their current assignment. Stable matchings always exist (Gale and Shapley, 1962) and can be found by the deferred acceptance algorithm. Alvin Roth won the 2012 Nobel Prize in Economics for applying matching market theory to kidney exchange, medical residency matching, and school choice.

Mechanism design is the branch of game theory that asks: given a desired social outcome, what rules (payoffs, information requirements, decision procedures) can produce it as an equilibrium? It is sometimes called 'reverse game theory' — instead of taking the game as given and asking what players do, it takes desired behavior as given and asks what game to design. The key challenge is incentive compatibility: the designed mechanism must make the desired behavior rational for participants, even when they have private information or self-interested motives. The Vickrey second-price auction is the canonical mechanism: it makes truthful bidding a dominant strategy, eliciting honest private-value reports without relying on trust. Roth's kidney exchange algorithm makes honest reporting dominant for hospitals. The Gale-Shapley deferred acceptance algorithm makes honest preference reporting dominant for the proposing side. Leonid Hurwicz, Eric Maskin, and Roger Myerson won the 2007 Nobel Prize for developing the theory of mechanism design; Paul Milgrom and Robert Wilson won the 2020 Nobel for applying it to spectrum auctions. The practical impact of mechanism design spans auction formats, school assignment, medical matching, environmental permit markets, and platform economics.

The deferred acceptance algorithm (also called the Gale-Shapley algorithm) is a procedure for finding a stable matching in a two-sided matching market. In the student-proposing version: (1) Each student proposes to their top-ranked school. (2) Each school tentatively accepts its most-preferred applicant among those who proposed, and rejects the rest. (3) Rejected students propose to their next-ranked school. (4) Each school compares newly received proposals with its tentatively accepted student and keeps its most-preferred, rejecting the others. Steps 3-4 repeat until no rejections occur; the tentative acceptances become final. The algorithm terminates in a stable matching that is optimal for students: every student is at least as well off as in any other stable matching. The receiving side (schools) gets the student-optimal stable matching, which may not be their preferred stable matching — and as a result, schools may have incentives to misreport preferences, which is why the algorithm is strategy-proof only for the proposing side. Roth (1984) showed that the US National Residency Matching Program uses the doctor-proposing deferred acceptance algorithm; the same algorithm has been adopted for school choice in New York (since 2003) and Boston (since 2005). The deferred acceptance algorithm is also the theoretical foundation for Roth's kidney exchange — extended to handle chains of three or more incompatible pairs.

A simultaneous ascending auction (SAA), also called a simultaneous multiple-round (SMR) auction, is an auction format in which multiple items are auctioned concurrently over successive rounds. In each round, bidders may raise bids on any item; at the end of each round, the current high bids are published for all to see. The auction ends when no new bids are submitted in a round. Designed by Paul Milgrom and Robert Wilson for the FCC's 1994 spectrum license auction, the SAA solves the price-discovery problem in multi-item auctions: rather than requiring bidders to commit to sealed bids on hundreds of items simultaneously, the multi-round format allows prices to evolve toward equilibrium as bidders respond to rivals' bids and adjust their strategies. The SAA is particularly useful when items are complements — a carrier that needs a contiguous set of licenses can monitor the auction's progress and adjust bids as the bundle becomes more or less achievable. The primary limitation of the SAA is the exposure problem: bidders who want bundles of complementary items may win some but not all, ending up with items they cannot profitably use. Combinatorial auction variants (allowing explicit bundle bids) address this but add computational complexity.

The exposure problem arises in multi-item auctions when a bidder wants a bundle of complementary items but values the bundle much more than the sum of its parts — so that winning a subset of the bundle is worth little or nothing. In a simultaneous auction where items are sold separately, such a bidder faces a dilemma: if they bid aggressively on all items in the desired bundle, they risk winning only a subset (because rivals outbid them on some items), ending up with items they cannot profitably use but have paid for. If they bid conservatively to limit financial exposure, they may fail to acquire any items and miss the opportunity entirely. The exposure problem is most severe when items are strong complements (the subset has near-zero value) and the auction format does not allow bundle bids. The FCC's simultaneous ascending auction mitigates exposure by allowing bidders to monitor competitors' bids in real time and withdraw from items if the bundle is becoming unachievable, but does not eliminate it. Combinatorial auctions — which allow explicit bids on bundles — are the theoretical solution, but they introduce computational complexity (the winner determination problem is NP-hard for large auction instances) and strategic challenges of their own.

A stable matching is an allocation in a two-sided matching market in which no unmatched pair would both prefer to be matched with each other rather than with their current partners. Formally, a matching is stable if there is no 'blocking pair' — a pair such that both prefer each other to their current match. If such a blocking pair exists, the allocation is unstable: the pair has an incentive to bypass the mechanism and arrange a side deal, undermining the allocation. David Gale and Lloyd Shapley (1962) proved that stable matchings always exist in finite two-sided matching markets and can be found by the deferred acceptance algorithm in polynomial time. The student-proposing deferred acceptance algorithm finds the student-optimal stable matching — the best stable matching for the proposing side. The hospital-proposing variant finds the hospital-optimal stable matching. When the proposing side's preferences are reported honestly (which is a dominant strategy), the algorithm is also efficient: no student can be made better off without making another student worse off. Stable matching is the solution concept for matching markets, playing the same role that Nash equilibrium plays in strategic games.