The mathematician woke up and saw there was a fire. He ran over to his desk, began working through theorems, lemmas, and hypotheses, and after a few minutes, put down his pencil and exclaimed triumphantly "I have reduced the matter to previously solved problems, thus proving that I can extinguish the fire!" He then went back to sleep.
This paper's accomplishment somewhat resembles the above joke. For 3-candidate voting systems in the RNEM, we have by plotting two curves demonstrated that range voting is superior (measured by Bayesian Regret) to the best rank-order voting system, for either honest or strategic voters, or any mixture (and approval voting also is except at 100% honesty where it equals but does not better Borda). But, strictly speaking, this was not a proof, because it does not exclude the possibility that through some miracle-conspiracy of arithmetic roundoff errors, or some miraculous incredibly sharp and high spike in one of the plotted curves, that the lower-regret curve might somehow manage to avoid being lower everywhere.
However, like the mathematician in the joke, we have proven that fire can be extinguished. Specifically:
It would probably be possible for a graduate student to now do the final step in about 1-10 weeks of computer programming and debugging. However, one has to ask whether it would really be worth that effort. There is no doubt the theorem is correct. If some graduate student announced "I have finally genuinely completed the proof and here is my 5000-line computer program which does it (the runtime of the program would be only seconds), which in turn rests on top of some commercial computer algebra system based on 1,000,000 lines of secret code plus a 500,000-line compiler, which in turn rests on top of a secret computer design involving billions of transistors" – then what? Would anybody then believe the result who does not already? And considering that humanity is pretty much incapable of rigorously verifying 5000-line (or 1,000,000-line!) computer programs as "bug-free" (although it would certainly be possible to run numerical spot checks that certain components of the code produce correct answers to high accuracy in test cases) would the confidence that everything is bug-free, be greater or less than the confidence inspired by the present much-simpler non-proof?
I have been asked why I claim that Bayesian Regret is the only correct way to objectively measure voting system quality. I'm tempted just to respond that statisticians over 200 years have pretty much come to a consensus that Bayesianism is the unique philosophically correct approach to statistics and objectively comparing the quality of different statistical estimators generally, and so ask them, not me. Also, I could respond that Bordley and Merrill both independently invented the Bayesian-Regret framework for comparative evaluation of voting systems (and before me), so again, ask them, not me. This argument was fought, and won, long ago, with a strong majority consensus being reached in every scientific area except economics, where (for rather obscure historical reasons) holdouts against the whole notion of "utilities" still are frequently encountered even in the 21st century.
For a somewhat deeper response, aimed particularly at those people, see /OmoUtil.html MAKE THIS WEB PAGE INTO A PAPER & CITE IT???
Our Bayesian Regret framwork and overarching technique for determining "best voting systems" in no way depend on the RNEM. Anybody who prefers a different and more-realistic model of voters is free to use it instead. (Our 1999-2000 computer results indeed did employ many other models and the superiority of range voting over all the rank-order-ballot based competitors tried, was very robust across models.)
I did not use the RNEM because I thought it was a highly-realistic model of elections. In many political scenarios, the opinions of voters about candidate C are correlated with their opinions about A and B; or the voters exhibit a large bias favoring A over B – either way directly contradicting, and revealing the unrealism of, the RNEM. "1-dimensional politics" (or 2D) models are more realistic in the former respect. The "Dirichlet model" where (in 3-candidate elections) the 3!=6 kinds of vote totals are assumed to be uniformly distributed on the 5-dimensional simplex
is more realistic in the latter respect. The reasons this paper focused on the RNEM are that it is
The so-called "impartial culture" (IC) is a degenerate special case of the RNEM that has been heavily studied by many political-science authors (IC is: all candidate-orderings equally likely by each voter independently). Despite IC's unreality, my personal experience is that the probabilities predicted by the IC model for various kinds of voting pathologies, usually agree tolerably respectably with attempts to measure frequencies of those pathologies in real life (where note that such real-life measurements usually are difficult, debatable, and noisy).
| Phenomenon | IC Probability | In real life |
|---|---|---|
| 3-canddt IRV is nonmonotonic | (14.7=12.2+2.47)% (two disjoint kinds of nonmonotonicity) | About 20% based on the 9 Louisiana governor elections |
| In 4-canddt Condorcet elections, adding new bloc of co-voting voters makes election result worsen in their view | Roughly (0.5 to 5)% depending on Condorcet flavor | ? |
| 3-canddt IRV eliminates a Condorcet Winner | 3.71% | Apparently 9 CWs eliminated in the 150 federal IRV elections in Australia 2007. (In "1-dimensional politics" models this phenomenon is more like 25-33% common.) |
| 3-canddt plurality voting winner same as "plurality loser" | 16.4% | Seems in right ballpark |
| 3-canddt IRV voting winner same as "IRV loser" | ≈2.5% | ? |
| 3-canddt IRV elections where adding new co-voting bloc causes election winner to worsen in their view | 16.2% | Apparently happens about 40% of time based on the 9 Louisiana governor elections |
| 3-canddt IRV voting "favorite betrayal" situation where a bloc of co-voting C voters can improve election winner in their view by not voting their favorite C top (does not count nonmonotone situations where this makes C win) | Apparently happens about 40% of time based on the 9 Louisiana governor elections | |
| 3-canddt election features Condorcet cycle | [3arcsec(3)-π]/(2π)≈8.78% (Gilbaud 1952) | About 1% (Tideman 2006's theoretical extrapolation from real-life data); some models of "1-dimensional politics" predict 0% |
| "Majority-top winner" exists in 3-canddt election | 0 | Happened for 50% of Australian federal IRV seats in 2007 election and 44% of the 9 Louisiana governor elections. (In "Dirichlet model" happens 9/16=56.25% of time.) |
But there certainly are some probabilities which IC considerably mis-estimates. Regenwetter et al explain in chapter 1 of their book theoretical reasons why IC would be expected to maximally overestimate the probability of "Condorcet cycles" in 3-candidate elections. And indeed the IC theoretical prediction 8.78% is a large overestimate of the real-life rate of approximately 1% (albeit Condorcet cycles seem fairly common in legislative votes since they are intentionally created as part of "poison pill" legislative tactics). Even worse, "majority-top winners" occur zero percent of the time in IC 3-candidate elections in the V→∞ limit but actually are quite common in real life. The "Dirichlet model" predicts 56.25%.
The reader may ask "why have you only focused on 3-candidate elections? What about 4, 5, and 6?" The answer is that the techniques in this paper will easily permit the reader to calculate the honest-voter regrets to, say, 4-digit accuracy and thus produce a convincing non-proof that range voting is superior to the best rank-order system, with honest voters, for those numbers N of candidates also. (Indeed, I have already done essentially this, albeit less cleanly, so I'm sure this will work.) I focused on the 3-candidate case because it is specially nice because closed formulas exist and hence this non-proof can be converted into a genuine proof. (Also, of course, 3 is the most important nontrivial number.) Perhaps in the 4-, and definitely in the 5- and 6-candidate cases, available techniques will not yield closed formulas. It nevertheless should be possible – just trickier – to produce rigorous computer-aided proofs, because our techniques always yield formulas expressed in terms of integrals of linear functions over nonEuclidean simplices, and thanks to the simple geometry behind them, there ought to be ways to evaluate those integrals numerically with provably small error. But to make this also work for strategic voters (or honest+strategic mixtures) would require first acquiring an understanding of the best rank-order voting systems in that environment. That understanding is unavailable in the present pages when N≥4, but I will start the ball rolling by claiming that the best rank-order system for strategic voters in 4-candidate RNEM elections, is "vote for two," i.e. the weighted positional system with
Strategic voters will rank the two "frontrunners" 1st and 4th (best first), then the two non-frontrunners 2nd and 3rd (best top).
Going further, the reader asks "what about 7, 8, 9,..., candidate elections? I want a theorem that range voting is better than the best rank-order system for every number N≥3 of candidates!" That is a good question. It is often possible to prove ∫A(x)dx>∫B(x)dx despite the absence of closed formulas for either integral. An interesting task for future authors, then, would be to develop suitable "comparison theorems" enabling such proofs.
Another question is: "what about other statisticial models besides RNEM (such as D-dimensional politics models, etc)?" Can future authors prove analogous results to ours in those models?
References for section 10:
G.Th.Guilbaud: Les théories de l'intérêt général et le problème logique de l'agrégation, Economie Apliquée 5,4 (1952) 501-584.
E.T. Jaynes: Probability theory: The logic of science, Cambridge Univ. Press 2003.
M.Regenwetter, B.Grofman, A.A.J.Marley, I.M.Tsetlin: Behavioral social choice: probabilistic models, statistical inference, and applications, Cambridge University Press, New York 2006.
Nicolaus Tideman: Collective Decisions and Voting: The Potential for Public Choice, Ashgate 2006.