fbpx
Wikipedia

Strategyproofness

In game theory, an asymmetric game where players have private information is said to be strategy-proof or strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information,[1]: 244  i.e. given no information about what the others do, you fare best or at least not worse by being truthful.

SP is also called truthful or dominant-strategy-incentive-compatible (DSIC),[1]: 415  to distinguish it from other kinds of incentive compatibility.

An SP game is not always immune to collusion, but its robust variants are; with group strategyproofness no group of people can collude to misreport their preferences in a way that makes every member better off, and with strong group strategyproofness no group of people can collude to misreport their preferences in a way that makes at least one member of the group better off without making any of the remaining members worse off.[2]

Examples edit

Typical examples of SP mechanisms are majority voting between two alternatives, second-price auction, and any VCG mechanism.

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

SP is also applicable in network routing. 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 SP, that is, the owners of some links can benefit by lying about the cost. We may end up paying far more than the actual cost. It can be shown that given certain assumptions about the network and the players (owners of links), a variant of the VCG mechanism is SP.

Notation edit

There is a set   of possible outcomes.

There are   agents which have different valuations for each outcome. The valuation of agent   is represented as a function:

 

which expresses the value it has for each alternative, in monetary terms.

It is assumed that the agents have Quasilinear utility functions; this means that, if the outcome is   and in addition the agent receives a payment   (positive or negative), then the total utility of agent   is:

 

The vector of all value-functions is denoted by  .

For every agent  , the vector of all value-functions of the other agents is denoted by  . So  .

A mechanism is a pair of functions:

  • An   function, that takes as input the value-vector   and returns an outcome   (it is also called a social choice function);
  • A   function, that takes as input the value-vector   and returns a vector of payments,  , determining how much each player should receive (a negative payment means that the player should pay a positive amount).

A mechanism is called strategyproof if, for every player   and for every value-vector of the other players  :

 

Characterization edit

It is helpful to have simple conditions for checking whether a given mechanism is SP or not. This subsection shows two simple conditions that are both necessary and sufficient.

If a mechanism is SP, then it must satisfy the following two conditions, for every agent  :[1]: 226 

1. The payment to agent   is a function of the chosen outcome and of the valuations of the other agents   - but not a direct function of the agent's own valuation  . Formally, there exists a price function  , that takes as input an outcome   and a valuation vector for the other agents  , and returns the payment for agent  , such that for every  , if:

 

then:

 

PROOF: If   then an agent with valuation   prefers to report  , since it gives him the same outcome and a larger payment; similarly, if   then an agent with valuation   prefers to report  .

As a corollary, there exists a "price-tag" function,  , that takes as input an outcome   and a valuation vector for the other agents  , and returns the payment for agent   For every  , if:

 

then:

 

2. The selected outcome is optimal for agent  , given the other agents' valuations. Formally:

 

where the maximization is over all outcomes in the range of  .

PROOF: If there is another outcome   such that  , then an agent with valuation   prefers to report  , since it gives him a larger total utility.

Conditions 1 and 2 are not only necessary but also sufficient: any mechanism that satisfies conditions 1 and 2 is SP.

PROOF: Fix an agent   and valuations  . Denote:

  - the outcome when the agent acts truthfully.
  - the outcome when the agent acts untruthfully.

By property 1, the utility of the agent when playing truthfully is:

 

and the utility of the agent when playing untruthfully is:

 

By property 2:

 

so it is a dominant strategy for the agent to act truthfully.

Outcome-function characterization edit

The actual goal of a mechanism is its   function; the payment function is just a tool to induce the players to be truthful. Hence, it is useful to know, given a certain outcome function, whether it can be implemented using a SP mechanism or not (this property is also called implementability). The Monotonicity (mechanism design) property is necessary, and often also sufficient.

Truthful mechanisms in single-parameter domains edit

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

For this setting, it is easy to characterize truthful 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 truthful if the following two conditions hold:[1]: 229–230 

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

Truthfulness of randomized mechanisms edit

There are various ways to extend the notion of truthfulness to randomized mechanisms. They are, from strongest to weakest:[3]: 6–8 

  • Universal truthfulness: for each randomization of the algorithm, the resulting mechanism is truthful. In other words: a universally-truthful mechanism is a randomization over deterministic truthful mechanisms, where the weights may be input-dependent.
  • Strong stochastic-dominance truthfulness (strong-SD-truthfulness): The vector of probabilities that an agent receives by being truthful has first-order stochastic dominance over the vector of probabilities he gets by misreporting. That is: the probability of getting the top priority is at least as high AND the probability of getting one of the two top priorities is at least as high AND ... the probability of getting one of the m top priorities is at least as high.
  • Lexicographic truthfulness (lex-truthfulness): The vector of probabilities that an agent receives by being truthful has lexicographic dominance over the vector of probabilities he gets by misreporting. That is: the probability of getting the top priority is higher OR (the probability of getting the top priority is equal and the probability of getting one of the two top priorities is higher) OR ... (the probability of getting the first m-1 priorities priority is equal and the probability of getting one of the m top priorities is higher) OR (all probabilities are equal).
  • Weak stochastic-dominance truthfulness (weak-SD-truthfulness): The vector of probabilities that an agent receives by being truthful is not first-order-stochastically-dominated by the vector of probabilities he gets by misreporting.

Universal implies strong-SD implies Lex implies weak-SD, and all implications are strict.[3]: Thm.3.4 

Truthfulness with high probability edit

For every constant  , a randomized mechanism is called truthful with probability   if for every agent and for every vector of bids, the probability that the agent benefits by bidding non-truthfully is at most  , where the probability is taken over the randomness of the mechanism.[1]: 349 

If the constant   goes to 0 when the number of bidders grows, then the mechanism is called truthful with high probability. This notion is weaker than full truthfulness, but it is still useful in some cases; see e.g. consensus estimate.

False-name-proofness edit

A new type of fraud that has become common with the abundance of internet-based auctions is false-name bids – bids submitted by a single bidder using multiple identifiers such as multiple e-mail addresses.

False-name-proofness means that there is no incentive for any of the players to issue false-name-bids. This is a stronger notion than strategyproofness. In particular, the Vickrey–Clarke–Groves (VCG) auction is not false-name-proof.[4]

False-name-proofness is importantly different from group strategyproofness because it assumes that an individual alone can simulate certain behaviours that would normally require the collusive coordination of multiple individuals.

See also edit

Further reading edit

  • 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.
  • On Asymptotic Strategy-Proofness of Classical Social Choice Rules An article by Arkadii Slinko about strategy-proofness in voting systems.

References edit

  1. ^ a b c d e 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. ^ (PDF). Archived from the original (PDF) on 2020-02-12.
  3. ^ a b Chakrabarty, Deeparnab; Swamy, Chaitanya (2014-01-12). "Welfare maximization and truthfulness in mechanism design with ordinal preferences". Proceedings of the 5th conference on Innovations in theoretical computer science. ITCS '14. New York, NY, USA: Association for Computing Machinery. pp. 105–120. doi:10.1145/2554797.2554810. ISBN 978-1-4503-2698-8. S2CID 2428592.
  4. ^ Yokoo, M.; Sakurai, Y.; Matsubara, S. (2004). "The effect of false-name bids in combinatorial auctions: New fraud in internet auctions". Games and Economic Behavior. 46: 174–188. CiteSeerX 10.1.1.18.6796. doi:10.1016/S0899-8256(03)00045-9.

strategyproofness, game, theory, asymmetric, game, where, players, have, private, information, said, strategy, proof, strategyproof, weakly, dominant, strategy, every, player, reveal, private, information, given, information, about, what, others, fare, best, l. In game theory an asymmetric game where players have private information is said to be strategy proof or strategyproof SP if it is a weakly dominant strategy for every player to reveal his her private information 1 244 i e given no information about what the others do you fare best or at least not worse by being truthful SP is also called truthful or dominant strategy incentive compatible DSIC 1 415 to distinguish it from other kinds of incentive compatibility An SP game is not always immune to collusion but its robust variants are with group strategyproofness no group of people can collude to misreport their preferences in a way that makes every member better off and with strong group strategyproofness no group of people can collude to misreport their preferences in a way that makes at least one member of the group better off without making any of the remaining members worse off 2 Contents 1 Examples 2 Notation 3 Characterization 3 1 Outcome function characterization 4 Truthful mechanisms in single parameter domains 5 Truthfulness of randomized mechanisms 5 1 Truthfulness with high probability 6 False name proofness 7 See also 8 Further reading 9 ReferencesExamples editTypical examples of SP mechanisms are majority voting between two alternatives second price auction and any VCG mechanism Typical examples of mechanisms that are not SP are plurality voting between three or more alternatives and first price auction SP is also applicable in network routing 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 SP that is the owners of some links can benefit by lying about the cost We may end up paying far more than the actual cost It can be shown that given certain assumptions about the network and the players owners of links a variant of the VCG mechanism is SP Notation editThere is a set X displaystyle X nbsp of possible outcomes There are n displaystyle n nbsp agents which have different valuations for each outcome The valuation of agent i displaystyle i nbsp is represented as a function v i X R displaystyle v i X longrightarrow R nbsp which expresses the value it has for each alternative in monetary terms It is assumed that the agents have Quasilinear utility functions this means that if the outcome is x displaystyle x nbsp and in addition the agent receives a payment p i displaystyle p i nbsp positive or negative then the total utility of agent i displaystyle i nbsp is u i v i x p i displaystyle u i v i x p i nbsp The vector of all value functions is denoted by v displaystyle v nbsp For every agent i displaystyle i nbsp the vector of all value functions of the other agents is denoted by v i displaystyle v i nbsp So v v i v i displaystyle v equiv v i v i nbsp A mechanism is a pair of functions An O u t c o m e displaystyle Outcome nbsp function that takes as input the value vector v displaystyle v nbsp and returns an outcome x X displaystyle x in X nbsp it is also called a social choice function A P a y m e n t displaystyle Payment nbsp function that takes as input the value vector v displaystyle v nbsp and returns a vector of payments p 1 p n displaystyle p 1 dots p n nbsp determining how much each player should receive a negative payment means that the player should pay a positive amount A mechanism is called strategyproof if for every player i displaystyle i nbsp and for every value vector of the other players v i displaystyle v i nbsp v i O u t c o m e v i v i P a y m e n t i v i v i v i O u t c o m e v i v i P a y m e n t i v i v i displaystyle v i Outcome v i v i Payment i v i v i geq v i Outcome v i v i Payment i v i v i nbsp Characterization editIt is helpful to have simple conditions for checking whether a given mechanism is SP or not This subsection shows two simple conditions that are both necessary and sufficient If a mechanism is SP then it must satisfy the following two conditions for every agent i displaystyle i nbsp 1 226 1 The payment to agent i displaystyle i nbsp is a function of the chosen outcome and of the valuations of the other agents v i displaystyle v i nbsp but not a direct function of the agent s own valuation v i displaystyle v i nbsp Formally there exists a price function P r i c e i displaystyle Price i nbsp that takes as input an outcome x X displaystyle x in X nbsp and a valuation vector for the other agents v i displaystyle v i nbsp and returns the payment for agent i displaystyle i nbsp such that for every v i v i v i displaystyle v i v i v i nbsp if O u t c o m e v i v i O u t c o m e v i v i displaystyle Outcome v i v i Outcome v i v i nbsp then P a y m e n t i v i v i P a y m e n t i v i v i displaystyle Payment i v i v i Payment i v i v i nbsp PROOF If P a y m e n t i v i v i gt P a y m e n t i v i v i displaystyle Payment i v i v i gt Payment i v i v i nbsp then an agent with valuation v i displaystyle v i nbsp prefers to report v i displaystyle v i nbsp since it gives him the same outcome and a larger payment similarly if P a y m e n t i v i v i lt P a y m e n t i v i v i displaystyle Payment i v i v i lt Payment i v i v i nbsp then an agent with valuation v i displaystyle v i nbsp prefers to report v i displaystyle v i nbsp As a corollary there exists a price tag function P r i c e i displaystyle Price i nbsp that takes as input an outcome x X displaystyle x in X nbsp and a valuation vector for the other agents v i displaystyle v i nbsp and returns the payment for agent i displaystyle i nbsp For every v i v i displaystyle v i v i nbsp if O u t c o m e v i v i x displaystyle Outcome v i v i x nbsp then P a y m e n t i v i v i P r i c e i x v i displaystyle Payment i v i v i Price i x v i nbsp 2 The selected outcome is optimal for agent i displaystyle i nbsp given the other agents valuations Formally O u t c o m e v i v i arg max x v i x P r i c e i x v i displaystyle Outcome v i v i in arg max x v i x Price i x v i nbsp where the maximization is over all outcomes in the range of O u t c o m e v i displaystyle Outcome cdot v i nbsp PROOF If there is another outcome x O u t c o m e v i v i displaystyle x Outcome v i v i nbsp such that v i x P r i c e i x v i gt v i x P r i c e i x v i displaystyle v i x Price i x v i gt v i x Price i x v i nbsp then an agent with valuation v i displaystyle v i nbsp prefers to report v i displaystyle v i nbsp since it gives him a larger total utility Conditions 1 and 2 are not only necessary but also sufficient any mechanism that satisfies conditions 1 and 2 is SP PROOF Fix an agent i displaystyle i nbsp and valuations v i v i v i displaystyle v i v i v i nbsp Denote x O u t c o m e v i v i displaystyle x Outcome v i v i nbsp the outcome when the agent acts truthfully x O u t c o m e v i v i displaystyle x Outcome v i v i nbsp the outcome when the agent acts untruthfully By property 1 the utility of the agent when playing truthfully is u i v i v i x P r i c e i x v i displaystyle u i v i v i x Price i x v i nbsp and the utility of the agent when playing untruthfully is u i v i v i x P r i c e i x v i displaystyle u i v i v i x Price i x v i nbsp By property 2 u i v i u i v i displaystyle u i v i geq u i v i nbsp so it is a dominant strategy for the agent to act truthfully Outcome function characterization edit The actual goal of a mechanism is its O u t c o m e displaystyle Outcome nbsp function the payment function is just a tool to induce the players to be truthful Hence it is useful to know given a certain outcome function whether it can be implemented using a SP mechanism or not this property is also called implementability The Monotonicity mechanism design property is necessary and often also sufficient Truthful mechanisms in single parameter domains editA single parameter domain is a game in which each player i displaystyle i nbsp gets a certain positive value v i displaystyle v i nbsp for winning and a value 0 for losing A simple example is a single item auction in which v i displaystyle v i nbsp is the value that player i displaystyle i nbsp assigns to the item For this setting it is easy to characterize truthful 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 truthful if the following two conditions hold 1 229 230 The assignment function is monotone in each of the bids and Every winning bid pays the critical value Truthfulness of randomized mechanisms editThere are various ways to extend the notion of truthfulness to randomized mechanisms They are from strongest to weakest 3 6 8 Universal truthfulness for each randomization of the algorithm the resulting mechanism is truthful In other words a universally truthful mechanism is a randomization over deterministic truthful mechanisms where the weights may be input dependent Strong stochastic dominance truthfulness strong SD truthfulness The vector of probabilities that an agent receives by being truthful has first order stochastic dominance over the vector of probabilities he gets by misreporting That is the probability of getting the top priority is at least as high AND the probability of getting one of the two top priorities is at least as high AND the probability of getting one of the m top priorities is at least as high Lexicographic truthfulness lex truthfulness The vector of probabilities that an agent receives by being truthful has lexicographic dominance over the vector of probabilities he gets by misreporting That is the probability of getting the top priority is higher OR the probability of getting the top priority is equal and the probability of getting one of the two top priorities is higher OR the probability of getting the first m 1 priorities priority is equal and the probability of getting one of the m top priorities is higher OR all probabilities are equal Weak stochastic dominance truthfulness weak SD truthfulness The vector of probabilities that an agent receives by being truthful is not first order stochastically dominated by the vector of probabilities he gets by misreporting Universal implies strong SD implies Lex implies weak SD and all implications are strict 3 Thm 3 4 Truthfulness with high probability edit For every constant ϵ gt 0 displaystyle epsilon gt 0 nbsp a randomized mechanism is called truthful with probability 1 ϵ displaystyle 1 epsilon nbsp if for every agent and for every vector of bids the probability that the agent benefits by bidding non truthfully is at most ϵ displaystyle epsilon nbsp where the probability is taken over the randomness of the mechanism 1 349 If the constant ϵ displaystyle epsilon nbsp goes to 0 when the number of bidders grows then the mechanism is called truthful with high probability This notion is weaker than full truthfulness but it is still useful in some cases see e g consensus estimate False name proofness editA new type of fraud that has become common with the abundance of internet based auctions is false name bids bids submitted by a single bidder using multiple identifiers such as multiple e mail addresses False name proofness means that there is no incentive for any of the players to issue false name bids This is a stronger notion than strategyproofness In particular the Vickrey Clarke Groves VCG auction is not false name proof 4 False name proofness is importantly different from group strategyproofness because it assumes that an individual alone can simulate certain behaviours that would normally require the collusive coordination of multiple individuals See also editIncentive compatibility Individual rationality means that a player cannot lose by playing the game i e a player has no incentive to avoid playing the game Further reading editParkes 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 On Asymptotic Strategy Proofness of Classical Social Choice Rules An article by Arkadii Slinko about strategy proofness in voting systems References edit a b c d e Vazirani Vijay V Nisan Noam Roughgarden Tim Tardos Eva 2007 Algorithmic Game Theory PDF Cambridge UK Cambridge University Press ISBN 0 521 87282 0 Group Strategy proofness And Social Choice Between Two Alternatives PDF Archived from the original PDF on 2020 02 12 a b Chakrabarty Deeparnab Swamy Chaitanya 2014 01 12 Welfare maximization and truthfulness in mechanism design with ordinal preferences Proceedings of the 5th conference on Innovations in theoretical computer science ITCS 14 New York NY USA Association for Computing Machinery pp 105 120 doi 10 1145 2554797 2554810 ISBN 978 1 4503 2698 8 S2CID 2428592 Yokoo M Sakurai Y Matsubara S 2004 The effect of false name bids in combinatorial auctions New fraud in internet auctions Games and Economic Behavior 46 174 188 CiteSeerX 10 1 1 18 6796 doi 10 1016 S0899 8256 03 00045 9 Retrieved from https en wikipedia org w index php title Strategyproofness amp oldid 1189893985, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.