Probability of different winners in a two candidate election (range voting vs majority)

Question

I was clicking through the xkcd comics, and I came upon xkcd 2225. I didn't know about "Range Voting", so decided to read about this voting system. I came up with the following problem based off it:

Let there be $2$ candidates in an election, $C_1$ and $C_2$. Each voter will randomly assign both candidates a score, choosing from the standard uniform distribution, $U(0, 1)$. The winner, counting by range voting, will be the candidate who got the greater sum of scores. The winner, counting by majority voting, will be the candidate who got the greater number of high scores. What is the probability that the two winners are different as the number of voters approaches $\infty$?

I fear that explanation was unclear, so let me illustrate an example: Let there be $5$ voters. Then the scores could be $$[0.1, 0.2]$$ $$[0.6, 0.7]$$ $$[0.9, 0.1]$$ $$[0.4, 0.5]$$ $$[0.8, 0.9]$$

Then $C_1$ would be the winner by range voting since $0.1 + 0.6 + 0.9 + 0.4 + 0.8 = 2.8 > 2.4=0.2+0.7+0.1+0.5+0.9$. $C_2$ would be the winner by majority because they secured voters $1, 2, 4, 5$, whereas $C_1$ only secured voter $3$.

I can rewrite the problem as $$2 \mathbb{P}(C_1 \text{ winning range} \cap C_2 \text{ winning majority})$$

This can in turn be written as $$2 \sum_{k=1}^{n/2}\mathbb{P}(C_1 \text{ winning range} \cap C_1 \text{ getting exactly k in majority vote})$$

Let $s_i$ be the value of the vote cast by the $i$th voter for $C_1$ minus the value of the vote cast for $C_2$. The values of $s_i$ will follow the distribution of $1 - |x|$ with $-1 < x < 1$. The inner probability can be written in terms of integrals, although it is very ugly, to get

$$2\sum_{k = 1}^{n/2}\binom{n}{k} \int_0^1 ... \int_0^1 \int_{-1}^0 ... \int_{-1}^0 \prod_{i=1}^{k}(1-s_i) \prod_{i=k+1}^n (1+s_i) \left[\sum_{i=1}^n s_i > 0\right] ds_n...ds_{k+1} ds_k...ds_1$$

where $[$ $]$ denotes the Iverson bracket. From here, the integral can be rewritten to get $$2\sum_{k = 1}^{n/2}\binom{n}{k} \underbrace{\int_0^1 ... \int_{0}^1 \prod_{i=1}^{n}s_i \left[\sum_{i=k+1}^n s_i - \sum_{i=1}^k s_i > n-2k \right] ds_n...ds_1}_{I_{n, k}}$$

Using Mathematica, I found that $I_{2, 1} = \frac{1}{8}, I_{3, 1} = \frac{19}{720}, I_{4, 1} = \frac{191}{40320}, I_{5, 1} = \frac{887}{1209600}, I_{6, 1} = \frac{6797}{68428800}, I_{5, 2} = \frac{10117}{1209600}, I_{6, 2} = \frac{467009}{239500800}$. However, I wasn't able to simplify the sum any further. I found that the approximation for $n = 3$ is $\frac{19}{120}$, for $n = 5$ it is $\frac{21121}{120960}$, and for $n = 7$, it is $\frac{56332921}{311351040} \approx 0.181$. I didn't include results about even $n$ because of possible ambiguity with the $k = n/2$ case. It seems that $I_{2k, k} = \frac{1}{2^{2k+1}}$, and $$\lim_{k \to \infty} \frac{\binom{2k}{k}}{2^{2k+1}} = 0$$ so this would confirm that ignoring the $k = n/2$ case would have no impact as $n \to \infty$.

My questions:

1. Would it be possible to find a closed form for $I_{n, k}$? If so, what is it?
2. What is the closed form for the limit of the probability as $n$ approaches $\infty$?

Edit: I can instead use the sums of the integral as the bounds. I get $$I_{n, k} = \int_0^k \int_{n-2k+S_1}^{n-k} P_{k}(S_1)P_{n-k}(S_2)dS_2 dS_1$$

where $P_m(x) = \int_0^1 ... \int_0^1 \prod_{i=1}^m s_i \left[\sum s_i = x\right]ds_m ... ds_1$

$P_m(x)$ can be rewritten as $$\int_{x-1}^{x} (x-t) P_{m-1}(t) dt $$ with $P_m(x) = 0$ for $x < 0$ and $x > m$.

I found that $P_1(x) = x$ for $0 \le x \le 1$, $$P_2(x) = \left\{\begin{array}{ll} \frac{1}{3!}x^{3} & : 0 \le x \le 1\\ \frac{1}{3!}(-x^3 + 6x - 4) & : 1 \le x \le 2 \end{array} \right.$$

$$P_3(x) = \left\{\begin{array}{ll} \frac{1}{5!}x^{5} & : 0 \le x \le 1\\ \frac{1}{5!}(-2x^5 + 30x^3 - 60x^2 + 45x-12) & : 1 \le x \le 2 \\ \frac{1}{5!}(x^5 - 30x^3 + 60x^2 + 45x-108) & : 2 \le x \le 3 \end{array} \right.$$

$$P_4(x) = \left\{ \begin{array}{ll} \frac{1}{7!}x^7 &: 0 \le x \le 1 \\ \frac{1}{7!}\left(-3x^{7}+84x^{5}-280x^{4}+420x^{3}-336x^{2}+140x-24\right) &: 1 \le x \le 2 \\ \frac{1}{7!}\left(3x^{7}-168x^{5}+560x^{4}+420x^{3}-4368x^{2}+6860x-3480\right) &: 2 \le x \le 3 \\ \frac{1}{7!}(-x^{7}+84x^{5}-280x^{4}-840x^{3}+4704x^{2}-4480x-1536) &: 3 \le x \le 4 \end{array} \right.$$

I wasn't able to find a closed form for $P_m(x)$, but I suspect that it might be related to the Irwin-Hall distribution.

Here is what I found so far for $P_m(x)$: $$\left\{ \begin{array}{ll} \frac{1}{(2m-1)!}x^{2m-1} &: 0 \le x \le 1 \\ \frac{1}{(2m-1)!}\left(x^{2m-1}-\left(2m-1\right)\cdot m\left(x-1\right)^{2m-2}-m\left(x-1\right)^{2m-1}\right) &: 1 \le x \le 2 \end{array} \right.$$

Edit $2$: Letting $P_{m, k}(x)$ be $P_m(x)$ for $k \le x \le k+1$ and repeatedly using the recurrence relation, I found that $$P_{m, k}(x) = \int_{x-1}^{k}\left(x-x_{1}\right)P_{m-1,k-1}\left(x_{1}\right)dx_{1}+\sum_{t=1}^{m-k-1}\frac{1}{\left(2t+1\right)!}\left(\left(x-k\right)^{2t}\int_{k-1}^{k}P_{m-t-1,k-1}\left(x_{2}\right)\left(2kt+x-\left(1+2t\right)x_{2}\right)dx_{2}+\int_{k-1}^{x-1}P_{m-t-1,k-1}\left(x_{2}\right)\left(1-x+x_{2}\right)^{2t}\left(-2t-x+x_{2}\right)dx_{2}\right)$$

However, when I try to use this for $P_{m, 2}(x)$, I get a really long and nasty function with hypergeometric functions.

Edit $3$: I was able to get that $$P_{m, m-1}(x) = (-1)^{m+1} \sum_{n=m-1}^{2m-1} \frac{\binom{m}{n-m+1}}{n!}(x-m)^n = \frac{(m-x)^{m-1}\ _1F_1(-m; m; m-x)}{(m-1)!}$$

Answer 1

Using the central limit theorem, there is a: $$\frac{1}{2} - \frac{\arctan(\sqrt{2})}{\pi} = 19.6\%$$ the two winners are different!

---

Let $X_{i} \in \{-1,1\}$ be whether voter $i$ votes for candidate $1$ or $2$. Then the margin of victory $\Delta$ in majority voting is: $$\Delta = \bar{X}\sqrt{n} \sim N(0,1)$$

Let $Y_{i} \in [-1,1]$ be the difference in voter $i$'s score for candidates $1$ and $2$. The pdf of $Y_{i}$ given $X_{i}$ is: $$f_{Y_{i}|X_{i}}(y_{i}|X_{i}=1) = 2(1-y_{i}), \quad y_{i}\in[0,1]$$ The expectation and variance can then be computed: $$\mathbb{E}[Y_{i}|X_{i}=1] = 1/3$$ $$\mathbb{E}[Y_{i}^{2}|X_{i}=1] = 1/6$$ $$\begin{align} \text{Var}(Y_{i}|X_{i}=1) &= 1/6-1/3^2 \\ &= 1/18 \end{align}$$

---

Let $\Lambda$ be the range voting outcome: $$\Lambda = \bar{Y}\sqrt{n}$$ The distribution of range voting $(\Lambda)$ conditional on majority voting $(\Delta)$ is: $$\Lambda | \Delta \sim N(\Delta/3, 1/18)$$ The conditional probability of candidate 1 winning the range vote is: $$\mathbb{P}[\Lambda < 0|\Delta] = \Phi\left( \frac{-\Delta \sqrt{18}}{3} \right)$$ Given candidate 2 wins the majority vote, the probability candidate 1 wins the range vote is: $$\begin{align} \mathbb{E}\big[\mathbb{P}[\Lambda < 0 | \Delta]\ \big| \, \Delta>0\big] &= 2\int_{0}^{\infty} \Phi\left( \frac{-\Delta \sqrt{18}}{3} \right)\phi(\Delta)d\Delta \\ &= \frac{1}{2} - \frac{\arctan(\sqrt{2})}{\pi} \\ &= .195913 \end{align}$$ Basically, $\Delta$ and $\Lambda$ follow a bivariate normal distribution when the number of voters $n$ gets large, therefore $\Lambda|\Delta$ is normally distributed as well. We can then compute whatever probabilities. Interestingly, nothing directly depends on $n$ (e.g. relevant means or variances), but rather that $\Delta$ and $\Lambda$ are approximately normal.

Answer 2

So not an answer per se, but I set up some simple python code.

import numpy as np

n=int(input("Enter number of voters: "))
m=int(input("Enter number of trials: "))

c1=np.random.rand(m,n)
c2=np.random.rand(m,n)
diff=np.subtract(c1,c2)
mv=np.sum(np.array(diff)>=0,axis=1)
mv=[x-n/2 for x in mv]
rv=np.subtract(np.sum(c1,axis=1),np.sum(c2,axis=1))
mv=np.sign(mv)
rv=np.sign(rv)
r=np.multiply(mv,rv)
r=np.sum(np.array(r)<0)

print("Loser of majority voting won range voting " +str(r) +" times out of "+str(m)+", "+str(int(r/m*100))+"% of the time")

I ran this for 100 trials as far as $n=100,000$, and it pretty consistently gives out an answer of around 13% (this is the probability of the range voting winner losing majority voting, you were trying to calculate the probability candidate C1 did this, so your answer would be half this). I couldn't get it to run for $n=1,000,000$, in retrospect I should have done the trials over a for loop and kept a counter but you could change that yourself if you wanted.

It's interesting information that this probability doesn't go to 0 at least.