Expected average gain from implementing a policy via majority vote

Question

Suppose a country with $n$ citizens decides whether to implement a new policy. The value of implementing that policy for each individual citizen is known only to them and is uniformly distributed on $[-1; 1]$ (it is positive, when they would gain from this policy being implemented and negative if they will lose). If the policy is not implemented nobody will either gain anything or loose anything. Whether to implement the policy is decided via a majority vote: the policy will be implemented if and only if at least half of the citizens votes for it.

A weakly dominant strategy for each citizen is to vote for the policy if their gain from it is positive and against it, if their gain from it is negative. What is the average expected gain of citizens if all of them follow this strategy?

The policy will be selected only if and only if more citizens gain from it than lose from it. Suppose $A$ is the set of all citizens with positive gain. Than conditional expectation for fixed $A$ will be $\frac{2|A|-n}{n 2^{n+1}}$. That means that total expected gain will be:

$\sum_{k=\lceil \frac{n}{2} \rceil }^n \frac{C_n^k (2k-n)}{n 2^{n+1}}$

It is quite obvious, that this value is bounded by 1 from above. It is also monotonously non-decreasing with growing $n$, because:

$\frac{C_{n+1}^k (2k-n-1)}{(n+1) 2^{n+2}} - \frac{C_{n}^k (2k-n)}{n 2^{n+1}} = \frac{C_{n+1}^k (2k-n-1)n - C_{n}^k (2k-n)(n+1)}{n (n+1) 2^{n+1}} = \frac{C_n^k}{{n 2^{n+1}}} (\frac{n(2k-1-n)}{n+1-k} - 2k - n) \geq 0$ when $k \geq \frac{n}{2}$

That means, it converges to some number on $[0;1]$. I would like to find that number, but I don't know how.

Answer 1

Let's consider this for very large odd $n$.

• The number of positive votes is binomially distributed with mean $\frac n2$ and variance $\frac{n}{4}$, and for large $n$ will be approximately normally distributed.

• So conditioned on being a majority, i.e. exceeding $\frac n 2$, this will be approximately half-normally distributed, and the conditional mean will be about $\frac{n}2+{\frac{\sqrt n}{\sqrt{2\pi}}}$.

• The expected conditional gain for an individual majority voter is distributed on $[0,1]$ and so the conditional expected sum of their gains is $\frac{n}4+{\frac{\sqrt n}{2\sqrt{2\pi}}}$.

• A similar analysis for the minority voters is an expected $\frac{n}2-{\frac{\sqrt n}{\sqrt{2\pi}}}$ number and a conditional expected net (negative) gain of about $-\frac{n}4+{\frac{\sqrt n}{2\sqrt{2\pi}}}$.

• So overall, the conditional expected net gain is about ${\frac{\sqrt n}{\sqrt{2\pi}}}$

• Half the proposals will have a positive decision

So the overall expected net gain is about ${\dfrac{\sqrt n}{2\sqrt{2\pi}}}$

Answer 2

Hint: For $n$ even, the sum is exactly $\binom{n}{n/2}2^{-n-2} \approx (8 \pi n)^{-1/2} $

Answer 3

Let $X$ be the number of voters whose gain is positive. Provided $X\ge n/2$, each of the $X$ voters gains $1/2$ on average, and each of the $n-X$ other voters gains $-1/2$ on average, so the average total gain is $$ E[\text{total gain}] =E\left[\frac12(X-(n-X))\cdot \def\1{{\bf 1}}\1(X\ge n/2)\right] =E\Big[(X-n/2)\cdot \1(X\ge n/2)\Big] $$ Using the equality $z\cdot \1(z\ge 0)=\frac12(|z|+z)$, this is equivalent to $$E[\text{total gain}]=E\left[\frac12(|X-n/2|+(X-n/2))\right]=\frac12 E|X-n/2|.$$

To compute this we use the following Lemma, first proved by de Moivre (see this excellent explanation of the history by [Diaconis and Zabell], or this question on cross-validated).

Lemma: (de Moivre) If $Y$ is binomially distributed with $n$ trials and probability $p$, then $$ E|Y-np|=2(1-p)\cdot (\lfloor np\rfloor +1)\cdot P(Y= \lfloor np\rfloor +1). $$

In this case, we have $$ E[\text{total gain}]=\frac12(\lfloor n/2\rfloor +1)\cdot 2^{-n}\binom{n}{\lfloor n/2\rfloor +1}=\boxed{2^{-(n+1)}\lceil n/2\rceil \cdot \binom{n}{\lfloor n/2\rfloor}.} $$

Diaconis, Persi; Zabell, Sandy. Closed Form Summation for Classical Distributions: Variations on a Theme of De Moivre. Statist. Sci. 6 (1991), no. 3, 284--302. doi:10.1214/ss/1177011699. https://projecteuclid.org/euclid.ss/1177011699