TL;DR
This paper introduces a purely geometric, non-partisan framework to detect gerrymandered redistricting maps without relying on election data or voting history. By defining a tractable distance metric between maps, the authors can identify a "central," structurally typical map and demonstrate that notorious gerrymandered maps are extreme geometric outliers.
What Problem Does This Paper Address?
Partisan gerrymandering—the practice of drawing legislative district boundaries to unfairly favor one political party—is a major challenge for modern democracies. To detect it, state-of-the-art methods typically generate an "ensemble" of thousands of alternative, legally valid maps using randomized sampling. They then simulate past election results on these maps to see if the enacted map produces an anomalous number of seats for the ruling party.
However, courts, independent commissions, and citizens increasingly demand auditing tools that are entirely non-partisan and do not look at political data. Prior attempts to create non-partisan, purely structural metrics have suffered from severe limitations, such as failing to scale computationally or lacking a clear numerical "outlier score." This paper addresses this gap by creating a mathematically rigorous, scalable, and purely geometric distance framework for evaluating redistricting maps.
Methods
The authors model a state as a graph where vertices represent voting blocks and edges represent geographic boundaries.
- Map Representation: Any redistricting map is represented as an adjacency matrix $A$, where $A(i,j) = 1$ if voting blocks $i$ and $j$ are assigned to the same district, and $0$ otherwise.
- Distance Metric: They define a family of distance measures based on a weighted Hamming distance. This has an intuitive "edit distance" interpretation: it measures the minimum edge-weight cost to transform one map's district assignments into another's by adding or deleting edges.
- Centroid vs. Medoid Maps:
- The Sample Centroid Map ($\bar{A}_c$) is the empirical average of all adjacency matrices in a sampled ensemble. It contains fractional values representing the probability that any two blocks share a district.
- The Medoid Map is the actual, legally valid map that minimizes the total distance to all other maps in the ensemble (the "most typical" map).
- Algorithmic Speedup: Finding a sample medoid normally requires comparing every map to every other map, scaling quadratically ($O(T^2)$) with the number of samples $T$. The authors prove a decomposition theorem showing an equivalence between the Hamming distance of binary matrices and squared Euclidean distance. This allows them to compute the centroid first and then find the closest valid map in linear time ($O(T)$), making it highly scalable.
- Theoretical Hardness: They prove that finding the true population medoid is NP-hard (equivalent to a constrained min $k$-cut problem) and that standard sampling cannot guarantee exact convergence to it, justifying their use of an efficient heuristic.
Datasets
The authors evaluated their framework using the open-source ReCom (Recombination) Markov Chain Monte Carlo (MCMC) algorithm to generate large map ensembles for three US states:
- North Carolina (NC): 13 districts, ~2,700 voting units (200,000 sampled maps).
- Maryland (MD): 8 districts, ~1,800 voting units (50,000 sampled maps).
- Pennsylvania (PA): 18 districts, ~8,900 voting units (50,000 sampled maps).
They compared these random ensembles against actual historical maps, including the heavily contested 2011 and 2016 enacted maps for North Carolina, the 2011 enacted map for Pennsylvania, and non-partisan remedial maps drawn by judges.
Key Insights and Ideas
- Gerrymandering Leaves a Structural Footprint: You do not need to know how people vote to see if a map is anomalous. Gerrymandered maps break the natural geographic groupings found across an ensemble, making them geometric outliers.
- The Centroid as a Probability Map: While the centroid map is not a valid partition itself, its entries have a clean probabilistic meaning: entry $(i,j)$ is exactly the probability that voting blocks $i$ and $j$ end up in the same district across the entire distribution of valid maps.
- Linear-Time Auditing: By leveraging the relationship between Hamming distance and Euclidean space, the authors turned a slow $O(T^2)$ problem into a fast $O(T)$ one. This allows researchers to audit maps against massive ensembles of hundreds of thousands of samples in a reasonable timeframe.
Key Results
- Outlier Detection: In North Carolina and Pennsylvania, the historically enacted maps widely considered to be gerrymandered landed squarely in the 99th percentile or higher of distance away from the centroid map.
- Remedial Maps are Central: Conversely, non-partisan remedial maps (such as the NC map drawn by retired judges) fell near the peak/mean of the distance distribution, confirming they are structurally "typical."
- Centroid Convergence: Despite the massive dimensionality of the centroid map ($\Omega(n)$ entries for $n$ voting units), the estimated centroids converged consistently across different MCMC random seeds, demonstrating the stability of the metric.
Limitations and Future Work
- The "Sophisticated Gerrymander" Loophole: The authors openly acknowledge a key limitation: a clever legislature could potentially craft a map that heavily favors their party while keeping its geometric structure close to the ensemble average, thereby evading detection by this metric alone.
- Sampling Assumptions: The theoretical proofs assume independent and identically distributed (iid) samples, whereas practical redistricting tools rely on MCMC chains where samples are correlated. Future work could bridge this theoretical gap.
- Ensemble Visualization: The authors suggest using this distance metric to power high-dimensional visualization techniques (like multidimensional scaling) to better understand the vast space of valid redistricting maps.
Summary updated