Incentive compatibility

From Wikipedia, the free encyclopedia
Jump to: navigation, search

A mechanism is called incentive-compatible (IC) if every participant can achieve the best outcome to him/herself just by acting according to his/her true preferences. [1]:225

There are several different degrees of incentive-compatibility:

  • 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 by being truthful, regardless of what the others do (even if they are irrational or even collude against you). In a DSIC mechanism, strategic considerations cannot help any agent achieve better outcomes than the truth; hence, such mechanisms are also called strategyproof[1]:244,752 or truthful.[1]:415 See the page about strategyproofness for more information about this property.
  • A weaker degree is Bayesian-Nash incentive-compatibility (BNIC).[1]:416 It means that there is a Bayesian Nash equilibrium in which all participants reveal their true preferences. I.e, if all the others act truthfully, then it is also best for you 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 majority voting between two alternatives, and second-price auction.

Typical examples of a mechanisms that are not DSIC are plurality voting between three or more alternatives and first-price auction.

Incentive-compatibility in randomized mechanisms[edit]

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[edit]

Main article: Revelation principle

The famous Revelation principle comes in two flavors 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, can be implemented by a BNIC mechanism.

See also[edit]


References[edit]

  1. ^ 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.