"Random normal elections" model – computer (and human) results
The model.
There are C candidates and V voters.
Each voter has a "utility value" for the election of each candidate.
All V·C of these values are independent standard normal random numbers.
For voting systems based on rank-order ballots, all voters give their
honest ordering as their vote.
If range voting is used,
then each voter gives the best candidate 100, the worst 0, and the rest
are honestly linearly interpolated.
If approval voting is used,
then each voter approves of candidates above the midway point between
the best and worst candidates.
Of course, in the real world, voters do not have to act these ways.
We are assuming they act these ways only for the purpose of generating
the tables below. If they act other ways, or if the underlying
probablistic model were different,
then different tables would result.
This model in some sense gives a uniform sampling of all mathematically-possible elections.
It is not claimed to be especially politically realistic.
Instead its main goals are simplicity and reproducibility of the
computer results below.
(This model has been called the "Impartial Culture" in the literature.)
There is a lot to be learned from this data despite the
considerable amount of political realism that it lacks.
Determining this data via Monte Carlo simulation required about a month of computer time.
To understand our terminology, it may help to consult the glossary.
If you want computer simulations that seem more politically-realistic, try papers #56 and #95
here, or you could examine our
list of genuine national presidential elections, or
you could check out our election-simulator IEVS or
the
Bayesian Regret framework.
If you want theorems in this model, see the bottom of this web page.
1. How often do "Condorcet winners" exist? (A CW is a candidate who beats each opponent pairwise.)
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
500
999
2000
5000
V=13 voters
100%
92%
84%
77%
71%
66%
61%
58%
54%
52%
49%
47%
45%
43%
36%
20%
12%
7%
2%
5123 voters
100%
91%
82%
75%
68%
63%
58%
55%
51%
48%
45%
43%
41%
39%
32%
16%
9%
5%
∞ voters
100%
91%
82%
75%
69%
63%
59%
55%
51%
48%
45%
43%
41%
39%
32%
16%
9%
5%
2%
1%
0.6%
0.3%
2. Given that a CW (beats-all winner) exists – how often is it the range-voting winner?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
100%
85%
84%
77%
77%
77%
77%
77%
77%
77%
77%
77%
78%
78%
79%
83%
91%
92%
5123 voters
100%
84%
80%
78%
77%
77%
77%
77%
77%
77%
77%
78%
78%
78%
78%
83%
87%
92%
3. Given that a CW exists – how often is it the approval-voting winner?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
999
V=13 voters
100%
76%
68%
64%
61%
59%
58%
57%
56%
55%
54%
54%
53%
53%
51%
46%
43%
42%
33%
5123 voters
100%
76%
69%
65%
63%
61%
60%
60%
59%
59%
59%
58%
58%
58%
57%
60%
61%
64%
4. Given that a CW exists – how often is it the plurality-voting winner?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
100%
81%
71%
64%
58%
54%
50%
47%
45%
42%
40%
38%
36%
35%
29%
15%
9%
4%
5123 voters
100%
76%
64%
56%
50%
45%
41%
37%
34%
32%
30%
28%
26%
25%
20%
7%
2%
1%
5. Given that a CW exists – how often is it the best (greatest utility sum) winner?
#candidates:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
13 voters
80%
75%
73%
73%
73%
73%
73%
73%
74%
74%
75%
75%
75%
76%
77%
82%
89%
92%
5123 voters
79%
74%
72%
72%
72%
72%
72%
73%
73%
73%
74%
75%
75%
76%
77%
83%
89%
93%
6. How often do the range and best (greatest utility sum) winners agree?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
80%
78%
78%
79%
79%
79%
80%
80%
80%
80%
81%
81%
81%
81%
81%
84%
85%
86%
5123 voters
79%
78%
78%
78%
78%
78%
79%
79%
79%
79%
80%
80%
80%
80%
81%
83%
85%
85%
7. How often do the range and approval winners agree?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
100%
85%
76%
71%
66%
62%
60%
57%
55%
53%
52%
50%
49%
48%
44%
33%
27%
22%
5123 voters
100%
86%
78%
72%
67%
64%
61%
59%
57%
55%
54%
52%
51%
50%
46%
37%
32%
27%
8. How often do the range and plurality winners agree?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
100%
74%
63%
55%
50%
46%
42%
40%
37%
35%
33%
32%
30%
29%
24%
14%
9%
5%
5123 voters
100%
73%
61%
52%
47%
42%
38%
35%
32%
30%
28%
26%
25%
24%
19%
8%
4%
2%
9. How often do the approval and plurality winners agree?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
100%
69%
55%
46%
39%
34%
30%
27%
25%
23%
21%
20%
18%
17%
14%
6%
3%
2%
5123 voters
100%
67%
53%
43%
37%
32%
28%
25%
22%
20%
19%
17%
16%
15%
11%
4%
2%
1%
10. How often do the approval and best (greatest utility sum) winners agree?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
80%
74%
69%
65%
61%
58%
56%
54%
52%
51%
49%
48%
47%
46%
42%
32%
26%
22%
5123 voters
79%
74%
69%
65%
62%
60%
57%
55%
54%
53%
51%
50%
49%
48%
45%
37%
32%
28%
11. How often do the plurality and best (greatest utility sum) winners agree?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
80%
67%
59%
53%
48%
45%
42%
39%
37%
35%
33%
32%
30%
30%
25%
14%
9%
5%
5123 voters
79%
66%
57%
50%
45%
41%
37%
34%
32%
30%
28%
26%
25%
24%
19%
8%
4%
2%
12. How often do the plurality and plur+top2-runoff winners agree?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
100%
84%
78%
74%
70%
68%
67%
65%
64%
64%
63%
62%
62%
61%
58%
58%
55%
54%
5123 voters
100%
81%
73%
70%
67%
65%
63%
61%
61%
60%
59%
58%
58%
58%
56%
53%
52%
51%
13. How often do the plur+top2-runoff and best (greatest utility sum) winners agree?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
80%
69%
63%
59%
55%
51%
49%
46%
44%
42%
41%
39%
38%
37%
31%
19%
12%
7%
5123 voters
79%
68%
61%
56%
52%
48%
44%
42%
40%
38%
36%
35%
33%
32%
26%
13%
7%
4%
14. Given that a CW exists – how often is it the IRV winner?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
100%
96%
92%
89%
86%
83%
81%
78%
76%
74%
71%
70%
69%
68%
61%
43%
29%
19%
5123 voters
100%
96%
93%
90%
87%
85%
83%
81%
79%
78%
77%
76%
75%
73%
68%
51%
38%
29%
15. How often do the IRV and range winners agree?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
100%
79%
70%
65%
60%
57%
54%
52%
50%
49%
46%
45%
44%
43%
38%
27%
20%
14%
5123 voters
100%
79%
70%
65%
61%
57%
55%
53%
52%
50%
49%
48%
46%
45%
42%
30%
24%
18%
16. How often do the IRV and best (greatest utility sum) winners agree?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
80%
71%
65%
61%
57%
54%
52%
50%
49%
47%
46%
45%
44%
43%
39%
28%
21%
14%
5123 voters
79%
70%
65%
60%
57%
55%
53%
52%
50%
49%
48%
47%
45%
44%
41%
30%
24%
18%
17. How often do the IRV and plur+top2-runoff winners agree? (Reason not 100% when C=3 is: different tiebreaking?? or bug?)
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
100%
95%
84%
77%
72%
68%
65%
62%
60%
57%
55%
54%
52%
51%
46%
36%
34%
28%
5123 voters
100%
90%
78%
70%
63%
57%
53%
50%
47%
44%
41%
38%
37%
35%
29%
14%
8%
5%
18. Given that a CW exists – how often is it the plur+top2 runoff winner?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
V=13 voters
100%
92%
86%
80%
76%
71%
68%
64%
61%
58%
55%
53%
52%
50%
42%
23%
13%
7%
5123 voters
100%
91%
82%
74%
68%
63%
59%
54%
51%
49%
45%
42%
41%
39%
30%
12%
4%
2.5%
19. Given that a CW exists – how often is it the Borda winner?
#candidates:
C=2
3
4
5
6
7
8
9
10
15
20
31
50
100
200
500
1021 voters
100%
87%
85%
88%
∞ voters
100%
90%
87%
85%
85%
84%
84%
84%
84%
85%
86%
90%
93%
96%
≈98%
20. How often is the Borda winner also a Condorcet Winner?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
500
1000
∞ voters
100%
82%
72%
64%
57%
54%
49%
46%
43%
40%
39%
37%
34%
33%
27%
14%
8%
5%
2%
1%
21. How often is the Borda winner an untied-Copeland winner?
#candidates:
C=2
3
4
5
6
7
8
9
10
11
12
13
14
15
20
50
100
200
500
1000
∞ voters
100%
82%
72%
66%
63%
62%
61%
60%
59%
59%
58%
58%
58%
58%
58%
61%
64%
68%
73%
≈76%
Want even more such data?
Look here for more such data (from more-recent programs);
and for the alternative
"Dirichlet" probability model, see the
puzzles including
puzzle #88.
Some theorems on Condorcet winners:
Jerry S. Kelly:
Voting Anomalies, the Number of Voters, and the Number of Alternatives,
Econometrica 42,2 (1974) 239-251.
Robert M. May: Some mathematical remarks on the paradox of voting,
Behavioral Science 16 (1971) 143-151.
Richard Niemi & Herbert Weisberg: A mathematical solution for the probability
of the paradox of voting,
Behavioral Science 13 (1968) 317-323.
M.B.Garmen & M.Kamien: The paradox of voting, probability calculations,
Behavioral Science 13 (1968) 306-316.
Frank DeMeyer & Charles R. Plott:
The Probability of a Cyclical Majority,
Econometrica 38,2 (March 1970) 345-354.
B.Jones, B.Radcliff, C.Taber, R.Timpone:
Condorcet winners and the Paradox of voting: probability calculations for weak preference orders,
Amer.Polit.Sci.Review 89,1 (1995) 137-144.
These authors consider the probability P(V,C) that there will not be a Condorcet winner
in a C-candidate, V-voter election. Kelly (theorems 9 and 10)
proves that P(V+2,C)<P(V+1,C)>P(V,C) whenever V≥2 is even
for all C≥3.
Kelly conjectures P(V+2,C)>P(V,C)
for all V≥3 (and also V=1) for all C≥3.
Kelly also conjectures P(V,C+1)>P(V,C)
for all V≥5 (and also V=3) for all C≥2.
May gives a rather sketchy and erroneous "proof" that
P(∞,C) = 1 - 21/28πe-2 (lnC)1/2/C + lower order terms
as C→∞, except he had the wrong constant factor.
May's ideas are definitely correct and good;
I just am skeptical of his
execution in view of the sketchiness of his paper and the fact, as I will soon
demonstrate, that it contains a large number of errors. I believe this particular
result was wrong and my correction of his constant factor has been confirmed by my own much
simpler re-derivation and numerical tests.
More importantly for us, May also proves P(3,C)→1.
That proof is definitely incorrect, but can be repaired.
By combining Kelly's conjecture with May's corrected result,
we would get
limC→∞ P(V,C)=1 for each odd V with 3≤V≤∞.
May seems to think he proved this, but I only think he proved it for V=3 and V=∞,
not the numbers between (although I have no doubt it is true).
May's claim that P(3,C)→1 can be shown as follows. Let P(3,C)=1-C·Q(3,C)
[May stated this formula incorrectly with a 3 incorrectly replacing the middle C]
where Q(3,C) is the probability that in a 3-voter, C-candidate election, candidate #1
is a Condorcet winner. Next, we have the exact formula
[May stated this formula incorrectly, omitting the final "-1"]
which can be derived as follows: candidate 1 wins if and only if, for each
other candidate X, X beats 1 in either 0 or 1 votes. That happens
in
[May did not notice this summability.]
Now, if we want to understand the asymptotic behavior of Q(3,N) for N→∞,
we realize that the sum can be regarded as Riemann and hence
approximated as a double integral over a triangle. We use Stirling's formula and do the
integral to get an asymptotic:
Q(3,N) = (1/2) (π/N)3/2 [ 1 - 0.75/√N + O(N-1) ]
where the "0.75" and everything after it is empirical and is not necessarily an exact result.
[May had the same claimed result except he believed the error term would
be larger, of order ln(N)/√N. I doubt that. My Q-formula here empirically is good
enough for 10% accuracy for every N≥2.]
Obviously, N·Q(3,N)→0 when N→∞, proving P(3,N)→1.
Partial repair:
A correct proof that P(∞,C)→1 when C→∞ was provided by
Colin E. Bell:
A random voting graph almost surely has a Hamiltonian cycle when the
number of alternatives is large,
Econometrica 49,6 (Nov. 1981) 1597-1603.
Another very simple proof by me is here.
Various specific exact-rational (and approximate decimal) values of P(V,C) include
P(V,2)=P(V,1)=P(1,C)=0,
P(3,3)=1/18≈0.05556,
P(3,4)=1/9≈0.1111,
P(3,5)=4/25≈0.1600,
P(3,6)=91/450≈0.2022,
P(3,15)≈0.417,
P(5,3)=5/72≈0.06944,
P(5,4)=5/36≈0.1389,
P(5,5)=7981/40000≈0.1995,
P(5,6)≈0.252,
P(5,15)≈0.504,
P(7,3)=875/11664≈0.07502,
P(7,4)=875/5832≈0.1500,
P(7,5)≈0.21533,
P(7,6)≈0.270,
P(7,15)≈0.536,
P(9,3)=65485/839808≈0.07798,
P(9,4)=65485/419904≈0.1560,
P(9,5)≈0.224,
P(9,6)≈0.282,
P(9,15)≈0.554,
P(∞,3)≈0.08774,
P(∞,4)=2P(∞,3)≈0.17548,
P(∞,5)≈0.25131,
P(∞,6)≈0.31524,
P(∞,7)≈0.36918,
P(∞,10)≈0.4887,
P(∞,20)≈0.6811,
P(∞,30)≈0.7648,
P(∞,40)≈0.8123,
P(∞,50)≈0.843,
and conjecturally P(V,∞)=1.
Wm. V. Gehrlein & Peter C. Fishburn:
Probabilities of election outcomes for large electorates,
J. Economic Theory 19 (1978) 38-49,
give
exact expressions as definite integrals for P(∞,5) and
P(∞,6). They also evaluate as definite integrals these probabilities:
Prob(entire social ordering is transitive) = P(∞,3)≈0.08774
for three candidates and = 0.73946 with four candidates.
Prob(Borda and Plurality winners are the same)
= 1 for two candidates, and
= (123/144) + (3/(4π²)) arcsin( √(13)/4 )² ≈ 0.758338
with three candidates.
Prob(a Condorcet winner exists and it is the Borda winner) =
3/2 - (3/(2π)) [arccos(√(8)/3) + arccos(√(2)/3)] ≈ 0.822119
with three candidates. Consequently,
Prob(The Borda winner is the CW given that a CW exists)
= 0.822119/[1-P(∞,3)] ≈ 0.9012.
Prob(a Condorcet winner exists and it is the Plurality winner)≈0.690763
with three candidates. Consequently,
Prob(The Plurality winner is the CW given that a CW exists)
= 0.690763/[1-P(∞,3)] ≈ 0.7572.
Jones et al. 1995 also calculate (by Monte-Carlo simulation) these probabilities
in a model in which voters are allowed to express indifference between
two candidates. With a fixed number of candidates (either 3, 4, or 5),
they find that greater indifference tends
to decrease the probability of a Condorcet winner if the number of voters is small (<501)
but to increase it if the number of voters is large (≥501). That was only
a crude description; the true behavior is more complicated than just stated.
These increases and decreases can be considerable.
Theorems on Instant Runoff Voting (IRV)
Theorem:
In the random elections model, when the number V of voters tends to infinity, and
then the number C of candidates tends to infinity, the probability P that the IRV
and plurality voting winners differ, tends to 100%.
Proof sketch:
Consider the last K rounds of IRV where K is large but the number C of
candidates is much larger (both C/K² and K →∞).
If the plurality winner has not made
it into the final K rounds, we are done. So assume it has.
Then ask: what is the probability P it will survive the remaining K
rounds? The probability of survival is
∏2≤k≤K
(1-1/k)
= ∏2≤k≤K
(k-1)/k
= 1/K since the product "telescopes"
which goes to zero when K is made large.
This product is only valid if
the plurality winner has chance
1/k of getting eliminated in a round with k contestants,
and
if these probabilities are independent in each of the first K
rounds.
Neither is true, but both become true in the limit
we are talking about in the probabilistic model we speak of because
the effect of all of the vote transfers from the C-K
previously-eliminated candidates is going to act like a very large
amount of random noise.
This argument should suffice to prove that the (100%-P) goes to zero
when C→∞ like
Cε-1/3
for any fixed ε>0 no matter how small, but it is a weak argument, i.e. probably
a statement considerably stronger than this is true.