# Strategyproofness

(Redirected from Strategyproof)

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,[1]: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),[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

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

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

## Notation

There is a set ${\displaystyle X}$ of possible outcomes.

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

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

${\displaystyle u_{i}:=v_{i}(x)+p_{i}}$

The vector of all value-functions is denoted by ${\displaystyle v}$.

For every agent ${\displaystyle i}$, the vector of all value-functions of the other agents is denoted by ${\displaystyle v_{-i}}$. So ${\displaystyle v\equiv (v_{i},v_{-i})}$.

A mechanism is a pair of functions:

• An ${\displaystyle Outcome}$ function, that takes as input the value-vector ${\displaystyle v}$ and returns an outcome ${\displaystyle x\in X}$ (it is also called a social choice function);
• A ${\displaystyle Payment}$ function, that takes as input the value-vector ${\displaystyle v}$ and returns a vector of payments, ${\displaystyle (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 ${\displaystyle i}$ and for every value-vector of the other players ${\displaystyle 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})}$

## 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 ${\displaystyle i}$:[1]:226

1. The payment to agent ${\displaystyle i}$ is a function of the chosen outcome and of the valuations of the other agents ${\displaystyle v_{-i}}$ - but not a direct function of the agent's own valuation ${\displaystyle v_{i}}$. Formally, there exists a price function ${\displaystyle Price_{i}}$, that takes as input an outcome ${\displaystyle x\in X}$ and a valuation vector for the other agents ${\displaystyle v_{-i}}$, and returns the payment for agent ${\displaystyle i}$, such that for every ${\displaystyle v_{i},v_{i}',v_{-i}}$, if:

${\displaystyle Outcome(v_{i},v_{-i})=Outcome(v_{i}',v_{-i})}$

then:

${\displaystyle Payment_{i}(v_{i},v_{-i})=Payment_{i}(v_{i}',v_{-i})}$

PROOF: If ${\displaystyle Payment_{i}(v_{i},v_{-i})>Payment_{i}(v_{i}',v_{-i})}$ then an agent with valuation ${\displaystyle v_{i}'}$ prefers to report ${\displaystyle v_{i}}$, since it gives him the same outcome and a larger payment; similarly, if ${\displaystyle Payment_{i}(v_{i},v_{-i}) then an agent with valuation ${\displaystyle v_{i}}$ prefers to report ${\displaystyle v_{i}'}$.

As a corollary, there exists a "price-tag" function, ${\displaystyle Price_{i}}$, that takes as input an outcome ${\displaystyle x\in X}$ and a valuation vector for the other agents ${\displaystyle v_{-i}}$, and returns the payment for agent ${\displaystyle i}$ For every ${\displaystyle v_{i},v_{-i}}$, if:

${\displaystyle Outcome(v_{i},v_{-i})=x}$

then:

${\displaystyle Payment_{i}(v_{i},v_{-i})=Price_{i}(x,v_{-i})}$

2. The selected outcome is optimal for agent ${\displaystyle i}$, given the other agents' valuations. Formally:

${\displaystyle 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 ${\displaystyle Outcome(\cdot ,v_{-i})}$.

PROOF: If there is another outcome ${\displaystyle x'=Outcome(v_{i}',v_{-i})}$ such that ${\displaystyle v_{i}(x')+Price_{i}(x',v_{-i})>v_{i}(x)+Price_{i}(x,v_{-i})}$, then an agent with valuation ${\displaystyle v_{i}}$ prefers to report ${\displaystyle 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 ${\displaystyle i}$ and valuations ${\displaystyle v_{i},v_{i}',v_{-i}}$. Denote:

${\displaystyle x:=Outcome(v_{i},v_{-i})}$ - the outcome when the agent acts truthfully.
${\displaystyle 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:

${\displaystyle u_{i}(v_{i})=v_{i}(x)+Price_{i}(x,v_{-i})}$

and the utility of the agent when playing untruthfully is:

${\displaystyle u_{i}(v_{i}')=v_{i}(x')+Price_{i}(x',v_{-i})}$

By property 2:

${\displaystyle 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 ${\displaystyle 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:[1]: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 ${\displaystyle \epsilon >0}$, a randomized mechanism is called truthful with probability ${\displaystyle 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 ${\displaystyle \epsilon }$, where the probability is taken over the randomness of the mechanism.[1]:349

If the constant ${\displaystyle \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.[3]

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.