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.
翻译:在代议制民主制中,选民往往被分成区,每个区选举一名代表,不幸的是,这些系统被证明很容易受到党派操纵做法的伤害,因此,采用了探测精密地图的方法,并取得了显著的成功。然而,如何以原则性的方式绘制地区地图的问题仍然开放,大多数现有文献侧重于优化某些特性,如地理紧凑性或党派竞争力。在这项工作中,我们采取了另一种办法,寻求找到最“典型”的重新分区地图。更确切地说,我们在重新划区地图上采用了一套动机良好的距离测量方法。然后,我们利用取样技术制作了大批地图,从而尽可能减少采集距离的总和,即最“中央”的地图。我们制作了可缩放的线性算法,并提出了样本复杂性保证。我们的方法的副产品是能够探测精密的地图,因为人们发现这些地图在距离上比远。