Strategyproof

Strategyproof

In game theory, an asymmetric game where players have private information is said to be strategyproof (or truthful) if there is no incentive for any of the players to lie about or hide their private information from the other players.

Although the "strategyproof" concept has applications in several areas of game theory and economics, it is most natural to the theory of payment schemes for network routing. As an example, consider a network as a graph where each edge (i.e. link) has an associated cost of transmission, privately known to the owner of the link. The owner of a link wishes to be compensated for relaying messages.

As the sender of a message on the network, one wants to find the least cost path. There are efficient methods for doing so, even in large networks. However, there is one problem: the costs for each link are unknown. A naive approach would be to ask the owner of each link the cost, use these declared costs to find the least cost path, and pay all links on the path their declared costs. However, it can be shown that this payment scheme is not strategyproof, that is, the owners of some links can benefit by lying about the cost. We may end up paying far more that the actual cost.

It can be shown that given certain assumptions about the network and the players (owners of links), there do exist strategyproof payment schemes. An important one is the Vickrey-Clarke-Groves (VCG) scheme. Thus, strategyproofness is a useful concept in game theory.

Strategyproofness can be thought of as two separate conditions:
* Incentive Compatibility: a player will reveal its true cost to maximize its profit regardless of the other players' actions.
* Individual Rationality: a player can choose whether or not to participate; in other words, the link will not relay a message if the payment is less than the cost.

References

*Parkes, David C. (2004), On Learnable Mechanism Design, in: Tumer, Kagan and David Wolpert (Eds.): Collectives and the Design of Complex Systems, New York u.a.O., pp.107-133.
* [http://www.math.auckland.ac.nz/~slinko/Research/Borda3.pdf On Asymptotic Strategy-Proofness of Classical Social Choice Rules] An article by Arkadii Slinko about strategy-proofness in voting systems.


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Vickrey auction — A Vickrey auction is a type of sealed bid auction, where bidders submit written bids without knowing the bid of the other people in the auction. The highest bidder wins, but the price paid is the second highest bid. The auction was created by… …   Wikipedia

  • List of network theory topics — Network theory is an area of applied mathematics. This page is a list of network theory topics. See also List of graph theory topics. Contents 1 Network theorems 2 Network properties 3 Network theory applications …   Wikipedia

  • Partage équitable — En économie, mais aussi en mathématiques, et plus particulièrement en théorie des jeux, le problème du partage équitable, connu aussi sous le nom de problème de partage du gâteau (de l anglais cake cutting problem), est le problème du partage d… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”