Strategyproofness

In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly-dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have private information (e.g. their type or their value to some item), and the strategy space of each player consists of the possible information values (e.g. possible types or values), a truthful mechanism is a game in which revealing the true information is a weakly-dominant strategy for each player. An SP mechanism is also called dominant-strategy-incentive-compatible (DSIC), to distinguish it from other kinds of incentive compatibility. A SP mechanism is immune to manipulations by individual players (but not by coalitions). In contrast, in a group strategyproof mechanism, no group of people can collude to misreport their preferences in a way that makes every member better off. In a strong group strategyproof mechanism, 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.

In mechanism design, a strategyproof (SP) mechanism is a game form in which each player has a weakly-dominant strategy, so that no player can gain by "spying" over the other players to know what they are going to play. When the players have private information (e.g. their type or their value to some item), and the strategy space of each player consists of the possible information values (e.g. possible types or values), a truthful mechanism is a game in which revealing the true information is a weakly-dominant strategy for each player. An SP mechanism is also called dominant-strategy-incentive-compatible (DSIC), to distinguish it from other kinds of incentive compatibility. A SP mechanism is immune to manipulations by individual players (but not by coalitions). In contrast, in a group strategyproof mechanism, no group of people can collude to misreport their preferences in a way that makes every member better off. In a strong group strategyproof mechanism, 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. u_i := v_i(x) + p_i The vector of all value-functions is denoted by v . For every agent i , the vector of all value-functions of the other agents is denoted by v_{-i} . So v \equiv (v_i,v_{-i}) . A mechanism is a pair of functions: An Outcome function, that takes as input the value-vector v and returns an outcome x\in X (it is also called a social choice function); A Payment function, that takes as input the value-vector v and returns a vector of payments, (p_1,\dots,p_n) , 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 and for every value-vector of the other players v_{-i} : 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}) Outcome(v_i,v_{-i}) = Outcome(v_i',v_{-i}) then: Payment_i(v_i,v_{-i}) = Payment_i(v_i',v_{-i}) PROOF: If Payment_i(v_i,v_{-i}) > Payment_i(v_i',v_{-i}) then an agent with valuation v_i' prefers to report v_i , since it gives him the same outcome and a larger payment; similarly, if Payment_i(v_i,v_{-i}) then an agent with valuation v_i prefers to report v_i' . As a corollary, there exists a "price-tag" function, Price_i , that takes as input an outcome x\in X and a valuation vector for the other agents v_{-i} , and returns the payment for agent i For every v_i,v_{-i} , if: Outcome(v_i,v_{-i}) = x then: Payment_i(v_i,v_{-i}) = Price_i(x,v_{-i}) 2. The selected outcome is optimal for agent i , given the other agents' valuations. Formally: Outcome(v_i, v_{-i}) \in \arg\max_{x} [v_i(x) + Price_i(x,v_{-i})] where the maximization is over all outcomes in the range of Outcome(\cdot,v_{-i}) . PROOF: If there is another outcome x' = Outcome(v_i',v_{-i}) such that v_i(x') + Price_i(x',v_{-i}) > v_i(x) + Price_i(x,v_{-i}) , then an agent with valuation v_i prefers to report v_i' , 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 and valuations v_i,v_i',v_{-i} . Denote: x := Outcome(v_i, v_{-i}) - the outcome when the agent acts truthfully. x' := Outcome(v_i', v_{-i}) - 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) + Price_i(x, v_{-i}) and the utility of the agent when playing untruthfully is: u_i(v_i') = v_i(x') + Price_i(x', v_{-i}) By property 2: u_i(v_i) \geq u_i(v_i') so it is a dominant strategy for the agent to act truthfully. ==Obvious strategyproofness== Obvious strategyproofness (OSP) is a strengthening of strategyproofness that captures a robustness of strategyproofness to cognitively-limited agents. The sealed-bid second-price auction is strategyproof but not obviously strategyproof because bidders have to trust that their bids remain sealed. In contrast, the ascending clock auction is obviously strategyproof, even though for fully rational agents the two auctions are equivalent. Other examples of strategyproof but not obviously strategyproof mechanisms include: Majority vote between two alternatives; Deferred acceptance Top trading cycles

Text derived from https://en.wikipedia.org/w/index.php?oldid=1361914943 under CC BY-SA 4.0; modifications have been made.