# Strategyproofness

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

SP is also called truthful or dominant-strategy-incentive-compatible (DSIC),: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.

## Examples

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.

## Notation

There is a set $X$ of possible outcomes.

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

$v_{i}:X\longrightarrow R_{+}$ 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$ and in addition the agent receives a payment $p_{i}$ (positive or negative), then the total utility of agent $i$ is:

$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})$ ## Characterization

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 $i$ ::226

1. The payment to agent $i$ is a function of the chosen outcome and of the valuations of the other agents $v_{-i}$ - but not a direct function of the agent's own valuation $v_{i}$ . Formally, there exists a price 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$ , such that for every $v_{i},v_{i}',v_{-i}$ , if:

$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.

### Outcome-function characterization

The actual goal of a mechanism is its $Outcome$ 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

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 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 iff the following two conditions hold::229-230

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

## Truthfulness with-high-probability

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

If the constant $\epsilon$ 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

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.

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.