Algorithmic game theory emerged from the interaction of game theory, economics, algorithms, complexity theory, optimization, networks, market design, and multi-agent systems.
From equilibrium theory to computational markets
The profiles cover foundational game theory as well as mechanism design, auctions, social choice, equilibrium computation, routing games, learning, and algorithmic fairness.
People · Incentives · Computation
Important Contributors
Key figures behind Nash equilibrium, Bayesian games, stable matching, truthful mechanisms, auction theory, social choice, Price of Anarchy, and computational equilibrium theory.
JN
John von Neumann
Minimax theorem · zero-sum games · 1920s onward
Established mathematical foundations of modern game theory, including the minimax theorem for two-player zero-sum games.
Technical significance
Minimax connects strategic optimization with linear programming, duality, and adversarial decision-making.
MinimaxZero-Sum GamesOptimization
Von Neumann's minimax theorem states that in finite two-player zero-sum games, optimal mixed strategies equalize the maximin and minimax values.
Introduced Nash equilibrium, the central stability concept for non-cooperative games.
Technical significance
Nash equilibrium provides a fixed point where no player can improve by unilateral deviation.
Nash EquilibriumBest ResponseMixed Strategy
For a finite game, a mixed-strategy Nash equilibrium always exists. Computationally, finding equilibria leads to fixed-point methods and complexity questions such as PPAD-completeness.
Developed the modern framework for games with incomplete information.
Technical significance
Bayesian games model uncertainty about private types, values, costs, and preferences.
Bayesian GamesTypesBeliefs
Harsanyi transformed incomplete-information games into games with types drawn from a commonly known probability distribution.
Technical concepts: private information, type spaces, common priors, Bayesian Nash equilibrium, expected utility, signaling.
RS
Reinhard Selten
Subgame-perfect equilibrium · refinement
Developed major equilibrium refinements for dynamic games.
Technical significance
Equilibrium refinement removes non-credible threats that can appear in ordinary Nash equilibria.
Subgame PerfectDynamic GamesRefinement
Subgame-perfect equilibrium requires strategies to form a Nash equilibrium in every subgame. Backward induction provides the canonical computational method for finite perfect-information games.
Made foundational contributions to cooperative games, market design, matching, and stochastic games.
Technical significance
The Shapley value provides a principled allocation rule for dividing cooperative surplus.
Shapley ValueMatchingCooperative Games
The Shapley value averages a player's marginal contribution over all possible coalition arrival orders. Shapley also co-developed the Gale–Shapley stable-matching algorithm.
Co-developed the deferred-acceptance algorithm for stable matching.
Technical significance
Stable matching is a central mechanism-design example where strategic preferences are converted into a feasible assignment.
Stable MatchingDeferred AcceptanceMarkets
Gale–Shapley repeatedly lets one side propose while the other tentatively keeps its most preferred offer. The resulting matching is stable and proposer-optimal among stable matchings.
Developed the second-price sealed-bid auction, a canonical truthful mechanism.
Technical significance
Vickrey auctions show how payment rules can make truthful bidding a dominant strategy.
Vickrey AuctionTruthfulnessDominant Strategy
In a single-item second-price auction, the highest bidder wins but pays the second-highest bid. A bidder cannot improve utility by misreporting relative to truthful valuation.
Mechanism design reverses game-theoretic analysis: instead of studying existing rules, it designs rules that produce desired outcomes.
Mechanism DesignIncentivesImplementation
A mechanism maps reported private information to allocations and payments. The central challenge is to ensure strategic behavior leads to desirable outcomes.
Established one of the central impossibility results in social choice theory.
Technical significance
Arrow's theorem shows that desirable voting properties can conflict fundamentally when aggregating rankings.
Social ChoiceVotingImpossibility
With at least three alternatives, no rank-order voting rule satisfies a standard set of fairness properties simultaneously under unrestricted preferences.
Complexity of equilibria · algorithmic game theory
Helped establish the computational-complexity foundations of algorithmic game theory.
Technical significance
His work connects equilibrium computation to complexity classes designed for total search problems.
PPADComplexityEquilibrium Computation
PPAD captures search problems whose solutions are guaranteed by parity-style arguments. Nash equilibrium computation became a flagship example of this complexity perspective.
Technical concepts: total search, PPAD, fixed-point computation, reductions, computational hardness of equilibria.
NN
Noam Nisan
Algorithmic mechanism design · AGT
Co-founded major parts of algorithmic mechanism design and helped define algorithmic game theory as a field.
Technical significance
His work studies how computational limitations interact with incentives and mechanism design.
Algorithmic Mechanism DesignAuctionsComplexity
Algorithmic mechanism design asks for mechanisms that are both incentive-compatible and computationally efficient.
Developed foundational results on inefficiency caused by selfish behavior in networks.
Technical significance
Price of Anarchy quantifies the gap between equilibrium performance and centralized optimum.
Price of AnarchyRouting GamesEfficiency
In selfish routing, each user chooses a minimum-latency path given congestion created by others. Equilibrium can be inefficient even when every user acts rationally.
Co-introduced the Price of Anarchy framework for quantifying equilibrium inefficiency.
Technical significance
The concept provides a worst-case measure of how decentralized strategic behavior degrades system performance.
Price of AnarchyGamesApproximation
PoA compares the objective value of the worst equilibrium with the globally optimal outcome. The exact ratio depends on whether the model minimizes cost or maximizes welfare.
Made major contributions to network optimization and algorithmic game theory.
Technical significance
Her work connects approximation algorithms, network flows, congestion, and strategic behavior.
NetworksApproximationCongestion Games
Algorithmic game theory often combines optimization benchmarks with equilibrium analysis. Tardos's work helped develop techniques for bounding inefficiency in networked systems.
Made major contributions to the complexity of equilibrium computation.
Technical significance
His work helped establish hardness results for computing Nash equilibria in finite games.
NashPPADComputational Complexity
Together with collaborators, Daskalakis showed that finding Nash equilibria is computationally difficult in the PPAD sense even for restricted classes of games.
Developed influential auction models and practical market-design mechanisms.
Technical significance
His work connects bidding behavior, information, allocation efficiency, and real auction platforms.
AuctionsMarket DesignBidding
Auction format changes bidder incentives, information revelation, revenue, and allocative efficiency. Multi-item environments introduce complementarity and substitution effects.
Technical concepts: ascending auctions, common values, information structure, allocation efficiency, activity rules.
AR
Alvin Roth
Matching markets · market design
Advanced matching theory into practical market design.
Technical significance
His work shows how algorithms can coordinate markets where prices are absent or insufficient.
MatchingMarket DesignStability
Practical matching systems must handle preferences, strategic behavior, institutional constraints, and stability simultaneously.