Gibbard–Satterthwaite Theorem

With at least three alternatives and unrestricted strict ordinal preferences, every deterministic onto single-winner rule that makes truthful reporting a dominant strategy is dictatorial.

Version

v2 · 2026-09-19 · History

Domain-specific #

1933

Domain group

Formal Sciences

Origin domain

Mathematics

Subdomain

Game Theory → Mathematics

Aliases

Gibbard-Satterthwaite theorem

Core Idea

The Gibbard–Satterthwaite theorem identifies a structural limit on deterministic collective choice. Let \(A\) be a set of at least three alternatives, let each voter be permitted any strict ordering of \(A\), and let a resolute social choice function \(f\) map every preference profile to one alternative. If \(f\) is onto and truthful reporting is a dominant strategy for every voter, then \(f\) is dictatorial: there is one fixed voter whose top-ranked alternative is always selected.

Equivalently, any onto, deterministic, single-winner, non-dictatorial rule on the unrestricted strict-order domain has at least one profile at which some voter can report a false ordering and obtain an outcome that voter strictly prefers according to the voter's true ordering.

How would you explain it like I'm…

Boss or Fibbing Chance

Say a class lines up three or more snacks in order of how much they like them, and a rule picks one winner snack. If no single kid is the boss and any snack could win, then there will be at least one time when some kid could fib about their order and get a snack they like better. It doesn't mean fibbing always works, just that a chance like that exists somewhere.

Every Fair Vote Can Be Gamed

Suppose voters each rank three or more choices from favorite to least favorite, and a rule always picks exactly one winner. Suppose also that every choice can win in some situation. The Gibbard–Satterthwaite theorem says that if no single voter always gets their way, then somewhere there's a situation where a voter could lie about their ranking and get a result they truly like more. It doesn't say every election can be gamed, or that voters will know how to do it.

Strategy-Proof Means Dictatorship

The Gibbard–Satterthwaite Theorem covers single-winner voting rules where each voter may submit any strict ranking of at least three alternatives. The rule is deterministic, and every alternative can win for some set of ballots. If being honest is always a voter's best strategy whatever the others do, the rule must be dictatorial: one fixed voter's top choice always wins. So every non-dictatorial rule of this kind is manipulable. Somewhere there is a profile of ballots where a voter gains by misreporting. The theorem is only about existence. It doesn't claim every situation is manipulable, that voters know how to lie profitably, or that strategic voting always changes the winner.

 

Let A be a set of at least three alternatives, let each voter report any strict ordering of A, and let a resolute social choice function f assign one alternative to every preference profile. The Gibbard–Satterthwaite theorem states that if f is onto (every alternative is selected at some profile) and truthful reporting is a dominant strategy for every voter (f is strategy-proof), then f is dictatorial. Dictatorial means there is one fixed voter whose top-ranked alternative is always chosen. The contrapositive is the usual reading: every onto, deterministic, single-winner, non-dictatorial rule on the unrestricted strict-order domain is manipulable. Manipulable means there exists at least one profile where some voter, by submitting a false ordering, obtains an outcome they strictly prefer under their true ordering. This is an existence claim only. It does not say every profile is manipulable, that voters can identify the profitable misreport, or that strategic voting always changes the winner.

Scope of Application

The theorem governs deterministic ordinal voting and allocation rules that select one outcome from at least three attainable alternatives on an unrestricted preference domain. It is foundational in social choice, voting theory, and mechanism design because it converts a design aspiration—universal truthful revelation without dictatorship—into a proved impossibility.

Its assumptions define the main escape routes. Restricting preferences can restore strategy-proof non-dictatorial rules; on single-peaked domains, median-type rules are the canonical example. Allowing money and cardinal information leads to transfer-based mechanism design rather than contradicting the theorem. Randomization changes the outcome space to lotteries and invokes Gibbard's later random-mechanism results.

Clarity

The theorem prevents vague claims that “all voting systems are manipulable.” The accurate diagnostic is conditional. Ask whether the rule is deterministic, resolute, onto at least three alternatives, defined on all strict ordinal profiles, non-dictatorial, and evaluated by dominant-strategy truthfulness. If every answer is yes, a profitable manipulation profile exists.

Manages Complexity

Without the theorem, designers might search indefinitely across scoring rules, elimination procedures, pairwise methods, and tie-breaking schemes for a universally strategy-proof non-dictatorial rule. Gibbard–Satterthwaite closes that search region at once. The remaining design problem is to choose an escape route and assess its cost: restrict preferences, reduce range, randomize, tolerate manipulation, accept dictatorship, add transfers or richer information, or weaken dominant-strategy truthfulness.

Abstract Reasoning

The theorem licenses a proof-by-assumption audit. If a deterministic onto rule with at least three alternatives is claimed both non-dictatorial and strategy-proof on unrestricted strict rankings, at least one assertion must be false. The appropriate response is not another simulation but a formal witness: a manipulation profile, a dictator, a restricted domain, or a reduced range.

Knowledge Transfer

The theorem's roles transfer within collective-choice settings: alternatives can be candidates, policies, facility locations, schedules, public projects, or non-monetary allocations. Voters become agents, ballots become type reports, and the selected winner becomes the social outcome. The same dominant-strategy and dictatorship tests apply when the outcome rule depends only on reported ordinal rankings.

Transfer outside that setting must retain the exact information and incentive structure. A recommender that predicts rather than chooses, an auction with payments and cardinal valuations, or an interactive bargaining protocol is not automatically governed by Gibbard–Satterthwaite.

Relationships to Other Abstractions

Current abstraction Gibbard–Satterthwaite Theorem Domain-specific

Parents (1) — outgoing typed relations

• Gibbard–Satterthwaite Theorem is a kind of Axiomatic Incompatibility Prime

  Gibbard–Satterthwaite is a strict domain-specific specialization of Axiomatic Incompatibility: it fixes the design domain and proves that unrestricted ordinal input, three-plus attainable outcomes, resoluteness, non-dictatorship, and.

Hierarchy path (1) — routes to 1 parentless root

• Gibbard–Satterthwaite Theorem → is a kind of Axiomatic Incompatibility

Neighborhood in Abstraction Space

Gibbard–Satterthwaite Theorem sits in a sparse region of the domain-specific corpus (91^st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

• Arrow's Impossibility Theorem — 0.80
• Transversal (Combinatorics) — 0.80
• Maharam Algebra — 0.79
• Condorcet's Jury Theorem — 0.79
• Compact element — 0.79

Computed from structural-signature embeddings · 2026-10-25