Must every false report make the participant worse off?

No. Equal outcomes are compatible with strategy-proofness; a false report must not improve the participant's utility.

Does the property require honest opponents?

No. The individual guarantee holds for every allowed combination of their reports.

Is group manipulation ruled out?

Not by individual strategy-proofness alone. Group guarantees require additional definitions and analysis.

AI Glossary / Graphs and symbolic AI / Intermediate

Strategy-proof

Definition

A rule is strategy-proof when no individual participant can obtain a better outcome, according to their true preferences, by misreporting their private information, whatever the other participants report. Truthful reporting is therefore a weakly dominant strategy within the specified model. The property concerns incentives created by the rule; it does not mean that participants cannot lie or that every possible form of manipulation is prevented.

What it means

Many systems ask people or agents for information that the system cannot directly observe: valuations, ranked preferences, or priorities. If reporting something false can improve the reporter's outcome, participants have an incentive to game the input process.

Strategy-proofness asks whether telling the truth is always at least as good as any alternative report, holding the others' reports fixed. “At least as good” matters: some false reports may produce exactly the same outcome. The property does not require truth to be strictly better in every situation or require software to identify which statements are true.

How it works

Specify the permitted private information, reports, outcomes, and the participant's preferences over those outcomes. If payments are involved, include them in utility rather than considering the allocation alone. Fix one participant's true information and every other participant's report.

Compare the outcome from that participant's truthful report with the outcomes from all allowed false reports. Repeat across participants, possible true information, and other-report combinations. Strategy-proofness requires that none of these unilateral comparisons favors a false report.

This is stronger than truthfulness being optimal only on average under a belief about other participants. A finite toy rule can sometimes be checked exhaustively. A general mechanism usually needs a mathematical argument that covers the full domain. Restricted examples, favorable simulations, or observed honest behavior alone do not establish the property.

Three practical examples

Allocation design: ask whether a participant could gain a preferred assignment by misstating preferences, before deploying an automated matching or booking rule.
Auction education: use a single-item second-price auction to explain why the payment rule can change the incentive to exaggerate a private value.
Voting-rule review: search for preference reports that benefit one voter while all other ballots stay fixed. A successful counterexample disproves strategy-proofness on that domain.

Think of it this way

Think of a form whose rules make accurate answers the safest individual choice for obtaining the outcome you actually prefer. The analogy is limited: strategy-proofness is not a lie detector, and it does not cover motives or actions omitted from the model. A participant might still lie through confusion, indifference, or a wish to help someone else.

Worked example

Consider an original educational single-item second-price auction. The highest bidder wins and pays the highest other bid; losers pay nothing. Assume private values, enforceable payments, and utility equal to value minus payment when winning, or zero when losing. Fix a bidder's true value at 40 and hold all other bids fixed.

If the highest other bid is 30, bidding 40 wins at 30 and gives utility 10. Bidding 35 or 60 also wins at 30 and still gives 10. Bidding 20 loses and gives zero. Exaggerating does not reduce the payment; understating can lose a beneficial purchase.

If the highest other bid is 50, truthful bidding loses and gives zero. Bidding 60 wins but gives 40 − 50 = −10. Bidding below 50 also loses and gives zero. When the highest other bid is exactly 40, either winning at 40 or losing gives zero, so an ordinary fixed tie rule does not create a profitable deviation.

These comparisons show the underlying threshold argument: truth wins when the price is below value and avoids winning when it is above value. The conclusion depends on this precise allocation, payment, and utility model. It is not a general instruction for every auction advertised as second-price.

Illustrative case study

Fictional case: a team builds an internal preference survey for allocating workshop places. Its first proposal gives more priority to employees who describe every session as essential. A designer notices that someone may benefit by exaggerating interest, so calling the proposal strategy-proof would be unjustified.

The team documents the permitted preferences and tests unilateral false reports while keeping everyone else's submissions unchanged. One beneficial deviation is enough to reject the claim for that proposal. The fictional exercise illustrates how to examine incentives; it does not claim that an alternative rule has been proven strategy-proof or suitable for an employment setting.

Common misconceptions and mistakes

Strategy-proof does not mean fair, efficient, inclusive, or revenue-maximizing. A rule can remove an individual incentive to lie while performing poorly on those separate objectives. It also does not automatically protect against coalitions, multiple identities, side payments, or changes to the surrounding process.

Do not replace “whatever others report” with “assuming everyone else is honest.” Do not confuse the participant's true value with a bid or declared preference. Finally, an approximate or modified implementation needs its own incentive analysis; borrowing a familiar mechanism's name does not transfer its proof.

Business use

The business value is clearer elicitation: participants have less reason to spend effort guessing which false answer will help them. Before making a product claim, identify exactly whose manipulation is covered and which reports are allowed. Treat identity controls, privacy, accessibility, participation, and outcome quality as separate design questions.

For AI agents, check whether their implemented reward really matches the utility used in the proof. An agent optimizing a different objective may behave differently without contradicting the theorem.

Check your understanding

A rule prevents profitable lies when everyone else is truthful, but permits one when another person lies. Is it strategy-proof?

Answer: No. The guarantee must hold regardless of the other participants' allowed reports.

Related terms

Mechanism design
Dominant strategy
Revelation principle
incentive compatibility
private value
second-price auction
preference profile
social choice

Learn next

Compare a small rule's outcomes for truthful and false reports, keeping other inputs fixed. Then study dominant-strategy versus Bayesian incentive compatibility, and distinguish individual strategy-proofness from coalition-resistant design.

Dominant strategy

Sources

Carnegie Mellon, Game Theory notes, strategy-proof voting definition: https://www.cs.cmu.edu/~15281/coursenotes/gametheory/ Tim Roughgarden, Mechanism Design Basics, private-value auction model and truthful-bidding argument: https://timroughgarden.org/f13/l/l2.pdf The auction amounts and workshop case are original illustrations. This entry explains mathematical incentives, not bidding advice or a certification of a real platform.

Previous: Strategy profile Next: Stratification