By Warren D. Smith, June 2009
In a previous 3-part paper, I had proved various results of the form that "range voting" was a superior single-winner voting method (measured by "Bayesian Regret") to every rank-order voting method. E.g. this was shown for N=3 candidates, for any mixture of "honest" and "strategic" voters, under the RNEM ("random normal elections model") with V→∞ voters, and also for honest voters for N=4,5,...,31 candidates.
However, one criticism of those results was that they pertained only to voting systems based on strict rank-order ballots. What if equalities are permitted in the rank orderings? For example, an allowed vote in a 5-candidate election might then be "A>B=C>D=E." In internet voting-method discussion groups over the last 15 years, a consensus has arisen that permitting equalities is very important to allow good performance in the presence of strategic voters.
We shall now give some extremely simple arguments indicating range voting's superiority (with V→∞ voters, either all-honest or all-strategic) over every such voting method which satisfies
P1. Monotonicity: worsening the rank of X in a ballot (leaving the rest of the ballot unaltered) cannot increase X's winning chances; and improving the rank of X cannot decrease them.
P2. Respects Majority-Top: if X is ranked unique-top by a majority of the voters, then X must win.
P3. No "dictator" (voter who singlehandedly can always control the winner) exists.
P4. Ties and near-ties (in which a single vote can alter the winner) have likelihood approaching 0 when the number of voters is made very large; and (≥3)-way ties and near-ties have likelihood approaching 0 faster (i.e. approach 0 relative to the 2-way tie+near-tie likelihoods).
Of these properties, almost every voting method seriously proposed by mankind satisfies P3 – indeed satisfies the stronger demands of "anonymity" and "neutrality" (permuting the voters has no effect on the winner; permuting the candidates has no effect aside from same-permuting the winner). Also P3 is, strictly speaking, not really needed at all because it is implied by P2. We confess that really P4 is about the voting method and some underlying probabilistic model describing how the voters generate their votes. P4 is also usually satisfied automatically, so only properties P1 & P2 have much interest. Examples of voting methods satisfying all these properties (all these voting methods that we do not define here, are defined in Tideman's book):
We shall soon state the argument. Throughout we assume the number of voters is V→∞ and the number of candidates is some fixed integer N≥3. Our model of strategy will be (as is common in the literature) "hindsight-based." Specifically, we do the election with honest votes (each voter voting in isolation), then each voter is now granted full information about the results and is permitted (in isolation acting under the assumption the other votes will change in a randomized manner but are unlikely to change much) to alter her vote; and finally we consider the result of the modified election.
In a probabilistic model such as the RNEM, the probability that any voter regards any two candidates as having exactly-equal utility values, is zero. Therefore, honest voters will never use equal rankings. Therefore, our extension to permit equalities in rankings, has no effect, and the previous papers' results about range voting's superiority versus rank-order voting methods, remain in effect.
1. With high probability, your vote (in an election with a large number V of voters) is going to have no effect – you cannot change the winner since you cannot create or break a tie because the election is too far away from being a tie. In this case, how you vote is irrelevant.
2. In the unlikely event your vote can have an effect, it is most likely to be because you have a chance to create or break a tie between two candidates – call them A & B – the two "frontrunners." More precisely, you have an opportunity to make either win. (Without loss of generality we shall assume you prefer A over B.)
3. Much less likely still is the situation where your vote actually has the power to make one of three or more candidates win (you choose which). Due to P4 we shall neglect that as just too incredibly unlikely in the V→∞ limit.
4. If in range voting the two frontrunners are A & B, your strategically best vote is scoring A max, B min. Now your scores for the others are irrelevant if only A & B can win, but to help yourself maximally in the ultra-unlikely 3-way-tie case in (3), you'd want to (semi-honestly) score everybody you prefer over A, also max, everybody you hate worse than B, also min, and everybody you think lies between A & B, ordered in some non-dishonest manner (which we shall not specify any more precisely). This strategic vote then is "semi-honest," that is, never orders X>Y for any X,Y for which you honestly feel Y>X.
5. In a monotone rank-order voting method you cannot go wrong, i.e. cannot make your vote strategically suboptimal, by ranking A unique-top and B unique-bottom – both of which, in general, will be dishonest, but this is always strategically correct. [Proof of that by contradiction: if you like some other vote, then I will alter your vote by raising A to unique-top and dropping B to unique-bottom, and by monotonicity (P1) and the assumption (3) that only A or B can win, these alterations can only make the vote more strategic. Q.E.D.] How one should vote about the candidates other than A and B is, however, much more mysterious. For example, it could be that some magic ordering of the others does the job and gives A the win.
Remark: Voting "honestly" (or even merely "semi-honestly" where you sometimes dishonestly rank candidates equal but never opposite-order them) is known to be incorrect strategy for any deterministic rank-order voting method in our class. (In general. Of course in some elections for some voters, honesty is best strategy.) This is the "Gibbard-Satterthwaite theorem." This remark will not be needed for our argument, but nevertheless is illuminating and hence we shall illustrate it with several concrete examples (whose details will only be sketched; the king-chicken theorem is described and proven by Maurer 1980 and extended by me as described in that citation):
We shall not specify how our voters rank the others besides A and B (aside from pointing out that ranking A unique-top and B unique-bottom cannot sacrifice strategic optimality).
6. If all voters cast votes of the type in (5), then (in the absence of a perfect tie, which P4 says has likelihood→0) by P2 we know that A or B must win. Furthermore, all our voting methods will yield the same winner, namely the same winner as we get from strategic plurality voting. Hence in this sense, no voting method of this form improves over plurality voting (contrary to advertising!) – all have the same Bayesian regret – for voters of the strategic ilk in (5).
7. However, approval voters will approve one (but not both, if they want to be strategic) of {A,B} and then as we discussed in (4), it then, when all the voters act this way, becomes entirely possible that (contrary to pre-election expectation) somebody other than A and B will win. Strategic approval (and range) voting thus is inequivalent to strategic plurality voting, and indeed results in my previous papers indicate approval's superiority (measured by Bayesian Regret under the RNEM). To be a bit more general about it, we conclude:
THEOREM: In every probabilistic setting in which all-strategic approval voting yields a better Bayesian regret than all-strategic plurality voting of the form described in (5) above, it also is better than every other rank-order(equalities permitted) voting method satisfying properties P1-P4, assuming the 100%-strategic-voters in the rank-order-method all take advantage of the theorem that ranking A and B unique-top and unique-bottom, is always optimally strategic in a situation where your vote cannot hope to make the winner be anybody else.
In view of our previous papers' experience and also in view of range voting's superiority-results with either 100%-honest or 100%-strategic voters, it now seems plausible that claims also could be formulated arguing range is superior for any honest+strategic voter mixture. But I have no proof of that. Re that, the following mini-theorem perhaps also is of some interest: in the event the rank-order(equalities permitted) voters were to cast only "approval style" ballots (of form like A=B>C=D=E involving at most one ">") then every Condorcet voting method, the Borda count, and approval voting, all elect the same winner; but IRV's winner can differ. [For proof of this mini-theorem, see puzzle #113 on the RangeVoting.org puzzle page http://rangevoting.org/PuzzlePage.html.]
The "naive exaggeration strategy" of (in rank-order ballot methods) ranking one of the two frontrunners artificially top and the other artifically bottom, in fact seems to be what about 80-95% of the voters in Australia do (at least if "bottom" is weakened to "bottom or second-from-bottom in, say, a 7-choice field"). This is true even though the rank-order-ballot voting methods used in Australia (Instant Runoff Voting IRV for the single-winner House elections, and Hare-Droop reweighted STV for multiwinner Senate elections) are not monotonic – and even though with IRV, lowering a candidate B in a ballot never helps his rival A whom you ranked higher. We conclude from this that the naive exaggeration strategy is very attractive in real life – perhaps to an even greater extent than is logically justified.
Critics have asked me whether I considered it plausible that many voters would vote dishonestly even though the expected payoff for doing so, might be extremely small. My answer is "yes." I also comment that
Somewhat surprisingly, in all of the (≈10) studies of range voting in real life that I am aware of, have found remarkably high rates (e.g. ≥75%) of manifestly non-strategic voting, e.g. votes not maxing and minning the scores of all the candidates. A partial explanation for this is that after one maxes and mins the scores for the two frontrunners, the payoff for doing the same to the remaining N-2 candidates (as opposed to being honest about them) is usually far smaller in comparison. Another hypothesis would be that voters experience a certain amount of joy (i.e. utility payoff) merely from the act of voting honestly and feeling they are doing something socially useful. This psychological payoff is ultimately a consequence of Darwinian evolution on tribes. And (we speculate further) it is greater in voting systems permitting greater expressivity, i.e. greater opportunity for a voter to be honest. Range voting has greater expressivity than all common rival schemes. If this speculation is correct, then range voting will enjoy an additional advantage over those rival voting schemes, beyond that predictable by cold mathematics about inhuman "voting entities" alone.
Allan F. Gibbard: Manipulation of Schemes That Mix Voting with Chance, Econometrica 45,3 (1977) 665-681.
Ehud Friedgut, Gil Kalai, Noam Nisan: Elections can be manipulated often, 49th FOCS conference [Foundations of Computer Science 2008] 243-249.
S.B.Maurer: The king chicken theorems, Mathematics Magazine 53,2 (1980) 67-80. [Maurer's results are re-proven and extended in puzzle 26 at the RangeVoting.org puzzle page http://rangevoting.org/PuzzlePage.html.]
Warren D. Smith: The Best Rank-Order Voting System versus Range Voting, etc (3-part paper) papers #101, #102, #103 at http://www.math.temple.edu/~wds/homepage/works.html. One may also find a great deal of information about range voting and other voting systems at http://RangeVoting.org.
T.N.Tideman: Collective decisions and Voting, Ashgate 2006.
Douglas R. Woodall: Monotonicity of single seat preferential election rules, Discrete Applied Maths. 77,1 (1997) 81-98.