Implementation theory

Implementation theory is an area of research in game theory concerned with whether a class of mechanisms (or institutions) can be designed whose equilibrium outcomes implement a given set of normative goals or welfare criteria. There are two general types of implementation problems: the economic problem of producing and allocating public and private goods and choosing over a finite set of alternatives. In the case of producing and allocating public/private goods, solution concepts are focused on finding dominant strategies. In his paper "Counterspeculation, Auctions, and Competitive Sealed Tenders", William Vickrey showed that if preferences are restricted to the case of quasi-linear utility functions then the mechanism dominant strategy is dominant-strategy implementable. "A social choice rule is dominant strategy incentive compatible, or strategy-proof, if the associated revelation mechanism has the property that honestly reporting the truth is always a dominant strategy for each agent." However, the payments to agents become large, sacrificing budget neutrality to incentive compatibility. In a game where multiple agents are to report their preferences (or their type), it may be in the best interest of some agents to lie about their preferences. This may improve their payoff, but it may not be seen as a fair outcome to other agents. Although largely theoretical, implementation theory may have profound implications on policy creation because some social choice rules may be impossible to implement under specific game conditions.

Implementation theory is an area of research in game theory concerned with whether a class of mechanisms (or institutions) can be designed whose equilibrium outcomes implement a given set of normative goals or welfare criteria.^[1]

There are two general types of implementation problems: the economic problem of producing and allocating public and private goods and choosing over a finite set of alternatives.^[2] In the case of producing and allocating public/private goods, solution concepts are focused on finding dominant strategies.

In his paper "Counterspeculation, Auctions, and Competitive Sealed Tenders", William Vickrey showed that if preferences are restricted to the case of quasi-linear utility functions then the mechanism dominant strategy is dominant-strategy implementable.^[3] "A social choice rule is dominant strategy incentive compatible, or strategy-proof, if the associated revelation mechanism has the property that honestly reporting the truth is always a dominant strategy for each agent."^[2] However, the payments to agents become large, sacrificing budget neutrality to incentive compatibility.

In a game where multiple agents are to report their preferences (or their type), it may be in the best interest of some agents to lie about their preferences. This may improve their payoff, but it may not be seen as a fair outcome to other agents.^[4]

Although largely theoretical, implementation theory may have profound implications on policy creation because some social choice rules may be impossible to implement under specific game conditions.^[1]

Implementability

[edit]

In mechanism design, implementability is a property of a social choice function. It means that there is an incentive-compatible mechanism that attains ("implements") this function. There are several degrees of implementability, corresponding to the different degrees of incentive-compatibility, including:

A function is dominant-strategy implementable if it is attainable by a mechanism which is dominant-strategy-incentive-compatible (also called strategyproof).
A function is Bayesian-Nash implementable if it is attainable by a mechanism which is Bayesian-Nash-incentive-compatible.

See for a recent reference. In some textbooks, the entire field of mechanism design is called implementation theory.^[5]

References

[edit]

^ ^a ^b Palfrey, Thomas R. "Chapter 61 Implementation Theory." Handbook of Game Theory with Economic Applications, 2002. doi:10.1016/S1574-0005(02)03024-2.
^ ^a ^b Maskin, Eric and Sjöström, Tomas. "Implementation Theory." Handbook of Social Choice and Welfare, 2002. doi:10.1016/S1574-0110(02)80009-1.
^ Vickrey, William. "Counterspeculation, Auctions, and Competitive Sealed Tenders." The Journal of Finance 16, no. 1 (1961): 8–37. doi:10.1111/j.1540-6261.1961.tb02789.x. JSTOR 2977633.
^ Jackson, Matthew O. "A Crash Course in Implementation Theory." Social Choice and Welfare 18, no. 4 (2001): 655–708. doi:10.1007/s003550100152. JSTOR 41106420.
^ Martin J. Osborne & Ariel Rubinstein: A Course in Game Theory (1994).

Game theory

Traditional game theory

Definitions	Asynchrony Bayesian regret Best response Bounded rationality Cheap talk Coalition Complete contract Complete information Complete mixing Conjectural variation Contingent cooperator Coopetition Cooperative game theory Dynamic inconsistency Escalation of commitment Farsightedness Game semantics Hierarchy of beliefs Imperfect information Incomplete information Information set Move by nature Mutual knowledge Non-cooperative game theory Non-credible threat Outcome Perfect information Perfect recall Ply Preference Rationality Sequential game Simultaneous action selection Spite Strategic complements Strategic dominance Strategic form Strategic interaction Strategic move Strategy Subgame Succinct game Topological game Tragedy of the commons Uncorrelated asymmetry Win–win game Zero-sum game
Equilibrium concepts	Backward induction Bayes correlated equilibrium Bayesian efficiency Bayesian game Bayesian Nash equilibrium Berge equilibrium Bertrand–Edgeworth model Coalition-proof Nash equilibrium Core Correlated equilibrium Cursed equilibrium Edgeworth price cycle Epsilon-equilibrium Gibbs equilibrium Incomplete contracts Inequity aversion Individual rationality Iterated elimination of dominated strategies Markov perfect equilibrium Mertens-stable equilibrium Nash equilibrium Open-loop model Pareto efficiency Payoff dominance Perfect Bayesian equilibrium Price of anarchy Program equilibrium Proper equilibrium Quantal response equilibrium Quasi-perfect equilibrium Rational agent Rationalizability Rationalizable strategy Satisfaction equilibrium Self-confirming equilibrium Sequential equilibrium Shapley value Strong Nash equilibrium Subgame perfect equilibrium Trembling hand equilibrium
Strategies	Appeasement Bid shading Cheap talk Collusion Commitment device De-escalation Deterrence Escalation Fictitious play Focal point Grim trigger Hobbesian trap Markov strategy Max-dominated strategy Mixed strategy Pure strategy Tit for tat Win–stay, lose–switch
Games	All-pay auction Battle of the sexes Nash bargaining game Bertrand competition Blotto game Centipede game Coordination game Cournot competition Deadlock Dictator game Trust game Diner's dilemma Dollar auction El Farol Bar problem Electronic mail game Gift-exchange game Guess 2/3 of the average Keynesian beauty contest Kuhn poker Lewis signaling game Matching pennies Obligationes Optional prisoner's dilemma Pirate game Prisoner's dilemma Public goods game Rendezvous problem Rock paper scissors Stackelberg competition Stag hunt Traveler's dilemma Ultimatum game Volunteer's dilemma War of attrition
Theorems	Arrow's impossibility theorem Aumann's agreement theorem Brouwer fixed-point theorem Competitive altruism Folk theorem Gibbard–Satterthwaite theorem Gibbs lemma Glicksberg's theorem Kakutani fixed-point theorem Kuhn's theorem One-shot deviation principle Prim–Read theory Rational ignorance Rational irrationality Sperner's lemma Zermelo's theorem
Subfields	Algorithmic game theory Behavioral game theory Behavioral strategy Compositional game theory Confrontation analysis Contract theory Drama theory Graphical game theory Heresthetic Mean-field game theory Negotiation theory Quantum game theory Social software
Key people	Albert W. Tucker Alvin E. Roth Amos Tversky Antoine Augustin Cournot Ariel Rubinstein David Gale David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Herbert Scarf Hervé Moulin Jean Tirole Jean-François Mertens Jennifer Tour Chayes Ken Binmore Kenneth Arrow Leonid Hurwicz Lloyd Shapley Martin Shubik Melvin Dresher Merrill M. Flood Olga Bondareva Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Aumann Robert Axelrod Robert B. Wilson Roger Myerson Samuel Bowles Suzanne Scotchmer Thomas Schelling William Vickrey

Combinatorial game theory

Core concepts	Combinatorial explosion Determinacy Disjunctive sum First-player and second-player win Game complexity Game tree Impartial game Misère Partisan game Solved game Sprague–Grundy theorem Strategy-stealing argument Zugzwang
Games	Chess Chomp Clobber Cram Domineering Hackenbush Nim Notakto Subtract a square Sylver coinage Toads and Frogs
Mathematical tools	Mex Nimber On Numbers and Games Star Surreal number Winning Ways for Your Mathematical Plays
Search algorithms	Alpha–beta pruning Expectiminimax Minimax Monte Carlo tree search Negamax Paranoid algorithm Principal variation search
Key people	Claude Shannon John Conway John von Neumann

Evolutionary game theory

Core concepts	Bishop–Cannings theorem Evolution and the Theory of Games Evolutionarily stable set Evolutionarily stable state Evolutionarily stable strategy Replicator equation Risk dominance Stochastically stable equilibrium Weak evolutionarily stable strategy
Games	Chicken Stag hunt
Applications	Cultural group selection Fisher's principle Mobbing Terminal investment hypothesis
Key people	John Maynard Smith George R. Price William Donald Hamilton Robert Axelrod

Mechanism design

Core concepts	Algorithmic mechanism design Bayesian-optimal mechanism Incentive compatibility Market design Myerson ironing Monotonicity Participation constraint Revelation principle Strategyproofness Vickrey–Clarke–Groves mechanism Virtual valuation
Theorems	Myerson–Satterthwaite theorem Revenue equivalence Border's theorem
Applications	Digital goods auction Knapsack auction Truthful cake-cutting

Other topics
Bertrand paradox Chainstore paradox Computational complexity of games Helly metric Multi-agent system PPAD-complete

Implementation theory

Implementability

See also

References