Incentive compatibility

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.
Find sources: "Incentive compatibility" – news · newspapers · books · scholar · JSTOR (June 2019) (Learn how and when to remove this message)

In game theory and economics, a mechanism is called incentive-compatible (IC)^[1]^: 415 if every participant can achieve their own best outcome by reporting their true preferences.^[1]^: 225^[2] For example, there is incentive compatibility if high-risk clients are better off in identifying themselves as high-risk to insurance firms, who only sell discounted insurance to high-risk clients. Likewise, they would be worse off if they pretend to be low-risk. Low-risk clients who pretend to be high-risk would also be worse off.^[3] The concept is attributed to the Russian-born American economist Leonid Hurwicz.^[2]

Typology

There are several different degrees of incentive-compatibility:^[4]

The stronger degree is dominant-strategy incentive-compatibility (DSIC).^[1]^: 415 It means that truth-telling is a weakly-dominant strategy, i.e. you fare best or at least not worse by being truthful, regardless of what the others do. In a DSIC mechanism, strategic considerations cannot help any agent achieve better outcomes than the truth; such mechanisms are called strategyproof,^[1]^{: 244, 752} truthful, or straightforward.
A weaker degree is Bayesian-Nash incentive-compatibility (BNIC).^[1]^: 416 It means there is a Bayesian Nash equilibrium in which all participants reveal their true preferences. In other words, if all other players act truthfully, then it is best to be truthful.^[1]^: 234

Every DSIC mechanism is also BNIC, but a BNIC mechanism may exist even if no DSIC mechanism exists.

Typical examples of DSIC mechanisms are second-price auctions and a simple majority vote between two choices. Typical examples of non-DSIC mechanisms are ranked voting with three or more alternatives (by the Gibbard–Satterthwaite theorem) or first-price auctions.

In randomized mechanisms

A randomized mechanism is a probability-distribution on deterministic mechanisms. There are two ways to define incentive-compatibility of randomized mechanisms:^[1]^{: 231–232}

The stronger definition is: a randomized mechanism is universally-incentive-compatible if every mechanism selected with positive probability is incentive-compatible (i.e. if truth-telling gives the agent an optimal value regardless of the coin-tosses of the mechanism).
The weaker definition is: a randomized mechanism is incentive-compatible-in-expectation if the game induced by expectation is incentive-compatible (i.e. if truth-telling gives the agent an optimal expected value).

Revelation principles

The revelation principle comes in two variants corresponding to the two flavors of incentive-compatibility:

The dominant-strategy revelation-principle says that every social-choice function that can be implemented in dominant-strategies can be implemented by a DSIC mechanism.
The Bayesian–Nash revelation-principle says that every social-choice function that can be implemented in Bayesian–Nash equilibrium (Bayesian game, i.e. game of incomplete information) can be implemented by a BNIC mechanism.

References

^ ^a ^b ^c ^d ^e ^f ^g Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
^ ^a ^b "Incentive compatibility | game theory". Encyclopedia Britannica. Retrieved 2020-05-25.
^ James Jr, Harvey S. (2014). "Incentive compatibility". Britannica.
^ Jackson, Matthew (December 8, 2003). "Mechanism Theory" (PDF). Optimization and Operations Research.

v t e Topics of game theory
Definitions	Asynchrony Bayesian regret Best response Bounded rationality Cheap talk Complete contract Complete information Complete mixing Confrontation analysis Congestion game Conjectural variation Contingent cooperator Coopetition Determinacy Dynamic inconsistency Escalation of commitment Extensive-form game Farsightedness First-player and second-player win Game complexity Game form Game semantics Game theory Game tree Hierarchy of beliefs Imperfect information Incomplete information Information set Mechanism design Move by nature Mutual knowledge Normal-form game No-win situation Non-credible threat Null move Outcome Payoff Perfect information Perfect recall Ply Preference Rationality Sequential game Simultaneous action selection Spite Solved game Strategic complements Strategic dominance Strategic form Strategic interaction Strategic move Strategy Subgame Succinct game Topological game Tragedy of the commons
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 Edgeworth price cycle Epsilon-equilibrium Evolutionarily stable strategy Gibbs equilibrium Implementation theory Incentive compatibility Incomplete contracts Inequity aversion Individual rationality Iterated elimination of dominated strategies Hierarchy of beliefs Markov perfect equilibrium Mertens-stable equilibrium Nash equilibrium One-shot deviation principle Open-loop model Pareto efficiency Participation constraint Payoff dominance Perfect Bayesian equilibrium Price of anarchy Program equilibrium Proper equilibrium Quantal response equilibrium Quasi-perfect equilibrium Rational agent Rationalizability Rationalizable strategy Risk dominance Satisfaction equilibrium Self-confirming equilibrium Sequential equilibrium Shapley value Strong Nash equilibrium Subgame perfection Trembling hand equilibrium
Strategies	Appeasement Behavioral strategy Bid shading Cheap talk Collusion Commitment device De-escalation Deterrence Markov strategy Dominant strategies Escalation Fictitious play Focal point Forward induction Grim trigger Hobbesian trap Markov strategy Max-dominated strategy Mixed strategy Pairing strategy Pure strategy Strategy-stealing argument Tit for tat
Classes of games	Asymmetric game Auction Bargaining problem Cooperative game Deterministic game Differential game Finite game Global game Infinite game Intransitive game n-player game Large Poisson game Market game Mean-field game Mean payoff game Minimum effort game Multi-stage game Network game Non-cooperative game Potential game Quantum refereed game Repeated game Screening game Signaling game Simultaneous game Stochastic game Strictly determined game Supermodular game Symmetric game Zero-sum game
Games	All-pay auction Battle of the sexes Bertrand competition Blotto game Centipede game Chess Chicken Coordination game Cournot competition Deadlock Dictator game Trust game Diner's dilemma Dollar auction Checkers El Farol Bar problem Electronic mail game Fair cake-cutting Fair division Gift-exchange game Go Guess 2/3 of the average Induction puzzles Infinite chess Keynesian beauty contest Kuhn poker Lewis signaling game Matching pennies Nash bargaining game Obligationes Optional prisoner's dilemma Pirate game Prisoner's dilemma Princess and monster game Public goods game Pursuit game Rendezvous problem Rock paper scissors Stackelberg competition Stag hunt Traveler's dilemma Two-level game theory Ultimatum game Volunteer's dilemma War of attrition
Theorems & theories	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 Myerson–Satterthwaite theorem Nash's theorem Negamax theorem One-shot deviation principle Parrondo's paradox Prim–Read theory Purification theorem Rational ignorance Rational irrationality Revelation principle Revenue equivalence theorem Shapley's axioms Sperner's lemma Sprague–Grundy theorem Zermelo's theorem
Key figures	Albert W. Tucker Alvin E. Roth Amos Tversky Antoine Augustin Cournot Ariel Rubinstein Claude Shannon Daniel Kahneman 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 John Conway John Nash John Harsanyi John Maynard Smith John von Neumann Ken Binmore Kenneth Arrow Kenneth Binmore 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
Search optimizations	Alpha–beta pruning Aspiration window Expectiminimax Game tree search Lazy SMP Lemke–Howson algorithm max^n algorithm Minimax algorithm Monte Carlo tree search Negamax Paranoid algorithm Principal variation search
Subfields	Algorithmic game theory Behavioral game theory Combinatorial game theory Compositional game theory Confrontation analysis Contract theory Cooperative game Drama theory Evolutionary game theory Graphical game theory Heresthetic Implementation theory Mean-field game theory Negotiation theory Quantum game theory Social software
Miscellaneous	Bertrand paradox Chainstore paradox Computational complexity of games Glossary of game theory Helly metric Lemke–Howson algorithm List of game theorists List of games in game theory Multi-agent system PPAD-complete

Typology

In randomized mechanisms

Revelation principles

See also

References

Portal di Ensiklopedia Dunia