Centralized Fairness for Redistricting

Seyed A. Esmaeili, Hayley Grape, Brian Brubach

Abstract

In representative democracy, a redistricting map is chosen to partition an electorate into a collection of districts each of which 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 imposed constraints are still loose enough to enable an enormous ensemble of valid redistricting maps. This fact introduces a difficulty in drawing redistricting maps and it also enables a partisan legislature to possibly 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 as being "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 run-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. More precisely, we show gerrymandered maps 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.

Introduction

Redistricting is a cornerstone of representative democracy, yet it remains highly vulnerable to gerrymandering. Traditionally, detecting gerrymandering has required analyzing election results to determine if a map unfairly favors a specific party. However, this approach is inherently partisan and can be legally problematic. This paper introduces a non-partisan, structural distance metric to evaluate redistricting maps without relying on election data. By defining "central" maps within an ensemble of valid plans, we provide a mathematically rigorous way to identify gerrymandered maps as statistical outliers based solely on their geometry and connectivity.

Methodology: Distance over Redistricting Maps

Existing non-partisan efforts often struggle with the astronomical number of ways to partition a state. While researchers use Markov Chain Monte Carlo (MCMC) methods to sample thousands of valid maps, they have lacked an efficient way to find the "most typical" map. Our framework addresses this through a structural representation.

Adjacency Representation

We represent a map as an adjacency matrix where an entry is 1 if two voting units are in the same district and 0 otherwise. This allows us to treat the partitioning problem as a graph-based structural problem.

Mapping a partition $M_2$ to its corresponding adjacency matrix representation $A_2$.

Distance Metric and Centrality

We define a family of distance measures (weighted Hamming distances) that calculate the "edit distance" between two maps—essentially, how many voters would need to be moved to turn one map into another.

Visualizing the distance between two maps $A_1$ and $A_2$ by identifying shared and differing district assignments.

From this metric, we derive two key concepts:

  • The Centroid: The "average" of all maps in a sample. While not a valid map itself, it represents the probability that any two units will be grouped together.
  • The Medoid: The "most central" valid map—the one that minimizes the total distance to all other maps in the ensemble.

By proving a Decomposition Theorem, we enable the calculation of the medoid in linear time ($O(T)$) relative to the number of samples, making it feasible to analyze ensembles of 200,000+ maps.

Key Insights and Results

Structural Outliers are Partisan Outliers

The most striking insight is that maps widely considered to be partisan gerrymanders (such as the 2011 and 2016 North Carolina enacted maps) are also extreme structural outliers. These maps exist in the 99th percentile of distance from the central map. Conversely, "remedial" maps drawn by non-partisan judges fall near the peak of the distance distribution, appearing "typical."

Geometry over Politics

Because the metric ignores election data, it provides a "cleaner" signal for courts. If a map is structurally anomalous compared to 200,000 other valid options, it suggests intentional strategic manipulation. Furthermore, we justify the medoid map by showing it mirrors the Kemeny ranking, a classic method in social choice theory for finding consensus.

Conclusion

While this metric provides a robust tool for outlier detection, proximity to the center does not guarantee absolute fairness. A sophisticated legislature could potentially create a "stealth gerrymander" that is structurally close to the center but still provides a decisive partisan edge. Future work will focus on integrating this distance metric into the map-generation process to steer sampling toward more central, and thus more typical, regions.

Summary updated

Abstract

In representative democracy, a redistricting map is chosen to partition an electorate into a collection of districts each of which 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 imposed constraints are still loose enough to enable an enormous ensemble of valid redistricting maps. This fact introduces a difficulty in drawing redistricting maps and it also enables a partisan legislature to possibly 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 as being "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 run-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. More precisely, we show gerrymandered maps 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{esmaeili2024centralized,
  author = {Seyed A. Esmaeili and Hayley Grape and Brian Brubach},
  title = {{Centralized Fairness for Redistricting}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=xO6brLL24e},
}
Figure