The Gibbard-Satterthwaite theorem about honest & strategic voting

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:

1. There is no "dictator."
2. If every voter ranks X top, then X wins the election.
3. The voting system is deterministic, i.e. its decision about who wins is based purely on the votes, not on random chance.
4. There are at least three candidates running.
5. Honest and strategic voting are the same thing, i.e. it never "pays for a voter to lie," i.e. (more precisely) there is no election situation in which a voter, by submitting a dishonest vote claiming A>B when really she does not agree that A is a better candidate than B, can make the election result come out better (from her point of view) than if she had voted honestly.

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):

Random-voter:

Pick a vote at random and do whatever it says (ignoring all other votes).

Random-pair:

Pick two candidates (call them A and B) at random. Eliminate all the other candidates (both from the election and from all rank-order ballots). Now elect whichever of A and B would have won a head-to-head election using those ballots.

Probabilistic mixture of the preceding two:

Based on a dice roll, use random-voter or random-pair.

Extension 2: Herve Moulin found a stronger version of this theorem for Condorcet-type voting systems.

Does Range Voting accomplish the impossible??

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:

1. There is no dictator, that is, there exists no single range voter who, no matter what the other voters say, always gets the winner he wants. Check.
2. If every range voter scores X top, then X wins the election. Check.
3. Range voting is deterministic, i.e. its decision about who wins is based purely on the votes, and not on random chance. Check. (Although we'd have to have some pre-determined method of breaking ties, such as alphabetically first tied candidate wins.)
4. Range voting has no problems handling any number of candidates whether three, more, or fewer. Check.
5. In range voting elections with 3-or-fewer candidates, it never pays to submit a dishonest vote claiming A>B when you really feel B≥A. PROOF: (using 0-99 scale) Score your favorite 99 and your most-hated 0. It should be obvious that doing those two things can never hurt you. Now, no matter what score you give the remaining candidate, it can never be above 99 or below 0. Q.E.D.

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:

1. What about if we consider situations with any number N (e.g. possibly more than three) candidates?
2. What about if we attempt (more finely than Gibbard & Satterthwaite) to distinguish between voter "honesty," voter "semi-honesty," and plain "lying"? That is, if a voter feels A>B, then voting A>B is honest, voting A=B is semi-honest, and voting A<B is lying. ( Also, if you feel A=B, then saying A>B is lying; our definition of "semi-honest" is if the vote you produce would be honest for a limit of candidates that obey your honest >,=,and < relations. A better name might have been "limit-honesty.")
3. What about if we consider "incomplete information scenarios" where the voter is not assumed to know everybody else's vote?

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:

1. Theorem (semi-honesty in range voting): In range voting, if a voter knows every other range vote, then, no matter how many candidates there are, there is always a strategically-best way for that voter to vote which is semi-honest. [Proof: trivial.]
2. Theorem (3-candidate range voting): In 3-candidate range voting elections, if a voter knows every other range vote (complete information) or knows less (incomplete information, such as probability estimates) then there is always a strategically-best way for that voter to vote which is semi-honest. [Proof: trivial.]
3. Theorem (impossibility theorem for voters with imperfect information): No deterministic single-winner voting system exists (based on either rank-order ballots, rank-order ballots with equalities permitted, or range-style ratings ballots) in which
   1. there are 4 or more candidates,
   2. the voting system is "reasonable" (i.e. in a certain specified set of election situations in which the number of voters of certain types is taken to infinity, certain specified winners must happen; for details see the paper),
   3. some semi-honest or honest vote must exist that is strategically optimal (in the sense of maximizing expected payoff).

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: ∑_v P_v≥Cε² for some absolute positive constant C.

News flash! Gibbard-Satterthwaite impossibility entirely circumvented!

In 2009 Forest W. Simmons invented the first class of voting system both:

1. Entirely evading Gibbard-Satterthwaite's impossibility, i.e. "accomplishing the impossible," and
2. Good enough as a voting system to be (perhaps) of practical interest.

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.

References

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.

Return to main page