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:
- Would it be possible to find a closed form for $I_{n, k}$? If so, what is it?
- 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)!}$$