[EM] Completion of Gibbard-Satterthwaite voting-honesty impossibility theorem (solves open problem)
Warren Smith
wds at math.temple.edu
Sat Jul 22 08:37:59 PDT 2006
COMPLETION OF THE GIBBARD-SATTERTHWAITE VOTING IMPOSSIBILITY THEOREM
----------Warren D. Smith---22 July 2006----------------------------
The Gibbard-Sattherthwaite theorem said, essentially, that, in
reasonable single-winner voting systems with rank-order ballots
(with equalities forbidden), "honest voting" and "strategic voting"
sadly are not the same thing.
More precisely: the only voting system based on strict-rank-order ballots in which
(a) voting honestly is always best (or co-equal best) strategy,
(b) unanimously top-ranked contenders get elected
(c) there are at least 3 candidates
is a "dictatorship" in which some particular voter (the "dictator")
gets whatever he wants regardless of the other votes.
(Review: http://www.math.temple.edu/~wds/homepage/works.html #79;
the present post now solves the top open problem posed there.)
Define "range voting" to be the following system:
1. Each voter gives to each candidate a real-number score in the interval [0,1].
2. The candidate with the highest average score wins. (Ties broken randomly.)
Define a "semi-honest vote" to be one in which the scores for the candidates
obey a set of <, >, and = relations which arise as a _limit_ of
the true relations. For example, if you truly feel A>B, then
a range vote which says A>B would be both honest and semi-honest, one which says A=B
would be dishonest but semi-honest, and A<B would be neither honest nor semi-honest.
For a second example, if you truly feel A=B, then every semi-honest vote says A=B.
But range voting evades the Gibbard-Sattherthwaite impossibility theorem in the following
two senses:
I. In any 3-candidate range-voting election situation (including ones in which you have
imperfect information about the other votes), there exists
a strategically-best range vote which happens to be semi-honest.
Proof: If in your view all candidates are equal, then you do not care what your
vote is, so cast a semi-honest vote. Otherwise:
It can never hurt you (i.e. never decrease the expected election utility)
to give your true-favorite(s) score 1.
Symmetrically, it also can never hurt you to give your truly-most-hated candidate(s) 0.
Then any vote with these properties is semi-honest. QED.
II. In any N-candidate range-voting election in which you have complete information
about every other vote, there always exists a semi-honest strategically-best range vote.
Proof: Let X be the greatest expected utility (in your view) of the winner
that (by choosing your vote correctly) you can achieve.
Then deliver the vote in which
all candidates better than or equal to X are 1,
and all candidates worse than X are 0. QED.
However, all the above facts left the following QUESTION open:
Does there exist a reasonable voting system in which a semi-honest vote
is always strategically best, even in election situations in which you have
imperfect information about the other votes?
We now settle that; the answer is "YES if there are 3 candidates (range voting),
but NO if there are 4 or more candidates." This result will even be valid
if some kinds of probabilistic voting systems are permitted, although the below proof
will simplify if the voting system is deterministic. More precisely:
A "voting system" inputs votes (which we demand be either [0,1]-range-style ballots, or
rank-order ballots with equalities permitted) and outputs the identity of a winner.
Consider the following (2N+2)-voter 4-candidate SITUATION
(we have written this for [0,1]-range-style ballots, but
if you prefer voting systems based on rank-order ballots with equalities permitted,
then please translate the votes below into the equivalent votes in that format):
#voters their vote
------- ------------
N voters: A=1, B=C=D=0
N voters: B=1, A=C=D=0
1 voter: B=1, A=C=1/2, D=0
1 voter: A=C=1, B=D=0
Definition: "Reasonable" voting systems are
(i) invariant under permutations of the candidate names (or more weakly we may merely demand that
the truths of the following properties be invariant), and
(ii) in the situation above (for any sufficiently large N) but with the last 2 votes
altered arbitrarily, it elects either A or B but never C or D -
or more weakly we may merely demand that in the N-->infinity limit, the probability of
electing C or D tend to 0. [A "unanimous 2-top" property]
(iii) in the situation above (for all sufficiently large N)
it elects A with probability > the probability of electing B.
(iv) in the situation above (for any sufficiently large N) but with the last vote
altered arbitrarily to a form
obeying 1 >= B >= A >= 0 and 0 <= C <= 1, 0 <= D <= 1,
it elects B with probability >= the probability of electing A.
(v) in the situation above (for any sufficiently large N) but with the last
vote altered arbitrarily to a form obeying
1 >= A >= B >= 1/2 >= C>=D >= 0
or obeying
1 >= C>=D >= 1/2 >= A >= B >= 0
or (IF we are considering rank-order ballots instead of range-voting-type ballots)
with the last vote altered to say either A>B>C>D or C>D>A>B
(or any of these with any >s replaced by =s),
it elects B with probability >= the probability of electing A.
(vi) in the situation above but with the last vote replaced by one of form
1 >= A > B > C > D >= 0 (or a limit form), altering that vote to 1 >= A > C > B > D >= 0
(or a limit form) by increasing the value of C and/or decreasing the value of B, holding
all else fixed, cannot increase the probability-ratio for B winning versus A.
(vii) in the situation above but with the last vote replaced by one of form
1 >= C > D > A > B >= 0 (or a limit form), altering that vote to 1 >= C > A > D > B >= 0
(or a limit form) by decreasing the value of D and/or increasing the value of A,
holding all else fixed, cannot increase the probability-ratio for B winnign versus A.
(viii) the _gap_ between the probability A wins in iii, and that probability in iv, v,
is at least some positive constant k.
Comment: an inequivalent different possible definition of "reasonable" could be to demand
that the voting system always elect a "Condorcet winner" when one exists.
But it is known already (some proofs originally arising from Kevin Venzke are
on the CRV website) that dishonest and not-semi-honest voting (which
indeed "betrays your favorite") always is uniquely strategically optimal in at
least some 3-candidate perfect information election scenario if the voting system
is based on rank-order ballots (with or without equalities permitted)
and always elects Condorcet winners.
Theorem:
In any reasonable voting system based on either [0,1]-range-style ballots, or
rank-order ballots with equalities permitted, there exists a 4-candidate
election scenario in which you have partial information about the other votes,
in which your only strategically-optimal votes are not semi-honest.
Proof:
Let your true candidate election utilities be
U_A=X+Y+Z, U_B=Y+Z, U_C=Z, U_D=0 where X, Y, and Z are positive constants.
Let the other votes be either
situation 1:
N voters: A=1, B=C=D=0
N voters: B=1, A=C=D=0
1 voter: B=1, A=C=1/2, D=0
or
situation 2:
N voters: C=1, A=B=D=0
N voters: D=1, A=B=C=0
1 voter: D=1, C=B=1/2, A=0
but you do not know which.
In that case, if you vote
(non-semi-honestly)
A=C=1, B=D=0
then in situation 1, you will cause A to win with probability>k+1/2,
and B and D to win with probability 0 (in the large-N limit); while in situation 2,
you will cause C to win with probability>k+1/2 (for some constant k>0)
and A and B to win with probability 0. (By reasonability i, ii, iii, viii.)
However, if you cast any semi-honest vote - the possibilities are
A>B>C>D
A=B>C>D
A>B=C>D
A>B>C=D
A=B=C>D
A>B=C=D
A=B>C=D
A=B=C=D
then by reasonability iv, v, _either_ in situation 1 you will cause
B to be elected with probability>=1/2 while C,D lose (costing expected utility>k*X),
or in situation 2 cause
D to be elected with probability>=1/2 while A,B lose (costing expected utility>k*Z)
but these losses will not be compensated by any gains in the other situation
due to reasonability vi and vii. (Note, we have lied slightly in the above
by saying 1/2+k and 1/2, but the truth is these are just two quantities near 1/2 separated
by a gap of at least k, and that is good enough.)
QED.
This theorem and proof still leaves open the possibility of having certain kinds of probabilistic
voting system in which semi-honest voting is always strategic.
Here is an interesting new one:
RANDOM-TRIPLET RANGE VOTING:
1. Each voter gives to each candidate a positive real-number score.
2. A triple of candidates (call them A,B,C) is selected randomly.
3. All voter-scores for all candidates other than A,B,C are ignored.
4. All range votes are rescaled by a linear transformation so the highest scorer among
A,B,C now gets score 1 and the lowest 0.
5. Using these rescaled range votes, the election winner is the member of {A,B,C}
with the greatest average score (break ties randomly).
Theorem:
In random-triplet range voting, voting semi-honestly is always best strategy.
Proof:
By continuity, it suffices to prove you will never want to vote
B>A if you truly feel A>B or A=B.
Suppose for a contradiction such misordering was strategically helpful.
Then it must help in some 3-candidate range-voting (with rescaling) election.
However, as a lemma, we can prove that in a
3-candidate range-voting (with rescaling) election, if you cast a vote
that is not semi-honest, then if the mis-ordered pair is adjacent in your
vote (such as B>A>C when honestly A>B>C or A=B>C or A=B=C)
you can always replace the vote by
one with that pair equal (A=B>C or A=B=C) without hurt; and if it is non-adjacent
(B>C>A when honestly A>C>B or A>C=B or A=C>B) then swapping the pair values
(swapping A,B) enver hurts your expected utility.
So any non-semi-honest N-candidate vote can always be altered to
make it nearer to semi-honesty in one of these two ways, without hurt,
and after a finite numbe rof such alterations we must reach semi-honesty.
QED.
Concluding Remark:
This all has shown senses in which
(1) range voting is superior to every rank-order ballot system, and
(2) no reasonable deterministic (or we even permit certain kinds of probabilistic)
voting system can do better than range voting in terms of inspiring voter honesty.
However, there are certain probabilistic voting systems (i.e. in which chance plays
a role in selecting the winner) which are superior both to range voting and to every
deterministic system, in the sense that honest (or semi-honest) voting is
always strategically optimal in those systems.
Random-triplet range voting is one such probabilistic voting system.
The other two I know of (found by Gibbard) are "do whatever a random voter wants"
and "use rank-order ballots to conduct a majority vote on a random candidate pair".
I conjecture there are no others besides these three (and probabilistic mixtures of them).
---Warren D Smith, 22 July 2006
More information about the Election-Methods
mailing list