Strategyproofness

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Strategyproofness (SP) in mechanism design means that telling the truth is the best strategy for every participant, no matter what the others do. If players have private information (like their own value for an item), a truthful mechanism makes it a weakly-dominant strategy to reveal that information. SP is also called dominant-strategy incentive-compatible (DSIC).

SP prevents manipulation by individuals, but not by groups. A stronger idea is group strategyproofness: no group of people can collude to misreport their preferences in a way that makes every member better off. A still stronger notion is strong group strategyproofness: no colluding group can misreport so that at least one member is better off without making the others worse off.

Typical SP mechanisms include certain auction formats and carefully designed payment rules. Some mechanisms that are not SP allow players to gain by lying about their private information.

A familiar setting is network routing, where each link owner privately knows its cost to relay messages and wants to be paid fairly. If you simply ask everyone for their costs and pay them according to those reports, owners can lie to raise payments. Under some assumptions, a variant of the VCG mechanism can be SP and still ensure reasonable payments.

Formal view with monetary transfers
- There are many possible outcomes. Each agent assigns a value to each outcome.
- Each agent’s utility is their value for the chosen outcome plus a payment (which can be positive or negative): value minus payment.
- A mechanism consists of an outcome rule (which outcome is chosen given the reports) and a payment rule (how much each agent is paid).

A mechanism is SP if:
1) Each agent’s payment can depend on the chosen outcome and on everyone else’s reports, but not on the agent’s own report. In other words, there is a price function that, for a given outcome and others’ reports, tells you what the agent pays, independent of what the agent reported.
2) Given the other agents’ reports, the chosen outcome is the one that maximizes the agent’s own value plus the payment.

These two conditions are both necessary and sufficient for SP with money transfers: if they hold, truth-telling is a dominant strategy; if they fail, there are simple deviations that can benefit a lying agent.

Single-parameter domains
When each agent’s value is just a single positive number for “winning” (and zero for losing), the domain is called single-parameter. A mechanism is normalized if losing payments are zero, and it is monotone if raising your bid never hurts your chance of winning. In this setting, a normalized mechanism is truthful exactly when:
- It is monotone (higher bids don’t reduce winning chances), and
- There is a critical value at which an agent switches from losing to winning.
These two conditions fully characterize truthful mechanisms in single-parameter problems like simple auctions.

Randomized mechanisms
Truthfulness can be extended to randomized mechanisms in several ways, from strongest to weakest:
- Universal truthfulness, then strong dominant-strategy truthfulness, then lexicographic truthfulness, then weak dominant-strategy truthfulness.
- A mechanism may be truthful with probability 1 − ε, meaning an agent cannot gain by misreporting more than an ε amount, for any fixed bids. If ε goes to 0 as the number of bidders grows, we get truthfulness with high probability.

False-name-proofness and obvious strategyproofness
- False-name-proofness asks for no incentive to bid under false identities. This is stronger than SP, and the well-known VCG auction is not false-name-proof.
- Obvious strategyproofness (OSP) strengthens SP to be robust for cognitively limited agents. The sealed-bid second-price auction is SP but not obviously SP, while the ascending clock auction is obviously SP. Some SP mechanisms are SP but not obviously SP.

In short, strategyproofness ensures honesty is the best move for each participant under a mechanism, while there are stronger notions (group-proofness, false-name-proofness, obvious strategyproofness) that protect against more sophisticated or constrained forms of manipulation.