Centralized Fairness for Redistricting

In representative democracy, the electorate is often partitioned into districts with each district electing a representative. Unfortunately, these systems have proven vulnerable to the practice of partisan gerrymandering. As a result, methods for detecting gerrymandered maps were introduced and have led to significant success. However, the question of how to draw district maps in a principled manner remains open with most of the existing literature focusing on optimizing certain properties such as geographical compactness or partisan competitiveness. In this work, we take an alternative approach which seeks to find the most "typical" redistricting map. More precisely, we introduce a family of well-motivated distance measures over redistricting maps. Then, by generating a large collection of maps using sampling techniques, we select the map which minimizes the sum of the distances from the collection, i.e., the most "central" map. We produce scalable, linear-time algorithms and derive sample complexity guarantees. We show that a by-product of our approach is the ability to detect gerrymandered maps as they are found to be outlier maps in terms of distance.