8
$\begingroup$

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)!}$$

$\endgroup$
8
  • $\begingroup$ My first thoughts are that you can ignore $I_{n,k}$ for all $k$ "away" from $n/2$. If $k=\alpha n$ for any $\alpha<\frac{1}{2}$ then you can use Stirling's approximation (or Cramer's Large Deviation Theorem) to show that $\mathbb{P}[C_1\text{ gets }\leq k\text{ votes}]$ decays exponentially, and $\mathbb{P}[C_1\text{ gets }\leq k\text{ votes and wins range voting}]$ is less than this value. You can also ignore any finite number of $k$ sufficiently close to $\frac{n}{2}$. $\endgroup$ Jun 16 '20 at 3:30
  • $\begingroup$ Maybe you can show that, for fixed $a>0$ and any $k<\frac{n}{2}-a$, $\mathbb{P}[C_1\text{ gets exactly }k\text{ votes and wins range voting}]$ decays faster than $O(\frac{1}{\sqrt{n}})$ as $n\rightarrow\infty$, the decay of $\mathbb{P}[C_1\text{ gets exactly }k\text{ votes}]$. My second thoughts are that this does seem like quite an involved question. $\endgroup$ Jun 16 '20 at 3:33
  • $\begingroup$ I think I can ignore any finite number of $k$, even if they are not "sufficiently close" to $\frac{n}{2}$. How would showing that $P(C_1 \text{ gets } \le k \text{ votes})$ decays exponentially be helpful? $\endgroup$ Jun 16 '20 at 13:46
  • $\begingroup$ It would be helpful because you can ignore $I_{n,k}$ for all those values of $k$. Say you could only get asymptotic behaviour for $I_{n,k}$ rather than a closed form. When trying to find asymptotic behaviour for a function of two variables (here $n$ and $k$), as both $k$ and $n$ go to infinity, you're going to find different behaviour depending on the relative rates of $n$ and $k$. $I_{n,k}$ will behave differently for $k=\frac{1}{2}n$ than it will for $k=\alpha n$ for any $\alpha<\frac{1}{2}$. $\endgroup$ Jun 16 '20 at 14:27
  • $\begingroup$ It's really hard to be able to make these statements with any authority, but my best guess is that this would be a really nice project for a graduate student or gifted undergrad, but it could be a semester long project. $\endgroup$ Jun 16 '20 at 14:34
5
+50
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I'm a bit confused: you said you don't have an answer to my "combinatorics question", but this answer seems to answer my question. What did you mean by that then? $\endgroup$ Jun 25 '20 at 20:12
  • $\begingroup$ Also what are $\Phi$ and $\phi$? $\endgroup$ Jun 25 '20 at 20:14
  • $\begingroup$ @VarunVejalla: I didn't answer your question about a closed form of $I_{n,k}$? But yes, I think the main probability question here is answered. The cdf of a standard normal is denoted by $\Phi$ and the pdf by $\phi$. $\endgroup$ Jun 25 '20 at 20:39
  • 1
    $\begingroup$ All right, thanks for clarifying. Plugging the final integral into Mathematica, I get that the final answer is $\frac{1}{2} - \frac{\arctan(\sqrt{2})}{\pi}$ $\endgroup$ Jun 25 '20 at 22:35
  • 1
    $\begingroup$ Thanks, I've put that into the answer now. $\endgroup$ Jun 25 '20 at 23:18
2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Testing with your code, I get that it approaches something closer to $19$ or $20\%$. Since you ran for only $100$ trials with $n = 100,000$, there will be too much variability to see the true limiting probability. $\endgroup$ Jun 16 '20 at 19:59
  • $\begingroup$ True. I'm also running on a very cheap laptop so I'm not going to be able to do large numbers very well, that'll have to be tested by someone else. $\endgroup$ Jun 16 '20 at 20:17
  • 1
    $\begingroup$ @VarunVejalla: My analytic answer is 19.6%, which is right in your estimate. (Thanks for the corroborating code @PepeSilvia!) $\endgroup$ Jun 25 '20 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.