Dummymandering for Dummies

In the next election cycle you’re back at it, gerrymandering on behalf of the Moon party once more. This time, you can draw a map that results in any set of probabilities $p_1$, $p_2$, $p_3$, $p_3$, $p_5$, $p_6$, and $p_7$ that you’ll win each of the corresponding districts—subject to the constraint that the average of the probabilities is $1/2.$ In other words, $$p_1 + p_2 + p_3 + p_4 + p_5 + p_6 + p_7 = 7/2.$$

The bosses of the Moon party want to go big. More specifically, they want to maximize the party’s chances of winning at least five of the seven districts. However, you are concerned that such a greedy attempt at gerrymandering may backfire, a phenomenon that has become known as dummymandering. When you draw a map that maximizes your chances of winning at least five districts, the probability the Moon party blows it and winds up losing most of the districts is $L_A.$

Your personal preference is to simply maximize the party’s chances of winning at least four of the seven districts—a simple majority of them. When you draw that maximizes these chances, the probability the Moon party loses most of the districts is $L_B.$ How much greater than $L_B$ is $L_A$?

Again, we will assume that $p_1 \leq p_2 \leq p_3 \leq \cdots \leq p_7.$ We have $X_i \sim B(p_i)$ is a Bernoulli distribution with probability of success $p_i.$ Then the Moons want $\sum_{i=1}^7 X_i \geq 5,$ so we should determine $$f_5(p) = \mathbb{P} \left\{ \sum_{i=1}^7 X_i \geq 5 \right\}.$$ In particular, we could have $$g(p) = \mathbb{P} \left\{ \sum_{i=1}^7 X_i = 7 \right\} = p_1 p_2 \cdots p_7.$$ We have $$h(p)=\mathbb{P} \left\{ \sum_{i=1}^7 X_i = 6 \right\} = (1-p_1) p_2 \cdots p_7 + p_1 (1-p_2) p_3 \cdots p_7 + \cdots + p_1 \cdots p_6 (1-p_7).$$ Finally, we have \begin{align*} k(p) = \mathbb{P} \left\{ \sum_{i=1}^7 X_i = 5 \right\} &= (1-p_1)(1-p_2) p_3 \cdots p_7 + (1-p_1)p_2(1-p_3)p_4 \cdots p_7 + \cdots + (1-p_1)p_2 \cdots p_6 (1-p_7) \\ & \quad + p_1 (1-p_2) (1-p_3) p_4 \cdots p_7 + \cdots + p_1 (1-p_2) p_3 \cdots p_6 (1-p_7) \\ & \quad\quad + \cdots + p_1 p_2 \cdots p_5 (1-p_6)(1-p_7)\end{align*} Putting this altogether we get f_5(p) = g(p) + h(p) + k(p), and for instance, we see that \begin{align*}f_5(p) &= p_1 \Biggl( p_2 \cdots p_7 + (1-p_2) p_3 \cdots p_7 + p_2 (1-p_3) p_4 \cdots p_7 + \cdots + p_2 \cdots p_6 (1-p_7) \Biggr. \\ & \quad\quad\quad\quad \Biggl.+ (1-p_2) (1 - p_3) p_4 \cdots p_7 + \cdots + p_2 \cdots p_5 (1-p_6) (1 - p_7) \Biggr) + \\ & \quad + (1 - p_1) \Biggl( p_2 \cdots p_7 + (1 - p_2) p_3 \cdots p_7 + p_2 (1-p_3) p_4 \cdots p_7 + \cdots + p_2 \cdots p_6 (1 -p_7 ) \Biggr) \\ & \quad\quad\quad + \text{ other terms not involving $p_1$ } \\ &= p_1 \Biggl( (1-p_2)(1-p_3) p_4 \cdots p_7 + (1-p_2) p_3 (1-p_4) p_5 p_6 p_7 + \cdots + p_2 \cdots p_5 (1-p_6) (1-p_7) \Biggr) \\ &\quad + \text{ other terms not involving $p_1$}.\end{align*} Therefore, we see that $\frac{\partial}{\partial p_1} f_5(p) \geq 0$ for all $0 \leq p \leq 1.$ Since the choice of $p_1$ was arbitrary, this holds for all $p_i, i = 1, \dots, 7.$ So it is clear that there will not be some $p^*$ such that $\nabla f_5(p^*) = 0.$ Therefore, we need to look at the boundary $\sum_{i=1}^7 p_i = 7/2,$ along with the other boundaries $0 \leq p_1 \leq p_2 \leq \cdots \leq p_6 \leq p_7 \leq 1.$

In particular, we need to look at potential solutions of the form $$q^{i,j} = \bigl( \overbrace{0, \dots, 0}^{i}, \overbrace{\lambda_{ij}, \dots, \lambda_{ij}}^{7-i-j}, \overbrace{1, \dots, 1}^j \bigr),$$ where $\lambda_{ij} = \frac{7 - 2j}{2(7- i - j)}.$ We see that for each $i, j,$ $$0 \leq q^{i,j}_1 \leq q^{i,j}_2 \leq \cdots \leq q^{i,j}_7 \leq 1,$$ and we have $$\sum_{k=1}^7 q^{i,j}_k = i \cdot 0 + (7-i-j) \cdot \lambda_{ij} + j \cdot 1 = \frac{7}{2}.$$ Plugging $q^{i,j}$ into $f_5(p),$ we see that, since the Moons will automatically lose $i$ districts and win $j$ districts, that $$f_5(q^{i,j}) = \sum_{k=5}^{7-i} \binom{7-i-j}{k-j} (1 - \lambda_{ij})^{7-i-k} \lambda_{ij}^{k-j},$$ which is just the upper tail of a binomial distribution with probability $\lambda_{ij}.$

Since we are already at it, and without the need to rigorously reprove anything, we can also define $$f_4(p) = \mathbb{P} \left\{ \sum_{i=1}^7 X_i \geq 4 \right\}.$$ We can reassert that when maximizing for $f_4$ that there will be no feasible solutions p^* with \nabla f_4(p^*) = 0, so we will also look for $f_4(q^{i,j})$ as previously define, where we additionally have $$f_4(q^{i,j}) = \sum_{k=4}^{7-i} \binom{7-i-j}{k-j} (1 - \lambda_{ik})^{7-i-k} \lambda_{ij}^{k-j}.$$

We obviously cannot have $j \gt 3,$ since there is only $7/2$ total probability to go around. Similarly, we see that $f_5(q^{5,j}) = 0,$ for each $j,$ since you have already allowed the Suns to win 3 districts and hence can only win a maximum of 4. Additionally, whenever So for $i, j \in \{0,1,2, 3\},$ we can calculate the values of $f_5$ and $f_4$ using some handy-dandy calculators, whether Excel or numpy or whatever you fancy, to obtain the following table:

$i$	$j$	$\lambda_{ij}$	$f_5(q^{i,j})$	$f_4(q^{i,j})$
$0$	$0$	$1/2$	$0.2265625$	$0.5000000$
$1$	$0$	$7/12$	$0.2082593$	$0.5097931$
$2$	$0$	$7/10$	$0.1680700$	$0.5282200$
$3$	$0$	$7/8$	$0.0000000$	$0.5861864$
$0$	$1$	$5/12$	$0.2030319$	$0.4902069$
$1$	$1$	$1/2$	$0.1875000$	$0.5000000$
$2$	$1$	$5/8$	$0.1525878$	$0.5187988$
$3$	$1$	$5/8$	$0.0000000$	$0.5787037$
$0$	$2$	$3/10$	$0.1630800$	$0.4717800$
$1$	$2$	$3/8$	$0.1680700$	$0.4812012$
$2$	$2$	$1/2$	$0.1516113$	$0.5000000$
$3$	$2$	$3/4$	$0.1516113$	$0.5625000$
$0$	$3$	$1/8$	$0.1630800$	$0.4138184$
$1$	$3$	$1/6$	$0.0740741$	$0.4212963$
$2$	$3$	$1/4$	$0.0625000$	$0.4375000$
$3$	$3$	$1/2$	$0.0000000$	$0.5000000$

We further note that the probability of losing the election is $L(p) = 1 - f_4(p).$ Therefore, we see that if the Moons want to greedily maximize the probability of winning at least 5 districts, then they need to pick $$p^A = (1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2),$$ which will give probability of losing the election of $$L_A = 1 - f_4(p^A) = \frac{1}{2}.$$ However, we see that $p^B = (0, 0, 0, 7/8, 7/8, 7/8, 7/8)$ is the maximizer of $f_4,$ which means that $$L_B = 1 - f_4(p^B) = 1- \frac{2401}{4096} = \frac{1695}{4096} = 0.4138184\dots.$$ Therefore, we see that the Moons' greedy decision to maximize the probability of winning 5 or more districts cost them $$L_A - L_B = \frac{353}{4096} = 8.61816\dots \%$$ in winning percentage.