Strategyproofness: When Telling the Truth Is Always Your Best Move

A rule for making group decisions is called strategyproof if no participant can ever do better by lying about what they want. Whatever everyone else says, telling the truth is at least as good for you as any misrepresentation. In the language of game theory, truthful reporting is a weakly dominant strategy. Strategyproof mechanisms are also called dominant-strategy incentive-compatible (DSIC) or, in computer science, truthful.

The idea sounds modest, but it sits at the centre of some of the most important results in economics, political science and computer science. It explains why sealed-bid auctions in which the winner pays the second-highest bid behave so differently from ones in which the winner pays their own bid. It underlies the famous impossibility theorem of Allan Gibbard and Mark Satterthwaite, which shows that every reasonable voting system with three or more options can be manipulated. And it has shaped the redesign of real institutions, from school assignment in Boston to online advertising auctions.

This article explains what strategyproofness means, why it is valuable, where it comes from historically, how it is achieved in practice, the theorems that limit it, and the common misunderstandings that surround it.

The basic idea

Many decisions require a planner to collect private information from people. An auctioneer wants to know how much bidders value an item. A city wants to know which schools families prefer. A committee wants to know how members rank candidates. A network wants to know how much it costs each router to carry traffic.

The planner uses some rule, a mechanism, to turn the reports into an outcome (who wins, who goes where, who is elected) and perhaps into payments. Participants know this rule. If it is possible to get a better outcome by reporting something other than the truth, many will do so, and the planner's information will be distorted.

A strategyproof mechanism removes that temptation. It is designed so that for every participant, and for every possible combination of what the others report, the truthful report is a best response. Participants do not need to guess what others will do, gather information about them, or compute clever strategies. They can simply say what they want.

Formal definition

The Wikipedia treatment uses a standard setting from mechanism design with money.

• There is a set of possible outcomes, X.
• There are n agents. Each agent i has a valuation v_i that assigns a value (measured in money) to each outcome.
• Agents have quasilinear utility: if the outcome is x and agent i receives a payment p_i (which can be negative, meaning the agent pays), then the agent's utility is v_i(x) + p_i.

A mechanism has two parts:

1. An outcome function, sometimes called the social choice function, that maps reported valuations to an outcome.
2. A payment function that maps reported valuations to payments for each agent.

The mechanism is strategyproof if, for every agent i, every true valuation v_i, every possible false report v_i′, and every combination v_−i of the other agents' reports, the agent's utility from reporting v_i is at least as high as from reporting v_i′.

Two features of the definition deserve emphasis:

• "For every combination of the others' reports." This is what makes strategyproofness so strong. It is not enough that truth-telling is best when others are also truthful (that weaker property is called Bayesian or Nash incentive compatibility). Under strategyproofness, truth-telling is best even if others lie, make mistakes or behave unpredictably.
• "At least as high." Truth-telling must be weakly better. There may be other reports that do equally well, but none does strictly better.

Strategyproofness also applies outside settings with money. In voting, school choice or matching, agents report rankings rather than monetary valuations, and the definition becomes: for every agent and every profile of others' rankings, the outcome from a truthful ranking is at least as good, by the agent's true preferences, as the outcome from any false ranking.

History

Early observations about manipulation

People have noticed strategic voting for as long as there have been elections. According to Wikipedia's account of the Gibbard–Satterthwaite theorem, Charles Dodgson, the Oxford mathematician better known as Lewis Carroll, commented on strategic voting in 1876. In 1961 the philosophers Michael Dummett and Robin Farquharson conjectured that essentially every voting procedure is open to manipulation.

Vickrey's auctions (1961)

The same year, the economist William Vickrey published "Counterspeculation, Auctions, and Competitive Sealed Tenders" in the Journal of Finance. Vickrey analysed an auction in which bidders submit sealed bids, the highest bidder wins, and the winner pays the second-highest bid. He showed that in this auction bidding one's true value is a dominant strategy. It was the first clear demonstration of a strategyproof mechanism in an economic setting. Vickrey shared the Nobel Memorial Prize in Economic Sciences in 1996 with James Mirrlees for work on incentives under asymmetric information.

Hurwicz and incentive compatibility

Around the same period, Leonid Hurwicz was developing the general framework of mechanism design, in which a designer chooses rules to achieve goals when participants hold private information. Hurwicz introduced the term incentive compatibility for mechanisms in which participants have an incentive to report truthfully. In 2007 Hurwicz, Eric Maskin and Roger Myerson shared the Nobel Memorial Prize for laying the foundations of mechanism design theory.

Clarke and Groves (1971–1973)

Vickrey's idea was generalised by Edward Clarke, in a 1971 article on pricing public goods in Public Choice, and by Theodore Groves, in a 1973 article in Econometrica. Their mechanisms, together with Vickrey's, are now known as Vickrey–Clarke–Groves (VCG) mechanisms. They show that, when money can be transferred and utility is quasilinear, it is possible to implement the socially efficient outcome in a strategyproof way.

Gibbard and Satterthwaite (1973–1975)

In 1973 the philosopher Allan Gibbard published "Manipulation of Voting Schemes: A General Result" in Econometrica (volume 41, pages 587–601). In 1975 the economist Mark Satterthwaite published "Strategy-proofness and Arrow's Conditions: Existence and Correspondence Theorems for Voting Procedures and Social Welfare Functions" in the Journal of Economic Theory (volume 10, starting at page 187). Working independently, they proved the result that confirmed Dummett and Farquharson's conjecture: any deterministic voting rule that chooses among at least three alternatives, where every alternative can win, is strategyproof only if it is a dictatorship. Satterthwaite's paper is also where the term "strategy-proofness" became standard.

Restricted domains and matching (1980s)

Researchers then looked for settings where the impossibility could be avoided. In 1980 Hervé Moulin published "On Strategy-Proofness and Single Peakedness" in Public Choice (volume 35, pages 437–455), characterising the strategyproof rules when voters' preferences are single-peaked along a line. In matching markets, Lester Dubins and David Freedman showed in a 1981 paper in the American Mathematical Monthly, "Machiavelli and the Gale–Shapley Algorithm," that the side that makes proposals in the deferred acceptance algorithm cannot gain by lying. Alvin Roth's 1982 paper "The Economics of Matching: Stability and Incentives" in Mathematics of Operations Research showed that no stable matching mechanism can be strategyproof for both sides of the market. Roth and Lloyd Shapley shared the 2012 Nobel Memorial Prize for the theory of stable allocations and the practice of market design.

Myerson and single-parameter settings (1981)

Roger Myerson's 1981 paper "Optimal Auction Design" in Mathematics of Operations Research gave a precise characterisation of truthful mechanisms in settings where each bidder's private information is a single number, such as their value for an item. This result, often called Myerson's lemma in textbooks, became a cornerstone of auction theory and later of algorithmic game theory.

Algorithmic mechanism design (1990s onward)

From the late 1990s computer scientists took up strategyproofness as a design goal for systems such as network routing, scheduling and online advertising, where participants are self-interested programs or companies. The textbook Algorithmic Game Theory (2007), edited by Noam Nisan, Tim Roughgarden, Éva Tardos and Vijay Vazirani, collected much of this work.

Example 1: the second-price auction

The second-price (Vickrey) auction is the classic strategyproof mechanism. Each bidder submits a sealed bid. The highest bidder wins and pays the second-highest bid.

Why bidding your true value is optimal

Suppose your true value for the item is V. Let H be the highest of the other bids. You do not know H.

• If you bid V and V > H, you win and pay H, gaining V − H > 0.
• If you bid V and V < H, you lose and pay nothing, gaining 0.

Now consider deviating:

• Bidding more than V. If H is below V, you still win and pay H, the same as before. If H is above your new bid, you still lose. The only case that changes is when H is between V and your new bid: now you win but pay H > V, a loss. So overbidding can only hurt.
• Bidding less than V. If H is below your lower bid, you win and pay H, the same as before. If H is above V, you lose either way. The only case that changes is when H is between your lower bid and V: you now lose an auction you would have won at a profit. So underbidding can only hurt.

The key insight is that your bid determines whether you win but not how much you pay. The price is set by someone else's bid. That separation is what makes truthfulness optimal.

A worked example (hypothetical)

The numbers here are hypothetical. Three bidders want a used bicycle. Their true values are: Ana $120, Ben $90, Cleo $70.

Under truthful bidding, Ana wins and pays $90 (Ben's bid), gaining $30.

• If Ana shades her bid to $80, Ben's $90 wins. Ana loses a gain of $30. Shading hurt her.
• If Ben inflates his bid to $130 hoping to win, he wins but pays $120 (Ana's bid) for something worth $90 to him: a loss of $30. Inflating hurt him.
• If Ben bids $100 instead of $90, Ana still wins, now paying $100 rather than $90. This does not help Ben, though it does hurt Ana. Notice that strategyproofness protects each agent's own interests from their own lies; it does not stop one agent's report from affecting another's payoff.

Contrast: the first-price auction

In a first-price sealed-bid auction, the highest bidder wins and pays their own bid. This is not strategyproof. If Ana bid her true value of $120 she would gain nothing even when she won. Her best strategy is to bid somewhat less, by an amount that depends on her beliefs about the others' bids. Bidders in first-price auctions therefore "shade" their bids, and the optimal amount of shading depends on information they may not have.

Example 2: voting with two alternatives

When there are only two alternatives, simple majority rule is strategyproof. If you prefer A to B, voting for B can only make B more likely to win, which is worse for you. Voting for A is always at least as good.

The trouble starts with three or more alternatives.

Example 3: manipulation in a ranked vote (hypothetical)

Consider the Borda count, a rule in which each voter ranks the candidates and each rank earns points. With four candidates, a first place earns 3 points, second 2, third 1 and last 0. The candidate with the most points wins.

The following profile is hypothetical. Three voters rank four candidates A, B, C and D.

Totals: A = 7, B = 8, C = 2, D = 1. B wins.

Voter 1 prefers A to B. Suppose Voter 1 instead submits A > C > D > B, deliberately "burying" B at the bottom.

New totals: A = 7, B = 6, C = 3, D = 2. A wins.

By misreporting, Voter 1 changed the result from B to A, which Voter 1 prefers. The Borda count is therefore not strategyproof. Wikipedia's article on the Gibbard–Satterthwaite theorem gives a similar example with three voters and four candidates.

Other common systems are manipulable in different ways. Under plurality voting, a voter whose favourite has no chance may vote for a second choice to stop a disliked front-runner. Under instant-runoff voting, a voter may rank a weak candidate first to change the order of eliminations. The Gibbard–Satterthwaite theorem says these are not quirks of particular rules: every reasonable deterministic ranked rule with three or more possible winners has some profile where someone can profit from lying.

The Gibbard–Satterthwaite theorem

Statement

Consider a deterministic voting rule that takes each voter's strict ranking of the alternatives and selects a single winner. Suppose:

1. There are at least three alternatives that can each win under some set of ballots.
2. The rule is strategyproof: no voter can ever obtain a preferred outcome by misreporting.

Then the rule is a dictatorship: there is one voter whose top choice always wins, regardless of everyone else.

Put the other way round, any non-dictatorial rule with at least three possible winners is manipulable. Since no one wants a dictatorship, every voting system used in practice must accept some vulnerability to strategic voting.

How it relates to Arrow's theorem

Gibbard and Satterthwaite both derived their result from Kenneth Arrow's impossibility theorem, which shows that no method of aggregating rankings into a social ranking satisfies a short list of reasonable conditions. Satterthwaite's paper title refers explicitly to a "correspondence" between strategyproof voting procedures and social welfare functions that satisfy Arrow's conditions. Later authors, including Salvador Barberà and Bezalel Peleg, gave alternative proofs.

Extensions

According to Wikipedia's summary:

• Gibbard's theorem generalises the result beyond ranked ballots to any process for making collective decisions, including cardinal (score-based) voting.
• Gibbard's work on lotteries and Hylland's theorem extend it to rules that use randomness. Roughly, the only strategyproof random rules are mixtures of dictatorships and of rules that choose between two fixed alternatives.
• The Duggan–Schwartz theorem extends it to rules that may choose sets of winners.

What the theorem does not say

The theorem guarantees that manipulation is possible for some profile. It does not say manipulation is easy, common, or that voters know when they can do it. Some rules are much harder to manipulate in practice than others, and research in computational social choice has studied how hard it is computationally to find a successful manipulation.

Escape routes from impossibility

The Gibbard–Satterthwaite theorem depends on its assumptions. Relaxing any of them opens the door to strategyproof mechanisms. The main escape routes are summarised below.

Single-peaked preferences and the median rule

Preferences are single-peaked if alternatives can be arranged along a line (for example, temperatures, tax rates or budget levels) and each person has a favourite point, liking options less the further they are from it in either direction.

When preferences are single-peaked, the rule "ask everyone for their favourite point and choose the median" is strategyproof. Suppose your favourite point is below the median. Reporting an even lower point does not move the median. Reporting a higher point can only move the median up, further from you. So you cannot gain by lying.

Hypothetical example. Five housemates choose a thermostat setting. Their favourite temperatures are 18, 19, 20, 22 and 24 degrees Celsius. The median is 20. The housemate who prefers 24 might be tempted to report 30 to "pull" the result upward. But the median of 18, 19, 20, 22 and 30 is still 20. The only way to move the median is for someone below or at it to report a number above it, which would move the result away from their own preference. Nobody gains.

Moulin's 1980 paper characterised all strategyproof rules in this setting (under an assumption that the rule depends only on each voter's top choice): they are generalised median rules, which can be described as taking the median of the voters' reported peaks together with a fixed set of "phantom" ballots chosen in advance. On this domain, strategyproofness and group strategyproofness turn out to be equivalent.

Using money: VCG mechanisms

When outcomes can be accompanied by payments and agents value money linearly (quasilinear utility), strategyproof mechanisms become much easier to design. The VCG mechanism works as follows:

1. Each agent reports their valuation for every possible outcome.
2. The mechanism chooses the outcome that maximises the total reported value.
3. Each agent pays an amount equal to the harm their presence causes to everyone else.

Under the commonly used Clarke pivot rule, agent i's payment is the total value that the other agents would have received if agent i had not participated, minus the total value they actually receive in the chosen outcome. This is agent i's externality on the others.

Why is this strategyproof? With these payments, agent i's utility equals the total welfare of everyone (by reported values, with i's own value true) minus a term that does not depend on i's report. So agent i maximises its own utility by making the mechanism maximise total welfare, which is achieved by reporting truthfully.

Hypothetical example: a public project. A street of three households is deciding whether to build a shared playground. Each household's value for the project, net of its fixed share of the construction cost, is: Household 1 +150, Household 2 −40, Household 3 −60. The total is +50, so the project is built.

Only Household 1 is pivotal: without it, the project would not be built. It pays 100, the net harm its participation causes the others. Its overall utility is 150 − 100 = 50, still positive.

Could Household 2 benefit by exaggerating its dislike, reporting −200? Then the total becomes 150 − 200 − 60 = −110, so the project is not built. But now Household 2 is pivotal: without it, the others' total would be 90 and the project would be built. Its payment is 90 − 0 = 90. Its true utility would be 0 (no project) − 90 = −90, worse than the −40 it gets by telling the truth. Exaggeration backfires.

The second-price auction is a special case of VCG: the winner's presence denies the item to the second-highest bidder, so the winner's externality is exactly the second-highest bid.

Matching and allocation without money

In many settings money is not allowed, such as assigning students to public schools or matching medical residents to hospitals.

• Deferred acceptance, introduced by David Gale and Lloyd Shapley in 1962, produces a stable matching. Dubins and Freedman (1981) showed it is strategyproof for the proposing side: no proposer, and no coalition of proposers, can gain by misreporting. It is not strategyproof for the receiving side. Roth (1982) showed that this asymmetry is unavoidable: no stable matching mechanism is strategyproof for everyone.
• Top trading cycles, attributed to David Gale and analysed by Lloyd Shapley and Herbert Scarf in 1974, allocates indivisible goods such as houses among people who each own one. It is strategyproof and produces efficient allocations.
• Serial dictatorship (also called random priority when the order is random) lets agents choose in order. Each agent simply picks their favourite remaining option, so truthfulness is trivially optimal.

A real-world case: Boston school choice

The importance of strategyproofness became concrete in Boston. Before 2005 Boston Public Schools used an assignment procedure, often called the "Boston mechanism," that first tried to give as many students as possible their first choice, then their second choice, and so on. Under this rule, ranking a popular school first and being rejected could cost a family their chance at their second choice, which might fill up in the first round. Families therefore had an incentive to rank strategically, for example putting a less popular but acceptable school first.

Economists Atila Abdulkadiroğlu, Parag Pathak, Alvin Roth and Tayfun Sönmez studied Boston's assignment data. In their paper "Changing the Boston School Choice Mechanism" (NBER Working Paper 11965, 2006), they reported that some parents paid close attention to school capacities while others did not, and that many unassigned students could have been assigned to one of their listed choices if they had ranked differently. In other words, the non-strategyproof mechanism rewarded sophistication and penalised families who simply listed their true preferences. The authors described this as a fairness argument for strategyproof mechanisms, and wrote that it was a critical argument in Boston's decision.

In July 2005 the Boston School Committee voted to replace the old mechanism with one based on deferred acceptance, with students proposing. Because student-proposing deferred acceptance is strategyproof for students, families could list their true preferences without fear of being punished for doing so. The paper also explains why Boston chose deferred acceptance over top trading cycles, which is also strategyproof.

The Boston case is often cited as a demonstration that strategyproofness is not only an elegant theoretical property but a practical tool for creating fair, simple and transparent institutions.

Characterising strategyproof mechanisms

The general characterisation with money

The Wikipedia article states two conditions that are together necessary and sufficient for a deterministic mechanism with quasilinear utility to be strategyproof:

1. Payment condition. Each agent's payment can depend on that agent's own report only through the outcome chosen. Formally, there is a price function Price_i(x, v_−i) that depends on the outcome x and on the other agents' reports, but not directly on agent i's own report.
2. Optimality condition. Given those prices, the mechanism chooses an outcome that maximises v_i(x) + Price_i(x, v_−i) for agent i, among the outcomes that agent i can bring about by changing its report.

Intuitively, each agent faces a "menu" of outcomes with prices set by others, and the mechanism must give each agent its favourite item on its menu according to its report. The second-price auction fits this description exactly: each bidder faces a menu of "lose and pay nothing" or "win and pay the highest other bid," and the mechanism gives each bidder whichever is better according to their bid.

Single-parameter settings and critical values

In many important settings, each agent's private information is a single number: a value for winning. Losing gives zero. Single-item auctions, many advertising auctions and procurement auctions fit this description.

In these settings the characterisation is especially clean. Following Algorithmic Game Theory (Vazirani and colleagues, 2007), as summarised in the Wikipedia article:

• A mechanism is monotone if raising your bid never turns you from a winner into a loser.
• For a monotone rule, each agent has a critical value: the bid at which, holding others fixed, the agent switches from losing to winning.
• A mechanism in which losers pay nothing is truthful if and only if (1) the winning rule is monotone in each agent's bid, and (2) every winner pays exactly its critical value.

This result is closely associated with Myerson's 1981 work. It has a powerful practical consequence: to design a truthful mechanism in a single-parameter setting, a designer only needs a monotone rule for deciding who wins. The payments are then determined uniquely by the critical values. In the second-price auction, the critical value for the winner is the highest competing bid, which is exactly what the winner pays.

Multi-parameter settings and Roberts' theorem

When agents have richer preferences, the menu of strategyproof mechanisms shrinks. A theorem due to Kevin Roberts (1979), summarised in Wikipedia's article on VCG, states that with unrestricted valuations and at least three possible outcomes, the only social choice functions that can be implemented in dominant strategies are affine maximisers: weighted versions of maximising total value. VCG mechanisms are therefore essentially the only truthful mechanisms that maximise total welfare. This result plays a role for money-based mechanisms similar to the one Gibbard–Satterthwaite plays for voting.

Variations and stronger notions

Group strategyproofness

Ordinary strategyproofness protects against an individual acting alone. It does not stop groups from coordinating. Wikipedia distinguishes:

• Group strategyproofness: no group can jointly misreport so that every member of the group is strictly better off.
• Strong group strategyproofness: no group can jointly misreport so that at least one member is better off and none is worse off.

VCG mechanisms are not group strategyproof: two bidders in a second-price auction can collude so that the winner's price falls. In the hypothetical bicycle auction above, if Ben agreed to bid $0 instead of $90, Ana would pay Cleo's $70, saving $20 she could share with Ben. Deferred acceptance, by contrast, is group strategyproof for the proposing side, as Dubins and Freedman showed.

Randomised mechanisms

When mechanisms use randomness, there are several ways to define truthfulness. The Wikipedia article lists them from strongest to weakest, following Chakrabarty and Swamy (2014):

Each implies the next, and the implications are strict. A further relaxation is truthfulness with probability 1 − ε: the chance that lying helps is at most ε, and if ε shrinks to zero as the number of participants grows, the mechanism is called truthful with high probability.

False-name-proofness

On the internet, one person can create several identities. A mechanism is false-name-proof if no participant can gain by submitting bids under multiple names. This is stronger than strategyproofness. Makoto Yokoo, Yuko Sakurai and Shigeo Matsubara showed in 2004 that VCG is not false-name-proof.

Obvious strategyproofness

Real people do not always recognise that truth-telling is a dominant strategy. Laboratory and field evidence shows that many people overbid or underbid in second-price auctions even though doing so cannot help them. In 2017 Shengwu Li introduced obvious strategyproofness (OSP), a stronger notion intended for agents with limited reasoning ability. Roughly, a strategy is obviously dominant if, at every point where a player must act, the worst outcome from following it is at least as good as the best outcome from deviating.

According to the Wikipedia summary:

• The ascending clock auction, in which a price rises until all but one bidder drops out, is obviously strategyproof: at any moment, staying in while the price is below your value cannot do worse than dropping out.
• The sealed-bid second-price auction is strategyproof but not obviously strategyproof, partly because bidders must trust that the auctioneer will keep bids sealed and apply the rule correctly.
• Deferred acceptance and top trading cycles are also strategyproof but not obviously strategyproof.

Related research, such as a 2023 working paper by Yannai Gonczarowski, Ori Heffetz and Clayton Thomas, has examined how the way a mechanism is described to participants affects whether they recognise that truth-telling is optimal.

Limits and costs of strategyproofness

Strategyproofness is valuable but not free. It typically conflicts with other goals.

Budget balance

VCG mechanisms usually collect more money than they pay out, or need a subsidy. They are not budget balanced. In settings such as public projects or shared costs, the leftover money cannot be returned to participants without disturbing incentives. The Myerson–Satterthwaite theorem (1983) shows a related impossibility for bilateral trade: when a buyer and a seller each have private values, no mechanism can be simultaneously efficient, incentive compatible, individually rational and budget balanced.

Revenue

Strategyproof mechanisms are not always the most profitable for the designer. Myerson's work showed how to design auctions that maximise expected revenue, for example by setting reserve prices, which may sacrifice efficiency.

Collusion

As noted above, strategyproof mechanisms often remain vulnerable to coordinated lying by groups.

Computation

VCG requires finding the outcome that maximises total value. In combinatorial auctions, where bidders value bundles of items, this optimisation problem is computationally hard (NP-hard). Replacing the exact optimum with an approximation can destroy strategyproofness, which motivates a large literature on designing approximately optimal mechanisms that remain truthful.

Stability in matching

Roth's 1982 result shows that, in two-sided matching, strategyproofness for everyone is incompatible with stability. Designers must choose which side to protect.

Restricted expressiveness

Some strategyproof mechanisms achieve truthfulness by limiting what they let participants express, or by ignoring information. Serial dictatorship is strategyproof but can produce outcomes that seem unfair.

Real people do not always behave as theory predicts

Strategyproofness says truth-telling is optimal; it does not guarantee people will tell the truth. If participants misunderstand the mechanism, they may still misreport. This gap is part of the motivation for obvious strategyproofness and for careful attention to how mechanisms are explained.

Common misconceptions

"Strategyproof means nobody can manipulate the outcome." Strategyproofness means no individual can benefit themselves by misreporting. It does not prevent groups from colluding, prevent the designer from cheating, or stop one agent's report from affecting another's payoff.

"A strategyproof mechanism is fair." Not necessarily. A dictatorship is strategyproof. Strategyproofness concerns incentives, not fairness or efficiency, though, as the Boston example shows, it can support fairness by removing the advantage of sophisticated strategising.

"Gibbard–Satterthwaite means voting is pointless." The theorem says every reasonable voting system has some situation where a voter can benefit from misreporting. It does not say manipulation is common, easy or decisive in practice.

"Truthful mechanisms always need money." Money is one escape route, but there are others: restricted preferences (the median rule), private-good allocation (top trading cycles), one-sided strategyproofness (deferred acceptance) and serial dictatorship.

"Strategyproof and incentive compatible mean the same thing." Strategyproofness, or dominant-strategy incentive compatibility, is the strongest common form. Bayesian incentive compatibility is weaker: truth-telling is optimal if everyone else tells the truth and given beliefs about others' types.

"The second-price auction always produces the same revenue as a first-price auction." Under certain idealised assumptions, the revenue equivalence theorem says expected revenue is the same. In practice, with different bidder behaviour, risk attitudes or information, revenues can differ.

Frequently asked questions

What does "weakly dominant" mean? A strategy is weakly dominant if it does at least as well as every other strategy against every possible behaviour by others, and strictly better against at least some. In strategyproof mechanisms, truth-telling has this property, or at least is never worse than any alternative.

Why do auction designers care about strategyproofness? When bidders do not need to guess others' behaviour, bidding is simpler, outcomes are easier to predict and the auction tends to allocate items to those who value them most. Strategyproofness also reduces the advantage of well-resourced bidders who can afford to study competitors.

Is any real election system strategyproof? With only two candidates, majority rule is. With three or more candidates and unrestricted preferences, the Gibbard–Satterthwaite theorem says no deterministic non-dictatorial ranked system can be. Systems differ in how vulnerable they are, but none is immune.

What is the difference between strategyproofness and the revelation principle? The revelation principle says that any outcome achievable by some mechanism in equilibrium can also be achieved by a mechanism in which participants report their private information truthfully. Its dominant-strategy version says that if a mechanism has a dominant-strategy equilibrium, there is a strategyproof direct mechanism with the same outcome. This lets theorists focus on strategyproof direct mechanisms without loss of generality, given the solution concept.

Can a mechanism be strategyproof for some participants but not others? Yes. Deferred acceptance is strategyproof for the proposing side but not for the receiving side. This is why designers choose which side proposes carefully.

Do people actually tell the truth in strategyproof mechanisms? Often, but not always. Experiments with second-price auctions have found that many participants bid above or below their values. This has led to interest in mechanisms that are obviously strategyproof, such as ascending clock auctions, where the optimality of truthful behaviour is easier to see.

Why isn't the VCG mechanism used everywhere? Because it can produce low revenue, is not budget balanced, is vulnerable to collusion and false-name bids, and can be computationally intractable when there are many items. Real designs often borrow its logic while modifying it to address these weaknesses.

Summary

Strategyproofness is the property that honesty is always a best response. It frees participants from strategic guesswork, makes outcomes depend on true preferences and can protect less sophisticated participants from being outmanoeuvred. Vickrey showed it was possible in auctions; Clarke and Groves generalised it; Gibbard and Satterthwaite showed it is impossible for general voting; and later researchers mapped out the settings, such as single-peaked preferences, quasilinear money and certain matching markets, where it can be achieved.

The concept's limits are as instructive as its successes. Strategyproofness often conflicts with budget balance, revenue, stability and computational feasibility, and it does not guarantee that real people will behave as theory predicts. Designing good institutions is therefore usually a matter of deciding which properties matter most in a given setting, and strategyproofness is one of the most important properties on that list.

Sources

• Strategyproofness (Wikipedia)
• Gibbard–Satterthwaite theorem (Wikipedia)
• Vickrey–Clarke–Groves mechanism (Wikipedia)
• Endriss, Computational Social Choice lecture slides on strategic manipulation (University of Amsterdam), citing Gibbard 1973 and Satterthwaite 1975
• Moulin (1980). On strategy-proofness and single peakedness. Public Choice 35(4)
• Median voting rule (Wikipedia)
• Roth (1982). The Economics of Matching: Stability and Incentives. Mathematics of Operations Research 7(4)
• Dubins & Freedman (1981). Machiavelli and the Gale–Shapley Algorithm
• Gale–Shapley algorithm (Wikipedia)
• Abdulkadiroğlu, Pathak, Roth & Sönmez. Changing the Boston School Choice Mechanism (NBER w11965)