Implications of Distance over Redistricting Maps: Central and Outlier Maps

Seyed A. Esmaeili, Darshan Chakrabarti, Hayley Grape, Brian Brubach

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.
Figure 1: We are given a hypothetical state consisting of 4 vertices V = {v1, v2, v3, v4} with M1 and M2 being two valid redistricting maps. The adjacency matrices A1,A2, and edit distance interpretation of dΘ(A1, A2) are demonstrated. Note that dΘ(A1, A2) = θ(1, 2) + θ(3, 4) + θ(1, 3) + θ(2, 4) which is exactly the minimum sum of edge weights that need to be deleted and added to obtain A2 from A1.
  • 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

Abstract

In representative democracy, a redistricting map is chosen to partition an electorate into districts which each elects a representative. A valid redistricting map must satisfy a collection of constraints such as being compact, contiguous, and of almost-equal population. However, these constraints are loose enough to enable an enormous ensemble of valid redistricting maps. This enables a partisan legislature to gerrymander by choosing a map which unfairly favors it. In this paper, we introduce an interpretable and tractable distance measure over redistricting maps which does not use election results and study its implications over the ensemble of redistricting maps. Specifically, we define a central map which may be considered "most typical" and give a rigorous justification for it by showing that it mirrors the Kemeny ranking in a scenario where we have a committee voting over a collection of redistricting maps to be drawn. We include running time and sample complexity analysis for our algorithms, including some negative results which hold using any algorithm. We further study outlier detection based on this distance measure and show that our framework can detect some gerrymandered maps. More precisely, we show some maps that are widely considered to be gerrymandered that lie very far away from our central maps in comparison to a large ensemble of valid redistricting maps. Since our distance measure does not rely on election results, this gives a significant advantage in gerrymandering detection which is lacking in all previous methods.
BibTeX
@inproceedings{esmaeili2024implications,
  author = {Seyed A. Esmaeili and Darshan Chakrabarti and Hayley Grape and Brian Brubach},
  title = {{Implications of Distance over Redistricting Maps: Central and Outlier Maps}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=xO6brLL24e},
}
Figure