The Mathematical Complexity Behind America's Map Problem

Hi friends, it’s been a while! I’ve been spending a bunch of time learning how to make animated maps (this is harder than I thought) and generally improve video quality (this was more time consuming than I thought). I’m happy to be back to writing. Hope you enjoy!

In 2021, Alabama’s redistricting commission released a map that had a couple peculiarities. The peculiarities were hard to pick out with the naked eye, but the map diluted the voting power of the state’s black population by packing the 7th district and drawing lines to split the remainder of the population amongst the 1st, 2nd, and 3rd districts. The Supreme Court agreed that this map had to be redrawn in a 2023 decision:

The legal saga prompted me to look into the complexity of algorithmically detecting a gerrymandered map. Conceptually, the problem is systemically important to ensure votes aren’t wasted and the House is responsive to voters. But difficult because of the lack of clear standards, myriad legal requirements, and vast space of possible map configurations (a fun statistics / sampling problem). Let’s go through each in turn.

📝 Standards (, Lack of)

One thing you may have missed from the image above is the tiny text at the bottom “© 2021 Caliper”. Let’s talk about this for a second. Caliper is a mapping tech company that develops a product called Maptitude. This product appears to be used to develop the blocked Alabama map (I’m sure others too). Using mapping tech on its own is pretty neutral - necessary really - but it underlines the importance of having a standard by which to judge a map’s fairness. A map can be optimized to favor one party’s voters without any visible irregularities as below:

“Fairness” is a vague term but most definitions I’ve seen boil down to protecting a “one person, one vote” standard - voters’ right to be represented is protected equally. Metrics to judge fairness represent this standard:

• Deviation from Partisan Symmetry (aka “Partisan Bias”): If one party won some percent of the statewide vote (say, 55%) resulting in 3 seats in a state with 5 states, we would expect the opposition party to have won 3 seats as well if they won 55% of the vote. The deviation from this symmetry is what we measure, that is how many seats above / below the vote share a party wins

• Efficiency Gap: This is a measure of “wasted” votes. Every vote above 50% + 1 for the winning candidate and under 50% for the losing candidate is considered “wasted” as the winning candidate would have won with 50% + 1. The difference between wasted votes for the controlling and opposition parties can measure if votes are packed into a district or cracked across several to dilute voting power.

The court has not tapped either of these metrics as a standard for judging the fairness of a map.

🏛 Encoding Legal Requirements

Just as a quick note, before getting into the algorithms for detecting gerrymandering, I just want to appreciate that any algorithm needs to consider state laws in addition to federal laws. While I don’t personally know what it’s like to capture these specific legal requirements into code, I can appreciate that it mustn’t be easy nor quick:

🤖 Proposed Algorithms

We’ll use Alabama as an example for the following 3 algorithms. For context, Alabama has 7 representatives and 67 counties. The potential number of map configurations for AL is at least in the trillion trillions but ultimately unknown. If you conceptualize a state as a matrix (e.g. a 5 county by 5 county square), the number of configurations scales as the matrix becomes more complex - this is a combinatorial explosion. States are way more complex than a 5 × 5 grid, so these algorithms are meant to help us sample from an option space of unknown size.

• Compact Random Seed & Grow: To start, we’ll allocate a representative to each of the 67 counties. So we need to go through a merging exercise. To do that, we’ll randomly pick (or seed) 7 counties and merge adjacent counties until we have the 7 districts that we’re looking for. We pick the adjacent counties based on the distance between the geographic centers of the counties. This process doesn’t guarantee that populations will be the same across the board. To fix that, cRSG looks at adjacent districts with too much deviation and finds a county that’s furthest from the centroid of both districts and swaps it from the district with a greater population to the district with a smaller population; we repeat this swapping again and again too until we have parity. This is what has been traditionally used but has some drawbacks (e.g. the time it takes to do all the limitations and bias caused by random seeding)

• Markov Chain Monte Carlo (ReCom): We need to start with a previously created map for this method and explore what happens if we recombine it. So, we take adjacent precincts, we merge them into something called a spanning tree. We then just have to break one connection as long as it maintains population parity to get 2 new districts.

• Sequential Monte Carlo: This time we don’t need an initial plan, we start off with 1 huge district. We create a spanning tree like in our ReCom approach, then make a split, so we have 2 districts. 1 of them will be final and the other will be split again. And we keep doing this until we get 7 districts. There’s an extra bit here that makes this approach more efficient and more complex. We won’t go into the specifics of this formula but Sequential Monte Carlo basically looks at all our constraints and weights them to create a distribution of priors (basically the distribution a plan should fall into if it follows the rules) - if it doesn’t fall into that distribution then the plan is rejected; every time we iterate on this approach, those weights update. 

These algorithms can simulate thousands of maps and help us construct a distribution of partisan bias and efficiency gap. We can then compare an enacted plan to the distributions.

Conclusions

Mathematicians across the country aren’t just trying to answer this fair maps question because of its complexity but also for its importance. There are outsized costs to getting this wrong or being slow in making a determination. Election cycles - especially for representatives - pass quickly, so politically biased maps create irreparable harm that can ultimately repeat after the next Census. 

A lot of the discourse around fair congressional maps center around independent commissions. Currently, 4 states have independent commissions that create congressional maps, 6 states have only 1 district, and the other 40 have court- or politically determined maps. And we should push for these types of commissions in the other 40 states that have more political processes. Because one necessitates the other: equations that determine the fairness of a map are nothing without independent commissions to put the insight into practice and an independent commission must have a baseline for what constitutes fairness in the first place. 

It may seem like overkill to go this in-depth on what constitutes “fairness” and pull out algorithms to determine that. But these maps are literal building blocks of democracy. Fair maps make for more competitive races, a more truly representative House, and most importantly more power to voters.

Sources / Shoutout:

• ALARM Redist R Package: https://github.com/alarm-redist/redist

• ALARM 50-State Simulations: https://alarm-redist.org/fifty-states/

• MGGG Redistricting Lab Metagraph: https://mggg.org/metagraph/

• Quanta Magazine. "How Math Has Changed the Shape of Gerrymandering", 2023. quantamagazine.org/how-math-has-changed-the-shape-of-gerrymandering-20230601/

  - Sequential Monte Carlo research paper (Kosuke Imai, Cory McCartan): https://imai.fas.harvard.edu/research/files/SMCredist.pdf

• Bloomberg Demographic Overlaid Congressional Map: https://www.bloomberg.com/news/features/2022-10-01/what-supreme-court-case-on-alabama-voting-maps-may-mean-for-black-americans

• Princeton Gerrymandering Lab: https://gerrymander.princeton.edu/redistricting-report-card/?planId=recotR1k8LgVMbB2g

• Geometry and Compactness. https://web.stevenson.edu/mbranson/m4tp/version1/gerrymandering-math-topic-compactness.html

• Brennan Center for Justice. “Who Controlled Redistricting in Every State”. https://www.brennancenter.org/our-work/research-reports/who-controlled-redistricting-every-state

Thank you for reading this article! If you enjoyed it, consider subscribing and sharing Statecraft or the video with a friend. Until next time! - Arman