This theorem, first proven in the mid-1970s (and re-proven in slicker ways many times since then) is probably the most famous and important theorem in all of voting theory (although, unfortunately, it was the less-important Arrow's theorem that got the Nobel prize).
It states that no single-winner voting method exists (in which the votes are rank-order ballots) satisfying all of the following short list of conditions:
In other words: In every "reasonable" rank-order voting system, there are situations in which lying pays.
Remark 1: If there are only two candidates, then many voting systems satisfy all the (other) GS criteria. The life of a voting-system designer only gets tough when there are ≥3 candidates.
Remark 2: Here is a helpful election example illustrating how dishonest voting pays. (It alone is good enough to prove the GS theorem for most of the voting systems humankind has seriously proposed, although not good enough to prove it for all possible voting systems.)
Remark 3: In the 3-candidate case, this theorem can be equivalently reworded: "In a deterministic nondictatorial rankorder-ballot voting system that always elects unanimous-top winners, there always is an election situation in which you, by honestly voting A>B>C (as opposed to some dishonest vote), cause A to stop winning or C to start winning."
Extension 1: Furthermore, even if we allow nondeterministic voting methods in which chance plays a role, then the Gibbard-Satterthwaite theorem remains true except for this list of voting methods (which are the only probabilistic rank-order voting methods satisfying all the GS criteria):
Or are they? In 2011, David R. MacIver pointed out that random-voter, in addition to inspiring honest voting, also is one of the few (only?) single-winner voting methods which yields proportional representation. E.g, with 70% honestly-Republican voters and 30% Democrats, random-voter will elect (up to random noise) 70% Republican and 30% Democratic winners. (Meanwhile, almost every other voting method would elect 100% Republican winners.)
Still: it seems very bothering that, say, some Republican with 20 years experience, who's done a great job, and gets 70% support, would just get randomly kicked out by a dice roll with his career in tatters. Past performance? Largely irrelevant under the random-voter system. There are deterministic proportional representation systems which (a) assure proportional representation and (b) also take into account candidate quality. They seem (subjectively) to be better than random-voter. For example, consider RRV. The known systems with this property all are multiwinner election systems and all are considerably more complicated than random-voter.
Extension 2: Herve Moulin found a stronger version of this theorem for Condorcet-type voting systems.
Wait a minute. Doesn't Range voting (in the ≤3-candidate case) satisfy all GS criteria, accomplishing the "impossible"?! Huh? Let's check that in slow-mo:
How can this be? The explanation is simple. The Gibbard-Satterthwaite theorem only applies to rank-order-ballot voting systems. (A fact that mentioners of this theorem in the popular press, generally forget to mention, thus creating a false impression in the public mind of the "overpowering and final" nature of this theorem.)
Range voting does not use that kind of ballot.
So range voting is superior to every voting system based on rank-order ballots when it comes to encouraging voter honesty in 3-candidate elections.
To repeat ourselves: I.e. no matter what dishonestly-ordered range-vote you invent in a 3-candidate election, there is a not-dishonest vote that would have been at least as good for you (and less stupid!). In contrast, with instant runoff, Condorcet, or Borda voting, (or, in fact, with any rank-order voting system at all!) there are 3-candidate elections in which the only way for you (a voter) to improve the election result, is to misorder. No honestly-ordered vote whatever, will do the job; only misordering will. That is a way Range Voting is superior to those other voting systems. With range voting, no dishonesty-forcing 3-candidate election situation exists. With the other systems, they do exist.
But now, some obvious questions suggest themselves:
Warren D. Smith in 2006 (paper #97 here) was able to extend Gibbard & Satterthwaite's work to answer those questions. Here are Smith's results:
I.e. in range voting with ≥4 candidates it can occasionally pay for a voter to lie without even being semi-honest (in incomplete information scenarios), but that, while sad, is not a defect in the design of range voting, since it was impossible for any reasonable voting system to do better.
Also in another even-more-recent paper (2008) by Friedgut, Kalai, and Nisan, they give a quantitative version of the Gibbard-Satterthwaite theorem. They prove:
Theorem:
Let E be a neutral (meaning invariant under permuting
the names of the candidates)
rank-order-ballot voting system for 3-candidate elections.
Suppose E is at least "ε-far from being a dictatorship,"
meaning at least ε>0 fraction of the winners, in the giant table
defining E (stating the winners for each vote-configuration)
need to change to make it become a
dictatorship.
Let the probability (in the
random elections model)
be P_{v}
that voter v will be able to dishonestly alter
her vote in order to get an improved (for her) election-winner.
Then:
In 2009 Forest W. Simmons invented the first class of voting system both:
One member of Simmons's class, called double range voting (invented by Warren D. Smith) is particularly interesting. Both are described (in draft form) in this puzzle-answer.
Allan F. Gibbard: Manipulation of voting schemes: a general result,
Econometrica 41,4 (1973) 388-410.
Allan F. Gibbard:
Manipulation of Schemes That Mix Voting with Chance,
Econometrica 45,3 (1977) 665-681.
Mark Satterthwaite: Strategyproofness and Arrow's conditions,
Journal of Economic Theory 10 (1975) 187-217.
Ehud Friedgut, Gil Kalai, Noam Nisan:
Elections can be manipulated often,
(49th FOCS conference [Foundations of Computer Science] 2008) 243-249.
Later expanded journal version (with Nathan Keller as additional author)
A Quantitative Version of the Gibbard-Satterthwaite
theorem for Three Alternatives,
SIAM Journal of Computation 40,3 (2011) 934-952.