The winning strategy for random ballot is not what I thought it was

In a previous post I used a normal distribution to show that if you didn’t have a majority of the vote then your probability of winning a majority of seats in a random ballot was maximized if you had an equal representation in every constituency.

Without the normality assumption, this turns out to be false. What is true is the following:

Theorem: Let \(W_i \sim \mathrm{Bernoulli}(q_i)\) be independent. Let \(q\) be a vector which maximizes \(P(\sum W_i > t)\) subject to \(\sum q_i = \mu\). Then if \(q_i \neq 0, 1\) and \(q_j \neq 0, 1\) then \(q_i = q_j\).

Proof:

Fix \(i, j\). Let \(u = \frac{q_i + q_j}{2}\), \(v = \frac{q_i – q_j}{2}\).

Then doing some algebra which I can’t currently be bothered to replicate in LaTeX (it’s fiddly but easy) we get \(P(W > t) = A + B v^2\) for some constants A, B. We are free to vary \(v\) without changing \(\sum q_i\), so we may choose \(v\) freely to maximize this value.

This expression only has a local maximum at \(v = 0\), but it may also be maximized by the end-points. These end-points occur when at least one of \(q_i, q_j\) is \(1\) or \(0\).

So for any pair \(i, j\) and any vector \(q\), if \(q_i \neq q_j\) and neither are 1 or 0 then we can strictly increase the probability \(P(W > t)\) by redistributing the two coordinates so that either \(q_i = q_j\) or one of \(q_i, q_j\) is \(1\) or \(0\).

This now proves our result almost immediately:

Let \(q\) be a vector that maximizes \(P(W > t)\). Suppose there are coordinates \(i, j\) such that neither \(q_i, q_j\) are \(1\) or \(0\). Then if they are not equal we can find some other \(q\) which strictly increases the probability, contradicting that \(q\) was a maximum.

QED

The question now becomes: What combination of zeroes and ones maximizes this probability?

In general, I don’t know. However some simulation suggests that the answer is quite different than I expected: If \(\mu > t\) then it’s easy, you just set at least \(t\) of the \(q_i\) to \(1\) and you’re done. However it appears to be the case that if \(mu < t\) what you want to do is have \(q_i\) non-zero for exactly \(t + 1\) values of i.

Here are some tables of brute force calculated optimum strategies. It’s all done with floating point numbers so some of these numbers are probably wrong where there’s not much in it, but should give a decent idea of the picture.

100 Constituencies

Popular vote Full constituencies Partial constituencies Victory probability
1% 0 49 0
2% 1 98 0
3% 2 97 0
4% 0 50 3.33067e-16
5% 1 50 3.33067e-16
6% 2 50 3.33067e-16
7% 0 50 1.44329e-15
8% 1 50 1.44329e-15
9% 2 50 1.44329e-15
10% 3 50 1.44329e-15
11% 4 50 1.44329e-15
12% 0 50 3.10862e-15
13% 1 50 3.10862e-15
14% 2 50 1.9984e-15
15% 3 50 3.10862e-15
16% 4 50 3.10862e-15
17% 1 49 6.66134e-15
18% 1 49 6.9611e-14
19% 1 49 6.14397e-13
20% 1 49 4.68026e-12
21% 1 49 3.11595e-11
22% 1 49 1.83468e-10
23% 1 49 9.65132e-10
24% 1 49 4.57618e-09
25% 1 49 1.9709e-08
26% 1 49 7.76285e-08
27% 1 49 2.81309e-07
28% 1 49 9.42896e-07
29% 1 49 2.93716e-06
30% 1 49 8.53927e-06
31% 1 49 2.32595e-05
32% 1 49 5.95608e-05
33% 1 49 0.000143831
34% 1 49 0.000328471
35% 1 49 0.000711237
36% 1 49 0.0014636
37% 1 49 0.00286849
38% 1 49 0.00536505
39% 1 49 0.00959356
40% 1 49 0.0164292
41% 1 49 0.0269891
42% 1 49 0.0425947
43% 1 49 0.0646781
44% 1 49 0.0946258
45% 1 49 0.133574
46% 1 49 0.182179
47% 1 49 0.240411
48% 1 49 0.307415
49% 1 49 0.381478

650 Constituencies

Popular vote Full constituencies Partial constituencies Victory probability
2% 3 325 3.77476e-15
3% 7 325 4.88498e-15
4% 2 325 7.88258e-15
5% 10 325 6.21725e-15
6% 15 325 7.88258e-15
7% 4 325 1.38778e-14
8% 10 325 1.04361e-14
9% 9 325 8.99281e-15
10% 23 325 1.04361e-14
11% 22 325 8.99281e-15
12% 1 325 1.14353e-14
13% 10 325 1.53211e-14
14% 10 325 2.67564e-14
15% 23 325 1.53211e-14
16% 4 325 1.86517e-14
17% 17 325 2.65343e-14
18% 8 325 1.96509e-14
19% 16 325 1.94289e-14
20% 8 325 2.19824e-14
21% 9 325 2.17604e-14
22% 21 325 2.19824e-14
23% 22 325 2.17604e-14
24% 34 325 2.19824e-14
25% 35 325 2.17604e-14
26% 12 325 2.88658e-14
27% 5 325 2.28706e-14
28% 3 325 2.94209e-14
29% 8 325 2.77556e-14
30% 0 325 3.25295e-14
31% 4 325 3.64153e-14
32% 11 325 3.34177e-14
33% 17 325 3.64153e-14
34% 23 325 4.21885e-14
35% 6 325 4.54081e-14
36% 1 324 1.14242e-13
37% 1 324 5.57576e-12
38% 1 324 1.98633e-10
39% 1 324 5.21813e-09
40% 1 324 1.02063e-07
41% 1 324 1.49951e-06
42% 1 324 1.66858e-05
43% 1 324 0.00014173
44% 1 324 0.000926012
45% 1 324 0.00468993
46% 1 324 0.0185649
47% 1 324 0.0579747
48% 1 324 0.144439
49% 1 324 0.291241

(1% value omitted because it gave buggy results, I think due to underflow).

So if we take 0.01% as the “this is kinda plausible” chance (i.e. we expect it to happen about once every 100 elections) and \(10^-7\) as the “You don’t need to worry about this chance”, then with 100 constituencies you’re not going to win if you’ve got 29% or less of the vote and you become plausible at 40%. With 650 constituencies on the other hand you’ve no chance below 40% and become plausible somewhere between 47% and 48%.

So the strategy I had was wrong, but the basic result that this isn’t something we need to worry about seems to hold up.

This entry was posted in voting on by .

One thought on “The winning strategy for random ballot is not what I thought it was

  1. Pingback: Best of drmaciver.com | David R. MacIver

Comments are closed.