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!

V A B C D E F G H I J
00.25040.25040.25040.18770.21910.21910.25040.12530.12530.0000
10.17530.25030.22940.18760.21890.21890.22520.12500.12500.0000
20.14240.22210.20290.17190.20060.20060.19760.12190.12190.0000
30.12290.19820.18270.15740.18360.18360.17720.11640.11640.0000
40.10970.17990.16720.14530.16960.16960.16180.11090.11090.0000
50.10000.16510.15470.13540.15800.15800.14950.10570.10570.0000
60.09260.15340.14490.12750.14860.14860.13990.10160.10160.0000
70.08670.14350.13650.12030.14040.14040.13160.09720.09720.0000
80.08160.13510.12940.11430.13340.13340.12480.09370.09370.0000
90.07790.12850.12370.10930.12780.12780.11930.09050.09050.0000
100.07390.12230.11840.10490.12230.12230.11400.08760.08760.0000
110.07050.11660.11340.10060.11750.11750.10910.08480.08480.0000
120.06800.11220.10950.09730.11350.11350.10530.08240.08240.0000
130.06520.10750.10530.09370.10930.10930.10130.07980.07980.0000
140.06280.10370.10180.09070.10580.10580.09790.07780.07780.0000
150.06120.10040.09900.08810.10280.10280.09520.07600.07600.0000
200.05340.08720.08710.07770.09070.09070.08380.06830.06830.0000
250.04810.07800.07870.07030.08200.08200.07570.06280.06280.0000
300.04390.07110.07220.06460.07530.07530.06940.05800.05800.0000
400.03810.06120.06280.05620.06560.06560.06030.05130.05130.0000
500.03420.05460.05640.05050.05900.05900.05410.04670.04670.0000
600.03120.04970.05170.04640.05420.05420.04960.04310.04310.0000
700.02900.04600.04800.04300.05020.05020.04610.04020.04020.0000
800.02730.04300.04510.04040.04720.04720.04330.03790.03790.0000
900.02560.04040.04250.03810.04450.04450.04080.03590.03590.0000
1000.02450.03860.04070.03660.04270.04270.03910.03460.03460.0000
1000.0242860.0383020.0404460.0363700.0423930.0423930.0388180.0343300.0343300.000000
10000.0077030.0116860.0128090.0115140.0134470.0134470.0122660.0113430.0113430.000000
100000.0024290.0036670.0040410.0036410.0042580.0042580.0038790.0036330.0036330.000000
1000000.0007790.0011590.0012840.0011510.0013440.0013440.0012370.0011550.0011550.000000
10000000.0002480.0003620.0004110.0003690.0004300.0004300.0003950.0003710.0003710.000000

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!

V A B C D E F G H I J
00.33290.33290.33290.23400.23320.24440.33290.24970.22190.1664
10.23870.33340.27880.23450.23360.24490.27490.24990.22220.1668
20.19440.28130.24280.22030.22490.23150.23370.24070.21630.1650
30.16850.24300.21670.20510.21220.21610.20610.22520.20510.1594
40.15060.21490.19710.19140.19960.20210.18620.21020.19360.1528
50.13710.19280.18160.17920.18800.18960.17080.19670.18290.1463
60.12730.17650.16980.16960.17880.17970.15920.18590.17420.1408
70.11870.16300.15950.16060.16990.17020.14900.17570.16570.1350
80.11230.15200.15150.15380.16310.16320.14130.16780.15920.1306
90.10610.14240.14380.14670.15600.15570.13400.15980.15240.1259
100.10140.13470.13770.14110.15010.14980.12810.15330.14680.1221
110.09700.12780.13220.13590.14490.14440.12290.14740.14170.1184
120.09330.12190.12720.13130.14000.13940.11810.14200.13710.1149
130.08980.11640.12280.12710.13580.13510.11390.13730.13290.1119
140.08680.11170.11890.12330.13170.13100.11020.13290.12900.1090
150.08380.10760.11500.11960.12790.12710.10660.12880.12540.1061
160.08150.10370.11190.11640.12470.12370.10370.12530.12230.1039
170.07900.10010.10860.11320.12130.12040.10050.12160.11890.1014
180.07700.09690.10580.11050.11860.11760.09800.11870.11630.0994
190.07510.09410.10350.10820.11610.11510.09570.11590.11390.0976
200.07350.09170.10120.10580.11370.11270.09360.11340.11150.0958
250.06580.08070.09100.09590.10300.10200.08400.10210.10110.0874
300.06040.07300.08360.08820.09480.09380.07710.09350.09310.0813
350.05570.06640.07730.08170.08820.08710.07130.08650.08660.0759
400.05250.06200.07290.07710.08320.08220.06720.08130.08180.0720
450.04950.05800.06880.07290.07870.07770.06330.07670.07740.0683
500.04690.05460.06520.06930.07480.07380.06010.07270.07350.0651
600.04300.04920.05980.06350.06860.06770.05500.06640.06750.0601
700.03990.04540.05560.05910.06380.06300.05120.06160.06280.0561
800.03730.04210.05200.05530.05970.05890.04780.05750.05880.0527
900.03520.03950.04900.05220.05650.05570.04510.05430.05560.0500
1000.03350.03730.04670.04990.05390.05320.04300.05160.05300.0477
2000.02370.02570.03320.03540.03830.03770.03050.03640.03770.0344
3000.01940.02080.02710.02900.03140.03090.02490.02960.03090.0283
4000.01680.01770.02340.02500.02710.02670.02150.02550.02670.0245
5000.01490.01580.02100.02240.02430.02390.01920.02280.02390.0220
6000.01370.01440.01920.02050.02230.02190.01760.02090.02190.0202
7000.01270.01330.01780.01910.02070.02040.01640.01940.02030.0187
8000.01180.01240.01660.01770.01920.01900.01520.01800.01890.0175
9000.01120.01170.01560.01670.01810.01790.01440.01700.01790.0165
10000.01060.01110.01490.01590.01730.01700.01370.01610.01700.0157
10000.0106100.0110640.0148410.0159130.0172250.0169600.0136340.0161220.0169520.015677
100000.0033600.0033770.0046780.0050260.0054430.0053630.0043090.0050410.0053690.005031
1000000.0010370.0010490.0014590.0015710.0017070.0016810.0013380.0015700.0016750.001573
10000000.0003400.0003450.0004790.0005130.0005560.0005430.0004390.0005110.0005470.000516

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!

V A B C D E F G H I J
00.40050.40050.40050.24940.24120.25030.40050.35040.24610.3004
10.29950.40020.32000.24910.24080.24990.31850.35000.24550.3000
20.24550.31500.27550.24400.23890.24560.26590.32990.24290.2945
30.21350.26050.24510.23460.23250.23710.23270.29890.23530.2793
40.19130.22260.22270.22350.22310.22620.20950.27120.22520.2620
50.17460.19570.20480.21260.21350.21550.19180.24810.21490.2458
60.16150.17460.19070.20260.20440.20570.17750.22860.20550.2316
70.15100.15870.17900.19360.19610.19660.16620.21280.19670.2189
80.14230.14580.16940.18560.18870.18880.15690.19940.18920.2080
90.13560.13540.16150.17890.18220.18190.14940.18840.18250.1990
100.12890.12650.15430.17280.17610.17580.14220.17850.17630.1904
110.12380.11930.14830.16710.17070.17010.13660.17010.17080.1829
120.11850.11250.14220.16140.16510.16440.13090.16190.16510.1757
130.11420.10700.13730.15660.16050.15950.12620.15530.16050.1697
140.11040.10190.13280.15210.15600.15500.12190.14930.15590.1640
150.10720.09760.12910.14870.15270.15150.11850.14400.15240.1593
160.10410.09400.12520.14470.14840.14730.11510.13930.14810.1544
170.10100.09030.12180.14130.14520.14400.11170.13470.14490.1502
180.09790.08690.11840.13790.14180.14050.10840.13040.14150.1459
190.09570.08400.11550.13490.13880.13750.10580.12670.13850.1424
200.09320.08120.11260.13180.13560.13430.10300.12290.13520.1386
250.08400.07080.10180.12020.12400.12260.09300.10900.12350.1247
300.07670.06270.09310.11070.11430.11280.08500.09810.11380.1135
350.07110.05700.08640.10300.10670.10520.07880.08990.10610.1049
400.06680.05270.08130.09720.10060.09920.07400.08360.10010.0983
450.06340.04920.07700.09240.09570.09440.07020.07850.09520.0926
500.06010.04600.07310.08780.09100.08970.06660.07390.09040.0877
600.05480.04130.06680.08060.08370.08240.06080.06690.08310.0799
700.05070.03760.06190.07480.07770.07650.05630.06120.07720.0735
800.04760.03500.05820.07040.07310.07190.05280.05720.07260.0688
900.04510.03230.05480.06650.06910.06790.04990.05330.06870.0647
1000.04270.03080.05220.06350.06600.06490.04740.05080.06550.0617
1000.0425400.0303100.0518710.0630420.0655280.0644030.0471470.0502240.0650990.061136
10000.0135580.0085940.0165710.0202970.0211410.0207330.0150170.0147830.0209830.018698
100000.0043300.0026200.0052870.0064480.0067080.0066000.0048050.0045760.0066540.005871
1000000.0013570.0008240.0016710.0020410.0021250.0020920.0015100.0014440.0021070.001848
10000000.0004650.0002760.0005720.0006890.0007140.0007040.0005200.0004870.0007110.000628

Conclusions

Strategy E (mean-based thresholding) is the best strategy here when the number V of other voters is sufficiently large, while strategy B (plurality-style) is the best when V>0 is sufficiently small. Furthermore, I believe E obtains the asymptotically maximum possible expected utility for any zero-info voting strategy when V→∞.

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

Δ = (A-1) (B+1) [ (BμB+X)/(B+1) - (AμA-X)/(A-1) ] - A B (μBA)
which after simplification is the same as
Δ = (A+B)(X-μ).
Notice that Δ is positive (i.e. the movement of the threshold was good, according to the expected utility difference) if and only if μ<X (i.e. if and only if it was good according to the mean-based-thresholding criterion).

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:

1≤p≤n-1p+1≤q≤n (q-p)2 / (n2-1) = n2/12
1≤p≤⌊n/2⌋⌊n/2⌋+1≤q≤n (q-p)/(n+1) = (1/2) ⌊n/2⌋ n ⌈n/2⌉ / (n+1) < n2/8
The ratio of the closed-form summations given, plainly is 2/3 or greater. Q.E.D.

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

∫∫0≤x<y≤1 (y-x)2 dxdy = 1/12    and    ∫∫0≤x≤½≤y≤1 (y-x) dxdy = 1/8.

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