Gerrymandering and mathematics

Sometimes I think about math which is not pure geometry/topology, so I want to discuss some of those areas in this blog as well.  This post was inspired by a recent talk of Moon Duchin in MD4SG and some discussions I had with Jim Allen and Manon Revel.  This is an oversimplification to get the ideas across - there are a lot of important ideas not present in this post.  If you want to learn more, check out Moon's group's website, which has lots of nice visuals and interactive explanations. 

Let me start with the background before getting into the math.  A major source of political conflict comes from gerrymandering.  If you're not familiar with this term, it's roughly the idea of restructuring voting districts to create some kind of political advantage.  I'll explain this a little further through the lens of the US system.  For simplicity, let's assume there are two political parties A and B in a state, which will be divided into voting districts.  For simplicity, say each district chooses their representative, so we care about the outcomes in individual districts, not just the aggregate at the state level.  We are party A and are redrawing the maps to make sure we win the most representatives.  There are two main techniques: "packing" and "cracking".  Packing is where we put a ton of voters from party B into very few districts; this cedes some districts to B at the expense of eating up a lot of their overall voting power.  (This is especially good if we knew B always wins in this area regardless.)  Cracking is where we split voters from party B into various nearby districts; by diluting their power, we can make it likely Party A wins in each of these districts.  (Here's a helpful picture if you haven't seen this before.)  

There is a somewhat complicated history in the US on the legality of gerrymandering.  For example, the Voting Rights Act of 1965 prevents parties from gerrymandering in a way that reduces political power for racial or ethnic groups.  This is currently under threat as it is being reconsidered by the Supreme Court through the case Merrill v. Milligan coming out of Alabama.  (For some more info on this case, see here.)  Partisan gerrymandering, gerrymandering based on party, is also a complicated issue.  In 2019, the Supreme Court ruled that it is unconstitutional, but that federal courts can't affect things - it is up to Congress and the states to regulate this.  It is an especially subtle issue in the US because many racial and ethnic minorities tend to align with a party so it is hard to disentangle the two.   

Gerrymandering is always changing and has ongoing major court cases - with mathematicians taking part!  For example, here is a document Moon Duchin submitted to court in North Carolina in the case NC League of Conservation Voters v. Hall, so you can see what this looks like.  But why should mathematics come into this?  One reason is that it helps us to construct measures for detecting gerrymandering.

Naively, there's an eye-ball test: does the region look reasonable?  A more technical term is compactness, not to be confused with open covers, which measures how wild the shape is.  This list has some pretty outrageous examples of very non-compact districts.  Some old political science metrics for measuring shape include the Polsby-Popper score which actually measures failure of compactness in terms of failure of sharpness of the isoperimetric inequality: the score is $\frac{4 \pi * \text{Area}}{\text{Perimeter}^2}$.  (Recall that the isoperimetric inequality says that $4 \pi$ times the area of a region in the plane is at most the square of the perimeter with equality only for disks.)  It's not as universal of a measure as it sounds.  For example, a region with a really jagged coastline is going to look gerrymandered no matter what relative to this score.  (Here's a picture of Louisiana's voting districts.  You tell me how to make these reasonable.)  One way mathematics has come into this field is to find new tools for identifying and measuring gerrymandering.  This draws in mathematics from lots of areas - geometry, statistics, etc.  To keep this post shortish, I'll just focus on one perspective, based on this paper by Daryl DeFord, Moon Duchin, and Justin Solomon.  (These posts give me an excuse to look at a paper more closely.)  

Here is one broad view on detecting gerrymandering.  Suppose we want to determine if a districting map used for a recent election was gerrymandered.  Consider the space of all possible districting maps (which also satisfy our state's rules, like equal numbers of voters in each district or connectedness of regions or protecting certain communities).  Choose a bazillion random districting maps.  Based on the voting results from our election, we can determine the outcome for each of these maps - how many representatives for party A vs party B.  If only 0.000001% of those simulated maps had the same outcome as the actual election, it might indicate that this is not fairly representing the population.  The interesting mathematical question is how to sample from this space?  I want to point out that this space is wildly big - see here for how complicated this gets in a toy model - so a naive random walk isn't guaranteed to really give a representative snapshot of the space.

To start building a space of districting maps, one imagines dividing up the state into very tiny regions (say census blocks) from which the voting districts will be built from.  These form a gigantic graph $G$: vertices are the tiny regions and edges connect them if they are adjacent geographically.  Note that regions correspond to subgraphs and we can think of a districting map as a partition of the vertices.  This is a nice perspective - for example, connectedness of the regions is equivalent to connectedness of the subgraphs.      

So how do we try to explore this space?  One means of "walking" in this space is via a method called Flip.  Two districting plans $P = \{P_1, \ldots, P_k\}$ and $Q = \{Q_1,\ldots,Q_k\}$ are related by a flip if they can be related by swapping an adjacent pair of vertices of $G$ (e.g. census blocks) in different regions.  In other words, after reordering the partitions, there exists $v \in P_1, w \in P_2$ such that $Q_1 = P_1 \cup \{w\} - \{v\}$ and $Q_2 = P_2 \cup \{v\} - \{w\}$, and $P_i = Q_i$ for $i > 2$.  For a picture of a flip, see this.  Therefore, to move around randomly in this space we can pick pairs of points to flip and see how the regions evolve.  One problem is that this walk does not "mix up the results" enough - if the census blocks are small relative to the size of the district, the impact of flipping is miniscule.  It also passes through lots of weird shapes which are not natural from a districting perspective and would have bad compactness scores.  

As an alternative, DeFord-Duchin-Solomon propose something they call ReCom, which I think is a really cool idea.  Rather than swap two vertices (which makes a very change), we are going to make more major changes to two districts.  Fix a partition $P = \{P_1,\ldots, P_k\}$ as before and choose two districts $P_i, P_j$ which share some boundary.  Take the union of these two districts to produce a region $R$, which can be thought of as a connected subgraph of $G$.  Choose a random spanning tree for $R$ and remove a random edge.  Looking at the two resulting subgraphs splits $R$ into $R_i$ and $R_j$, two connected regions.  (For simplicity, let's assume we can choose among edges that split $R$ into regions with equal populations.)  Then, our new partition is obtained by replacing $P_i, P_j$ with $R_i, R_j$.  This has the cool property that it changes the districting plans quickly and keeps the compactness of the regions reasonable.  See p.17 of their paper to see some pictures demonstrating the comparison with the Flip method.  It's so wild!  

Anyway, there's a lot of cool work going on in this space, which I might discuss in future posts.  If you're interested, there will likely be a lot of exciting activities next fall at MSRI at this program.  Check it out!