Mathematics of Gerrymandering
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 
and each 
Note, we assume that 
Definition 1 Define
to the maximum over all
of the number of wins; and define
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
What can we say about these functions? Here are some simple observations.
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: 
Lemma 2 Suppose that
. Then
Proof: Let 
So it follows
This proves that 
It may help to set 
and so
Thus for 
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]
I remember reading online about a gerrymandering whose goal was to create a district that had primarily minority population groups, although it had a strange shape. The intention was to give them a representative, as otherwise they were scattered in different districts and their votes were lost. Is this fair? Here geometry was considered to be a less important bond than culture.
Dear domotorp:
Thanks as always for you comment. You raise an interesting issue: Can gerrymandering be used for a good propose? Like many things there are potentially good and bad uses of gerrymandering. Perhaps one can look at methods that satisfy other social goods?
Best
Dick
Geometric constraints on a flat map also have another problem: the world is a sphere, and various geometric criterea turn out not to be robust to the projection you use to flatten things out: https://arxiv.org/abs/1905.03173
Dear Aaron Roth:
Thanks for your comment. The reference is interesting too: The Gerrymandering Jumble: Map Projections Permute Districts’ Compactness Scores. I will have to look at it. There is a great deal of literature on this problem. Thanks again.
Best
Dick
Are you familiar with the paper “An impossibility theorem for gerrymandering”? As far as I recall it agreed with your conclusion that “nice geometry” was not the key issue.
I think statistical approaches are gaining traction as well. There is some work [1 and others] in which MCMC is used to explore the space of possible “reasonable” districtings (hopefully faithfully to uniform on the “space” of such redistrictings), and then for each districting estimated election simulations are run. A proposed districting can be called unfair, then, if its resulting election is extremely skewed compared to the distribution as a whole.
[1]: https://services.math.duke.edu/~sb337/gerrymandering/
“Suppose the voters have to be divided into {d} districts of the same size.”
A natural question here is whether the voters indeed *have* to be divided into districts. If the objective is to obtain “fair” (proportional?) representation, one could imagine a mechanism which allocates seats to representatives simply based on the popular vote. There is precisely such a move to reform the electoral college system for the presidential election, for example. See https://en.wikipedia.org/wiki/National_Popular_Vote_Interstate_Compact
Besides considering which notions of fairness we are after, it might also be worth revisiting our assumptions and considering wider families of algorithms (voting/cake-cutting rules).
Dear David Wajc:
Exactly right. I suspect that the real issue is the vested interest of the two parties. They do want fair as long as they get their share. If they are happy not so clear that means that voters are happy.
What do you think?
Best
Dick
❗ 💡 :star: wow talk about missing the forest for the trees. have heard about gerrymandering issues for years & the increasing theoretical/ mathematical scrutiny but never thought of the following. isnt the simple problem that votes are aggregated at the district level? how about districts just submit total counts to higher authorities for final tallying instead of “win vs losing candidate”? isnt this obvious? have never heard it proposed before… it seems to remove the problem entirely. ofc am sure there are other constraints pushing against it… but maybe this all needs a major rethink. and one wonders if the rise of political parties might be coupled loosely or tightly with gerrymandering tendencies (warned about by Washington in a remarkable quote someone just pointed out to me)
Exactly, get rid of the winner takes all nonsense by merging some or all districts.
Dear jz:
I like your comment on trees and the forest. I do wonder if the whole geometry idea is wrong headed.
Best
Dick
You might be interested in this paper: https://arxiv.org/abs/1808.08905 by Kueng, Mixon, Villar: “Fair redistricting is hard”
Dear Martin Schwarz:
Thanks for the link. Indeed a nice paper that shows even following simple geometry constraints is NP hard. The result is clever and raises obvious questions. I do not see if approximations are also hard.
Thanks
Best
Dick
this is my first time coming across this but it really great
Dear tessykayler:
Thanks much. I hope you continue to enjoy.
Best
Dick
Perhaps “one can achieve anything from districts all won by the majority, to most won by the majority.” -> “one can achieve anything from districts all won by the majority, to most won by the *minority*.”?
I think one could apply gradient descent or some other hill-climbing algorithm to draw districts automatically.
To draw districts for an upcoming election, we start from the last map and the last election result. Let x_v be the percentage of votes won by the majority party, and x_d the percentage of districts won by the majority party. We want to minimize the quantity: A = x_v – x_d. We can redraw the districts, recalculate A, and keep iterating until we reach some local minimum.
There is of course the non-algorithmic question of why would we try to optimize based on the results of the last election, instead of some other criterion. But it still seems much fairer than the current system.
In a related story …
• Someone made a font out of gerrymandered congressional districts
Dear Jon Awbrey:
Great find. The font is crazy.
Best
Dick