Gibbard–Satterthwaite Theorem

Definition

Gibbard–Satterthwaite (1973, 1975)

Let $C$ contain at least three alternatives and let $n\ge 1$ be the number of voters. Every deterministic single-winner voting rule

$$f:\mathcal{L}(C{)}^n⟶C$$

defined on all profiles of complete, strict preference rankings satisfies

$$\underset{\text{every alternative can win}}{\underbrace{f\text{ is surjective}}}\wedge \underset{\text{no voter benefits by lying}}{\underbrace{f\text{ is non-manipulable}}}⟹f\text{ is dictatorial}.$$

Thus no such rule can be simultaneously surjective, non-dictatorial and non-manipulable. Single-winner output supplies resoluteness; non-manipulability is also called strategy-proofness. The unrestricted ranking domain and the requirement $|C|\ge 3$ are essential assumptions.