Range Voting and Best Voting Systems

Slides for WDS lecture at Public Choice Society meeting Las Vegas NV 7 March 2009: http://rangevoting.org/PCS09lecture.html

Warren D. Smith            Center for Range Voting
http://RangeVoting.org = http://ScoreVoting.net
   Papers here: http://rangevoting.org/WarrenSmithPages/homepage/works.html

Thesis.
OLD (1999-2000): "Bayesian Regret" (BR) measurements indicated "range voting" was the best single-winner voting method among all commonly proposed alternatives. If adopted instead of the currently most-used system, "plurality voting," humanity's lot should improve by an amount comparable to or exceeding the improvement got from switching from undemocratic forms of government to democracy. [Crude (but conservative?) estimate: each day delay getting range voting costs (statistically) 5000 lives.]
NEW (2008): Theory breakthroughs now allow, in certain probabilistic models, evaluating BRs for numerous voting methods in closed form and provably finding best voting methods (with minimum-possible BR). Range voting is shown, in one model called RNEM ("random normal elections model") to have strictly lower BR than any rank-order-ballot based method, for any mixture of honest and strategic voters, in 3-candidate elections. Many other theorems and in some non-RNEM models too.
3-part paper amounts to 100 pages ⇒ can only partially sketch the results and core underlying ideas.

Speaker is mathematician who co-founded CRV in 2005.


Outline – The OLD

  1. What is Range Voting (RV) & other single-winner voting systems? Why should you care?
  2. How can we compare them?
    1. Historical performance
    2. Properties
    3. Bayesian Regret (BR)
    4. "Biological" method
  3. What is Bayesian Regret (BR)? How to measure it?
  4. Results of BR measurement. Presumed underlying intuitive reasons. Adopting RV instead of plurality ⇒ BR-improvement comparable in magnitude to inventing democracy.
  5. Properties various voting systems have [or do not] – (summary chart):
    1. "Favorite-betrayal" & voter honesty vs "strategy.".
    2. Cloning; and removing "irrelevant losers."
    3. DH3 pathology.
    4. Monotonicity.
    5. Participation & "reversal failure."
    6. Countable in precincts.
    1. Countable on dumb machines.
    2. Risk of tie or near-tie "nightmare chad counting" lawsuit scenario.
    3. Extremist vs Centrist Bias. Yee diagrams
    4. Condorcet ("beats-all") winners, tyranny of majority and center-squeeze problems (and what did Condorcet actually intend anyway?)
    5. "Simplicity", Expressivity
    6. ARROW's theorem+mythology, Gibbard-Satterthwaite theorem.
  6. When & where have RV & other interesting systems been used? What happened?

The NEW (...fat chance lecture can actually cover all this...)

  1. What's sad about that?
    1. All complain (forever): why didn't you try my voting method / utility model / voter-behavior model / etc?
      [One answer: you try it via IEVS.]
    2. Mathematicians complain: Was based on computer simulations – not theorem. BRs found numerically – not exact formulas. (There were theorems on RV properties, but not on its BR.)
    3. Doesn't identify best voting system. Only know "Range>the voting methods we programmed & tried"; ∞ as-yet un-invented voting methods not tried.
  2. New breakthrough theorems give exact BR formulas & best voting systems; show superiority of RV vs. every rank-order system. How established?
    1. Best voting system (maximizing expected utility of winner) can be got by "remembering history forever"; in principle allows computer to "converge to" it.
    2. Certain simple-enough probabilistic models (including RNEM) ⇒ can discard computer. The Answer: In RNEM, best rank-order system weighted-positional with
      WeightK=expected utility of the canddt that a given random voter ranks Kth
      (in given utility, voter-distrb'n & -behavior models; weights expressible as N-dim'l ∫)
      Immediate consequence: Borda optimal (among rank-order voting systems) if N≤3 canddts.
    3. BR(voting system) expressible as V·N-dimensional integral.
    4. Correlation-based method says how to write & do those integrals; can reduce dimensionality≤2N in V→∞ limit. If N≤4 candidates, can do ∫s in "closed form" via Schläfli functions. Also important: normal order statistics.
    5. Sample integrals. Generic weighted-positional voting correlation formulas. Reversal symmetry theorem: BR(Plurality)=BR(AntiPlurality). Automatic rigorous proofs of inequalities.
  3. Results: picture & table for 3-candidate elections. The best rated-ballot system.
    1. Exactly same BRs for honest approval & Borda!?! Robust superiority of RV.
    2. Strategy-related difficulties & results when extend to N≥4 candidates. Table. Picture. Best voting systems for N=4 and 31 candidates. Best strategic weights "converge toward approval" while best honest "diverge away from Borda."
    3. When N→∞: Honest-range optimal relative to random-winner; strategic range gets constant-factor lower BR than random-winner, while, e.g, strategic plurality approaches same BR as random winner.
  4. D-dimensional binary-issues politics model ("YN model"):
    1. Honest range voting always optimal (even with arbitrary issue weights)!
      Pessimality of IRV, apprvl, plurlty, Condrct, Borda... in contrived worst-case scenarios.
    2. Random (more realistic than worst-case) YN-scenarios: nonoptimality of apprvl, Borda...
  5. D-dimensional continuum-issues politics model (instead of RNEM):
    1. Utilities based on L2 distance & voters distributed spherically-symmetric normally ⇒ Condorcet optimal when V→∞!
      [Also certain kinds of approval voting optimal; but range not optimal.]
    2. But: L1 distance, utilities based on dot products not distance, or voter-distrib arbitrarily-slightly aspherical ⇒ RV can be (& usually is) better than Condorcet.
  6. Advantages for median-based RV versus average-based? Yes in contrived model involving "sharp-peaked utility distributions" & "biased strategists." Maybe ≈realistic for "figure skating judging" but not in political contexts; there prefer average.
  7. End.


World situation: approaching crises. Need good decision-making.

  1. End of cheap oil,
  2. Global fisheries species collapse,
  3. Exhaustion of important fossil water reserves,
  4. Climate change,
  5. Overpopulation,
  6. Nuclear and bioweapon proliferation.

Important that world make right decisions. But what is world's decision-making algorithm?

US now sole superpower ⇒ closest simple approximation to answer = USA's appalling voting system. Features Bugs:


Definitions of common Single-Winner Voting Systems

System What is a "Vote"? Who wins?
Plurality Name one candidate then shut up ("Nader") The most-named candidate.
(AntiPlurality: least-named canddt wins.)
Runoff "Name one candidate" again – except there might be two elections Top-two from 1st round get to be in 2nd (but only 1 election needed if "majority winner")
Borda Rank ordering of all candidates ("Nader2>Bush1>Gore0") "Borda Score"=Get K points for each voter who ranks you K slots above bottom. Highest ∑score wins.
(More generally weighted positional methods have weights
WK for Kth-ranked candidates, greatest ∑score wins.)
Condorcet Rank ordering of all candidates ("Nader>Bush>Gore") If someone exists who beats every rival pairwise, then wins (else tricky; numerous rule-flavors)
"Instant Runoff" (IRV) Rank ordering of all candidates ("Nader>Bush>Gore") Eliminate "loser" candidate top-ranked by fewest voters (eliminated both from election, and from all ballots). Now repeat that over & over until only one remains (who wins).
Approval = Range1 The set of candidates you 'approve' e.g. {Bush, Nader} The most-approved candidate.
Range9 Award score in 0-9 range to each and every candidate, e.g. "Bush=5, Gore=9, Nader=9" Candidate with highest average score.
Range99 Award score in 0-99 range to each and every candidate, e.g. "Bush=50, Gore=99, Nader=99" Greatest average score wins.

Systems most common in political science literature illustrated by example:

#votersTheir Vote
4 A>D>E>C>B>F
3 B>E>D>F>C>A
2 C>B>E>D>F>A
1 D>C>F>A>E>B
1 F>C>E>D>B>A
An 11-voter, 6-candidate election (candidates A,B,C,D,E,F)

Plurality: A wins (most top-rank votes with 4).
Plurality+Runoff among top two: B wins over A in the runoff, 6-to-5.
Instant Runoff (IRV): C wins (eliminate E, D, F, and B in that order – doesn't matter which way you break DF tie – then C beats A in final round 7 to 4). IRV repeatedly deletes the candidate with fewest top-rank votes, then the remaining one wins.
Borda: D wins. (D's Borda score is 16+9+4+5+2=36 versus E with 12+12+6+1+3=34 and with lower scores for A, B, C, and F.) In the Borda system a candidate gets awarded 0 points if ranked last, 1 if ranked second-last, 2 if... and the candidate with the greatest score-sum ("Borda count") wins.
Condorcet: E wins. (Since E pairwise-beats each other candidate, e.g. beating A 6:5, B 6:5, C 7:4, D 6:5, and F 9:2.)
Approval Voting: If all the red candidates are "approved," then F wins with 7 approvals (versus A=4, B=5, C=3, D=6, E=5).

And with 0-99 Range Voting, it would in fact be possible to make any of the 6 candidates win, depending on how the voters chose the scores compatibly with the orderings above. In Range Voting each voter awards a score from 0 to 99 to each candidate; greatest average score wins. (Fancier rules allow also scoring a candidate with X = intentional blank = "no opinion" – only numerical scores incorporated into averages.)

Another idea is median-based instead of ordinary average-based range voting.


Arrow impossibility theorem & Nobel causes 50 year timewaste

K.J.Arrow's (1950) theorem states that no voting method can satisfy following short list of conditions:

  1. #voters Their Vote
    8 B>C>A
    6 C>A>B
    5 A>B>C
    B wins? Drop C then A wins
    Is no dictator.
  2. If every voter prefers A to B then so does group.
  3. Relative positions of A and B in the group ranking depend on their relative positions in the individual rankings, but do not depend on the individual rankings of any irrelevant alternative C.
Prof. W.R.Webb: "This discovery was a major factor in Arrow winning the Nobel Prize in Economics."

Commonly heard: "Arrow's theorem shows that no 'best' voting system exists."
"Proof": By Arrow, for every voting system, including the putative "best" system B, exists an election which makes it look bad. Construct system A which looks good in that situation. Then A is "superior" to B so B cannot be best. Q.E.D.

That all is wrong. Range voting satisfies all three criteria, accomplishing the "impossible"!

"Property based" thinking misled all of political science for 50 years.



Gibbard-Satterthwaite impossibility theorem

No single-winner voting method exists (in which the votes are rank-order ballots) satisfying all of the following short list of conditions:

  1. There is no "dictator."
  2. If every voter ranks X top, then X wins the election.
  3. The voting system is deterministic, i.e. its decision about who wins is based purely on the votes, not on random chance.
  4. There are at least three candidates running.
  5. 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.

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."

Wait a minute. Doesn't Range voting (in the ≤3-candidate case) satisfy all GS criteria, accomplishing the "impossible"?!

  1. 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.
  2. If every range voter scores X top, then X wins the election. Check.
  3. 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.)
  4. Range voting has no problems handling any number of candidates whether three, more, or fewer. Check.
  5. 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.

more


Four ways to (try to) seek a best voting system

A. Look at human elections through history, or artificial ones (paid subjects).
Pros: Real; right sample space.
Cons[Historical]: Often hard to assess how "good" different election results were or would have been and what results "would" have occurred had other election method X had been used instead. (And subjective. And you'll be accused of bias.) Also, still not really correct sample space (since space might change over time with new X...).
Cons[Paid subjects]: Very expensive. Not really real.
Cons[Both]: Little data ⇒ low statistical significance ⇒ few results. And people lie to pollsters.
B. Examine logical properties of the methods using artificial election examples / proving theorems.
Pros: Keeps political scientists employed. Educational. Insane paradoxes fun to complain about.
Cons: Some paradoxes arise rarely, some commonly. Some usually cause serious harm, others usually only minor damage. This approach offers no way to tell which. Which properties are more important? That is subjective. Qualitative not quantitative. Starts eternal debate, not ends it.
C. Measure Bayesian regret of different election methods via computer election sims.
Pros: Large amounts of data ⇒ statistical significance is no problem. Artificial cyber-voters better than humans: Can read their "minds" to find their true desires unpolluted by lies (measured in standard "happiness units" too).
Cons: Computer results out = only as good as the assumptions & models in. Only try voting systems you try, not all possible.
Pros: Can try large number of assumption sets & models. If so lucky that in all of them, one voting method robustly is best, convincing.
Con: If not so lucky – some methods best in this model, others best in that ⇒ bummer.
Pro: Automatically takes account of all properties (including ones nobody invented yet) weighted correctly.
D. Find planet; create eusocial lifeform that needs to conduct elections as important part of life-cycle; better decisions via the elections ⇒ more fitness; put on planet; wait 20-200 million years; see what voting system Darwinian evolution comes up with.
Pros: Real (arguably more real than with humans). Lots of data ⇒ high significance.
Cons: Spare planets unavailable in local drug store.
Pros: Already been done at least twice on this planet (social insects)!! Hundreds of trillions of very-important-to-the-insects elections so far! All voting systems considered (in some sense).

What is Bayesian Regret?

Oversimplified into nutshell: "Bayesian regret" of election method E is "expected avoidable human unhappiness" caused by using E.

More precise answer: Bayesian regret is gotten via this procedure:

  1. Each voter has a personal "utility" value for the election of each candidate. (E.g, if Nixon elected, then Jill Voter acquires -55 extra lifetime happiness units.) In computer simulation, "voters" & "candidates" are artificial, and the utility numbers are generated by some randomized "utility generator" and assigned artificially to each candidate-voter pair.
  2. Now the voters vote, based both on their private utility values, and (if strategic voters) on their perception from "pre-election polls" (also generated artificially within the simulation, e.g. from a random subsample of "people") of how the other voters are going to act.
    (Note. Some people here have gotten the wrong impression that this is assuming that voters will be "honest" or that we are assuming that honest range voters will use candidate-utilities as their candidate-scores. Neither impression is correct: These assumptions are not made.)
  3. Election system E elects some winning candidate W.
  4. The sum over all voters V of their utility for W, is the "achieved societal utility."
  5. The sum over all voters V of their utility for X, maximized over all candidates X, is the "optimum societal utility" which would have been achieved if the election system had magically chosen the societally best candidate.
  6. The difference between 5 and 4 is the "Bayesian Regret" of the election system E, at least in this experiment. It might be zero, but if E was bad or if this election was unlucky for E, then it will be positive because W and X will be different candidates.

Redo steps 1-6 zillion times (i.e. do zillion simulated elections) to find average Bayesian regret of election system E.

∃ at least 5 different "knobs" to "turn" on our machine for measuring Bayesian Regret of elctn method E:


Results of 1999 computer simulation study:

Measured Bayesian regrets for about 30 different election methods. 720 different "knob setting" combinations tried. Amazing result: in all 720 scenarios, range voting was best (had lowest Bayesian regret, up to statistically insignificant noise). We repeat: RV best in every single one of those 720 with either honest or strategic voters, regardless of ignorance-level, #candidates (3-5), #voters (5-200), #issues (0-∞) etc.

Typical BR results table (highly abbreviated)

Regret measurements. Column A: 5 candidates, 20 voters, random utilities; Each entry averages the regrets from 4000000 simulated elections. Column B: 5 candidates, 50 voters, utilities based on 2 issues, each entry averages the regrets from 2222222 simulated elections.
Voting system Regret A Regret B
Magically elect optimum winner 0 0
Range (honest voters) 0.04941 0.05368
Borda (honest voters) 0.13055 0.10079
Approval (honest voters) 0.20575 0.16549
Condorcet-LR (honest voters) 0.22247 0.14640
IRV (honest voters) 0.32314 0.23786
Plurality (honest voters) 0.48628 0.37884
Range & Approval (strategic exaggerating voters) 0.31554 0.23101
Borda (strategic exaggerating voters) 0.70219 0.48438
Condorcet-LR (strategic exaggerating voters) 0.86287 0.58958
IRV (strategic exaggerating voters) 0.91522 0.61072
Plurality (strategic voters) 0.91522 0.61072
Elect random winner 1.50218 1.00462

Warning: Table makes it appear Borda is second-best after range. But in fact the full study considers hundreds of tables like this, & in many of them, Borda is not second best, in fact in many it's way down in the rankings. The question of which system is second best has no clear answer – some better in some kinds of election situations, others in others.


Bayesian Regrets as Picture


A second BR study (2006)

Less ambitious (but simpler and more reproducible) study: only did the "one-dimensional 3-candidate left-middle-right" political scenario, and very few kinds of voter strategy. But attempted exhaustive set of 623700 configurations, essentially completely covering that space.

Results (some surprises):

Number of voters = 23.  Total number of scenarios = 623700.   BetterCt[][]: 
        0       1     2     3      4      5      6       7      8      9     10
      RANGE   COND  PLUR  PKING RUNOFF  BORDA APPROVAL APRNG  WORST   BEST RANDOM
 0:       0  74096 140855  97481  95160  61600  89724    348 623603      0 623354
 1:   23164      0  83007  27911  26539  19214  74446  22604 622834      0 619786
 2:   19896  13239      0  22143  11271  32453  87685  19689 616431      0 581325
 3:   22189   3246  58393      0   1197  22460  77692  21701 607990      0 597901
 4:   22301   4606  60895  14571      0  23820  79052  21805 621036      0 603912
 5:   23146  31692 114699  59603  58231      0  55232  22322 622674      0 619190
 6:   23288  58942 141949  86853  85481  27250      0  22096 622426      0 602400
 7:    1204  74380 141498  97833  95520  61620  89376      0 623606      0 623386
 8:       0      0      0      0      0      0      0      0      0      0      0
 9:   28918  79832 149525 103473 101767  67354  95336  28062 623700      0 623700
10:     328   3808  42130  25711  19664   4429  21094    296 623700      0      0
BR:   2.03    10.9  27.7   17.5   15.6   7.5    18.0   1.94   69.0     0    39.7
  1. Every method (except WORST) better than every other in at least some 3CLMR situations.
  2. But overall, Range voting is best method here.
  3. "Gift from God": APRNG (half-honest and half-strategic range voters) actually better than either fully-honest RANGE, or fully-strategic=APPROVAL.

How much does RV matter to humanity?

RV ⇒ better decisions ⇒ saved lives.

MY ESTIMATE: Each day delay getting Range voting ≈ 5500 deaths.

RV=comparable improvement over democracy as invention of democracy. Both transitions non-democracy(modeled by "random winner" or better) → democracy(strategic plurality voting) → Range Voting (halfway between honest & strategic BR numbers) comparable in terms of BR reduction; if anything second looks larger. So: How important is democracy?

1. Democide: Governments killing own people for ethnic, racial, tribal, religious, or political reasons.

2. Government waste: Economist M.Bailey estimates US Govt spending is 50% waste (e.g. same power military could be got with half the money, etc.); detailed tabulation in his book.

3. Life expectancy & GNP/capita: both significantly higher (on average) in democracies. (E.g: [a] Life expectancy in E.Germany jumped 6 years since reunification; [b] Taiwan 77.4 vs China 71 also 6 years; [c] Compare North & South Korea; [d] check Vanhanen's & Barro's large cross-country datasets and fits.)

4. Save world via better decisions? Suppose USA, by adopting range voting, lowers risk of 2-billion population crash in 50 years, by 5%. That's 5500 lives/day.

5. Better economic growth? USA 20× richer than Pakistan per capita. But 300 years ago, about same. Vast disparity is result of 1% faster economic growth.


$$ Gazillionaire donors $$ – listen up!

Range voting gives you more "bang" for your buck than almost any other philanthropic option. Maybe the most lives saved for this small an effort. And you can be in the steep part of the learning curve by seeding the start of the RV movement, getting huge leverage for your money. (More details)


Techniques behind this: Bayesian regrets, estimates of what fraction of elections and votes each item would swing. (Half as much ⇒ half as "important.") Techniques can be grounded in something "rigorous" either as a generalized "voting power" or using "small perturbation" models.


Barro's multiD least-square fit, cross-country study

Barro's democracy vs GDP growth-rate plot

Book R.J.Barro: Determinants of Economic Growth: A Cross-Country Empirical Study predicts growth rate of country's real GDP from facts about country. GDP growth enhanced by:

But democracy increases GDP in peculiar way (pictured): increases in Barro's political rights index from 0 to 5.6 on a scale of 0-10 (yielding a moderate level of freedom and democracy) increased GDP growth rates additively by 2.6% but a further increase in the index from 5.6 to 10 retarded growth by negative 1.6%.

All of Barro's causative factors (listed) cause approximately equal additive effects on predicted real-GDP-growth-rate, namely about 2-5% each. That is, having the optimum level 5.6 of political rights causes about 2.6% higher (additively) annual GDP growth rate than the pessimal level 0; countries about one standard deviation above usual in education levels are predicted to have about 3% higher than usual annual-GDP-growth; etc.

Correlation≠certainty so democracy does not force a good economy. E.g, China doing better than India.

Why that peaking and downturn?

Barro ideologically tries to explain by postulating: more democracy ⇒ more government income redistribution ⇒ hurts growth. But attackable because Barro's fit already had incorporated government expenditures as different predictor; democratization was only being fit to unexplained part of the GDP growth above and beyond that explainable as result of government outlays. Barro partly defends by saying that government transfer payments were not held constant. But, assuming Barro has idea that transfers aim toward equalizing wealth, he is exactly wrong about its economic effect: the Deininger-Squires 1998 World Bank cross-country study found that greater initial inequality is strongly negatively correlated to future economic growth!

In other words, the "trickle down theory" often associated with Ronald Reagan is wrong. According to George R. G. Clarke: More Evidence on Income Distribution and Growth, J. Development Economics 47,2 (Aug. 1995) 403-427, "This conclusion is robust across different inequality measures, and to many different specifications of the growth regression. Furthermore, inequality appears to have a negative effect on both democracies and non-democracies. Interaction terms between inequality and regime type, when included in the base regression, do not affect the sign or significance of [this]." So this seems to settle the matter. (However, to completely clarify matters, it would be good to put transfer payments into Barro's fit also, to see what happens. And two other good predictors to try inserting would be a country's winter temperature and the "centralization fraction" of its government [See A.Lijphart: Democracies 1984 table 10.2 page 178].)

Two other possible explanatory hypotheses: (more supported than Barro's):

  1. More democracy ⇒ dumb people make more dumb decisions ⇒ worse economic growth.
  2. Even smart people make dumb decisions if the "decision-making algorithm" is "a poor voting system." If so, then replacing voting system with better one, e.g. range voting, would yield big economic growth win, and that peak & downturn might be avoidable – the curve instead would just keep going up!
Which? (Or both?) If b ⇒ economic growth win attainable by switch to Range or other better Voting appears greater than attainable by altering any other factor identified by Barro (also seems much easier to change voting system than to alter any of those other factors).


Why is RV best? (Aside from "because my computer says so.")

There's also psychological reasons, tactical reasons, and "secondary effects"...

Let's look into all these in a little more depth...


Some theorems saying range voting reacts mildly to strategic voting

Avoids favorite betrayal: In range voting, there is never a strategic reason to give your favorite a non-top score. (Unlike: IRV, Condorcet, Borda, Plurality, where favorite-betrayal often advisable.)

Semi-honesty: In range voting, if you know all other votes (or in a ≤3-candidate election even if you have only partial knowledge of the other votes), then there is always a strategically-optimal "semi-honest" threshold-style vote, where create a "threshold" T and give all candidates better than T score=99, all others score=0. (Unlike: IRV, Condorcet, Borda, Plurality, where it can happen that every honest & semi-honest vote is non-strategic.)

Pleasant surprise theorem: Suppose each voter chooses T=their expectation of the value of the winner. Then: the range-winner will maximize the number of voters who are "pleasantly surprised" (result exceeds expectations). That's an optimality property related to, but not identical to, minimizing Bayesian regret.

Range⇒Condorcet theorem: Suppose each chooses T somewhere between candidates C and A, where C and A are viewed as the two most likely to win. If one of C or A is an honest-voter Condorcet winner, then he will also be the range-winner. (Suggests that in practice, Condorcet cannot have much advantage over range.)


Incentivizing Voter disHonesty; "Favorite Betrayal"

Why? Strategy. Don't want to "waste vote." (⇒ all previous BR studies, with only "honest voters," are of little interest. Also all previous left out Range Voting)

Genl purpose FB example
#voters Their Vote
8 B>N>G
6 N>G>B
5 G>B>N

19-voter example illustrating "Favorite Betrayal" & "Condorcet cycle." B wins under vast variety of rank-order election methods (e.g. Borda, Condorcet-LR, IRV).

But if the six N>G>B voters insincerely switch to G>N>B ("betraying their favorite" N) then their "lesser evil" G becomes the winner under all those voting systems – in their view a better election result.

This favorite-betrayal example very important because, once voters understand exaggerating their stances on the apparent-frontrunners can be necessary to prevent "greater evil"s victory, strategic voting is guaranteed, often causing "third parties" to tend to die out (since the strategic voters won't "waste their vote" on honest-favorite third-party candidates like N whom they perceive as having "no chance of winning").

Range Voting: Favorite-betrayal never strategically forced.


Expressivity – Range leads the pack – suggesting better behavior for honest voters

System# kinds of vote
Plurality N
Borda & Condorcet N!
Approval 2N
Range 100N, or ∞N if continuum scores;
also can express ignorance
using "intentional blank" scores

100-voter example election illustrates: old controversy between Borda and Condorcet (France ≈1780):

#voters Their Vote
51 A>B>C
49 B>C>A

Condorcet: A should win. (A also wins under IRV voting method.) Borda: no, B should win! Who really should win? Good question.

How would range voting handle this? RV allows voters to say how much they prefer B over A (or whoever). Quantitatively. Really, Borda or Condorcet are both right – but depending on intensity-of-preference information unavailable to their voting methods, but available to range voting. So this example illustrates an advantage of range voting over both previous voting systems.

A wins
#voters Their Vote
51 A=99, B=70, C=60
49 B=95, C=90, A=85
Average A=92.14, B=82.25, C=74.70
B wins
#voters Their Vote
51 A=99, B=95, C=40
49 B=90, C=85, A=40
Average A=70.09, B=92.55, C=62.05
#votersTheir Vote
1 A>B>C>D
1 A>B>C>D
1 B>C>D>A
1 C>D>A>B
1 D>A>B>C

A 5-voter example. Borda totals: A=9, B=8, C=7, D=6. Reversed Approval counts: A=1, B=2, C=3, D=4! (Generalizes to N candidates.) Both Borda and Approval clueless; range voting (with extra intensity info) can do something sensible.


Cloning – bad news for Borda & Plurality

Several near-identical "clone" candidates run. Plurality voting: they split the vote and all lose. The very popularity of a view can cause its defeat! Borda voting (basically): enough clones ⇒ opposite effect ("teaming"); assured victory!

Obviously, Mush wins this one.
#voters their vote
51 Mush
49 Bore
But now, if Bore has numerous clones (call them Bore1, Bore2, and Bore3 in decreasing order of attractiveness) then the Borda vote would give Bore1 an easy victory:
#voters their vote
51 Mush > Bore1 > Bore2 > Bore3
49 Bore1 > Bore2 > Bore3 > Mush
(totals) Mush=153, Bore1=249, Bore2=149, Bore3=49.

Cloning the Bores ⇒ huge advantage! Boring party can just arrange for mucho Bores to enter the race & totally Boring! Of course, Mushites could try to defeat that by intentionally lying in their votes by ranking Bores in opposite of true order, to try to cancel out the Borites and make Mush win. But this strategy causes them to be massively dishonest in their votes and risk not only a Bore-victory, but in fact a victory by the worst of the Bores! (Which would in fact happen if the Borons counterstrategized by also being dishonest in their Bore-orderings!) Crazy!

Mushites: fight by nominating own clones, Mush1, Mush2, Mush3, and Mush4, so they'll win. Bores: countersponsor more clones Bore4, Bore5, Bore6. Etc. War of clone armies. All about gall, little to do with what voters actually want.

Has caused parties to intentionally aid opponents of their point of view ("helping a spoiler")! And it also has (more often) caused parties to intentionally hurt allies of their point of view!

Range Voting: clones & "vote splitting" don't matter, election result not affected. Can't manipulate the election by creating or abolishing clones.


Removing an "irrelevant loser" Candidate

4 candidates and 7 voters. Start looking at situation on left.

Johnson's Borda example. The winner is C with 13 Borda votes. (Losers: B=12, A=11, and D=6.)
#voters their vote
3 A>B>C>D
2 B>C>D>A
2 C>D>A>B
Johnson's Borda example (after D eliminated). The winner is now A with 8 Borda votes. (Losers: B=7 & C=6.)
#voters their vote
3 A>B>C
2 B>C>A
2 C>A>B

Range Voting: Removing a loser (from all ballots & the election) never changes anything.


DH3 pathology – bad news for Borda & Condorcet

Common scenario: Whenever there are 3 rival contenders A,B,C plus one or more "dark horses" D we all agree are worthless no-hopers: In Borda & most Condorcet systems it pays for each for the 3 factions to dishonestly rank D "above" the other two rivals. (Strategic justification: Whichever faction votes honestly, guaranteed to lose the election. Condorcet systems with equal rankings allowed? Ranking D co-equal-last like A>B=C=D is not good enough strategy; only "full force" dishonesty A>D>B>C is strategic.)

#voters Their (honest) Vote
33 A>B>C>D
33 B>C>A>D
34 C>A>B>D
#voters Their (strat) Vote
33 A>D>B>C
33 B>D>C>A
34 C>D>A>B

But – Worst possible disaster result: if enough voters do that, D wins.

(DH3 resembles "spoiler pathology" & game of "chicken." But it's worse. And probably more common.)
Range, IRV, plurality: immune to DH3.


Plurality fails badly

#voterstheir vote
28 A>B>C>D
25 B>C>D>A
24 C>D>B>A
23 D>C>B>A

A would lose to any opponent in head-to-head election by 72-to-28 margin, and is ranked dead last by 72% of the voters.

But plurality elects A with 28% of the vote (28>25).


Monotonicity

is the property of a voting system that both

  1. If somebody increases their vote for candidate C (leaving the rest of their vote unchanged) that should not worsen C's chances of winning the election.
  2. If somebody decreases their vote for candidate B (leaving the rest of their vote unchanged) that should not improve B's chances of winning the election.

Unfortunately, Instant Runoff Voting (IRV) is not monotonic; fails both criteria.

Examples of nonmonotonicity of IRV

Criterion I fails: when two voters change their vote to C, that stops C from winning.

Details: C wins this 17-voter IRV election (B is eliminated and 1 more of his 5 votes transfer to C than to A, causing C to win 9:8 over A). But after the two A>C>B voters instead give their vote to C, then B wins. (In the new election, A is eliminated and his 4 votes transfer to B, causing B to win 9:8 over C.)

This occurred in the Louisiana 1991 governor election, which was a (non-instant) runoff election with 12 candidates but only the top 3 got over 410,000 votes each; the remaining 9 candidates each got under 83,000 individually and under 125,000 in the aggregate.

#voters their vote
6C>A>B
2B>A>C
3B>C>A
4A>B>C
2A>C>B

Criterion II fails: when two voters change their vote away from B, that causes B to win.

Details: C wins this 17-voter IRV election (A is eliminated and his 4 votes transfer to C so that C wins 9:8 over B). But after 2 of the B>A>C voters instead give their vote to A, then B wins. (In the new election, C is eliminated and his votes transfer to B so that B wins 11:6 over A.)

This occurred in (an altered form, with extra Currie voters added, of) the Irish 1990 presidential election, which was an IRV election with 3 candidates.

#voters their vote
5C>B>A
4A>C>B
8B>A>C

More.


1. "Reversal failure" and 2. "Participation failure" illustrated with IRV

Winner=Loser reversal paradox in IRV
#voters their vote
9 B>C>A
8 A>B>C
7 C>A>B

1. In this 24-voter IRV election, A wins after C is dropped. But now suppose every voter reverses his preference order (now attempting to choose worst rather than best). In that case A still wins after B is eliminated. I.e. IRV contradicts itself; IRV's unambiguously "best" candidate A is here the same as its "worst"!

(After only 3 votes reverse)
#voters their vote
6 B>C>A
3 A>C>B
8 A>B>C
7 C>A>B

Also illustrates bizarre kind of strategic voting: Suppose 3 of the B>C>A voters reverse their votes to A>C>B (or alter them to A>B>C; that also works). Then B is eliminated whereupon C wins 13-to-11 over A. The raising of A from bottom-to-top in their vote caused A to lose – and voting maximally dishonestly as though they were suicidally trying to elect the worst candidate, was actually optimal strategy!

2. Also illustrates "no show paradox": If those three B>C>A voters had simply refused to vote, then C would have won (an improvement in their view). Different way of saying the same thing: these three voters' decision to cast an honest A-last vote caused A to win.

Thus IRV violates participation property: Honest voter, by participating, should not worsen election result (in her view). I.e, "abstaining is not a better strategy than voting."


IRV "not countable in precincts," only "centrally countable"

There is no such thing as a district "subtotal" anymore if we use IRV voting. Example:

District I
#voters Their Vote
6 A
4 B
3 C>B>A
District II
#voters Their Vote
6 C
4 B
3 A>B>C

In district I, IRV eliminates C, then B wins 7:6. In district II (same as district I but the roles of A and C are reversed), B also wins 7:6. But in the combined 2-district country, B has 8 top-rank votes, A and C have 9 each, so B is eliminated and either A or C wins. Thus merging two districts both won by Bush under IRV, can produce an IRV victory for Gore.

Fraud prevention: I want precinct totals to be published. That's not going to happen if a precinct is going to have to publish 6!=720 "totals" in one race. (And even if that did happen, then this publishing would defeat ballot secrecy and open the door to vote-selling and coercion.)

(More; analogous problem for Condorcet voting systems)


Range Voting works on "dumb plurality" vote-counting machines!

Computers⇒new kinds of election fraud. Many people think best to forbid computers. Use "dumb" (mechanical, noncomputerized) machines.

Mathematically: ∃ transformation of one C-candidate (0-9 plus X) range voting election to 11C artificial "plurality elections." In some cases, this is easy and convenient from the viewpoint of voters (optical scan machines) in others it is less convenient (which is why we would prefer to have purpose-designed range-voting machines) – but it always works, easing transition worries greatly.

Demo:

Award each candidate a numerical score from 0 to 9. Advise giving your favorite candidate 9 and the worst one 0. If you intentionally wish to express no opinion about that candidate, then please do not select any score for him – equivalently leave the default "X" choice selected; only numerical scores will be incorporated into the averaging.

George Washington 0 1 2 3 4 5 6 7 8 9 X
Mahatma Gandhi 0 1 2 3 4 5 6 7 8 9 X
Jesus Christ 0 1 2 3 4 5 6 7 8 9 X
Abraham Lincoln 0 1 2 3 4 5 6 7 8 9 X
Ronald Reagan 0 1 2 3 4 5 6 7 8 9 X
Muhammad 0 1 2 3 4 5 6 7 8 9 X
Theodore Roosevelt 0 1 2 3 4 5 6 7 8 9 X
Franklin D. Roosevelt 0 1 2 3 4 5 6 7 8 9 X
Winston Churchill 0 1 2 3 4 5 6 7 8 9 X
Nelson Mandela 0 1 2 3 4 5 6 7 8 9 X
Martin Luther King 0 1 2 3 4 5 6 7 8 9 X
 
   

Also try zohopolls, SuperDuperApps, or this instant runoff demo (IRV will not run on many of today's voting machines).


Risk of Tie and near-Tie "nightmare chad-counting lawsuit" scenarios

Here's an interesting hypothetical election to keep in mind when considering the risk of ties under IRV (Instant Runoff Voting).

%Voters Their vote
50 Kiss > Miller > Curley
25 Curley > Miller > Kiss
25 Miller > Curley > Kiss

With plain plurality voting, Kiss wins in a landslide and there's no recount called for.

With IRV Miller and Curley are nearly tied, and so all kinds of recount lawsuit nonsense ensues. Then the winner of that battle goes against Kiss, and then he and Kiss are nearly tied and so another series of lawsuits ensues.

More. IRV "exponential amplification".



Extremist or Centrist bias? Yee diagrams

Voting system Favors Centrists or Extremists?
Plurality Extremists
Approval Centrists or no bias (depends on assumed voter "thresholding" behavior); also if they vote "plurality style" will duplicate plur's extremist-favortism
Condorcet Rank-order systems no bias
Borda Rank-order; Range little or no bias (pictures = slightly distorted version of above)
Instant Runoff (IRV) Extremists irv270.bmp

Here's two pictures (by Ka-Ping Yee himself!) comparing Condorcet & IRV:


Condorcet ("beats-all") winners

Condorcet's idea: a winner should beat every rival pairwise. (Unfortunately there can be a cycle and then no CW exists.)

#voters Their Vote
51 A>B>C
49 B>C>A

This 100-voter example election illustrates an old controversy between Borda (1733-1799) and Condorcet (1743-1794). According to Condorcet, A should win. (Here A also wins under the IRV voting method.) But according to Borda, B should win. Who really should win? Good question.

Now let's see how range voting would handle this. If the voters say

#voters Their Vote
51 A=99, B=70, C=60
49 B=95, C=90, A=85
Average A=92.14, B=82.25, C=74.70

then A wins. But if they say

#voters Their Vote
51 A=99, B=95, C=40
49 B=90, C=85, A=40
Average A=70.09, B=92.55, C=62.05

then B is the winner.

The point is that range voting allows voters to say how much they prefer B over A (or whoever).


Tyranny of Majority

Classic over-simplified and over-dramatized example is the "kill the Jews" vote with choices

  1. Kill the Jews and steal their money, using it to reduce taxes for non-Jews.
  2. The Jews (who are a minority) live.
  3. ...
With honest Condorcet voting (i.e. honestly indicating the choice that is best solely for that voter, no matter how slightly): A wins.
But with honest range voting if the voters honestly express weak preference for A but strong preference for B (because the voters who benefit from reduced taxes wish to indicate honestly that is a small gain for them, while the Jews who die, wish honestly to indicate that is a large loss for them), B can win. B is better for society overall.
If there is enough voter honesty, range can deliver superior results than any other of the usual voting method proposals. No other commonly-proposed voting method can avoid the "tyranny of the majority" problem.


IRV can "squeeze out" Condorcet winners

------------Leftist-------------Centrist--------------Rightist---------------
              35                   32                    33

In this 3-candidate election, Leftist voters prefer Centrist>Rightist and Rightist voters prefer Centrist>Leftist. Result: Centrist is (huge) "Condorcet winner" defeating each rival pairwise by 65:35 or larger majority.

But Instant Runoff Voting (IRV) eliminates Centrist immediately. This happened in e.g. Peru 2006.


What did Condorcet actually intend?

"When all but two candidates (X & Y) are removed from all ballots then X defeats Y, we say X "pairwise" defeats Y. Condorcet demands that a candidate who pairwise defeats every rival must win the election."

Wait: According to this wording, range voting is a Condorcet method!

(BUT: According to the usual view, range is not a Condorcet method because, e.g, one voter could have hugely-strong preferences outweighing a lot of voters all with very weak preferences. In such case, no reason majority will win.)


SUMMARY CHART of voting system properties

Voting system Expressive Participation Favorite-
Safe
Clone-
Safe
Monotonic Remove-
Loser-
Safe
Precinct-
Countable
Dumb-
Machines
Extremist/
Centrist
Bias
Simplicity
Plurality The Worst yes FAILS! FAILS! yes FAILS! yes yes Extremist good
Approval or
on each canddt
yes yes partial yes yes yes yes voter-
behavior-
dependent
best (excellent for meetings)
Condorcet systems rank order FAILS! (2.5%?) FAILS! yes & no yes & no FAILS! 9% yes & no FAILS! unbiased complex
Borda rank order yes FAILS! FAILS! yes FAILS! yes FAILS! ok medium
Instant Runoff (IRV) rank order FAILS! 16.2% FAILS!
19.6-100%
yes FAILS!
14.7%
FAILS! FAILS! FAILS! Extremist complex
Range The Best yes (if no "blanks") yes yes yes yes yes surprisingly yes ok (bias, if any, small) surprisingly good




Intuitive (presumably underlying) reasons Range > other systems

Range>Plurality:
No vote splitting & "cloning" problems, no "favorite-betrayal" incentive, vastly more expressivity.
Range>Borda:
More expressive (opinion-strengths not discarded) ⇒ better for honest voters.
No DH3 and "favorite-betrayal" strategy-caused problems ⇒ better for strategic voters.
No cloning problem; no problem with removing "irrelevant" loser causing result-reversals.
Same nice "symmetries" & "geometry" (beloved by Saari).
Range>Condorcet:
Diminished tyranny of majority problem & greater expressivity ⇒ better for honest voters.
For strategic voters, under reasonable assumptions range will elect honest-voter Condorcet winners whenever they exist (Condorcet methods often do not!). Also Condorcet systems suffer favorite-betrayal & DH3, and strategic Condorcet voters always elect strategic-plurality winner ⇒ Range better for strategic voters.
Range>Approval:
Both essentially same for strategic voters (although are circumstances where strategic range voting is not approval style).
Range more expressive ⇒ better for honest voters.
Also range better for honest+strategic mixtures; range enjoys diminished "Burr dilemma" problem.
Range>Instant Runoff:
For strategic voters, IRV always elects strategic-plurality winner.
Range more expressive. Also range free of many weird IRV-pathologies such as non-monotonicity, favorite-betrayal, no-show paradoxes, winner=loser reversal paradox, centrist squeeze-out... ⇒ better for honest voters.
Range (average-based)>Range (median-based):
Average range vote is better approximation to average utility than median range vote ⇒ average better for honest voters.
Both essentially same (and become approval voting) for strategic voters.


Properties voting systems may or may not have

Expressiveness: The more kinds of votes you can cast, the more expressivity you have. With plurality voting in an N-candidate election, you have N possible votes (or N+1 if "not voting" is allowed and we count it as an additional option). That is a lot less expressivity than approval voting with 2N possible votes. With rank-order voting systems you have N! and with 0-99 range voting you have 100N (or 101N if "no opinion" scores permitted for each candidate).

Participation: If casting an honest vote can never cause the election result to get worse (in that voter's view) than if she hadn't voted at all, then that voting system satisfies the "participation property." (Some voting systems like Condorcet and IRV fail this – they exhibit "no-show paradox" elections where some class of voters would have been better off "not showing up.")

Favorite-safe: If it never is more strategic to vote a non-favorite ahead of your favorite, then the voting system is "favorite-safe." (So-called because it is "safe" to vote for your favorite.)

Clone-safe: If a "clone" of a candidate (rated almost identical to the original by every voter) enters or leaves the race, that should not affect the winner (aside from possible replacement by a clone). We call voting systems obeying this "clone-safe." Borda and plurality voting severely fail this property.

Monotonicity is the property of a voting system that

  1. If somebody increases their vote for candidate C (leaving the rest of their vote unchanged) that should not worsen C's chances of winning the election.
  2. If somebody decreases their vote for candidate B (leaving the rest of their vote unchanged) that should not improve B's chances of winning the election.

Remove-loser safe: If some losing candidate X is found to be a criminal and ineligible to run, then the same ballots should still be usable to conduct an election with X removed, and should still elect the same winner. (But if X's departure changes the winner, the property fails. In several voting systems, e.g. Borda, X's departure can actually reverse the finish-order of all the other candidates, a dramatic failure.)

Precinct-countable: If each precinct can publish a succinct summary of the vote (sub)total in that precinct, and the overall country-wide winner can be determined from those precinct subtotals, then the voting system is "precinct-countable."

Dumb machines: Are "dumb" (i.e. non-computerized) totalizing voting machines, designed only to support plurality voting, usable for this voting system?

Extremist/Centrist bias: Suppose the candidates are positioned along a line (1-dimensional) or in a plane (2-dimensional) and voters prefer candidates located nearer to them. In some voting systems, it is usually difficult or impossible for "centrists" (centrally located relative to the other candidates) to win. Those systems "favor extremists." Other voting systems "favor centrists." We apologize for defining this property rather vaguely, but in practice it is often quite clear which category a voting system belongs in. For example, see these pictures (especially "note #2") to see that Instant Runoff (IRV) voting favors extremists.

Simplicity: Voting systems with simpler rules, simpler counting algorithms, and found to be simpler by human voters are "simpler." If you want to be precise about this, then we point out you can objectively measure the "simplicity" of the rules and vote-counting algorithm as the length of the shortest computer program that inputs, checks-validity-of, and counts the votes to determine the winner. And you can objectively measure how simple humans find it to vote by e.g, comparing ballot spoilage rates under different voting systems, or comparing the average time it takes humans to cast their vote or for other humans (or computers) to count them.


"Secondary effects"

"Primary" effect (reckoned using Bayesian regret) = just who wins the election & how much utility that is. "Secondary" effects exert themselves over historical time in sequence of many elections. When these also reckoned, RV looks even better...

2-party domination: In systems where "favorite betrayal" common enough, "2-party domination" happens (third parties die out). 2PD quickly became massive (>99.5%) in the USA (plurality voting) since "idiotic to waste vote by voting Nader." 2PD also experimentally has always happened under IRV, despite moronic propaganda (Australia, Ireland, Fiji). 2PD has not happened under plur+top-2-runoff. ("Duverger's laws.") 2PD might happen under Condorcet systems.

Consequent diminution of voter choice:

Bush & Kerry 2004:
pro, versus all third-party canddts against: PATRIOT act, WTO, NAFTA, "war on drugs," Iraq war, subsidy-laden "farm bill," (tax cuts leading to) huge budget deficit.
McCain & Obama 2008:
Both pro "bailout" and also for keeping all third-party candidates out of the presidential debates. [All third-party candidates, and majority of US public, against.]

One-party domination: 98% predictability in contemporary USA. (One reason is gerrymandering... by which one party can stay permanently in power even if only 25+ε% support.)

Cash: is extremely important in plurality voting, but perceived to be less so in other systems e.g. plur+top-2-runoff. Why? Need to demonstrate you are one of the top-2 "frontrunners," i.e. create illusion of winnability, otherwise not worth wasting vote on you. That's expensive. (Educating about issues: cheap.)less

Media: Pays no attention to third-party views (no motivation; they're not news). Media "lapdogs" unquestioningly accept politicians' BS without much critical examination (because with 2-party and 1-party domination, politicians are in monopoly position to cut off media lifeblood; with multiparties no such info monopoly). Much more interested in the "horse race" than the issues.

Lack of congressional oversight: For most of about 8 years, Democrats in Congress haven't been able to subpoena anyone.

Rubberstamped agency heads & judge appointments: In votes for court of appeals nominees, Republican Senators during the Bush administration (during majority control) produced 2703 votes for the nominee as opposed to only a single "no" vote (cast by Trent Lott against judge Roger Gregory, the first Black ever appointed to this position).

Hurricane protection money budget figures

Bush appointed Joseph Allbaugh as head of FEMA in 2001, although Allbaugh had no expertise or experience handling emergencies, but rather had been then-Texas-Governor Bush's chief of staff & campaign manager for Bush-Cheney nationwide campaign. (Allbaugh had B.S. in political science from Oklahoma State University.) In 2003, Allbaugh replaced by Michael D. Brown – Former estate and family lawyer and bar examiner. The Boston Herald reports that Brown was "fired from his last private-sector job, overseeing horse shows... after a spate of lawsuits over alleged supervision failures... `He was asked to resign,' Bill Pennington, president of the IAHA at the time, confirmed last night."

Pork & earmark game-playing:

FEMA (Federal Emergency Management Agency), in report well before both Hurricane Katrina and the 9/11 attack, summarized top 3 threats to the USA as a terrorist attack on New York, major earthquake in San Francisco and hurricane strike on New Orleans. But Bush and Congress by bipartisan budget vote turned down Louisiana's requests for mere tens of millions per year to protect New Orleans. New Orleans contained urban & poor people, many blacks, hence a high% Democrat voters; Louisiana had democrat senator, & starting in 2004, a democrat governor.

Compare with: $28 billion embassy (constructing in Iraq); $231 million for Alaska bridge between Gravina Island (population<50) & Ketchikan (pop. 8,000); Wyoming $31 million in anti-terrorism funding in 2003 (more per capita than any state).


Our exit-poll (2004 Pres. election) Range and Approval study

2004 results:
Candidate Plur AV RV
Bush(Rep) 50.7 39 40
Kerry(Dem) 48.3 61 55
Nader 0.38 21 25
Badnarik 0.32 0.6 9
Cobb 0.10 2 5
Peroutka 0.12 1 6
Calero 0.003 0 4
Total3rd 0.92 25 49

Pseudo-election with real US voters (122 range & 656 approval) simultaneously with the 2004 presidential election (as exit poll). Note RV psychological drive for human honesty"nursery effect" ⇒ RV far more likely than AV to encourage growth of small third parties ⇒ enabling escape from 2-party domination, media lapdogs, rubberstamped party hack agency heads & judges, etc. Third parties: suicidally foolish to support anything besides range voting.

More data: French Approval-Voting Study and French Range-Voting Study.

1992 US Pres. Election [analysis NES data by Steven J. Brams & Samuel Merrill III Politics and Political Science 27,1 (March 1994) 39-44], the vote totals again would have been tremendously altered with approval voting (although finish order would not have changed) again illustrating tremendous distortionary penalty faced by third-party candidates under plurality system.

And in the 1980 US Presidential Election, according to analysis based on many polls in ch. 9 of Brams & Fishburn's book,
1992 results:
Candidate Plur AV
Clinton(Dem) 43.0 55
Bush(Rep) 37.4 49
Perot 18.9 42
Anderson probably actually would have come in second behind Reagan but ahead of Carter, under approval voting, whereas under plurality voting he was far in third place with under 7% of the votes. Again illustrates the tremendous distortionary penalty faced by third-party candidates under the undemocratic plurality system.


Psychology-aided effects

RV has some further advantages perhaps not mathematically explainable, but which instead are experimental facts that are consequences of human psychology:

  1. Altruism: Range Voters exhibit unstrategic honesty to far greater degree than plurality voters. (76% of RV ballots manifestly unstrategic... versus: 90% of the time US plurality voters can choose between strategic V honest, they pick strategic.)
  2. Nursery effect follows: third parties should favor RV (unless death wish)
  3. Range (and approval) voters have low ballot-invalidating error rates, while IRV voters have high rates.
    Plurality: 1.0-3.1% spoiled (6 countries). IRV: 3.4-6.2% spoiled (Australia 8 territories).
    Also ≥7X increase IRV vs plurality spoilage rate in San Francisco.
    French 2002 approval study: 2.0% spoilage for official plurality votes, 0.3% for approval exit-poll votes.
    Range: 0.026% spoilage rate (per candidate) observed in our exit poll; 99.5% confidence that range rate per canddt is at least twice as small as USA's plurality error rate of 1.8%. Similar results in French study. One reason: RV & AV: every way to fill in scores is legal. IRV & plurality: not so. Another(?): range & approval voters repeatedly do the same operation many times in each race, causing them to be more careful and inherently self-checking. (Plurality: do it only once.)
  4. That'll reduce fraud-like Florida-style election manipulation.

"Spoiled ballots" & election manipulation

Comparison of uncounted "spoiled" ballot rates in the 4 blackest and 4 whitest Florida counties [from Greg Palast's book]:
County Black pop. Uncounted County Black pop. Uncounted
Gadsden 52% 12% Citrus 2% 1/2 %
Madison 42% 7% Pasco 2% 3%
Hamilton 39% 9% Santa Rasa 4% 1%
Jackson 26% 7% Sarasota 4% 2%

Cornell U. prof. Walter Mebane Jr. analysed ballot-level data from the NORC Florida ballots project and ballot-image files, concluded that "If the best type of vote tabulation system used in the state in 2000 – precinct-tabulated optical scan ballots – had been used statewide then [due to inequities in the distribution of voting machines & settings of those machines] Gore would have won by more than 30,000 votes." [ W.Mebane Jr.: The Wrong Man is President! Overvotes in the 2000 Presidential Election in Florida, Perspectives on Politics 2,3 (September 2004) 525-535]

This happening not only at the county level, but also district by district statewide. 268 Duval precincts: fluke result due to random fluctuations? Not. Enough to swing the Bush-Gore election result in Florida (which was decided by an official margin of only 537 votes)? Easily. (Palast maps, caption)

Duval spoiled ballots histogram

Range Voting can get unified third-party support (due to Nursery effect, they'd be crazy to support anything else).


Iowa 2008 Pres-Primary Caucuses – perfect stage for range voting

Tactics: All major power groups want RV in Iowa (unlike usual)

  1. Iowa caucuses get tremendous media attention, have tremendous impact despite small Iowa population. Mucho publicity for range voting.
  2. Appears can change the rules without altering state or federal law, only Dem. & Repub. party internal procedures, central committee. Easier target.
  3. Iowa caucuses use pen & paper ballots & manual totaling (hand calculators or adding machines). Hence can easily institute single-digit range voting – essentially no complexity penalty versus approval & plurality.
  4. Both the Dems & Repubs (at all levels: rank-and-file members countrywide and Iowa-wide, Iowa state party leaders, national party leaders), are motivated to want to use range so they can get a better presidential nominee, and seem in favor of reform, and get free publicity; Iowans may also be in favor of change since many may believe Kerry (or Bush) was a mistake by them.
  5. Because expect 10 Dem & 10 Repub candidates, range voting will have maximized quality advantage versus plurality & approval. Computer sims:
    "Random normal elections": How often do the range & plurality winners agree?
    #candidates: C=2 3 4 5 8 10 15 20 50 100 200
    5123 voters 100% 73% 61% 52% 38% 32% 24% 19% 8% 4% 2%
  6. Third parties want range voting and their supporters constitute at least 1% and arguably as much as 40% of society. They could swing the election. It is worth catering to their desires, especially when it also benefits everybody else including the major parties and all USA-wide.
  7. Leads to voter education, reform, free good publicity beneficial for all involved, and better US presidential candidates.

Social Insects

BeeOnFlower2 BeeOnFlower

Honeybee (Apis Mellifera) swarms (each spring) and the 3mm-long eusocial ant Leptothorax Albipennis (after nest destruction) both use range voting to decide on the location of their new nest.

Problems bees face: Tiny brains. Can they do "addition," "division," and "averaging"? If so, can they communicate results reliably? What if some bees mentally defective or miscommunicate? How to reach a swarm-wide consensus? How to do it quickly?

Problems bees face: Tiny brains. Can they do "addition," "division," and "averaging"? If so, can they communicate results reliably? What if some bees mentally defective or miscommunicate? How to reach a swarm-wide consensus? How to do it quickly? "Robust log-time parallel algorithm"...

How bees do it:   (Robust log-time parallel algorithm!)

  1. Scouting. (Only 5%=scouts, rest sit there.)
  2. Dances. Better nest sites get longer, more vigorous dances (greater "range vote scores").
  3. More (& hotter) dancers at any given time ⇒ more probability of recruiting new scout ⇒
  4. Higher "exponential growth rate" for nest sites with greater range votes.
  5. Eventually the faction advocating the site with greatest average score, dominates population (even if initially small; higher exponential wins out over constant factor).
  6. "Quorum rule" that it ain't over until enough votes are in.

The Point

In the ∞-time limit, the "bank account" with the greatest "interest rate" wins, no matter who was richest at the beginning of the process. The interest (i.e. recruitment, i.e. faction-growth) rate in bee-elections is by design/definition proportional to its range-vote score.

∴ The range-voting winner is the faction which eventually dominates.

*(However, the bees do not have infinite time – only willing to wait about 1 week – and also since only a finite number of bees, there is statistical noise. These non-idealities could cause some other winner, if unlucky.)

How good are they? Swarm: 2000-20000 bees. ≥1015 elections so far. Usually find ≈20 different housing options within about 100 km2, and ≈90% of the time, bee swarm succeeds in selecting (what appears to entomologists to be) best one.

Compare plurality-using humans: Computer sims ⇒ 1283 honest plurality-voters, given 10 choices (each voter regards each choice as worth standard-normal-random-number "dollar amount," all randoms generated independently before experiment begins) succeed in choosing the best (maximum ∑ dollars) 32% of the time.

Random guess: (10%),

Sim-humans employing "approval voting" (approving choices with value greater than midway between the best & worst available) then 54%.

Sim-humans employing "range voting" (scoring best choice 99, worst 0, rest linearly interpolated) then 79%... at least approaching bee-quality.

Ants: The most successful macroscopic land animals (15-20% of all land animal biomass?!). 200 Myr old.


Where was Range Voting used and what happened?

  1. Sparta 650 BC - 300 AD (?) – continuum range
  2. Venice 1268-1797 AD – range = {-1, 0, +1}
  3. USA before 1800 – approval voting (≤2 approvals) to elect president
  4. Olympic gold medals – range = {0,1,2,..., 99,100}×0.1
  5. Internet sites like hotornot.com
  6. USSR 1987 – approval voting – range = {0, 1}
Spartan Caste system: Estimated population distribution of Sparta during the 500 BCs
ClassApprox Population (1000s)
Citizen (all genders & ages)9-15
Perioikoi30-60
Helot140-200
Sparta main branches of govt:
BranchNumberTermFunctions
Co-Kings2Until death or deposedRoads, army command
Ephors51 year (elected)Supreme Ct, executive
Gerontes2860-to-death (elected)Court & advisory
Assembly1000smale Spartiates over 30Elect and choose

"[The Spartans'] unique constitution cannot be placed under any general head; cannot be called kingdom, oligarchy, or democracy, without misleading... it participated in all three." — J.B.Bury (quote p.118).

Sparta at its peak was the most powerful state in Greece, hence world. Both the earliest, and longest-lasting, government with substantial democratic component ever (somewhere between 580 and 1040 years):

Puzzle: How to perform manifestly honest range voting elections quickly & simply?

Election fraud.

Sparta's solution: (Aristotle called it "childish")

  1. Order candidates in obviously random way.
  2. Election judges sit in separate room and do not know this ordering.
  3. For each candidate C, in order:
    1. Assembly screams to express level of support for C;
    2. Judges record decibel level to decide who won.



Renaissance Venice


Venice was the most-democratic country of its age, and at its peak the richest biggest-trading city, with the greatest navy. It had the second-longest-lasting government with substantial democratic component ever:

Neither Venice nor Sparta is reported to have been 2-party dominated (nor indeed were political parties reported to play any major role at all).

Her unique system of government... was stern, occasionally even harsh... but [overall it had a] better record of fairness and justice than any other [European government]. – J. Norwich (introduction to A history of Venice)

Approval voting used in 1987 USSR democratization experiment by M.S.Gorbachev: 5% of all USSR's 50,000 villages, towns, cities, and counties. (But USSR collapsed few years later.)

Essentially Approval voting used in early USA to elect President. [≤2 approvals; 2nd-placer wins vice-presidency.]

Ireland 1990, Australia 2007, France 2007, more.


Some (Old) Theorems about range voting

CLONING+FB THEOREM (WDS 2007): Every reasonable(*) voting method based on rank-order votes is vulnerable either to candidate cloning or to favorite-betrayal. But range voting has neither defect.

(*) "Reasonable" = No "dictator," symmetric under candidate renaming, deterministic aside from tiebreaks which (if any) are random equally likely.


Does range voting maximize happiness? No (unfortunately). What does it maximize?

MAX-PLEASANT SURPRISE THEOREM (Ossipoff; proof trivial): Strategic Range (if that means Approval-style) voting maximizes (under reasonable assumptions) the number of "pleasantly surprised" voters and minimizes the number "unpleasantly surprised."

The reasonable assumption: strategic voters estimated expected utility (for them) E of the winner, then "approve" candidates above E.

"Surprise" is "pleasant" if winner has utility above expectation.


CONDORCET THEOREM (WDS, easy): Strategic Range (Approval) voting yields (under reasonable assumptions) a "Condorcet winner" whenever one exists.

The reasonable assumption: Approval voters act according to the following strategy: they order the candidates from best-to-worst, then select a "threshold" T, and they approve the candidates above T. They choose T to cause their vote to have the most impact.

The precise claim: Let N≥2. There does not exist an N-candidate tie-free election in which the Approval (A) and Condorcet (C) winners differ, provided that, if they were going to differ (A≠C) that all the approval voters would place their threshold T strategically under the assumption the winner was going to be either A or C, i.e. would place T somewhere between them.

Proof: Assume for a contradiction that A≠C. Then the approval voters will strategically place their thresholds between C and A. But that will cause C to be approved more times than A is approved (since C, being the Condorcet winner, is preferred over A by a majority). Hence the claim A was the Approval winner and A≠C, leads to a contradiction. Hence either A=C or there is no Condorcet winner C. Q.E.D.

Interpretation: Range does as well as Condorcet if strategic voters (actually can yield CWs more often) and better if honest voters.


DHILLON+MERTENS (1999) THEOREM: Normalized Range Voting ("normalized" meaning that every voter scores her favorite with the maximum allowable score and her most-hated candidate with the minimum) is the unique voting system (in situations with at least 3 voters and at least 5 candidates) obeying the following Arrow-like axioms:

INDIV:
If all voters are totally indifferent, so is society (note: "society" means the output of the voting system).
NONT:
Society is not always indifferent.
NOILL:
If every voter is indifferent except for one voter, then society is not always opposed to her.
ANON:
Permuting the voters has no effect.
CONT:
Continuity. This axiom is rather technical. But it has in mind that voter preferences are somehow continuously variable. [You will need to consult the original paper to get the full details; I think they are trying to say voter preferences must form a simply-connected compact set in a topological space, or anyhow some subset of those concepts?]
IRA:
If a "candidate" which happens to be a lottery among other candidates, is removed, then the election result (as a full ordering) is unaltered.
MON:
Monotonicity. It is messy to state Dhillon and Mertens's monotonicity axiom, which is why I am not stating it (see their paper); but suffice it to say that it actually is weaker than any of these three axioms (i.e. any of them imply it, but the reverse implications do not hold).


More theorems & computer explorations

Define "semi-honesty":
Your true feeling: A>B>C. Semi-honest: A=B>C. Lying: B>A. Better name: limit honesty.

Extended Gibbard-Satterthwaite theorem: With range voting

  1. If voter has perfect information about all other votes, then a best-strategic vote exists which is "semi-honest." (Contrast: no rank-order system satisfies this.)
  2. If voter has imperfect info about others then if ≤3 candidates a best-strategic vote exists which is "semi-honest." (Contrast: no rank-order system satisfies this.)
  3. In ≥4-candidate elections, 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
    1. 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),
    2. some semi-honest or honest vote must exist that is strategically optimal (in the sense of maximizing expected payoff).

Examples of 4-candidate range-voting elections where strategically-best vote is to lie (not even semi-honest).

Examples where best strategy in range voting is not "approval style" – when is it?

Honesty is not a bad strategy in range voting (computer experiments) hence Clay Shentrup argues, in view of the considerable difficulty of computing optimum-strategy range votes (he explains how) thos enaive people who just vote honestly may actually not be very "victimized"?

Analysis of how good various voting strategies are in 3-candidate range voting election – quite subtle

Benham's nasty anti-range example where strategists cause a social problem.

Strategic+Honest voter mix experiments with range voting; also victimization experiments


Criticisms of the 1999-2000 simulation-based BR study:

  1. Why didn't you try my voting method / utility model / voter-behavior model / etc?
  2. Old work based on computer simulations – not a theorem. BRs found numerically, not exact formulas. Doesn't identify best voting system – only knows about whatever voting methods were invented, programmed, & tried. What about infinite number not yet invented?!?!

(WDS 2008) – Best voting systems & closed form BRs

OPTIMALITY THEOREMS (WDS 2008): In a breakthrough, II, III, developed methodology for determining the exact best rank-order, and best range-style-ballot voting system (i.e. minimizing Bayesian Regret under some utility & voter-behavior models). Under the RNEM ("random normal elections model") the best rank-order ballot voting system for 3-candidate elections is Borda. Range and Approval both are superior to Borda for any mixture of honest and strategic voters in 3-candidate elections.

Sketch of Proof methods:

  1. Best voting system maximizing expected utility of winner can be got by "remembering history forever."
  2. In principle this allows computer to "converge to" best voting system.
  3. Can in some simple-enough probabilistic models (including RNEM) bypass the need for a computer!
  4. The best voting systems and their BRs are expressed in terms of certain multidimensional integrals. Develop large theory of how to write & do those integrals (if ≤4 candidates, they all can be done in "closed form").
  5. (There are also numerous related theorems, extensions to more candidates, other models, etc.)


Best Voting Systems via "remembering history forever"

  1. Perform infinite number of (simulated) elections.
  2. For each possible "combinatorial election" (i.e. table saying how many votes of each type were cast) remember expected utility of each candidate (in all historical occurrences of isomorphic elections).
  3. Eventually ("strong law of large #s") statistics converge.
  4. Best voting method (in whatever prob'c model generated the history) ≡
    Acquire votes. Find canddt (conditioned on those votes) with greatest expected utility based on historical memory. Elect him.

Automatic conversion of garbage into rigorous proofs of inequalities!

Interval arithmetic:

  1. In computer programs, replace all reals by intervals bracketing them. E.g. replace 5 by [4.9, 5.1].
  2. Replace + by "add interval endpoints and round top side upwards, bottom side downwards." [2,5]+[1,4]=[3,9].
  3. Replace -, ÷, ×, sin(x) similarly (don't divide by interval containing 0, but if do, get the complement of an interval).
  4. Run program. Output is interval giving rigorous lower & upper bounds on (exact) output!
  5. Want more than just bounds on a number, want inequalities on functions? Can do:

Works if A(x), B(x) have exact formulas. Also works for programs involving numerical integration, if know easy "derivative bounds" and "tail bounds" bounding numerical ∫≈&sum error.


Table I.2. Bayesian Regrets of various voting methods in 3-candidate (V→∞)-voter RNEM elections.
Voting method"Wrong winner" percentageV-1/2Regret
Magic Best00
BRBH=Best ratings-based (Honest voters, see sec. 6)18.70338(6)%0.0674537(2)
Honest Range22.35938(6)%0.0968636(3)
Honest Approval (mean as threshold)25.86333(3)%0.1300873(4)
Best rank-order-based (Honest Voters)=Borda25.86335(4)%0.1300876(2)
Strategic Approval (=Range, see theorem 13)30.98197(3)%0.1863856(2)
Honest Plurality=AntiPlurality33.99984(3)%0.2260388(4)
Magic best among the 2 frontrunners only1/3≈33.3333333%G1(3)-G1(2)=π-1/2/2≈0.282094792
Strategic Plurality (=Borda=IRV=Condorcet=BRBH,
see theorems 8 & 13)
45.43326(5)%(3/2)π-1/2-21/2/π≈0.3961262173
Random winner=Strategic AntiPlurality2/3≈66.6666667%(3/2)π-1/2≈0.8462843754
Worst winner100%-1/2≈1.6925687506

Why do Approval & Borda have same BRs and same wrong-winner probabilities [V→∞ honest voters in (≤3)-canddt RNEM elections]??

Core idea behind proof: "Don Saari's planar geometrical picture."

Although 3-candidate Borda and Approval votes v seem 3-dimensional, really only 2D because OK to project into plane v1+v2+v3=0.

In this plane, the 6=3! allowed Borda votes

(-1, 0, +1),    (-1, +1, 0),    (+1, 0, -1),    (+1, -1, 0),    (0, -1, +1),    (0, +1, -1),

are vertices of a regular hexagon. (Non-Borda weighted positional systems ⇒ irregular hexagons.)

The 6=23-2 non-silly approval votes (rescaled and translated to lie on the v1+v2+v3=0 plane)

(-2, +1, +1),    (+1, -2, +1),    (+1, +1, -2),    (+2, -1, -1),    (-1, +2, -1),    (-1, -1, +2)

also vertices of regular hexagon.

Up to a scaling by a factor of √3 (which cannot matter) and rotation by 30 degrees: same hexagon!


BRBH≡The best rated-ballot voting system (3-canddt elections, honest voters, RNEM)

THEOREM I.12: It's range voting ("honest" means rate favorite +1, worst -1, others linearly interpolated between based on utility) except that votes (-1, v, 1) are multiplicatively weighted by W(v) and then the candidate with the greatest weighted ∑score wins. Magic optimal weighting function:

W(v) = (3π)1/2(3+v2)-1/2,     |v|<1.








Table II.1. Wrong winner percentages and V-1/2Regrets for voting methods under N-candidate V-voter RNEM with V→∞. Honest Range Voting has less regret than best rank-order voting system for each N, 3≤N≤31. If instead have strategic voters, then same thing happens (at least, if distinction between "pseudo-best" and "best" is ignored) indicated by comparing "strategic approval=range" versus the strategic rank-order systems. When N=4, strategic range voting is also superior to the best "semi-strategic" rank-order system, which is "top-2" voting.
line
#
#Canddts→
↓Voting Method
N=4N=5N=6N=7N=8N=9N=31
1Magic Best0%, 00%, 00%, 00%, 00%, 00%, 00%, 0
2Honest Range22.50%,
0.08299
22.28%,
0.0731
21.97%,
0.0657
21.67%,
0.0602
21.38%,
0.0559
21.10%,
0.0523
18.13%,
0.0279
3Honest Best Ranked27.83%,
0.1289
28.64%,
0.1236
28.93%,
0.1174
28.96%,
0.1113
28.86%,
0.1057
28.69%,
0.1005
23.90%,
0.0504
4Honest Borda27.91%,
0.1297
28.85%,
0.1255
29.32%,
0.1207
29.55%,
0.1161
29.67%,
0.1120
29.71%,
0.1083
29.31%,
0.0786
5Honest Strat-Best-Ranked30.44%,
0.1553
33.92%,
0.1767
36.05%,
0.1879
37.35%,
0.1925
39.03%,
0.2033
40.73%,
0.2159
52.88%,
0.3052
6Mean-Thresh Approval31.75%,
0.1695
35.96%,
0.2000
39.15%,
0.2245
41.65%,
0.2444
43.70%,
0.2613
45.41%,
0.2756
59.28%,
0.4060
7Strategic Approval=Range37.25%,
0.2357
41.59%,
0.2728
44.79%,
0.3016
44.26%,
0.3244
49.22%,
0.3429
50.81%,
0.3578
62.41%,
0.4674
8Honest Top-237.60%,
0.2411
42.30%,
0.2829
46.73%,
0.3303
50.67%,
0.3780
54.10%,
0.4238
57.12%,
0.4675
82.67%,
1.0440
9Honest Plurality43.24%,
0.3230
50.05%,
0.4069
55.30%,
0.4804
59.51%,
0.5460
62.96%,
0.6046
65.85%,
0.6580
87.43%,
1.2717
10Best Semi-Strategic (Top-2)46.44%,
0.3928
  
11Magic Best-Of-250.00%,
0.4652
60.00%,
0.5988
66.67%,
0.7030
71.43%,
0.7880
75.00%,
0.8594
77.78%,
0.9208
93.55%,
1.4923
12Strategic PsuBest Ranked53.10%,
0.5096
56.81%,
0.5481
59.2%,
0.569
60.85%,
0.5806
61.94%,
0.5861
62.74%,
0.5878
68.27%,
0.5836
13Strategic Top-253.12%,
0.5273
  
14Strategic Borda54.33%,
0.5201
58.69%,
0.5716
61.44%,
0.6005
63.42%,
0.6201
64.95%,
0.6350
66.22%,
0.6677
76.41%,
0.7809
15Strategic Hon-Best-Rnkd54.70%,
0.5248
59.42%,
0.5835
62.49%,
0.6199
64.73%,
0.6465
66.52%,
0.6686
68.02%,
0.6880
80.30%,
0.9089
16Strategic Plurality58.25%,
0.5792
66.11%,
0.7128
71.43%,
0.8170
75.29%,
0.9020
78.21%,
0.9734
80.51%,
1.0349
94.03%,
1.6062
17Random Winner75.00%,
1.0294
80.00%,
1.1623
83.33%,
1.2672
85.71%,
1.3522
87.50%,
1.4236
88.89%,
1.4850
96.77%,
2.0565
18Magic Worst100.0%,
2.0588
100.0%,
2.3259
100.0%,
2.5344
100.0%,
2.7043
100.0%,
2.8472
100.0%,
2.9700
100.0%,
4.1129


Difficulties with strategic voters in (N≥4)-canddt elections

  1. In general-abstract setting ("votes"=bitstrings, "voting method"=algorithm) seems no meaning to terms "honest" & "strategic" voting. But if rank-order or ratings-type ballots, meanings exist.
  2. Also in "games" is no such thing as "best strategy" if #voters≥3.
    ∴ Only reasonable way to model "strategy" is specify a plausible behavior.
  3. Most of our investigations assume moving-average strategy:
    "God" (or Gallup) pre-announces ordering of candidates in decreasing order of a priori election chances. Each voter gives max-permissible vote to the best among the 2 frontrunners, min-permissible to other, then going down the order gives each canddt max or min depending on whether utility > or < mean(utility of preceding canddts).
  4. When N≤3, best rank-order system is Borda (for honest voters, strategic, or any mixture). But when N≥4 the best voting system depends on voter-honesty fraction H.
  5. The best system would abuse its knowledge of "God's order." Unacceptable.
  6. So demand "pseudo-best" system, or equivalently "best weighted positional" system.
  7. RNEM ⇒ a certain exact formula (known sum involving binomials) for the optimum N weights.
  8. But... sometimes weights can increase! Cure: replace increasing-weight-blocks with block-mean. These "corrected weights" still obey optimality-condition that Weightk=Expected utility of canddt k, conditioned on that (strategic) vote.



RNEM = Random Normal Elections Model

Ultra-simple mildly-realistic model (generalizes "impartial culture"): "All elections equally likely."


Bayesian-Regret as N·V-dimensional multiple integral

BR(E,M) = ∫∫...∫ [Maxj(Uj) - Utility(WinnerE,M)] ProbDensity(U1,U2,...UNV) dU1 dU2... dUNV

Integral over all NV-dimensional space. "Election winner" depends on the rules of the election method E (saying how "winner" determined from "votes") and the voter-behavior model M saying how voters generate their votes from their utilities.

In RNEM, the best rank-order system is weighted-positional with
WeightK=expected utility of the canddt that a given random voter ranks Kth
(in given utility, voter-distrb'n & -behavior models; weights expressible as N-dim'l ∫)
Immediate consequence: Borda optimal (among rank-order voting systems) if N≤3 canddts.

"Correlation-Based method" allows expressing BR as only (≤2N)-dimensional integral in V→∞ limit (for many voting methods under RNEM)

BR(E,M) = ∫∫...∫ ∫∫...∫ [Maxj(Uj) - WinnersUtilE(V1,V2,...VN, U1,U2,...,UN)] ·
ProbDensE,M(U1,U2,...,UN, V1,V2,...VN) dV1dV2...dVN dU1dU2...dUN

The correlation-based method for finding BR(E):

  1. Compute the correlations, means, variances amongst the Uj and Vk, by evaluating certain (≤N)-dimensional integrals.
  2. We now understand the joint ellipsoidal-normal ProbDens for the Uj and Vk. Do the (≤2N)-dimensional integral to find BR.
    [Sometimes even-lower dimensionality due to "reduced rank" matrices & tricks; instead of BR also can evaluate "wrong winner probability" by same method.]

How to do these N- and 2N-dimensional integrals?


Schläfli functions for dummies

THEOREM: Any N-dimensional multiple integral with

Can be expressed in closed form. Formula may involve

matrix-stuff, square-roots, exp(z), ln(z), trig(z), arctrig(z), Li2(z), Li3(z).

PROOF SKETCH:

Good news: hlinked to my paper is world's first computer program to output Schläfli fn closed forms for N≤5.

Bad news: The formulas get exponentially hairy when N large:
N=4 ⇒ Murakami formula 1 page long.
N=7 ⇒ perhaps 500,000 pages (estim.) when fully expanded


Normal order statistics (also called "Rankits")

Definition:

Gk(N) = Expected value of the kth greatest of N independent standard normal deviates (1≤k≤N).

Formula as 1-dimensional integral:

Γ(k)Γ(N+1-k) Gk(N) = -Γ(N+1) ∫-∞<y<∞ y F(y)k-1 [1-F(y)]N-k F'(y) dy

where
F'(y)=(2π)-1/2exp(-y2/2) is the standard normal density;
F(x)=[1+erf(2-1/2x)]/2 is the CDF of (i.e. integral dy from -∞ to x of) the standard normal density;
[Formula valid for any probability density F'(y), not just normal, arises since kth smallest of N i.i.d. random deviates has F(y) that is "Beta(k, N+1-k)-distributed."]

By symmetry:

Gk(N) + GN+1-k(N) = 0.

Of particular interest: G1(N) = expected value of maximum of N independent standard normal deviates:

G1(N)   =   N∫-∞<y<+∞ y F(y)N-1 F'(y) dy

Only need the G1(N) because all other Gk(N) can be computed in terms of them alone, via (Federer 1951) recurrence

Gk+1(N) = [N Gk(N-1) - (N-k) Gk(N)]/k.

Table I.4: G1(N), the expected max of N independent standard normals, versus N.
NG1(N)NG1(N)
10 111.58643635190800
2π-1/2≈0.56418958354775 121.62922763987191
3(3/2)π-1/2≈0.84628437532163 131.66799017704913
4-1/2[1/2+π-1arcsin(1/3)]≈1.02937537300396 141.70338155409998
5(5/2)π-1/2[1/2+(3/π)arcsin(1/3)]≈1.16296447364052 151.73591344494104
61.26720636061147 161.76599139305479
71.35217837560690 171.79394198088269
81.42360030604528 181.82003187896872
91.48501316220924 191.84448151160382
101.53875273083517 201.86747505979832
2002.7460424474511520003.435337162
200004.018789262000004.53333091

Previous authors found closed forms for Gk(N) when N≤5. Using our Schläfli function and moment theory we know closed formulas also exist for all the G(6), and G(7) (involving dilogs); and if also allow trilogs then closed forms exist for all the G(8) and G(9) too. [But the G1(6) formula is about 4 pages long!]


Some sample integrals (arise when computing correlations & means)

Let P(x)=F'(x)=(2π)-1/2exp(-x2/2) be the standard normal density function. Then:

  1. -∞<x<+∞ P(x) dx = 1

  2. -∞<x<+∞ x P(x) dx = 0

  3. ∫∫-∞<x,y<+∞ |y-x| P(x) P(y) dx dy = 2π-1/2 ≈ 1.1283

  4. ∫∫∫-∞<x<y<z<+∞ P(x) P(y) P(z) dx dy dz = 1/6

  5. ∫∫∫-∞<x<y<z<+∞ z P(x) P(y) P(z) dx dy dz = G1(3) = (3/2)π-1/2 ≈ 0.8463

  6. ∫∫∫-∞<x/2+z/2<y<z<+∞ y P(x) P(y) P(z) dx dy dz = (31/22-3)π-1/2/12 ≈ 0.02182

  7. ∫∫∫-∞<x<y<z<+∞ z2 P(x) P(y) P(z) dx dy dz = 31/2/(12π)+1/6 ≈ 0.2126

  8. ∫∫∫-∞<x<y<z<+∞ y2 P(x) P(y) P(z) dx dy dz = (π-31/2)/(6π) ≈ 0.07478

  9. ∫∫∫-∞<x<y<z<+∞ x y P(x) P(y) P(z) dx dy dz = 31/2/(12π) ≈ 0.04594

  10. ∫∫∫-∞<x<y<z<+∞ y (2y-x-z)/(z-x) P(x) P(y) P(z) dx dy dz =
    = ∫0<u<1∫∫-∞<x<y<+∞ (uy+[1-u]x) (2u-1) P(x) P(uy+[1-u]x) P(y) dx dy du
    = (ln3-1)π-1/2/2 ≈ 0.02782

Correlations in any Weighted Positional Voting system:

Weighted-positional voting system, N-candidate election, defined by N "weights" W1≥W2≥...≥WN. We "standardize" so mean-weight=0 and mean-square-weight=1.

LEMMA (WPV correlations 1): The voteivotej correlation in the RNEM is

LEMMA (WPV correlations 2): The voteiutilityj correlations in the RNEM obey

where note (to justify simplifications) that variance of each vote is 1 and variance of each utility (since is standard normal deviate) also is 1.


Reversal Symmetry Theorem:

Reversing the order of, and negating, the weights in a (standardized) weighted positional voting system, yields the same vote-utility (and vote-vote) correlations as for the original voting system; and hence the same wrong-winner probabilities and BR values arise in the V→∞ limit (for any fixed number N of candidates, under RNEM).

Example: AntiPlurality and Plurality voting have the same regrets and same wrong-winner probabilities in the V→∞ limit. But (apparently) for any finite #voters V, AntiPlurality does worse (by both measures)!


The YN-model

Definition:

Optimal/Pessimal Theorem:

  1. "Honest" range voting always elects YYYY. (Optimal.)
    [Proof: all utility-ranges same, so honest range voting = honest utility voting ⇒ maximizing vote-total always maximizes utility-total for winner.]
  2. But plurality can elect NNNN (and make YYYY finish last)! (Pessimal.)
    [Nice to have a voting system "property" that acknowledges that issues exist.]
    Contrived Example (Brams): 31-voter, 4-issue, 16-candidate election:

    candidatevotescandidatevotes
    YYYY0YNYY4
    YYYN4YNYN1
    YYNY4YNNY1
    YYNN1YNNN1
    NYYY4NNYY1
    NYYN1NNYN1
    NYNY1NNNY1
    NYNN1NNNN5
  3. I've cooked up ∞ examples where IRV, Approval (top F fraction of available candidates approved, with F any fixed value 1/N≤F<1-1/N), Borda, and Condorcet elect NNNN.
  4. Indeed, I have ∞ examples where Borda & Condorcet order all 2D finishers exactly in reverse order: NNNN first, more Ys ⇒ finish further back, YYYY last!

Random-Voter YN model

Contrived worst-case voter-distributions attackable as unrealistic "cherry=picking."
∴ Examine random voters:

Range=Optimal & Others=Worse Theorem:

  1. Honest range voting always elects YYYY. (Optimal.)
  2. Honest plurality voting: if D≥4, for some constant C>0 (C independent of D):
    Prob(elects candidate with over 50% Ns in name) > C.
  3. Honest approval voting, if D≥4 and voters approve candidates disagreeing on ≤F-fraction of the issues (any fixed F with 0≤F<50%): same thing. And if F=50% then
    Prob(elects candidate with at least a positive constant fraction of Ns in name) > C.
  4. Latter inequality also true for Borda.

(In all these cases, get significant regret.)

Conjecture: Prob(no Condorcet winner exists)→1 so the question for Condorcet methods depends entirely on their "backup" method invoked when no CW.


Continuum issues model

Definition:

Condorcet=Optimal (in V→∞ limit) & Others=Not Theorem:

  1. With probability→1 with V→∞ honest voters:
    1. Condorcet winner exists;
    2. It is the candidate closest to C;
    3. And that is the candidate maximizing ∑utility.
  2. Honest approval voting also elects the best-utility winner with probability→1 in some voter behavior models, e.g, "voter approves candidates closer than T, and each voter chooses T independently from some fixed everywhere-positive ProbDensity on (0, ∞)."
  3. But there are simple 3-candidate 1D examples showing RV, plurality, Borda, every weighted positional system, IRV each can deliver nonoptimal winner with probability→1.

Proof:
1A & 1B: Steal results of Davis, de Groot, Hinich 1972 + some probability theory.
1C & 2: Steal Fourier result of Beckner 1975.
3: Example for IRV: Place three candidates at -0.01, 0, +0.01 and voters distributed standard normal on real line.

-------------X----------------------0-----------------------X-------------
Although the Condorcet winner(hence max-utility by 1B), 0 will be the plurality-loser and IRV will eliminate it in first round. With the sharp-peaked utility function U(S)=ε/(ε2+S2), where S is distance (concave-∪ except in ε-wide region) RV also fails to elect 0.
3: Example for Borda: Place three candidates at -0.10, -0.11, +0.12 and voters standard normal distibution on real line.
---------------X-X------------------0-----------------------X-------------
Best winner would be -0.10 (by 1B) but -0.11 wins with Prob→1 for all suffic. small ε. (Similar 1D examples for the other systems.) Q.E.D.

But: L1 distance, utilities based on dot products not distance, or voter-distrib arbitrarily-slightly aspherical ⇒ RV can be (& usually is) better than Condorcet.

Yee diagrams: Thm shows Condorcet methods ⇒ "Voronoi Diagram."


Conclusions

  1. Bayesian Regret (BR) = the correct quantitative framework for measuring quality of single-winner voting systems.
  2. Measurements-via-sims: Range voting (RV) better than all(?) voting methods political scientists proposed up to 90s – robustly to altering simulation assumptions.
  3. Darwin: Two kinds of social insects use RV. (So does your immune system.)
  4. Quantitatively: RV seems more important than all(?) other democracy reforms, comparably important to invention of democracy, though a bit less important than curing worst diseases. Many democracy-reformers have mis-prioritized goals.
  5. Theorems saying RV good and/or best: Under RNEM, RV superior to every rank-order-ballot voting system (and robustly to all small perturbations) if 3-9 candidates, any honest+sttrategic voter mix.
    In 3-canddt RNEM elections, approval voting also superior (but not robustly; and it is dominated by RV; and Borda is superior to Approval if #candidates≥4 and enough honest voters).
    Under YN-model with honest-voters: RV optimal while most other things can be pessimal and in randomized scenarios significantly non-optimal.
  6. Theorems saying RV not best: Under a certain continuum issues-based politics model, Condorcet voting (and Approval too under certain voter-behaviors) is asymptotically optimal while range isn't (but A & C's superiority not robust against arbitrarily-tiny perturbations).
    Under a certain contrived strategic-voting model resembling "figure skating judging," range voting inferior to "trimmed mean" (e.g. median-based) RV, but simulations say plain RV better under more-politically-realistic assumptions.
    With honest voters in 3-canddt elections, the optimum ratings-ballot-based system is known and is superior to RV, but it's worse if honesty-fraction<91%.

How can you help?



Return to main RV page