Range voting strategy experiments – honesty isn't a bad strategy

By Warren D. Smith, inspired by Kevin Venzke. Skip to conclusions.

We report on computer simulations to measure the expected utility (above that got by not voting at all) of various voting strategies in zero-info range elections ([0,1]-continuum range voting).

(Other strategy experiments, different models than here, include 3-candidate Range-2 and Strat-Hon voter mix and Victimization.)

The model: One specific voter has sincere ratings in [0,1] for each of C candidates. (The sincere ratings were randomly and independently determined uniform random reals in [0,1].) There are V other voters, each of whom submits an independent random-uniform score in [0,1] as her vote for each candidate. These voting strategies are tested:

1. Sincere. This voter rates the candidates sincerely even if this means she doesn't use the top or bottom ratings.
2. Plurality. Voter awards the maximum range vote to the best candidate (in her view) and min to all others.
3. Scaled sincerity. Voter linearly transforms utilities to make best have rescaled utility 1, worst 0, and rest linearly interpolated, then uses that as her vote.
4. "Acceptables" strategy. The voter gives max to every candidate worth 0.5 or more, and min to the others. (This can mean that the voter gives a 1 to every candidate, or a 0 to every candidate.)
5. Mean-based thresholding. The voter gives max to every candidate at least as good as the average value of all candidates, and gives min to the others.
6. Bisector-based thresholding. The voter gives max to every candidate at least as good as the average value of the two extreme candidates, and gives min to the others.
7. Maxing+sincerity: All scores sincere except the best candidate gets 1 and the worst 0.
8. Top-two: Give max score to the best two candidates, min to everybody else.
9. Bisect penultimates: The voter gives max to every candidate at least as good as the average value of the two "penultimate" (2nd best and 2nd worst) candidates, and gives min to the others.
10. Top-three: Give max score to the top three candidates, min to everybody else.

And the winning strategies (shown blue) are... scaled sincerity, plurality, top-two, top-three, bisector-based thresholding, and mean-based-thresholding (depending on the number of candidates and voters)!

C=3 candidates; 1,300,000 trials; expected utilities for the one voter, shown (causes standard errors to be about 3 units in the last decimal place). Scaled-sincerity (strategy C, shown pink) is not bad: it always gets ≥91% of the best strategy's utility (among strategies A-J tried) no matter what number of other voters V=0-100 there are, and there is no other strategy (among A-J) that can say that! So honesty can pay!

C=5 candidates; 2,500,000 trials (causes standard errors to be about 2 units in the last decimal place). Scaled-sincerity (strategy C, shown pink) is not bad: it always gets ≥80% of the best strategy's utility (among strategies A-J tried) no matter what number of other voters V=0-1000 there are, and there is no other strategy (among A-J) that can say that! So honesty can pay!

C=9 candidates; 1,300,000 trials each (causes standard errors to be about 3 units in the last decimal place). Scaled-sincerity (strategy C, shown pink) is not bad: it always gets ≥78% of the best strategy's utility (among strategies A-J tried) no matter what number of other voters V=0-1000000 there are, and there is no other strategy (among A-J) that can say that! So honesty can pay!

Conclusions

The "honest" scaled-sincerity strategy C does impressively well. I can prove (below) that it always does at least 2/3 as well as strategy E (no matter what the number of candidates is) when V→∞, and I conjecture it always does at least 2/3 as well as any strategy.

Furthermore, in any election situation at all C always is better than (or at least as good as) not voting at all. This obvious claim may not sound enormously impressive, but note that instant runoff voting IRV, as well as all Condorcet voting systems, fail that criterion.

Some Theorems and Proofs

Theorem: Mean-based thresholding is optimal range-voting strategy in the limit of a large number of other voters, each random independent full-range.

Proof: In this limit, it should be clear that the optimal strategy is to choose the threshold to maximize the sum of across-threshold utility-pair-differences. This sum has A·B terms if there are A below-threshold and B above-threshold candidates, and it is proportional in our model & limit to the expected increase in your utility that you get by voting using that threshold (versus if you had not voted).

What is not obvious, and what we shall now prove, is that this is the same thing as mean-based thresholding.

Let there be A utilities below threshold and B above. Let their means be μ_A and μ_B respectively, and the mean of the entire utility-set is μ where (A+B)μ = Aμ_A+Bμ_B. Consider moving the threshold slightly so that the greatest below-threshold utility X becomes above-threshold. The amount by which the sum of across-threshold utility-pair-differences changes (additively) is

The best situation is when no motion can improve utility, and that happens when the threshold is exactly located at μ. Q.E.D.

See also this more general theorem.

Theorem: The "honest" scaled-sincerity strategy C always does at least 2/3 as well as the mean-based thresholding strategy E (no matter what the number of candidates is) in the V→∞ limit.

Proof sketch: The expected utility of scaled-sincerity is lower-bounded by the first sum below (in an n-candidate election), while the expected utility of mean-based thresholding is upper-bounded by the second sum below (up to some common V-dependent proportionality factor) in the V→∞ limit:

Remark: The 2/3 ratio actually is attained in the double limit when V→∞ and the number of candidates also goes to infinity. That is because

Conjecture: Scaled-sincerity strategy C always does at least 2/3 as well as the optimum possible voting strategy, no matter what the number of candidates and voters are.

That was based on the above theoretical indications, my experiments here, and also other experiments by Kevin Venzke.

Open question 1: Settle this conjecture.

Open question 2: since the best strategy (among A-J) changes when you change the numbers V of voters and C of candidates – can you cook up a simple universal strategy that knows C and V, and which always outperforms or equals all of the strategies above?

Return to main page