80 topics
Game theory
Strategy, equilibrium and incentives, from the prisoner’s dilemma to mechanism design.
A
B
- Backward InductionAlgorithm for solving finite perfect-information games by reasoning from terminal nodes back to the root.
- Banzhaf Power IndexA measure of a voter's ability to influence the outcome of a vote, calculated as the number of coalitions in which they are pivotal.
- Battle of the SexesA coordination game with asymmetric preferences over the two coordinated outcomes.
- Bayesian GameA game in which players have private information (types) drawn from a common prior.
- Berge EquilibriumAn equilibrium where each player maximizes the payoff of all others, assuming they do not deviate from their Berge strategies.
- Bertrand CompetitionSimultaneous price-setting competition among firms producing a homogeneous good.
- Best-response tableA best-response table marks the actions that maximize each player’s payoff against each fixed action of the opponent. Mutual best…
C
- Centipede GameA multi-stage game where backward induction predicts immediate termination despite cooperative gains.
- Cheap TalkCostless, non-binding, and verifiable communication prior to play that can influence equilibrium selection.
- Chicken GameAn anti-coordination game where both players prefer to yield if the other stays the course.
- Coalition FormationStudy of which coalitions form and how they share surplus.
- Common KnowledgeAn event is common knowledge if everyone knows it, everyone knows that everyone knows it, and so on ad infinitum.
- Congestion GamesGames where each player's payoff depends on the load each facility carries.
- Cooperative GameA game where binding agreements among coalitions are allowed; analysis focuses on joint payoffs.
- Core (of a Cooperative Game)The set of coalition-stable payoff allocations.
- Core Selection (Matching)The selection of an allocation from the core of a matching market, typically via deferred-acceptance algorithms.
- Correlated EquilibriumAn equilibrium in which players obey recommendations from a common randomization device.
- Cournot CompetitionA simultaneous-move duopoly/oligopoly with quantity as the strategic variable.
D
E
- Evolutionarily Stable SetsA set of strategies such that every strategy in the set resists invasion by any outside mutant.
- Evolutionarily Stable StrategyA strategy that, if adopted by the population, cannot be invaded by any rare mutant.
- Evolutionary Game TheoryStudies strategy frequencies in large populations under selection and mutation.
- Extensive-Form GameA representation of sequential play using a rooted tree with information sets.
F
- Fair DivisionThe study of how to divide resources among agents so that each receives a fair share according to some criterion.
- Fictitious PlayA learning process in which players best-respond to the empirical distribution of past opponent play.
- Folk TheoremAny individually rational feasible payoff can be sustained in an infinitely repeated game with patient enough players.
G
H
I
L
M
- Matching PenniesA zero-sum 2 2 game with no pure equilibrium and a unique uniform mixed equilibrium.
- Mean Field GameA game with a continuum of players where each player's influence on aggregate is negligible, simplifying equilibrium to a PDE system.
- Mechanism DesignDesigning the rules of a game so that equilibrium behavior yields desired outcomes.
- Minimax TheoremIn any finite two-player zero-sum game, max-min and min-max values coincide in mixed strategies.
- Mixed StrategyA probability distribution over a player's pure strategies.
- Mixed-equilibrium calculationTo find an interior mixed equilibrium, choose each player’s mixing probability to make the other player indifferent between actions in…
N
- Nash Bargaining SolutionThe unique allocation satisfying Pareto-efficiency, symmetry, scale invariance, and IIA.
- Nash EquilibriumA profile of strategies where no player can profit by unilateral deviation.
- No-Regret LearningLearning dynamics where a player's cumulative payoff is no worse than the best fixed action in hindsight, up to a vanishing average error.
- Non-Cooperative GameA game in which binding agreements are not possible; each player chooses independently.
- Normal-Form GameA simultaneous-move representation via strategy sets and payoff functions.
P
- Pareto EfficiencyAn allocation is Pareto efficient if no player can be made strictly better off without making someone else worse off.
- Perfect Bayesian EquilibriumA refinement for dynamic games of incomplete information pairing strategies with beliefs.
- Potential GamesGames where all unilateral payoff changes are captured by a single real-valued function.
- Price of AnarchyThe worst-case ratio between the social cost of a Nash equilibrium and the social optimum.
- Price of StabilityThe best-case ratio between the social cost of a Nash equilibrium and the social optimum.
- Principal-Agent ProblemA contracting problem where an agent's action is unobservable to the principal.
- Prisoner's DilemmaCanonical 2x2 game where individually rational defection leads to a Pareto-inferior outcome.
- Proper EquilibriumA refinement of trembling-hand perfection where more costly mistakes are infinitely less likely.
- Public-Goods GameA game in which individuals contribute to a shared good; the efficient outcome is not individually rational.
- Pure StrategyA deterministic choice of an action from a player's strategy set.
Q
R
- RationalizabilityThe set of strategies surviving iterated elimination of strategies that are never a best response.
- Repeated GameA stage game played repeatedly, allowing histories to influence future play.
- Replicator DynamicsODEs describing how strategy frequencies evolve under selection proportional to fitness.
- Revelation PrincipleAny equilibrium outcome of any mechanism can be reproduced by a direct truthful mechanism.
- Rubinstein BargainingA non-cooperative alternating-offers model of bargaining with a unique subgame-perfect outcome.
S
- Screening GamesGames where an uninformed principal offers a menu of contracts to sort informed agents.
- Sequential EquilibriumA refinement of PBE requiring beliefs to be limits of fully mixed strategy perturbations.
- Shapley ValueA unique fair allocation in cooperative games satisfying efficiency, symmetry, dummy, and additivity.
- Signaling GamesDynamic incomplete-information games where an informed sender chooses a signal that a receiver observes.
- Smoothed Analysis of Price of AnarchyA framework showing that worst-case PoA bounds can be overly pessimistic — typical-case bounds are often dramatically better.
- Social Choice TheoryThe theoretical study of how individual preferences and judgments can be aggregated into collective decisions.
- Stackelberg CompetitionA sequential duopoly in which a leader commits to an output and the follower best-responds.
- Stag HuntA coordination game where mutual cooperation on the risky action maximizes welfare.
- Subgame Perfect EquilibriumA Nash equilibrium that also prescribes a Nash equilibrium in every subgame.
- Supermodular GamesA game in which a player's incentive to raise their action increases with opponents' actions (strategic complements).
T
- Tit-for-TatA simple reciprocal strategy — cooperate first, then mimic the opponent's previous action.
- Tragedy of the CommonsOveruse of a shared resource when individual users ignore the externality they impose on others.
- Trembling-Hand PerfectionAn equilibrium robust to small probabilities of mistakes.