Mathematics of Gerrymandering

Gödel’s Lost Letter and P=NP 2019-08-20

Can theory help?

source; art by Bill Hennessy

John Roberts is the Chief Justice of the United States.

Today I will discuss the recent Supreme Court decision on gerrymandering.

The 5-4 decision in Rucho v. Common Cause takes the courts out of deciding if redistricting was done fairly. Roberts, penning the majority argument, felt that it was hard, if not impossible, for courts to determine whether districts were reasonably drawn. That is, whether partisan motives dominated when they were created.

I will explain what gerrymandering is, and how computational methods may play a role. I must add a takeaway:

The current view of computational methods to avoid gerrymandering may be based on incorrect assumptions.

How It Works

You probably know that gerrymandering is used, negatively, to describe creating voting districts that do not reflect the voters will. The term was coined as part of an attack on the then Governor of Massachusetts in 1812. The shape of one particularly contrived district looked like a salamander. Since his name was Elbridge Gerry, it became a gerrymander. He was a Democratic-Republican and was not re-elected.

Here is a figure from our friends at Wikipedia that presents examples of gerrymandering.

By redistricting in the above, one can achieve anything from districts all won by the majority, to most won by the majority. These examples, show how the party who controls the districts can control the outcome.

Well that is an overstatement. They can control the believed leanings of the voters in the districts. In the above example, they can control how yellow a district is. Real life is complicated by other factors:

A candidate may win because they are just more popular. That is a green candidate could still win in a yellow district.
A candidate may win because of random fluctuations. If the voter margin is small enough, random fluctuations could change the “expected” outcome.

The latter is a danger for gerrymanderers. This site on gerrymandering says:

The trick is not to spread your voters out so much that districts become vulnerable to flipping to the other party in the normal give and take of electoral politics.

How We Model It

Since Roberts is not our intended audience we will use mathematical definitions. I am sure Roberts and the rest of the Supreme Court justices are smart, but we have our own methods. We do not use legal jargon such as “prima facie” and suspect they do not use math jargon like “prime” numbers.

So let the yellow party have ${\alpha}$ fraction of the voters. Suppose the voters have to be divided into ${d}$ districts of the same size. A division is just a vector ${y=(y_{1},\dots,y_{d})}$ so that

$\displaystyle y_{1} + \cdots + y_{d} = 1,$

and each ${y_{i}}$ is non-negative. For such a vector ${y}$ the number that yellow wins is the number of indices ${k}$ so that

$\displaystyle y_{k} \ge \frac{1}{2d}.$

Note, we assume that ${1/2}$ of the voters makes a district a win. We can change this to strictly larger than ${1/2}$ , but will leave it for now.

Definition 1 Define ${{\rm MaxWin}(d, \alpha)}$ to the maximum over all ${y}$ of the number of wins; and define ${{\rm MinWin}(d, \alpha)}$ to be the minimum number of wins.

Note, we do not care who is doing the redistricting. Nor do we care about the geometry. For example

$\displaystyle {\rm MaxWin}(5, 0.60) = 5 \text{ and } {\rm MinWin}(5, 0.60) = 1.$

What can we say about these functions? Here are some simple observations.

${\bullet }$ If ${\alpha \ge 0.5}$ , then ${{\rm MaxWin}(d, \alpha) = d}$ . Just place ${\alpha }$ fraction of the voters in each district.

${\bullet }$ If ${\alpha > 0.5}$ , then ${{\rm MinWin}(d, \alpha) \ge 1}$ . No matter how the districts are drawn there must be at least one where yellow has a majority.

An advantage of these functions is that now we can discuss growth rates, not just present examples. A strength of theory is that we have replaced statements like “this algorithm is fast” by formulas for their running time. Another advantage is that these functions are independent of geometry. Previously I thought the dominating issue was how regions looked. Now I believe the issue is how close one gets to the best and worst case: ${\rm MaxWin}$ and ${\rm MinWin}$ .

Lemma 2 Suppose that ${\alpha > 1/2}$ . Then
$\displaystyle {\rm MinWin}(d, \alpha) = d-\lfloor 2(1-\alpha) d \rfloor$

Proof: Let ${\beta = 1-\alpha}$ . Let’s create the arrangement that makes green win as many districts as possible. If ${g}$ regions are mostly green then that takes ${\frac{g}{2d}}$ of the ${\beta}$ green voters. This implies that

$\displaystyle \frac{g}{2d} \le \beta.$

So it follows

$\displaystyle g \le 2\beta d.$

This proves that ${g}$ is equal to ${\lfloor 2\beta d \rfloor}$ . $\Box$

It may help to set ${\alpha = 1/2 + \epsilon}$ where ${\epsilon>0}$ . Let’s agree to ignore the rounding off and delete the floor and ceiling functions. Then

$\displaystyle {\rm MinWin}(d, \alpha) = d-2(1-\alpha) d$

and so

$\displaystyle {\rm MinWin}(d, \alpha) = 2\epsilon d.$

Thus for ${\epsilon = 1/10}$ we get that

$\displaystyle {\rm MaxWin}(d, \alpha) = d \text{ and } {\rm MinWin}(d, \alpha) = 0.2d.$

This says that independent of any geometry if yellow has a ten percent majority, then best case if they set the districts they could win all, and if green sets the districts the worst they can get is twenty percent of the districts.

How Algorithms Can Help

There is long-term and continuing interest in algorithms that automate redistricting. The hope is that automated systems will be able to create districts that are fair. A trouble with this research is that there is no universal notion of what makes districts fair. The mantra is:

A redistricting is fair if and only if the districts collectively satisfy some geometric criterion.

An explicit statement of such a criterion, from a site on such algorithms, is:

The best district map is the one where people have the lowest average distance to the center of their district.

Of course the name “gerrymandering” came from how districts looked. Somehow this enshrined the notion that districts must look right. I feel this could be wrong.

Here is a quote from a recent paper on an algorithm for redistricting.

We propose a method for redistricting, decomposing a geographical area into subareas, called districts, so that the populations of the districts are as close as possible and the districts are compact and contiguous. Each district is the intersection of a polygon with the geographical area. The polygons are convex and the average number of sides per polygon is less than six.

The authors are Philip Klein and Neal Young, who are well known researchers on various aspects of algorithms. They do interesting work, their paper is interesting, but the assumption that geometry is the key I do not get.

How To Do Better?

I think that we need to go beyond geometry to understand and avoid gerrymandering. The connection between geometry and fairness is driven—I believe—by tradition. Voters in the same district probably want to be near each other. In the past being near each other was probably important, since travel was so difficult. Perhaps today location is less of an issue then it was before cars, phones, cell phones, internet access, and email. Perhaps districts can be fair and yet do not look good.

Open Problems

An analogy to cake cutting may occur to you. Recall in the cake cutting problem success is not measured in how the pieces of the cake look. It is only measured by whether the parties cutting the cake are happy. Is there some way to push this analogy? I just came across a paper using the cake cutting method: A Partisan Districting Protocol With Provably Nonpartisan Outcomes by Wesley Pegden, Ariel Procaccia, and Dingli Yu. More in the future.

Can algorithmic methods help? Is geometry the fundamental issue?

[sourced photo, other word edits]