# Implications of Distance over Redistricting Maps: Central and Outlier Maps

arXiv: https://arxiv.org/abs/2203.00872 · HTML: https://mlsanity.com/paper/2203.00872/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 44 references that are in the map.
- First posted on arXiv 2 Mar 2022.

## Builds on (most cited first, 10 of 10)

- [Clustering with Same-Cluster Queries](https://mlsanity.com/paper/1606.02404/) (2016)
- [A black-box adversarial attack for poisoning clustering](https://mlsanity.com/paper/2009.05474/) (2020)
- [Recombination: A family of Markov chains for redistricting](https://mlsanity.com/paper/1911.05725/) (2019)
- [Suspicion-Free Adversarial Attacks on Clustering Algorithms](https://mlsanity.com/paper/1911.07015/) (2019)
- [A Sub-Quadratic Exact Medoid Algorithm](https://mlsanity.com/paper/1605.06950/) (2016)
- [Geometry of Graph Partitions via Optimal Transport](https://mlsanity.com/paper/1910.09618/) (2019)
- [Assessing significance in a Markov chain without mixing](https://mlsanity.com/paper/1608.02014/) (2016)
- [Impartial Redistricting: A Markov Chain Approach](https://mlsanity.com/paper/1510.03247/) (2015)
- [A partisan districting protocol with provably nonpartisan outcomes](https://mlsanity.com/paper/1710.08781/) (2017)
- [Balanced Districting on Grid Graphs with Provable Compactness and Contiguity](https://mlsanity.com/paper/2102.05028/) (2021)

## Abstract (arXiv)

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.