strategyproof

Strategyproofness is a property of a mechanism or social choice rule indicating that truth-telling about one’s private information is a dominant strategy for every participant. In a strategyproof mechanism, each agent maximizes their utility by reporting their true type (valuations, costs, or preferences) regardless of what others report. The concept is usually analyzed under quasi-linear utilities, where an agent’s payoff equals their value for the outcome minus any payment.

Formally, a mechanism maps reported types to outcomes and payments. It is strategyproof if for every agent i, for all possible true types t_i and all misreports t'_i, and for every fixed profile of others’ types t_{-i}, the utility from reporting t_i is at least as high as the utility from reporting t'_i.

Key results and examples:

- The second-price (Vickrey) auction is strategyproof for a single item: bidding truthfully is a dominant strategy.

- In single-parameter domains, strategyproofness often requires a monotone allocation rule with a critical-payment structure (Myerson’s lemma).

- VCG mechanisms provide strategyproofness in dominant strategies in many settings with quasi-linear utilities, aligning truthfulness with efficient outcomes.

- In deterministic, unrestricted preference domains with at least three alternatives, the Gibbard-Satterthwaite theorem shows that every strategyproof, nontrivial mechanism collapses to a dictatorship; randomized extensions (Gibbard–Sen results) can mitigate this, though with trade-offs.

- Strategyproofness can conflict with efficiency; achieving both in complex environments (e.g., combinatorial auctions) often requires concessions or restricted domains.

Applications span auction design, public goods decisions, and resource allocation, where eliciting truthful information simplifies mechanism design and improves predictability.