Incentive_compatibility

Incentive compatibility

Incentive compatibility

Concept in game theory

A mechanism is called incentive-compatible (IC) if every participant can achieve their own best outcome by acting according to 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]

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,[1]: 415  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-choice 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 (e.g. 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 (e.g. if truth-telling gives the agent an optimal expected value).

Revelation principles

Main article: Revelation principle

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.

See also

References

  1. [1]
    Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
  2. [2]
    "Incentive compatibility | game theory". Encyclopedia Britannica. Retrieved 2020-05-25.
  3. [3]
    James Jr, Harvey S. (2014). "Incentive compatibility". Britannica.
  4. [4]
    Jackson, Matthew (December 8, 2003). "Mechanism Theory" (PDF). Optimization and Operations Research.
Share this article:

This article uses material from the Wikipedia article Incentive_compatibility, and is written by contributors. Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.