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:
There is no "dictator."
If every voter ranks X top, then X wins the election.
The voting system is deterministic, i.e. its decision about who wins is
based purely on the votes, not on random chance.
There are at least three candidates running.
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.
Remark:
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: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.)
Extension:
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.
Unfortunately, these voting methods are (in Gibbard's words)
unacceptable because they "leave too much to chance."
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:
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.
If every range voter scores X top, then X wins the election.
Check.
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.)
Range voting has no problems handling any number of candidates whether three, more,
or fewer. Check.
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:
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.
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:
What about if we consider situations with any number N
(e.g. possibly more than three) candidates?
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.")
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:
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.]
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.]
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 ballots)
in which
there are 4 or more candidates,
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),
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 (giving winners as a function of the votes) need to change to make it become a
dictatorship.
Let the probability (in the
random elections model)
be Pv
that voter v will be able to dishonestly alter
her vote in order to get an improved (for her) election-winner.
Then:
∑v Pv≥Cε²
for some absolute positive constant C.
In 2009 Forest W. Simmons invented the first class of voting system both:
Entirely evading
Gibbard-Satterthwaite's impossibility, i.e. "accomplishing the impossible," and
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.