How Millions of Simulated Maps Can Help Us Make Electoral Districts That Feel Fair

Partisan gerrymandering is having a heyday. Politicians in at least 16 states are enacting or considering new congressional maps designed to advantage one party over the other; most recently, California voters approved a map designed to increase Democratic seats, in order to counter a Republican-leaning map in Texas. Democrats and Republicans are locked in a zero-sum game—and democracy itself seems to be the only guaranteed loser.

Is there a path to a world in which the House of Representatives is more, well, representative? The answer to this question requires us to first answer an even more fundamental one: What does this ideal world look like? What does a “fair” redistricting map even mean?

This question has puzzled political scientists and captivated courts. It may be easy to point to a particular map as intuitively unfair, such as the recent headline-making maps from Texas and California. The more challenging task is to precisely define and quantify fairness so that it can be enforced, whether by legislation or litigation.

Here's a simple example illustrating the difficulty. Take the fictional state of Grid Haven, which has nine census blocks arranged in a three-by-three grid, each containing 100 people. The percentage of voters for the Blue Party in each block is shown in the sketch on the left.

Grid Haven has been allocated three congressional seats, so the nine blocks must be partitioned into three contiguous electoral districts of three blocks each. The governor of Grid Haven has just approved the map on the right, resulting in one district that will be won by the Blue Party and two for the Red Party.

Is this map fair? One way to think about fairness is proportionality. Over 60% of Grid Haven votes for the Blue Party. If the goal is to make the number of seats proportional to the number of votes, the Blue Party would get two districts rather than one, because 2/3 is a lot closer to 60% than 1/3.

This map might also be unfair because it “wastes” Blue votes according to a measure called the efficiency gap. All of the Blue Party votes in Red districts are wasted, along with the number of Blue votes in the Blue district in excess of the 150 needed to win. The total number of wasted Blue votes is 145 + 145 + (255 - 150) = 395, whereas the number of wasted Red votes is only 55. A fair redistricting map would equalize the wasted votes for each party.

However, both of these definitions of fairness suffer from a fundamental flaw: They only consider statewide partisan statistics. Courts have viewed such arguments with skepticism, as it is unclear which exact formula to use. And this whole line of thinking ignores the geographic constraints that are inherent to redistricting. If Congress passed a law requiring proportionality, the state of Massachusetts would be in serious trouble. Roughly one third of the state votes Republican, yet the geographic distribution of these voters makes it impossible to draw a redistricting map under which a Republican candidate can be expected to win any of the nine congressional districts. Consequently, all Republican votes are wasted while most Democratic votes are not.

Is there a better way to determine whether a map is fair? In order to conclude that a map exhibits partisan bias, it is necessary to consider what could have been drawn instead. By understanding the design space the mapmaker was working in, we can better assess their motives. Grid Haven happens to be small enough that we can write down every possibility. The results are quite stark: Of the 10 valid redistricting maps, the governor’s map is the only one that yields one Blue district, as seen in the histogram below; three of the remaining maps have two Blue districts and in six the Blue Party wins all three.

How can we push this analysis beyond the nine census blocks of Grid Haven to the 900,000+ census blocks of Texas? Even for a 10x10 grid, with a modest 100 blocks, there would be more than 8 quintillion potential divisions into 10 districts of 10 blocks each, which is far more than any supercomputer can enumerate.

This is where algorithms come in—specifically, a kind of algorithm I study in my research called Markov Chain Monte Carlo (MCMC). We don’t actually need to compute every possible map; we just need a quick way to statistically sample them. If the map under consideration still looks like an outlier with respect to an ensemble of one million unbiased samples, that is robust statistical evidence that the map is gerrymandered. Such evidence has been presented as part of expert testimony by mathematicians in high-profile court cases from battleground states like Pennsylvania and North Carolina, several going all the way up to the U.S. Supreme Court.

The current state-of-the art approach is to take any redistricting map and repeatedly merge and split pairs of districts to get new maps, as shown below. The splitting step uses a mathematical object called a uniformly random spanning tree. After only a few hundred steps, the resulting maps look nothing like the initial one. Even better, there are theorems precisely characterizing the probabilities of observing each map. This guarantees that the maps produced will not exhibit any hidden biases, such as from the choice of initial map.

Designing algorithms for this task is challenging. In the maelstrom of politics, it is not enough to create an algorithm that just runs fast; the algorithm also has to be explainable. Being able to articulate in layman’s terms what the algorithm is doing builds trust in its conclusions. My research has shown that these spanning-tree based algorithms favor “compact” districts—which intuitively feel more fair. I am currently developing a new implementation that is both theoretically faster and conceptually more transparent, in which the algorithm essentially draws random district lines by putting a pen down on the map and repeatedly moving tiny amounts in each direction with equal probability.

The mathematics underlying these algorithms may be complex, but the main idea behind them is simple. At the end of the day, we are making histograms like we did for Grid Haven—the magic lies in scaling this up to the level of U.S. states.

Gerrymandering is a multi-faceted political and legal problem that no algorithm can simply “solve.” But it also presents unique technical challenges which may call for increasingly advanced technical solutions. The ability to define fairness in a way that is driven by data, backed by theory, and aligned with human intuition is a groundbreaking development. It will doubtless continue to play a role, whether through court cases, independent commissions, or—hopefully—federal legislation that finally buries gerrymandering for good.