Impossibility Results

Three theorems fence off three different ambitions, and all three are routinely misquoted by dropping a condition. Arrow (1951) says no rule aggregating individual preference orderings into a social ordering can satisfy unrestricted domain, social ordering, weak Pareto, independence of irrelevant alternatives and non-dictatorship once there are three or more alternatives (SEP, Arrow’s Theorem §3.2). Gibbard (1973) and Satterthwaite (1975) say that a social choice function on the unrestricted domain of strict rankings that is onto and strategyproof must be dictatorial when there are at least three outcomes (Reny 2001, Corollary; Nisan, AGT Thm 9.8). Myerson & Satterthwaite (1983) say that no bilateral-trade mechanism is simultaneously ex-post efficient, interim individually rational and Bayesian incentive compatible without an outside subsidy — provided both valuations have positive density on properly intersecting intervals (Myerson & Satterthwaite 1983, Corollary 1). Every italicised clause above is load-bearing, and this note’s main job is to show how load-bearing, by checking the theorems computationally rather than citing them: a complete backtracking enumeration over the space of social choice functions confirms that at 3 voters and 3 alternatives the onto strategyproof survivors are exactly the 3 dictatorships, that dropping “onto” leaves 57 further rules, and that dropping “at least 3 alternatives” leaves 15 non-dictatorial ones.

Where this sits

This is the P7 (mechanism design) fence-post note of Games and Strategic Systems in C MOC. It assumes the mechanism-design vocabulary — incentive compatibility, individual rationality, efficiency, budget balance — which is developed in Mechanism Design and Incentive Compatibility. It is the negative counterpart to The VCG Mechanism, which achieves dominant-strategy truthfulness with money and therefore lives outside Gibbard–Satterthwaite’s hypotheses; and to The Gale-Shapley Algorithm, which achieves one-sided strategyproofness on a restricted domain and therefore also escapes.

Mental Model — Three Fences Around Three Different Fields

The single most common error is treating these as one theorem. They are not: they quantify over different objects, and a construction that escapes one may sit squarely inside another.

Arrow is about preference aggregation. Its output is a social ranking of all alternatives. It is not, in the first instance, about voting or about strategy. A voting rule that outputs a single winner is not an Arrovian social welfare function at all, and “Arrow’s theorem proves that no voting system is fair” is a category error before it is a factual one.
Gibbard–Satterthwaite is about strategy in voting. Its output is a single winner, and its conclusion is about manipulability. It is the theorem that actually applies to elections.
Myerson–Satterthwaite is about trade with money and private values. It lives in a Bayesian world with transfers and quantitative valuations, none of which appear in the other two.

flowchart TB
    subgraph ORD["ORDINAL, NO MONEY"]
        A["<b>Arrow 1951</b><br/>input: profile of preference ORDERINGS<br/>output: a social ORDERING<br/>kills: U + SO + WP + IIA + non-dictatorship"]
        GS["<b>Gibbard 1973 / Satterthwaite 1975</b><br/>input: profile of strict RANKINGS<br/>output: a single WINNER<br/>kills: onto + strategyproof + non-dictatorship"]
        A -->|"GS is a corollary of Arrow<br/>(Nisan's route) or shares its proof<br/>(Reny's route)"| GS
    end
    subgraph CARD["CARDINAL, WITH MONEY"]
        MS["<b>Myerson-Satterthwaite 1983</b><br/>input: independent private VALUES<br/>output: trade decision + transfer<br/>kills: efficiency + IR + BIC + budget balance"]
    end
    ORD --> ESC["<b>escape routes</b>"]
    CARD --> ESC
    ESC --> E1["restrict the domain<br/>(single-peaked -> median voter)"]
    ESC --> E2["randomise<br/>(random dictatorship)"]
    ESC --> E3["approximate<br/>(give up exact optimality)"]
    ESC --> E4["relax budget balance<br/>(VCG, subsidies, brokers)"]

What it shows: the three theorems partitioned by what their inputs are made of — ordinal rankings versus cardinal money-denominated values — and the four families of escape route that all three share. The insight to take: the escapes are not clever tricks, they are the negations of specific hypotheses. Every deployed mechanism you will meet is sitting in one of those four boxes, and knowing which one tells you what it gave up.

Arrow’s Theorem, Stated Exactly

Fix a finite set of alternatives X and a finite set of people 1, …, n. Each person i has a weak ordering R_i of X — a binary relation that is connected (for all x, y: x R_i y or y R_i x or both) and transitive. “Weak” means ties are allowed, and a tie is read as indifference. A preference profile is the list ⟨R_1, …, R_n⟩. A social welfare function f assigns to each admissible profile a binary relation f⟨R_i⟩ on X. Write P_i for the strict part of R_i (so x P_i y means i genuinely prefers x, not merely weakly), and P for the strict part of the social relation (SEP §2).

The five conditions, in the canonical modern form:

	Condition	Statement	What it forbids
U	Unrestricted Domain	The domain of `f` includes every list of `n` weak orderings of `X`.	Assuming anything at all about what people might want.
SO	Social Ordering	For every admissible profile, `f⟨R_i⟩` is itself a weak ordering of `X` — transitive and connected.	Producing a cycle.
WP	Weak Pareto	If `x P_i y` for all `i`, then `x P y`.	Overruling unanimity.
D	Non-dictatorship	There is no `d` such that `x P_d y ⟹ x P y` for every profile and every pair.	One person’s strict preferences always winning.
I	Independence of Irrelevant Alternatives	If two profiles agree on everyone’s ranking of the pair `{x, y}`, then the social relations they produce also agree on `{x, y}`.	Letting a third alternative change the `x`-vs-`y` verdict.

Arrow’s Theorem. Suppose there are more than two alternatives. Then no social welfare function satisfies U, SO, WP, D and I simultaneously (SEP §3.2, which cites Arrow 1951 for the original proof and Geanakoplos 2005 among others for variants).

Three things about that statement are worth pausing on, because each is the site of a standard misquotation.

First, SO is a separate condition, and Arrow did not state it as one. He built the requirement into the definition of a social welfare function, arguing that the output must be an ordering if it is to “reflect rational choice-making” (Arrow 1951 [1963]: 19, quoted in SEP §4.2). Modern presentations pull it out as a condition precisely so that its consequences can be examined — and it is the condition that pairwise majority rule violates. Criticised by Buchanan for transferring a property of individual choice onto collective choice, Arrow’s second-edition rationale was path independence: an intransitive social relation makes the winner depend on the order in which you narrow the field. Charles Plott (1973) formalised this. Take the Condorcet profile ABC / BCA / CAB: majority rule gives A over B, B over C, and C over A. Start from the division {{A,B},{B,C}} and you end at {A}; start from {{A,C},{B,C}} and you end at {B} (SEP §4.2). The agenda-setter chooses the winner.

Second, “non-dictatorship” does not mean what its name says. An Arrovian dictator is merely someone whose strict preferences are invariably a subset of society’s strict preferences. That is a statement about correlation, not about power. SEP’s illustration is Zelig, the human chameleon who has no preferences of his own and adopts those of whoever is sitting nearest. On a three-person committee where Zelig always duplicates one other member, majority voting makes Zelig an Arrovian dictator — “It’s just that this one mad little fellow has a way of always ending up on the winning side” (SEP §4.4). Note that this example only works because the domain is restricted (Zelig’s copying constrains which profiles arise); it is U in combination with D that gives non-dictatorship its intended bite.

Third, and worst, there are at least three different conditions in circulation under the name “IIA”. Arrow’s own choice version quantifies over feasible sets S: if two profiles agree on S, the chosen set from S is the same. The pair version I in the table above is the simpler modern standard. And then there is the impostor:

I*: for all x, y and all profiles ⟨R_i⟩, ⟨R*_i⟩, if for all i (x R_i y iff x R*_i y), then (x f⟨R_i⟩ y iff x f⟨R*_i⟩ y).

I* looks nearly identical and is strictly stronger, because its antecedent is satisfied in cases where individual preferences over {x, y} are not the same in the two profiles — for instance when everyone is indifferent between T and S in one profile and everyone strictly prefers T to S in the other (SEP §4.5). A version of Arrow’s theorem using I* is a weaker, less interesting theorem, and I* is a condition many would reasonably reject: it forbids a rule that favours reform when everyone wants it and the status quo when everyone is indifferent. Stronger still is Strong Neutrality (SN), which demands consistency across pairs as well as across profiles, and which is what actually encodes welfarism — the doctrine that individual preferences are the only admissible basis for ranking social states. Arrow’s I does not imply welfarism; SN does.

Uncertain

Verify: the exact wording and numbering of Arrow’s original conditions in Social Choice and Individual Values (1951; 2nd ed. 1963). Reason: the primary text was not retrieved. Attempts at an Archive-It mirror and at course-page mirrors returned a JavaScript “Session Verification” interstitial and HTTP 404 respectively; this is a retrieval failure, not an extraction failure. Every quotation of Arrow above is taken second-hand from the SEP entry, which quotes page numbers from the 1963 edition. To resolve: read Arrow, Social Choice and Individual Values, 2nd ed., Wiley 1963, ch. III. Note that the SEP entry states explicitly that condition I “is not Arrow’s formulation” but a later simplification, so the canonical statement given here is deliberately the modern one. #uncertain

How the proof actually goes: the pivotal voter

Both Arrow and Gibbard–Satterthwaite are proved by the same five-step manoeuvre, due in this form to Geanakoplos and used by Reny (2001) to run the two proofs as parallel columns on the same page. The engine is a pivotal voter, located by a marching argument rather than assumed.

flowchart TB
    S0["<b>Step 1.</b> Start from the profile where every voter<br/>ranks a FIRST and b LAST.<br/>By weak Pareto, society strictly prefers a to b."]
    S1["<b>March.</b> Raise b one position at a time in voter 1's ranking,<br/>then voter 2's, then voter 3's...<br/>By IIA, society keeps a above b while b is below a for the mover."]
    S2["<b>The flip must happen.</b> Once b is top for everyone,<br/>weak Pareto forces society to rank b above a.<br/>So some voter n is PIVOTAL: society flips exactly when b passes a in n's list."]
    S3["<b>Step 2.</b> Move a to the bottom for voters i &lt; n<br/>and to second-last for voters i &gt; n.<br/>IIA says none of this changes the a-vs-b verdict."]
    S4["<b>Steps 3-5.</b> For any third alternative c, transport that configuration<br/>to an arbitrary profile without changing any individual's a-vs-c ranking.<br/>Conclude: whenever n ranks a above x, so does society."]
    S5["<b>Close.</b> n is a dictator for a. Since a was arbitrary, there is<br/>a dictator for every alternative - and they cannot be different people."]
    S0 --> S1 --> S2 --> S3 --> S4 --> S5
    NOTE["swap IIA for MONOTONICITY throughout<br/>and the identical argument proves<br/>Muller-Satterthwaite, hence Gibbard-Satterthwaite"]
    S5 -.-> NOTE

What it shows: the skeleton of Reny’s shared proof, with the pivotal-voter search as the load-bearing step. The insight to take: IIA is what freezes the social verdict during the march. Every step of the march is licensed by the fact that nobody’s a-vs-b ranking changed, so the social a-vs-b verdict may not change either. Take IIA away and the march has no traction — which is precisely why Borda counting, which violates IIA, escapes.

Verified: the theorem, by complete enumeration

Arrow’s theorem is usually presented as unverifiable by machine, because the space of social welfare functions is astronomically large. For 3 voters and 3 alternatives there are 6³ = 216 profiles of strict rankings and 6 possible strict social orders per profile, so there are 6²¹⁶ ≈ 10¹⁶⁸ candidate functions. Enumerating them is not merely slow; it is physically impossible.

But the conditions are constraints, and constraint propagation is exactly the tool for a search space defined by constraints rather than by generation. Encode f⟨·⟩ as one variable per profile with domain the six linear orders; impose weak Pareto as a unary constraint that prunes each variable’s domain directly; impose I by grouping profiles according to the column pattern of each alternative-pair and requiring every profile in a group to agree on that pair’s bit. Then run arc consistency to a fixed point and backtrack on whatever is left. The search is complete — it enumerates every satisfying assignment — and it never has to touch the 10¹⁶⁸.

=== complete enumeration of social WELFARE functions satisfying
    Unrestricted domain + Social Ordering + Weak Pareto + IIA ===
  n=2 m=2: profiles=4,    naive |SWF| = 2^4;    nodes=7   survivors=4   (2 dictatorships, 2 non-dictatorial)
  n=3 m=2: profiles=8,    naive |SWF| = 2^8;    nodes=127 survivors=64  (3 dictatorships, 61 non-dictatorial)
  n=2 m=3: profiles=36,   naive |SWF| = 6^36;   nodes=3   survivors=2   (2 dictatorships, 0 non-dictatorial)
  n=3 m=3: profiles=216,  naive |SWF| = 6^216;  nodes=5   survivors=3   (3 dictatorships, 0 non-dictatorial)
  n=4 m=3: profiles=1296, naive |SWF| = 6^1296; nodes=7   survivors=4   (4 dictatorships, 0 non-dictatorial)
  n=2 m=4: profiles=576,  naive |SWF| = 24^576; nodes=3   survivors=2   (2 dictatorships, 0 non-dictatorial)

Measured 2026-08-29 on python3 3.14.7. Read the m column as the number of alternatives. At m = 2 the conditions are satisfiable in bulk — with 3 voters there are 64 surviving aggregators of which 61 are non-dictatorial, majority rule among them. At m ≥ 3 the survivors collapse to exactly the n dictatorships, for every n and every m tested. The “more than two alternatives” hypothesis is not a technical convenience; it is where the theorem lives.

The node counts are the surprising part. At n = 3, m = 3 the complete search visits 5 nodes and hits zero dead ends. Arc consistency alone very nearly decides the problem: after propagating weak Pareto and I, almost every variable is already pinned. That is a computational restatement of what Geanakoplos’s proofs make combinatorial — the conditions are so tight that there is essentially nothing to search.

SO is the condition most often left out of informal statements (“no fair voting system exists”), so it is worth pricing. Drop it — let the social verdict be any tournament, cycles permitted — and I plus WP decouple the pairs completely: the verdict on each unordered pair becomes a function of that pair’s column alone, subject only to unanimity. The count is then exact rather than searched:

voters `n`	alternatives `m`	per-pair aggregators `2^(2ⁿ−2)`	total `U + WP + I` aggregators	profiles where majority rule cycles
3	3	64	`64³ = 262,144`	12 / 216 = 5.56 %
5	3	1,073,741,824	`≈ 1.24 × 10²⁷`	540 / 7,776 = 6.94 %
3	4	64	`64⁶ ≈ 6.87 × 10¹⁰`	2,352 / 13,824 = 17.01 %

The right-hand column is the price. Pairwise majority decision satisfies U, WP, I and non-dictatorship perfectly. It fails only SO — and it fails it on 5.6 % of random 3-voter 3-alternative profiles, rising to 17 % once there are four alternatives. So the honest summary of Arrow is not “majority rule is unfair”; it is “majority rule is fine except that 1 profile in 18 has no coherent answer, and the theorem says every repair costs one of the other four conditions.”

Gibbard–Satterthwaite, Stated Exactly

Now the output is a single winner. Let Λ be the set of strict linear orders on a set of alternatives A, and let f : Λ^N → A be a social choice function. Following Reny (2001) §2:

f is strategyproof if for every individual i, every profile L ∈ Λ^N, and every misreport L'_i ∈ Λ: if f(L'_i, L_{−i}) ≠ f(L), then f(L) is ranked above f(L'_i, L_{−i}) according to i’s true ranking L_i.
f is onto if every alternative in A is chosen at some profile.
f is dictatorial if there is an i such that f(L) = a if and only if a is at the top of i’s ranking L_i.

Gibbard–Satterthwaite Theorem. If |A| ≥ 3 and f : Λ^N → A is onto and strategyproof, then f is dictatorial (Reny 2001, Corollary; Nisan, AGT Theorem 9.8, whose phrasing adds the pointed remark “Note the requirement that f is onto, as otherwise the bound on the size of A has no bite”).

The proof route that makes the structure clearest goes through monotonicity. Nisan states the equivalence as Proposition 9.6: f is strategyproof if and only if it is monotone, where monotone means that if the winner changes from a to a' when voter i alone changes their vote, it must be because i swapped their preference between a and a'. Reny’s Proposition then does the rest of the work:

Proposition (Muller–Satterthwaite). If f is strategyproof and onto, then f is Pareto efficient and monotonic.

and the Muller–Satterthwaite theorem (Reny’s Theorem A) says Pareto efficiency plus monotonicity plus |A| ≥ 3 forces dictatorship. Reny’s contribution is that the same five-step argument, run in two parallel columns, proves Arrow’s theorem and this one, with “monotonicity” in the social-choice column playing exactly the role that “IIA” plays in the social-welfare column. His footnote makes the identification explicit: “whenever monotonicity is used in the proof of Theorem A, strategy-proofness would also have sufficed.”

flowchart LR
    SP["strategyproof<br/>(no profitable misreport)"] --> MONO["monotone<br/>(winner only changes when the<br/>deviator swaps those two)"]
    MONO --> SP
    SP --> PROP["Muller-Satterthwaite<br/>Proposition"]
    ONTO["onto<br/>(every alternative wins somewhere)"] --> PROP
    PROP --> PE["Pareto efficient"]
    PROP --> MONO2["monotone"]
    PE --> THMA["Reny Theorem A<br/>= Muller-Satterthwaite"]
    MONO2 --> THMA
    THREE["at least 3 alternatives"] --> THMA
    THMA --> DICT["DICTATORIAL"]
    ARROW["Reny Theorem B<br/>= Arrow, same 5 steps<br/>with IIA in place of monotonicity"] -.->|"identical logical<br/>underpinnings"| THMA

What it shows: the actual implication chain from the two hypotheses to the conclusion, with the strategyproof/monotone equivalence drawn as the two-way arrow it is. The insight to take: “onto” enters the proof only to manufacture Pareto efficiency. That is why dropping it is such a cheap escape — and why so many real mechanisms are quietly non-onto.

There is a third formulation in circulation, and it exposes yet another silently-assumed condition. SEP’s Social Choice Theory §3.5 states the theorem for social choice rules that output a set, and lists the hypotheses as universal domain, non-dictatorship, the range constraint (the range contains at least three alternatives), resoluteness (the rule always produces a unique winner), and strategy-proofness. Here “onto” has become “range constraint” — and resoluteness has been promoted to an explicit axiom, because a set-valued rule can dodge the theorem by returning ties. Someone quoting the Reny form at someone quoting the SEP form will talk past each other for an hour.

Verified: the theorem, by complete enumeration

This is the check the whole note is built around, because Gibbard–Satterthwaite is small enough to settle by machine and famous enough that settling it changes how you read it.

The naive space is worse than Arrow’s. For 3 voters and 3 alternatives there are 3! ³ = 216 profiles and 3 possible winners each, giving 3²¹⁶ ≈ 10¹⁰³ social choice functions. Direct enumeration is out. So the enumeration is done as a complete backtracking search with arc-consistency propagation over the strategyproofness constraints, which have a convenient bilateral form. For two profiles P and P' that differ only in voter i’s ranking (L_i versus L'_i), a pair of winners (a, b) = (f(P), f(P')) is admissible if and only if

a == b   OR   ( a is above b in L_i   AND   b is above a in L'_i )

— the first conjunct says i cannot gain by reporting L'_i when L_i is true, the second says the reverse. Precompute that relation as a bitmask table per ordered pair of rankings, propagate to a fixed point, branch on the minimum-remaining-values variable, and filter the complete solution set for ontoness at the end.

=== complete enumeration of strategyproof social CHOICE functions
    (unrestricted domain of strict rankings) ===
 n=2 m=2: profiles=    4  naive = 3^0 ... 2^4
    search: nodes=     11  dead ends=  0   0.000s
    strategyproof total =    6  ->  onto =  4, non-onto =  2
    onto survivors: 2 dictatorships + 2 NON-dictatorial
 n=3 m=2: profiles=    8  naive = 2^8
    search: nodes=     39  dead ends=  0   0.000s
    strategyproof total =   20  ->  onto = 18, non-onto =  2
    onto survivors: 3 dictatorships + 15 NON-dictatorial
 n=2 m=3: profiles=   36  naive = 3^36
    search: nodes=     32  dead ends=  0   0.001s
    strategyproof total =   17  ->  onto =  2, non-onto = 15
    onto survivors: EXACTLY the 2 dictatorships
 n=3 m=3: profiles=  216  naive = 3^216
    search: nodes=    118  dead ends=  0   0.016s
    strategyproof total =   60  ->  onto =  3, non-onto = 57
    onto survivors: EXACTLY the 3 dictatorships
 n=4 m=3: profiles= 1296  naive = 3^1296
    search: nodes=   1008  dead ends=  0   0.488s
    strategyproof total =  505  ->  onto =  4, non-onto = 501
    onto survivors: EXACTLY the 4 dictatorships
 n=2 m=4: profiles=  576  naive = 4^576
    search: nodes=     73  dead ends=  0   0.157s
    strategyproof total =   38  ->  onto =  2, non-onto = 36
    onto survivors: EXACTLY the 2 dictatorships
 n=3 m=4: profiles=13824  naive = 4^13824
    search: nodes=    251  dead ends=  0  14.642s
    strategyproof total =  127  ->  onto =  3, non-onto = 124
    onto survivors: EXACTLY the 3 dictatorships

The headline row is n=3, m=3: 216 profiles, 10¹⁰³ candidate functions, and the complete search terminates in 16 milliseconds having visited 118 nodes and found that the onto strategyproof functions are precisely voter 0’s dictatorship, voter 1’s, and voter 2’s. That is Gibbard–Satterthwaite, checked rather than cited.

Three further readings of the table are worth more than the headline.

1. Both hypotheses are separately necessary, and the table prices each. Delete |A| ≥ 3 — go to the m = 2 rows — and at 3 voters there are 18 onto strategyproof rules, 15 of them non-dictatorial. Simple majority is one of them; so is every rule of the form “alternative x wins unless at least k voters prefer y”. Delete “onto” instead and at n = 3, m = 3 you gain 57 further strategyproof functions, so ontoness is doing the heavy lifting: of the 60 strategyproof rules, 95 % are excluded by ontoness alone.

2. The non-onto survivors have an exact and pretty structure, and the counts cross-check each other. Every strategyproof rule turns out to be “pick a range R ⊆ A, then run an onto strategyproof rule on R”. Test the prediction. At n = 3, m = 4 the search reports 124 non-onto rules split as 4 constants, 108 with |range| = 2, and 12 with |range| = 3. Predicted: C(4,2) = 6 two-element ranges times the 18 onto strategyproof rules found at n=3, m=2, giving 6 × 18 = 108 ✓; and C(4,3) = 4 three-element ranges times the 3 dictatorships found at n=3, m=3, giving 4 × 3 = 12 ✓. Running the search at n = 4, m = 2 to close the loop returns 166 onto rules, matching the 498 / 3 = 166 demanded by the n=4, m=3 row’s range-2 count. Four independent numbers agreeing to the unit is strong evidence the search is not quietly wrong.

3. Zero dead ends, at every size. As with Arrow, arc consistency alone essentially decides the problem. Strategyproofness constraints propagate so aggressively that no branch ever has to be abandoned. If you implement this yourself and your search does backtrack, you have a bug.

Myerson–Satterthwaite, Stated Exactly

The third fence is in a different world: money, cardinal valuations, and Bayesian rather than dominant-strategy incentives.

Individual 1 (the seller) owns an indivisible object; individual 2 (the buyer) wants it. Their valuations Ṽ₁ and Ṽ₂ are independent random variables, Ṽᵢ distributed on an interval [aᵢ, bᵢ] with density fᵢ(·) that is continuous and positive on that interval, and cumulative Fᵢ(·). Both are risk-neutral with utility additively separable in money and the object (Myerson & Satterthwaite 1983 §2).

A direct mechanism is a pair of functions (p, x) where p(v₁, v₂) ∈ [0,1] is the probability the object transfers to the buyer and x(v₁, v₂) is the expected payment from buyer to seller. Note that x is a transfer between the two parties, so budget balance is built into the model’s shape rather than stated as an axiom — “no outside subsidy” is what budget balance means here. Then:

Bayesian incentive compatible (BIC): honest reporting is a Bayesian Nash equilibrium — each individual maximises expected utility by reporting truthfully given that the other reports truthfully. This is strictly weaker than dominant-strategy IC.
Individually rational (IR): each individual has non-negative expected gains from trade after learning their own valuation but before learning the other’s. This is interim IR. Myerson and Satterthwaite are explicit that they do not require ex-post IR.
Ex post efficient: p(v₁, v₂) = 1 if v₁ < v₂ and 0 if v₁ > v₂ — the object ends up with whoever values it more, always.

Corollary 1 (Myerson & Satterthwaite 1983). “If the seller’s valuation is distributed with positive probability density over the interval [a₁, b₁], and the buyer’s valuation is distributed with positive probability density over the interval [a₂, b₂], and if the interiors of these intervals have a nonempty intersection, then no incentive-compatible individually rational trading mechanism can be ex post efficient.”

The interval-overlap condition is not decoration, and the paper says so immediately: “It should be noted that our proofs have used the assumption that the valuations have positive density over their respective intervals. Without this assumption the corollary is untrue.” Their counterexample is worth memorising. Let [a₁, b₁] = [1, 4] and [a₂, b₂] = [0, 3] — properly intersecting intervals — but put all the probability mass at the endpoints:

Pr(Ṽ₁ = 1) = Pr(Ṽ₁ = 4) = ½ = Pr(Ṽ₂ = 0) = Pr(Ṽ₂ = 3)

Then the mechanism “sell at price 2 if both are willing, otherwise no trade” is incentive compatible, individually rational and ex post efficient. The impossibility evaporates. Smear any positive density across the intervals and it returns. So a fixed-price mechanism can be fully efficient when the type distribution is discrete and separated — which is exactly why “just post a price” works fine in some markets and burns surplus in others.

The quantitative version, checked with exact rational arithmetic

The theorem says efficiency is unattainable; the more useful question is by how much. For the symmetric uniform case Ṽ₁, Ṽ₂ ~ U[0,1], Myerson and Satterthwaite solve the constrained problem in §4 and find that the gains-maximising mechanism trades if and only if the buyer’s valuation exceeds the seller’s by at least ¼, arising from α = ⅓ in their family p^α. Their numbers were re-derived here with Python’s fractions.Fraction, so nothing below is a floating-point artefact:

first-best   E[(v_b − v_s)⁺]                     = 1/6   = 0.166667
second-best  E[(v_b − v_s)·1(v_b − v_s ≥ 1/4)]   = 9/64  = 0.140625   [paper: 9/64 ✓]
ratio second-best / first-best                   = 27/32 = 0.843750
minimum lump-sum outside subsidy ∫₀¹(1−t)t dt    = 1/6
Chatterjee–Samuelson: trade iff v_b − v_s ≥ (1/4 − 1/12)/(2/3) = 1/4    ✓
α = 1/3 gives threshold α/(1+α)                  = 1/4                  ✓

Walk the symbols. E[(v_b − v_s)⁺] is the expected surplus a fully efficient mechanism would realise: integrate (b − s) over the region where the buyer values it more. 1/6 is that first-best number. The second-best integral restricts the region to b − s ≥ ¼ and comes to 9/64. The unavoidable loss is 1/6 − 9/64 = 5/192 ≈ 2.6 % of the object’s expected value, or 1 − 27/32 = 15.6 % of the available gains from trade. That is the price of private information in the smallest possible market, and it is not small.

The third line is the escape hatch quantified. Myerson and Satterthwaite show the minimum outside subsidy that would restore ex-post efficiency is ∫_{a₂}^{b₁} (1 − F₂(t)) F₁(t) dt, which for the uniform case is ∫₀¹ (1−t)t dt = 1/6. Read that against the first line: the subsidy needed to buy full efficiency is exactly equal to the entire first-best surplus. A broker who wants an efficient bilateral trade must, in expectation, pay in as much as the trade is worth.

The last two lines close a loop the paper draws itself. Chatterjee and Samuelson had studied the split-the-difference double auction — both sides name a price, trade happens at the average if the buyer’s is higher — and found the linear equilibrium in which the seller bids ⅔v₁ + ¼ and the buyer bids ⅔v₂ + 1/12. Setting buyer-bid ≥ seller-bid gives v₂ − v₁ ≥ (¼ − 1/12)/(⅔) = ¼, verified exactly above. So this actual, simple, played-in-the-wild bargaining game attains the theoretical second-best exactly. As the paper puts it, its equilibrium “gives the highest expected total gains from trade among all equilibria of all bargaining games satisfying individual-rationality for this symmetric-uniform trading problem.” That is a rare and comforting result: the constrained optimum is not some exotic direct revelation device, it is haggling.

Uncertain

Verify: the extension of the 9/64 and 1/6 figures to asymmetric or non-uniform distributions. Reason: only the symmetric-uniform case was computed here, and the general formulas involve the virtual-valuation functions c₁(v₁, α) = v₁ + α F₁(v₁)/f₁(v₁) and c₂(v₂, α) = v₂ − α (1−F₂(v₂))/f₂(v₂), whose monotonicity is a hypothesis of the paper’s Theorem 2 and is not automatic. To resolve: recompute for, say, Ṽ₁ ~ U[0,1] and Ṽ₂ ~ U[½, 3/2] and check G(α) = 0 has a root in (0,1]. The exact-rational cross-check by midpoint Riemann sums converged slowly (N=80 gave 0.141777 against the exact 0.140625) because the second-best integrand has a discontinuity at the trade boundary — the grid check corroborates the closed form but does not by itself pin the fourth decimal. #uncertain

The Misquotation Catalogue

Every row below is a statement you will hear, an omitted hypothesis, and a concrete counter-example that the omission admits.

The claim as usually heard	Missing condition	What the omission admits
“Arrow proved no voting system is fair.”	Arrow is about social orderings, not winners; the theorem for voting is Gibbard–Satterthwaite.	Categorically the wrong theorem. Plurality is not an Arrovian social welfare function at all.
“Arrow proved majority rule doesn’t work.”	SO (transitive output).	Majority rule satisfies `U`, `WP`, `I`, `D`. It fails only `SO`, on a measured 5.56 % of 3-voter 3-alternative profiles.
“Arrow’s theorem applies to any 2+ alternatives.”	more than two alternatives (`\|X\| > 2`).	With two alternatives, majority rule satisfies all five. Measured: 61 of 64 survivors at `n=3, m=2` are non-dictatorial.
“Any rule where a third candidate can change the outcome violates IIA.”	The distinction between `I`, `I*`, `SN` and Arrow’s choice version.	`I` and `SN` are strictly stronger and often undesirable*; a theorem proved with them is weaker.
“Arrow’s non-dictatorship rules out undemocratic rules.”	It rules out correlation, not power.	Zelig the conformist is an Arrovian dictator under plain majority voting.
“Gibbard–Satterthwaite: every voting rule is manipulable.”	onto.	Measured at `n=3, m=3`: 57 non-onto strategyproof rules exist, including “always elect `a`” and majority over any 2-element range.
“Gibbard–Satterthwaite: every voting rule is manipulable.”	at least three outcomes (`\|A\| ≥ 3`).	Measured at `n=3, m=2`: 15 non-dictatorial onto strategyproof rules.
“Gibbard–Satterthwaite: every voting rule is manipulable.”	resoluteness (in the set-valued formulation).	Set-valued rules returning ties escape the SEP form of the theorem outright.
“Gibbard–Satterthwaite applies to auctions too.”	The domain is preferences without money.	The VCG Mechanism is onto, non-dictatorial and dominant-strategy truthful. Quasi-linear utility is a domain restriction.
“Myerson–Satterthwaite: efficient bargaining is impossible.”	positive density on properly intersecting interval supports.	With mass only at endpoints, “sell at price 2 if both willing” is efficient, IC and IR.
“Myerson–Satterthwaite: no strategyproof efficient trade.”	It is Bayesian IC and interim IR.	The theorem is stronger than the dominant-strategy version (Vickrey’s) precisely because BIC is weaker. Quoting it as a dominant-strategy result understates it.
“Myerson–Satterthwaite kills VCG.”	budget balance, i.e. no outside subsidy.	VCG is efficient, IR and dominant-strategy IC for bilateral trade — it just runs a deficit, of expected size `1/6` in the uniform case.

Escape Routes

1. Restrict the domain

The oldest and by far the most deployed escape. Nisan’s AGT opens Chapter 10 by calling Gibbard–Satterthwaite “a Procrustean bed that is escaped only by relaxing its assumptions,” and observes that “in most applications it is clearly unreasonable to assume that agents’ preferences are completely unrestricted.”

The canonical restriction is single-peakedness. Order the alternatives along a line — a tax rate, a thermostat setting, a left–right axis. A preference is single-peaked if it has a most-preferred point pᵢ and declines monotonically as you move away from it in either direction. SEP’s illustration is three bears choosing porridge temperature: Papa wants hot, Mama wants cold, Baby wants warm, and each likes options less the further they are from their bliss point (SEP §5.1).

On this domain both fences fall.

Black (1948): with an odd number of voters and a single-peaked profile, pairwise majority always produces an ordering, and its maximum is the bliss point of the median voter.
Moulin (1980): the median mechanism is strategyproof, and more generally the rule picking the k-th highest peak is strategyproof for every k ≤ n, “for precisely the same reasons: an agent can only move the k-th peak further from his own” (AGT §10.2.1). Moulin’s phantom voter device — pad the electorate with fixed fictitious peaks — both restores odd parity for Black’s theorem and characterises the full family.

The contrast with averaging is the part to internalise: AGT notes that the rule choosing the average of the peaks is manipulable by every agent whose peak differs from the average, who simply reports a more extreme peak. Median is strategyproof; mean is not. That single sentence is the practical content of the whole escape route.

Verified by complete enumeration on the single-peaked domain (only rankings single-peaked with respect to the natural order are admissible; there are 2^(m−1) of them):

voters	alternatives	admissible rankings	profiles	strategyproof rules	of which onto	onto and NON-dictatorial	dictatorships
3	3	4	64	186	129	126	3
4	3	4	256	7,747	7,246	7,242	4
3	4	8	512	1,199	571	567	4

and in every case the median-of-peaks rule was confirmed to be strategyproof, onto and non-dictatorial. Compare the unrestricted-domain rows above, where the same search returned exactly n survivors and all of them dictatorial. Restricting the domain from m! rankings to 2^(m−1) turns 3 admissible rules into 129.

Black’s theorem was checked on the same domain: across all 4³ = 64 single-peaked profiles at m = 3, and all 16³ = 4,096 at m = 5, the pairwise-majority relation was transitive in every single one, and the Condorcet winner equalled the median peak in every single one. Against the 5.56 % cycle rate on the unrestricted domain, that is the escape made visible.

This is also precisely the family that The Gale-Shapley Algorithm belongs to. Matching preferences are not arbitrary preferences over global outcomes; each agent cares only about their own partner. That restriction is what allows one-sided strategyproofness to coexist with a non-dictatorial, onto mechanism — see Proposer-Optimality and Strategic Truncation for how far it goes and exactly where it stops.

2. Randomise

Gibbard’s own 1977 sequel asked what happens when the mechanism may output a lottery over alternatives. The right notion of strategyproofness becomes stochastic dominance: reporting truthfully must yield a lottery that first-order stochastically dominates, under your true ranking, the lottery from any misreport — equivalently, for every k, the probability mass on your top k alternatives is maximised by honesty.

Random dictatorship — draw a voter uniformly and elect their top choice — passes. Verified exhaustively here:

rule	`n=3, m=3` SD-manipulations	`n=3, m=4` SD-manipulations	ex-post-inefficient support entries (`n=3, m=3`)
random dictatorship	0 / 3,240	0 / 953,856	0
single dictatorship	0 / 3,240	0 / 953,856	0
uniform lottery over all alternatives	0 / 3,240	0 / 953,856	138
Borda-proportional lottery	0 / 3,240	0 / 953,856	114

The two right-hand columns are the interesting ones and they reproduce Gibbard’s characterisation exactly. The uniform lottery and the Borda-proportional lottery are also stochastically-dominance-strategyproof — the Borda one because a voter’s own contribution to the score of their top-k set is maximised by ranking those k first, and the denominator is a constant. But both put positive probability on Pareto-dominated alternatives: 138 and 114 support entries respectively, out of 216 profiles. Only random dictatorship (and its degenerate case, plain dictatorship) is both SD-strategyproof and ex-post efficient. That is the content of Gibbard’s theorem, and the measurement is what makes it feel inevitable rather than arbitrary.

The catch is the one that keeps random dictatorship out of real elections: it is strategyproof and efficient but wildly unfair ex post. A 49 % faction wins outright 49 % of the time.

Uncertain

Verify: the exact statement of Gibbard (1977), “Manipulation of schemes that mix voting with chance,” Econometrica 45(3), including whether the characterisation requires ex-post efficiency, unanimity, or non-imposition, and whether it covers n = 2. Reason: retrieval failure — the JSTOR landing page (jstor.org/stable/1911681) returned HTTP 200 with a 3 KB JavaScript “Client Challenge” page, not the article; no open mirror was located, and the session’s web-search budget was exhausted before an alternative could be found. The characterisation as stated above is inferred from the measurements plus the framing in SEP §3.5 and AGT ch. 10, not read from Gibbard’s text. To resolve: read Gibbard 1977 §§3–5. #uncertain

3. Approximate

The computer-science escape, and the one with the most recent literature. If exact optimality is what forces dictatorship, ask instead for a strategyproof mechanism that is approximately optimal, and measure the ratio.

Procaccia and Tennenholtz’s facility location programme is the cleanest instance. Agents report points on a line; the mechanism places a facility; each agent’s cost is the distance to it. Minimising total cost is achieved exactly by the median, which is strategyproof — no approximation needed, because this is the single-peaked domain again. Minimising maximum cost is where it bites: the optimal rule (place at the midpoint of the extremes) is manipulable, and the best strategyproof deterministic mechanism achieves a 2-approximation, with randomisation improving the ratio (Procaccia & Tennenholtz, Approximate Mechanism Design without Money). The later approximation–variance work shows the randomised escapes trade approximation ratio against outcome variance, which is the honest way to state the cost.

A second, subtler version of “approximate” is computational hardness as a shield. Bartholdi, Tovey and Trick (1989) observed that for some voting rules, determining a profitable misreport is NP-hard; Harrison and McDaniel (2008) provide experimental evidence that the Kemeny rule is “behaviourally incentive-compatible” in this sense (SEP §3.5). Treat this route with suspicion. NP-hardness is worst-case; a manipulator does not need a general algorithm, only a heuristic that works on the instance in front of them.

4. Relax budget balance

The specific escape from Myerson–Satterthwaite, and the reason The VCG Mechanism exists. Myerson and Satterthwaite open by crediting Vickrey (1961) with the dominant-strategy version of the impossibility and d’Aspremont & Gérard-Varet (1979) with the observation that weakening dominant-strategy IC to Bayesian IC does allow efficient, budget-balanced mechanisms — the AGV or “expected externality” mechanism. The catch, which is why Myerson and Satterthwaite wrote the paper at all, is that AGV mechanisms “may give negative expected gains from trade to some individuals”: they satisfy efficiency, BIC and budget balance, and fail interim IR. An agent who already knows their own type may expect to do worse by participating than by walking away.

So the design space for bilateral trade is exactly a choose-three:

flowchart TB
    W["want all four for bilateral trade?<br/>Myerson-Satterthwaite Corollary 1 says NO<br/>(given overlapping positive-density supports)"]
    W --> A["give up BUDGET BALANCE<br/>-> VCG: efficient, IR, dominant-strategy IC<br/>cost: expected deficit 1/6 (uniform case)"]
    W --> B["give up INDIVIDUAL RATIONALITY<br/>-> AGV / d'Aspremont-Gerard-Varet:<br/>efficient, BIC, budget balanced<br/>cost: some types prefer not to participate"]
    W --> C["give up EFFICIENCY<br/>-> Chatterjee-Samuelson double auction:<br/>IR, BIC, budget balanced<br/>cost: 9/64 of 1/6 = 84.4% of available surplus"]
    W --> D["give up the DENSITY hypothesis<br/>-> fixed-price mechanism on discrete types<br/>all four hold; requires separated supports"]

What it shows: the four-way choose-three forced by Corollary 1, each branch labelled with the mechanism that takes it and the measured price. The insight to take: there is no default. Deployed markets differ mainly in which of these four they chose, usually without anyone writing it down.

Failure Modes and Gotchas

Quoting Arrow at a voting rule. The most common failure, and it is a type error. If your object outputs a winner rather than a ranking, the theorem you want is Gibbard–Satterthwaite. If your object outputs a ranking, Arrow applies — but then ask whether you actually need SO, because that is usually the condition your application does not care about.

Assuming “onto” is free. It is the first thing a real system violates, usually by accident. A voting rule whose implementation can never return certain candidates — because of a ballot-access filter, a quorum threshold, a default, or a tie-break that structurally favours the incumbent — is not onto, and Gibbard–Satterthwaite says nothing about it. This is a live source of confusion in system design: a rate limiter with a hard-coded fallback tier, or a scheduler that can never select a class of tasks, is a non-onto social choice function, and its strategyproofness is an open question rather than a settled impossibility. See Rate Limiting as a Mechanism.

Confusing dominant-strategy and Bayesian incentive compatibility. Myerson–Satterthwaite is a Bayesian result, which makes it stronger than the dominant-strategy version. People routinely quote it as if it were weaker (“well, we only need Bayes-Nash”), which gets the implication backwards. Conversely, escaping Gibbard–Satterthwaite by moving to Bayes-Nash is a genuine relaxation — see Incentive Compatibility for the two notions side by side.

Treating the single-peaked escape as automatic. Single-peakedness is a property of the profile, not of the alternatives, and it must hold with respect to one common ordering shared by everyone. A profile in which each voter is single-peaked with respect to their own private axis is not single-peaked, and the median mechanism is not strategyproof on it. Note also the parity trap: with an even number of voters, single-peakedness alone does not guarantee SO. SEP gives the two-voter profile CAB / BCA, which is single-peaked with respect to the order B < C < A and still yields a majority relation violating transitivity (SEP §5.1). Moulin’s phantom voters exist to fix exactly this.

Believing NP-hardness protects you. A hardness result about the manipulation problem in general says nothing about the instances you will actually face. Worst-case complexity is a poor security model; treat computational barriers as speed bumps, not fences.

Implementing the verification with a naive enumeration. If you try to write the Gibbard–Satterthwaite check as a loop over all 3²¹⁶ functions, you will conclude the theorem is uncheckable. The search must be constraint-driven. And if your constraint search reports dead ends at n=3, m=3, the propagation is incomplete — the measured dead-end count is zero at every size tested.

Alternatives and When to Choose Them

If you need…	Take this route	Give up	Real example
Strategyproof choice among ≥3 outcomes, no money	Restrict the domain (single-peaked / matching)	Generality of preferences	Median-voter mechanisms; The Gale-Shapley Algorithm; Top Trading Cycles
Strategyproof and efficient, money available	Charge externalities	Budget balance; simplicity	The VCG Mechanism — and read Why VCG Is Rare in Practice first
Strategyproof, ≥3 outcomes, no domain restriction	Randomise	Ex-post fairness	Random dictatorship; lottery-based school assignment
Strategyproof, near-optimal, no money	Approximate	Exact optimality (a measured ratio, e.g. 2× for max-cost facility location)	Approximate mechanism design; Approximate and Simple Mechanisms
Efficient bilateral trade	Subsidise	Budget balance	Broker-subsidised markets; a market maker eating the spread
Budget-balanced efficient trade	Use AGV	Interim IR	Rarely deployed; participation cannot be made voluntary
Budget-balanced, IR, voluntary trade	Accept the second best	15.6 % of the gains from trade	The split-the-difference double auction
Only two outcomes	Take majority rule	Nothing — all five Arrow conditions hold	Referenda; binary consensus, see Consensus as a Coordination Game

The row that matters most in practice is the first. Almost every strategyproof mechanism that actually ships is a domain restriction in disguise, and the restriction is usually so natural that nobody names it. School choice works because students care only about their own school. Auctions work because bidders have quasi-linear utility. Scheduling works because processes care only about their own share. Each is a hypothesis of a theorem that would otherwise forbid the thing being built.

Production Notes

The NRMP is the flagship domain-restriction deployment. The National Resident Matching Program clears roughly 20,000–25,000 applicants a year through a deferred-acceptance mechanism that is strategyproof for applicants — impossible under Gibbard–Satterthwaite’s hypotheses, entirely possible under matching preferences. The measured strategic exposure is tiny: Roth & Peranson’s upper bound on applicants who could profit from misreporting ran to 11–22 per year out of more than 20,000. The full story, including why the other side is not protected, is in Hospital-Residents and the NRMP and Proposer-Optimality and Strategic Truncation.

Ad auctions are a live instance of the choose-three. The generalised second-price auction that funds search advertising is not truthful, despite the name, and the industry ran it anyway for years — choosing simplicity and revenue over incentive compatibility rather than choosing VCG. See Ad Auctions and GSP and Why VCG Is Rare in Practice.

Ranked-choice voting debates are Arrow arguments conducted badly. Nearly every public argument about instant-runoff, approval or Borda voting is a dispute over which of Arrow’s conditions to sacrifice, conducted by people who have not noticed that is what they are doing. Borda counting violates I — SEP walks the four-candidate profile where moving B from second to last on one ballot flips the social ranking of A and B, and notes that this same slack is what makes Borda manipulable (SEP §5.2). Iain McLean’s blunt summary is worth keeping: “Take out [I] and you have gross manipulability.”

Bilateral-trade impossibility explains market makers. Any exchange that hopes to clear every mutually beneficial trade must, per Corollary 1, be subsidised — and the subsidy is not marginal. In the symmetric-uniform case it equals the entire first-best surplus. Real exchanges instead accept the second best and capture the difference: price-time priority in Stock Exchange Order Matching System Design is a budget-balanced, IR, incentive-imperfect mechanism, which is exactly the Chatterjee–Samuelson branch of the diagram above.

Deployment checklist. Before claiming a mechanism is strategyproof, answer four questions in writing: (1) is it onto? (2) how many outcomes are there really — is it secretly binary? (3) what is the domain, and is the restriction one you can enforce or merely one you hope holds? (4) is the claim dominant-strategy or Bayes-Nash, and under whose prior? A strategyproofness claim that does not answer all four is not a claim.

vault

Explorer

Impossibility Results

Impossibility Results

Mental Model — Three Fences Around Three Different Fields

Arrow’s Theorem, Stated Exactly

How the proof actually goes: the pivotal voter

Verified: the theorem, by complete enumeration

Gibbard–Satterthwaite, Stated Exactly

Verified: the theorem, by complete enumeration

Myerson–Satterthwaite, Stated Exactly

The quantitative version, checked with exact rational arithmetic

The Misquotation Catalogue

Escape Routes

1. Restrict the domain

2. Randomise

3. Approximate

4. Relax budget balance

Failure Modes and Gotchas

Alternatives and When to Choose Them

Production Notes

See Also

Graph View

Table of Contents

Backlinks

vault

Explorer

Impossibility Results

Impossibility Results

Mental Model — Three Fences Around Three Different Fields

Arrow’s Theorem, Stated Exactly

How the proof actually goes: the pivotal voter

Verified: the theorem, by complete enumeration

Verified: what dropping Social Ordering buys

Gibbard–Satterthwaite, Stated Exactly

Verified: the theorem, by complete enumeration

Myerson–Satterthwaite, Stated Exactly

The quantitative version, checked with exact rational arithmetic

The Misquotation Catalogue

Escape Routes

1. Restrict the domain

2. Randomise

3. Approximate

4. Relax budget balance

Failure Modes and Gotchas

Alternatives and When to Choose Them

Production Notes

See Also

Graph View

Table of Contents

Backlinks