Research map / Learning theory and algorithms / Prediction and decision losses
Implications of Distance over Redistricting Maps: Central and Outlier Maps
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces a tractable edit-distance family over redistricting maps, shows the centroid and medoid map relate to Kemeny aggregation, and uses distance from the sampled centroid to flag gerrymandered NC and PA maps without election data.
Problem
Redistricting maps are constrained only loosely, so the ensemble of valid maps is huge; there is no non-partisan, interpretable way to identify a "central" map or to detect gerrymandered maps as outliers, since existing sampling methods rely on election outcomes.
Approach
Define a weighted Hamming-style distance over binary adjacency matrices of partitions; by a decomposition theorem the sample medoid is the map closest to the sample centroid (mean adjacency matrix), giving O(T) computation, and enacted maps far from the centroid in distance percentile are flagged as outliers without election data.
Key results
- Gerrymandered NC enacted maps (2011 and 2016) and PA 2011 enacted map lie above the 99th percentile of distance from the centroid across three seeds, while remedial/judges' maps sit near the peak (about 50th to 65th percentile).
- Centroid estimates from three seeds differ by at most about 1.2e2 (unweighted) in squared distance, versus a minimum distance of about 1.05e5 between centroids and sampled maps for NC.
- Sample medoid is found in O(T) time via the decomposition theorem, and a negative result shows sampling cannot recover the population medoid with high probability.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Measure enacted-map distance from the centroid using unweighted distance | Redistricting-map outlier detection · NC | distance percentile: 2016 enacted map: 99.942, 99.927, 99.943; 2011 enacted map: 100.0, 100.0, 100.0; Judges' map: 58.362, 57.004, 54.558 | Helped |
| Measure enacted-map distance from the centroid using population-weighted distance | Redistricting-map outlier detection · NC | distance percentile: 2016 enacted map: 99.999; 99.997; 99.996; 2011 enacted map: 100.0; 100.0; 100.0; Judges' map: 65.359; 64.454; 63.238 | Helped |
| Measure enacted-map distance from the centroid using unweighted distance | Redistricting-map outlier detection · PA | distance percentile: 2011 enacted map: 100.0; 100.0; 100.0; Remedial map: 49.992; 51.875; 48.715 | Helped |
| Measure enacted-map distance from the centroid using population-weighted distance | Redistricting-map outlier detection · PA | distance percentile: 2011 enacted map: 100.0; 100.0; 100.0; Remedial map: 22.383; 20.956; 21.813 | Helped |
| Estimate the centroid from 200,000 sampled maps | Redistricting-map centroid estimation · NC | centroid distance: 1.2051×10^{2} vs 1.051030×10^{5}; 1.5446 × 10^{9} vs 1.333014×10^{12} | Helped |
Surprising findings
- Sampling arbitrarily many maps cannot guarantee finding the population medoid, even though the centroid converges.
- The distance histogram from the centroid is roughly normal and the gerrymandered maps are only identified in the tail, not as a clear separated cluster.
Limitations
- ReCom samples are MCMC and not i.i.d., so the theoretical sample-complexity guarantees do not strictly hold.
- Population medoid is an NP-hard constrained min k-cut problem; the medoid is only approximated by a heuristic.
- Evaluation is limited to three states and a few enacted and remedial maps.
Experimental setup
Datasets: North Carolina precinct graph and enacted/remedial maps Pennsylvania precinct graph and enacted/remedial maps Maryland precinct graph
Benchmarks: North Carolina redistricting ensemble Pennsylvania redistricting ensemble Maryland redistricting ensemble
Metrics: squared weighted distance percentile of distance from centroid centroid convergence distance
Baselines: ReCom ensemble election-outcome analysis Kemeny rule embedding-based redistricting distance (prior work)
Builds on: Kemeny rule ReCom Kendall tau distance
Closest papers by meaning
- Generalized Dimension Reduction Using Semi-Relaxed Gromov-Wasserstein Distance (AAAI 2025 · similarity 0.85)
- Distances Between Top-Truncated Elections of Different Sizes (AAAI 2025 · similarity 0.85)
- Metric Distortion of Line-up Elections: The Right Person for the Right Job (AAAI 2025 · similarity 0.84)
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.84)
- Proportional Representation in Metric Spaces and Low-Distortion Committee Selection (AAAI 2024 · similarity 0.83)
- Individual Fairness in Graph Decomposition (ICML 2024 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.