Compendium

Game Theory — Strategic Decision-Making

20 min read

Game Theory — Strategic Decision-Making

Game theory is the mathematical study of strategic interaction — situations where each agent’s best action depends on what others do, and they know it, and they know that the others know, and so on. Born in mathematics, raised in economics, and now applied across computer science, biology, political science, and artificial intelligence, it provides the formal vocabulary for nearly every multi-agent problem worth studying.

This note covers foundations and history, representation, solution concepts, the canonical 2×2 games, repeated and sequential play, games of incomplete information, mechanism design and auction theory, cooperative game theory, bargaining, evolutionary dynamics, the computational frontier, and applications.

1. Foundations and history

1.1 von Neumann–Morgenstern (1944)

John von Neumann and Oskar Morgenstern’s Theory of Games and Economic Behavior (Princeton, 1944) is the founding text. It established:

  • The minimax theorem (vN 1928) for two-player zero-sum games: every finite zero-sum game has a value, and each player has a (possibly mixed) optimal strategy that guarantees that value.
  • The expected-utility axioms that justify treating preferences over lotteries as expectations of a utility function (see behavioral-economics §2).
  • The characteristic-function form for cooperative n-player games.

The book unified mathematical economics with rigorous decision theory and remains foundational despite — or because of — its dense formalism.

1.2 Nash and the equilibrium concept (1950)

John Nash (Nobel 1994, shared with Harsanyi and Selten — the first of three Nobels for non-cooperative game theory) showed in his 1950 PNAS paper and 1951 Annals of Mathematics paper that every finite game with mixed strategies has at least one equilibrium. Nash equilibrium became the dominant solution concept for non-cooperative game theory and remains so today.

The 1994 Nobel Committee specifically cited:

  • Nash — the equilibrium concept and existence theorem.
  • John Harsanyi — games of incomplete information (Bayesian games, Harsanyi transformation).
  • Reinhard Selten — subgame perfection and equilibrium refinements.

1.3 Three Nobels for game theory

YearLaureatesContribution
1994Nash, Harsanyi, SeltenNon-cooperative equilibrium theory
2005Aumann, SchellingConflict and cooperation through game theory (correlated eq., focal points)
2007Hurwicz, Maskin, MyersonMechanism design
2012Roth, ShapleyStable matching, market design
2014TiroleMarket power, regulation (heavy GT content)
2020Milgrom, WilsonAuction theory and practical auction design

Several other Nobels — Akerlof/Spence/Stiglitz 2001 (asymmetric information), Holmström/Hart 2016 (contracts) — also rest on game-theoretic foundations.

2. Representing games

2.1 Normal (strategic) form

A normal-form game is a triple G = (N, S, u) where:

  • N = {1, …, n} is the set of players.
  • S_i is player i’s strategy set; S = S_1 × … × S_n the joint strategy space.
  • u_i : S → ℝ is player i’s utility (payoff) function.

For finite two-player games this is a matrix with one entry per cell.

2.2 Extensive form

A game tree with nodes for choice points, edges for actions, terminal nodes labeled by payoffs, and information sets grouping indistinguishable nodes (for imperfect information). Extensive form captures sequencing and information flow that normal form collapses.

2.3 Strategies and strategy profiles

  • A pure strategy for player i is an element s_i ∈ S_i.
  • A mixed strategy is a probability distribution σ_i ∈ Δ(S_i) over pure strategies.
  • A behavioral strategy (extensive form) is a probability distribution over actions at each information set.
  • A strategy profile is (s_1, …, s_n) or (σ_1, …, σ_n).
  • −i denotes “everyone except i.”

3. Solution concepts (non-cooperative)

3.1 Dominance

  • A strategy s_i is strictly dominated if some other strategy s’i yields strictly higher payoff for every opponent profile s{−i}.
  • Iterated elimination of strictly dominated strategies (IESDS) repeatedly removes dominated strategies; the order of elimination does not matter.
  • IESDS rarely solves games on its own (only those that are dominance-solvable, e.g. prisoner’s dilemma).

3.2 Nash equilibrium

A strategy profile σ* is a Nash equilibrium if no player can strictly improve by unilateral deviation:

u_i(σ*_i, σ**{−i}) ≥ u_i(σ_i, σ**{−i}) for all σ_i, all i.

In words: each player’s strategy is a best response to the others’. A NE need not be unique, Pareto-efficient, or fair.

Nash existence theorem (1950): every finite game has at least one Nash equilibrium in mixed strategies. Proof uses Kakutani’s fixed-point theorem applied to the best-response correspondence.

3.3 Mixed strategies and the indifference condition

A player who mixes between two pure strategies must be indifferent between them given opponents’ strategies (otherwise they would pick the better one with probability 1). This indifference condition is the standard tool for computing mixed-strategy equilibria.

Worked example (matching pennies):

HeadsTails
Heads(+1, −1)(−1, +1)
Tails(−1, +1)(+1, −1)

For Row to be indifferent, Column must play H and T with equal probability. Symmetry gives the unique NE: both mix 50/50, expected payoff 0.

3.4 Correlated equilibrium (Aumann 1974)

Robert Aumann (Nobel 2005) generalized Nash equilibrium. A trusted device sends each player a (correlated) private signal recommending an action; if no player benefits from deviating from the recommendation given their own signal, the joint distribution is a correlated equilibrium (CE).

  • Every Nash equilibrium is a CE; the converse is false.
  • CE can yield strictly higher payoffs than any NE (e.g. traffic-light coordination).
  • CE is computable in polynomial time, unlike NE (see §10).

3.5 Evolutionarily stable strategy (Maynard Smith 1972)

In biological populations, John Maynard Smith proposed the ESS: a strategy x is an ESS if, when adopted by the entire population, no mutant strategy y can invade. Formally, either u(x, x) > u(y, x), or u(x, x) = u(y, x) and u(x, y) > u(y, y), for all y ≠ x.

Every ESS is a symmetric Nash equilibrium; not every symmetric NE is an ESS.

4. Canonical 2×2 games

4.1 Prisoner’s dilemma

CooperateDefect
Coop.(3, 3)(0, 5)
Defect(5, 0)(1, 1)

Defect strictly dominates Cooperate for each player. Unique NE: (Defect, Defect) with payoff (1, 1). Mutual cooperation (3, 3) Pareto-dominates the equilibrium — the central paradox.

Sustainable cooperation requires repetition (Folk theorem §5), binding agreements (move to cooperative GT), or altered preferences (social preferences, reputation, kin selection).

4.2 Stag hunt

StagHare
Stag(4, 4)(0, 3)
Hare(3, 0)(3, 3)

Two pure NE: (Stag, Stag) — payoff-dominant — and (Hare, Hare) — risk-dominant. The stag hunt is the canonical coordination game with a trust component: hunting Stag is best if your partner does the same, but going alone after Stag means starvation.

4.3 Chicken / Hawk-Dove

SwerveStraight
Swerve(0, 0)(−1, 1)
Straight(1, −1)(−10, −10)

Two pure asymmetric NE — (Swerve, Straight) and (Straight, Swerve) — plus a mixed NE. The biological hawk-dove version (Maynard Smith) explains aggression-display equilibria in animal contests.

4.4 Battle of the sexes

OperaFootball
Opera(2, 1)(0, 0)
Football(0, 0)(1, 2)

Coordination with conflicting preferences. Two pure NE (both coordinate) plus a mixed NE that is Pareto-dominated.

4.5 Matching pennies

Pure conflict — zero sum. No pure NE; unique mixed NE at 50/50 (§3.3). The canonical example for mixed strategies.

5. Repeated games and the folk theorem

5.1 Finitely repeated games

If a finite-horizon game has a unique stage NE, backward induction unravels cooperation: in the last period, defect; anticipating that, defect in the penultimate period; and so on. Finitely-repeated prisoner’s dilemma has a unique SPNE of all-defect.

5.2 Infinitely repeated games and the folk theorem

In an infinitely repeated game (or one with continuation probability δ ∈ (0,1)), almost any feasible, individually-rational payoff profile can be sustained as a subgame-perfect equilibrium with patient enough players. This is the folk theorem (Friedman 1971 for Nash; Fudenberg & Maskin 1986 for SPNE).

Key strategies:

  • Trigger strategies (Friedman): cooperate forever; defect forever after first defection. Sustains (C, C) iff δ ≥ (T − R)/(T − P), where T is temptation, R reward, P punishment.
  • Tit-for-tat (Anatol Rapoport): cooperate first round, then copy opponent’s previous move. Famously won Robert Axelrod’s 1980 tournaments (analyzed in The Evolution of Cooperation, 1984). Properties: nice, retaliatory, forgiving, clear.

5.3 Reputation and finite-horizon cooperation

Kreps, Milgrom, Roberts & Wilson (1982) — the “gang of four” — showed that even in finitely-repeated PD, small uncertainty about opponent rationality (e.g. a tiny probability of facing a tit-for-tat type) sustains cooperation for many rounds via reputation. This is one of the foundational results in industrial organization.

6. Sequential games

6.1 Backward induction

In games of perfect information, work back from the leaves of the game tree. At each node, the moving player chooses the action maximizing their payoff given optimal future play. The result is the unique backward-induction equilibrium (when payoffs at terminal nodes are distinct).

6.2 Subgame-perfect Nash equilibrium

Reinhard Selten (Nobel 1994) defined SPNE: a strategy profile is SPNE if it induces a Nash equilibrium in every subgame. SPNE eliminates non-credible threats — Nash equilibria sustained only by promises the threatener would not actually carry out off the equilibrium path.

6.3 Centipede game (Rosenthal 1981)

Players alternate; each can either take a growing pile or pass; if both pass repeatedly, the pile keeps doubling. Backward induction predicts the first player takes immediately. Experimentally, most players pass for several rounds — a classic empirical violation of SPNE.

6.4 Ultimatum game

(See behavioral-economics §9.1.) Proposer offers a split; Responder accepts or rejects. Self-interested SPNE: proposer offers ε, responder accepts. Empirically: ~40–50% offers; rejections of low offers ~50%. The single clearest experimental failure of standard non-cooperative theory.

7. Games of incomplete information

7.1 Harsanyi transformation (1967–68)

John Harsanyi (Nobel 1994) showed how to convert a game of incomplete information (players don’t know each others’ payoffs) into a game of imperfect information (they don’t know each others’ moves) by introducing types drawn from a common prior. Each player has a private type t_i ∈ T_i; type spaces are commonly known; the distribution over type profiles is common knowledge.

7.2 Bayesian Nash equilibrium

A strategy is a map σ_i : T_i → Δ(S_i). A Bayesian Nash equilibrium (BNE) has each player maximizing expected utility given their own type and the conditional distribution over opponents’ types and strategies.

7.3 Perfect Bayesian equilibrium

For dynamic Bayesian games, PBE adds belief consistency: at every information set, beliefs are derived from prior + strategies via Bayes’ rule (where possible), and players play optimally given those beliefs.

7.4 Signaling games — Spence (1973)

Michael Spence (Nobel 2001, with George Akerlof and Joseph Stiglitz) modeled education as a signal of worker productivity in a labor market with asymmetric information. High-productivity workers can attain education at lower cost than low-productivity workers; firms cannot observe productivity directly. The separating equilibrium has high types acquire education and earn high wages; low types do not and earn low wages. Education conveys information even if it produces no direct productivity.

Pooling vs separating equilibria, the intuitive criterion (Cho & Kreps 1987), and divinity refinements (Banks & Sobel 1987) discipline equilibrium selection.

8. Mechanism design

8.1 Revelation principle and Myerson

Roger Myerson (Nobel 2007, with Hurwicz and Maskin) proved the revelation principle: any social-choice function implementable by some mechanism is implementable by a direct, incentive-compatible mechanism in which agents truthfully report their types. This dramatically simplifies the design problem — design over the class of truth-telling mechanisms.

The 2007 Nobel honored:

  • Leonid Hurwicz — foundations of mechanism design; incentive compatibility.
  • Eric Maskin — implementation theory; Maskin monotonicity.
  • Myerson — optimal auctions, revenue equivalence.

8.2 VCG mechanisms

William Vickrey (Nobel 1996) introduced the second-price sealed-bid auction: highest bidder wins, pays second-highest bid. Truthful bidding (bidding your value) is a weakly dominant strategy. Generalizations:

  • VCG (Vickrey-Clarke-Groves) mechanisms apply to general allocation problems; each agent pays the externality they impose on others. Truthful reporting is dominant-strategy incentive-compatible.
  • VCG is efficient but not always budget-balanced and is vulnerable to coalition manipulation in multi-unit settings.

8.3 Auction theory and revenue equivalence

Myerson’s revenue equivalence theorem (1981): for any two auctions with the same allocation rule and the same expected payoff to a bidder with the lowest possible value, expected revenue is the same.

Standard auction formats for a single indivisible good with independent private values:

  • First-price sealed bid — highest bidder wins, pays own bid; bidders shade below their value.
  • Second-price sealed (Vickrey) — pays second-highest bid; truthful.
  • English (ascending open) — strategically equivalent to Vickrey with private values.
  • Dutch (descending open) — strategically equivalent to first-price sealed.

All four yield the same expected revenue under revenue equivalence assumptions. They diverge with risk aversion, correlated values, or budget constraints.

Common-value auctions introduce the winner’s curse (Capen, Clapp & Campbell 1971; Wilson 1969): the winner is the bidder who most overestimated the common value. Optimal bidding requires shading by the expected curse — a major theme of Robert Wilson’s Nobel-winning work (2020, with Paul Milgrom).

8.4 Practical mechanism design

  • FCC spectrum auctions (Milgrom, Wilson, McAfee 1994–): simultaneous multiple-round (SMR) auctions; later the combinatorial clock auction. The 2020 Nobel cited these specifically.
  • Kidney exchange (Roth, Sönmez, Ünver 2004): chains and cycles of incompatible donor-recipient pairs. Now standard in major transplant networks; Alvin Roth shared the 2012 Nobel with Lloyd Shapley.
  • School choice (Boston, NYC): truncation-proof mechanisms — deferred acceptance over Boston Mechanism.
  • NRMP / residency matching: uses Gale-Shapley deferred acceptance (1962) — stable, strategy-proof for the proposing side.

9. Cooperative game theory

9.1 Characteristic function and the core

A cooperative game is (N, v) where v: 2^N → ℝ assigns a value to each coalition. The core is the set of payoff allocations x with Σ x_i = v(N) (efficiency) and Σ_{i∈S} x_i ≥ v(S) for every coalition S (no blocking).

The core can be empty (no stable allocation) or large. Convex games (v(S∪T) + v(S∩T) ≥ v(S) + v(T)) always have a non-empty core, and the Shapley value lies in it.

9.2 Shapley value

Lloyd Shapley (Nobel 2012) defined the unique allocation rule satisfying efficiency, symmetry, dummy, and additivity:

φ_i(v) = Σ_{S ⊆ N \ {i}} [|S|! (n − |S| − 1)! / n!] · [v(S ∪ {i}) − v(S)]

— the expected marginal contribution of i over all orderings. Used in cost allocation, ML feature attribution (SHAP — Lundberg & Lee 2017), and influence measurement.

9.3 Nucleolus

Schmeidler (1969): minimizes the lexicographically largest coalition dissatisfaction. Always exists, is unique, and lies in the core when non-empty.

10. Bargaining

10.1 Nash bargaining solution (1950)

Nash (1950): a unique solution to two-person cooperative bargaining problems satisfying four axioms — Pareto efficiency, symmetry, scale invariance, and independence of irrelevant alternatives (IIA) — is the allocation maximizing the Nash product Π_i (u_i − d_i) over the feasible set, where d is the disagreement point.

10.2 Rubinstein alternating offers (1982)

Ariel Rubinstein’s alternating-offers bargaining model gives a unique SPNE: player 1’s share is (1 − δ_2) / (1 − δ_1 δ_2). With equal discount factors and a small period length, the split approaches 50/50. With δ_1 = δ_2 = δ → 1, the Nash bargaining solution emerges as a limit — a strategic foundation for the cooperative concept.

10.3 Bayesian persuasion (Kamenica & Gentzkow 2011)

A sender designs an information structure (signal); a receiver updates beliefs and takes an action. Even with a self-interested sender and a Bayesian receiver, the sender can commit to releasing information strategically — and benefit. Solution via the concavification of the sender’s value function over the belief simplex. Now central to the theory of information design, advertising, and strategic disclosure.

11. Information economics

11.1 Lemons (Akerlof 1970)

George Akerlof (Nobel 2001) showed how adverse selection can collapse markets. Sellers know quality; buyers do not; buyers pay average quality; high-quality sellers exit; quality falls; price falls; market unravels. The used-car market is the canonical example; analogous failures arise in health insurance and credit markets.

11.2 Screening

The uninformed party offers a menu of contracts that induces the informed party to self-select. Rothschild & Stiglitz (1976) — insurance contracts; Mussa & Rosen (1978) — quality discrimination. Standard tool in IO and contract theory.

11.3 Signaling

The informed party takes a costly action to credibly reveal type (Spence; §7.4).

11.4 Moral hazard and the principal-agent problem

Once the contract is signed, the agent takes hidden actions that affect outcomes. The principal designs a contract that aligns incentives subject to the agent’s individual-rationality (IR) and incentive-compatibility (IC) constraints. Solutions trade off risk-sharing against effort provision.

Bengt Holmström & Oliver Hart (Nobel 2016):

  • Holmström: informativeness principle, multitask agency, career-concerns.
  • Hart: incomplete contracts, property-rights theory of the firm.

12. Voting and social choice

12.1 Arrow’s impossibility theorem (1951)

Kenneth Arrow (Nobel 1972). No social welfare function aggregating ≥ 3 alternatives from individual rankings can simultaneously satisfy:

  1. Unrestricted domain
  2. Pareto efficiency
  3. Independence of irrelevant alternatives
  4. Non-dictatorship

Some axiom must give. Foundational for democratic theory and mechanism design.

12.2 Gibbard-Satterthwaite (1973, 1975)

Any non-dictatorial voting rule with ≥ 3 alternatives is manipulable — there exist preference profiles where someone gains by reporting falsely. Strategy-proofness and reasonable democratic properties are incompatible.

12.3 Median voter theorem

Anthony Downs (1957), drawing on Black (1948): with single-peaked preferences on a one-dimensional issue space, the Condorcet winner is the median voter’s preferred policy. Drives much of formal political economy.

13. Evolutionary game theory

13.1 Replicator dynamics

Strategy frequencies evolve according to:

ẋ_i = x_i [u(s_i, x) − ū(x)]

— strategies above average grow; strategies below average shrink. Rest points are Nash equilibria; asymptotically stable rest points are ESS.

13.2 Hawk-Dove and the price of anarchy in nature

In a population of hawks (always fight) and doves (always yield), the ESS mixes both. Maynard Smith’s biology established that strategies persist via stability, not optimality.

13.3 Evolution of cooperation

Mechanisms that sustain cooperation in evolutionary settings (Nowak 2006 — “Five rules for the evolution of cooperation”): kin selection (Hamilton 1964 — r > c/b), direct reciprocity (Trivers 1971; Axelrod 1984), indirect reciprocity (Nowak & Sigmund 1998), network reciprocity (Lieberman/Hauert/Nowak 2005), and group selection.

14. Computational game theory

14.1 Complexity of Nash equilibrium

Daskalakis, Goldberg & Papadimitriou (2009) — Gödel Prize 2008, von Neumann Theory Prize — proved that computing a Nash equilibrium is PPAD-complete, even in two-player normal-form games (Chen & Deng 2009). PPAD (“polynomial parity arguments on directed graphs”) is the complexity class of problems whose existence is guaranteed by a topological fixed-point argument. PPAD-completeness is strong evidence NE is not polynomial-time computable in general.

Implications:

  • Markets reach equilibrium somehow, but no efficient algorithm computes it.
  • The rational-expectations equilibrium concept faces a computational challenge to its plausibility.

14.2 Correlated equilibrium is easy

Correlated equilibria can be computed in polynomial time by linear programming, and no-regret learning algorithms converge to the set of correlated equilibria.

14.3 Learning algorithms

  • Fictitious play (Brown 1951): each player best-responds to the empirical distribution of opponents’ past moves. Converges in 2-player zero-sum games and some classes of games; can cycle in general.
  • Multiplicative weights (Littlestone-Warmuth 1989; Arora-Hazan-Kale 2012): no-regret algorithm with strong guarantees; equivalent to many other procedures.
  • Regret matching (Hart & Mas-Colell 2000): each player plays each action with probability proportional to its positive regret; the empirical joint distribution converges to the set of correlated equilibria.

14.4 CFR and superhuman poker

Counterfactual regret minimization (CFR) (Zinkevich et al. 2007) is a regret-matching variant tailored to extensive-form games with imperfect information. It is the engine behind:

  • Libratus (Brown & Sandholm 2017): defeated top heads-up no-limit Texas hold’em pros.
  • Pluribus (Brown & Sandholm 2019): first AI to beat elite humans at six-player no-limit Texas hold’em.

These results vindicate equilibrium-based reasoning at scale and demonstrate that decoupled, abstraction-based, regret-minimizing self-play can solve massive imperfect-information games.

14.5 Learning in games and ML connections

Generative adversarial networks (Goodfellow et al. 2014) train via a two-player zero-sum game (generator vs discriminator); min-max optimization theory carries over. Multi-agent reinforcement learning increasingly leans on game-theoretic frameworks (policy gradients vs equilibrium computation, mean-field games for large populations).

15. Applications

15.1 Industrial organization

  • Cournot oligopoly (1838): firms choose quantities simultaneously; price clears the market. NE: each firm produces (a − c)/((n+1)b); price approaches marginal cost as n → ∞. Cournot’s 1838 model predated formal GT by over a century.
  • Bertrand competition (1883): firms choose prices simultaneously. With homogeneous products and capacity, NE price = marginal cost (the Bertrand paradox) — two firms suffice for perfect competition.
  • Stackelberg leadership (1934): one firm moves first; the follower best-responds. Leader earns more than in Cournot (first-mover advantage), provided commitment is credible.
  • Repeated competition sustains tacit collusion via grim-trigger-like strategies (folk theorem).
  • Entry deterrence: limit pricing, capacity commitment, predation (Milgrom-Roberts 1982 — Nobel-cited).

15.2 Market design

  • Roth & Sotomayor (1990) Two-Sided Matching: deferred acceptance, top-trading cycles.
  • Kidney exchange and National Resident Matching Program: applied stable-matching theory.
  • School choice (Boston, NYC, New Orleans): replaced manipulable systems with strategy-proof DA mechanisms.
  • Spectrum auctions (Milgrom, Wilson 2020 Nobel): SMR, combinatorial clock auctions; >$200 billion raised globally.

15.3 Security games

Stackelberg security games allocate defender resources against strategic attackers. Deployed at LAX (ARMOR), the US Coast Guard (PROTECT), and TSA (IRIS) — leader–follower games with mixed-strategy patrols (Tambe 2011).

15.4 Cyber and AI alignment

  • Cybersecurity: attacker-defender games with imperfect information.
  • AI alignment: principal-agent framing of AI systems; mesa-optimization; assistance games (CIRL — Hadfield-Menell, Russell, Dragan, Abbeel 2016) treat human-AI cooperation as a partially-observable game with the human as the reward-bearing principal.
  • Mechanism design for ML: incentive-compatible federated learning, truthful peer prediction, prediction markets.

15.5 Political economy

  • Voting (Arrow, Gibbard-Satterthwaite, median voter).
  • Coalition formation in legislatures (Baron & Ferejohn 1989 — bargaining).
  • War and conflict (Schelling 1960 Strategy of Conflict, 2005 Nobel — focal points, credible commitment, brinkmanship).

16. Open frontiers

  • Mean-field games (Lasry & Lions 2007): equilibrium with a continuum of players; tractable approximation of large-population games.
  • Information design (Bergemann-Morris 2019): generalization of Bayesian persuasion to multi-receiver, multi-sender settings.
  • Computational mechanism design: combinatorial auctions, automated mechanism design with machine learning (Dütting et al. 2019 onward).
  • Behavioral game theory: see behavioral-economics for empirical departures from Nash and the integration of fairness, reciprocity, and bounded depth of reasoning (level-k, cognitive hierarchy — Camerer, Ho & Chong 2004).
  • Quantum games (Eisert-Wilkens-Lewenstein 1999): equilibrium analysis when strategies are quantum operations.
  • Algorithmic collusion: independent reinforcement-learning pricing agents that learn supra-competitive prices (Calvano et al. 2020). Major antitrust frontier.

Game theory began as the mathematics of bridge and poker, became the lingua franca of economics, and is now indispensable for any system involving strategic agents — markets, networks, biological populations, and AI. Its central concepts (equilibrium, mechanism, commitment, signaling) are part of the basic toolkit of every quantitative social and computational science.

17. Glossary of key terms

  • Backward induction: solving an extensive-form game by reasoning from terminal nodes backward.
  • Bayesian Nash equilibrium: equilibrium of a game with incomplete information using Harsanyi types.
  • Best response: a strategy maximizing expected utility given opponents’ strategies.
  • Cheap talk: pre-play, non-binding, costless communication (Crawford & Sobel 1982).
  • Coalition: a subset of players that can cooperate in cooperative game theory.
  • Common knowledge: a fact is common knowledge if everyone knows it, everyone knows everyone knows it, and so on ad infinitum (Aumann 1976).
  • Commitment: irreversible action that changes the strategic environment.
  • Correlated equilibrium: equilibrium with respect to a public correlating device (Aumann 1974).
  • Dominant strategy: best regardless of opponents.
  • ESS: evolutionarily stable strategy (Maynard Smith 1972).
  • Extensive form: tree representation of a game.
  • Folk theorem: any individually-rational, feasible payoff is sustainable in infinitely-repeated games.
  • Incentive compatibility: truth-telling is optimal.
  • Mechanism: a rule mapping reports to outcomes; the design problem is to choose the mechanism.
  • Mixed strategy: probability distribution over pure strategies.
  • Nash equilibrium: no player can benefit from unilateral deviation.
  • Normal form: matrix representation of a game.
  • PPAD: complexity class of fixed-point search problems; Nash is PPAD-complete.
  • Revelation principle: any implementable social choice is implementable by a truthful direct mechanism.
  • Shapley value: unique fair cost-sharing rule satisfying four axioms.
  • Signaling: informed party takes costly action to credibly reveal type.
  • Subgame-perfect Nash equilibrium: Nash equilibrium in every subgame (Selten 1965).
  • Type: private information characterizing a player in a Bayesian game.
  • VCG: Vickrey-Clarke-Groves dominant-strategy mechanism for efficient allocation.
  • Zero-sum game: total payoff across players is constant (often zero).

Adjacent

Graph View