Incentive compatibility

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

In mechanism design, a process is incentive-compatible (IC) if all of the participants fare best when they truthfully reveal any private information asked for by the mechanism.[1] As an illustration, voting systems which create incentives to vote dishonestly lack the property of IC. In the absence of dummy bidders, collusion, incomplete information, or other factors which interfere with process efficiency, a second price auction is an example of a mechanism that is IC.

There are different degrees of incentive-compatibility: in some games, truth-telling can be a dominant strategy. A weaker notion is that truth-telling is a Bayes-Nash equilibrium: it is best for each participant to tell the truth, provided that others are also doing so.

Incentive-compatible mechanisms in single-parameter domains[edit]

A single-parameter domain is a game in which each player i gets a certain positive value vi for "winning" and a value 0 for "losing". A simple example is a single-item auction, in which vi is the value that player i assigns to the item.

For this setting, it is easy to characterize IC mechanisms. Begin with some definitions.

A mechanism is called normalized if every losing bid pays 0.

A mechanism is called monotone if, when a player raises his bid, his chances of winning (weakly) increase.

For a monotone mechanism, for every player i and every combination of bids of the other players, there is a critical value in which the player switches from losing to winning.

A normalized mechanism on a single-parameter domain is IC iff the following two conditions hold:[2]

  1. The assignment function is monotone in each of the bids, and:
  2. Every winning bid pays the critical value.

See also[edit]

References[edit]

  1. ^ Vleugels, Jan - "Incentive compatibility" 1997
  2. ^ Noam Nisam (2007), "Introduction to Mechanism Design for Computer Scientists", in Nisan, Noam; Roughgarden, Tim; Tardos, Eva; Vazirani, Vijay (eds.). Algorithmic Game Theory (PDF). pp. 229–230. ISBN 978-0521872829.  edit