Fairmandering: A column generation heuristic for fairness-optimized political districting
Fairmandering: A column generation heuristic for fairness-optimized political districting
复制标题
Fairmandering：公平优化政治选区的列生成启发式
DOI：
10.1137/1.9781611976830.9
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
D. Shmoys
中科院分区：
文献类型：
--
作者：
Wes Gurnee;D. Shmoys
美国赢家通吃的国会选区制度赋予政客们通过操纵选区边界来设计选举结果的权力。现有的计算解决方案大多专注于通过忽略政治和人口输入来绘制无偏见的地图，而只是简单地优化紧凑性。我们认为这是一个有缺陷的方法，因为紧凑性和公平性是正交的性质，并引入了一个可扩展的两阶段方法来显式地优化任意分段线性的公平性定义。第一阶段是一种随机化的分而治之的列生成启发式算法，它通过利用图划分问题的组成结构来生成指数数量的不同分区计划。这一地区集合形成了主选择问题的输入，以选择要包括在最终计划中的地区。我们的分离设计允许在定义公平对齐的目标函数方面具有前所未有的灵活性。该管道是任意可并行化的，可以灵活地支持额外的重新划分限制，并且可以应用于广泛的其他区域化问题。在有史以来对国会选区进行的最大规模的整体研究中，我们使用我们的方法来理解可能的预期结果的范围，以及这个范围对公平的潜在定义的影响。
The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. Existing computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimize for compactness. We claim that this is a flawed approach because compactness and fairness are orthogonal qualities, and introduce a scalable two-stage method to explicitly optimize for arbitrary piecewise-linear definitions of fairness. The first stage is a randomized divide-and-conquer column generation heuristic which produces an exponential number of distinct district plans by exploiting the compositional structure of graph partitioning problems. This district ensemble forms the input to a master selection problem to choose the districts to include in the final plan. Our decoupled design allows for unprecedented flexibility in defining fairness-aligned objective functions. The pipeline is arbitrarily parallelizable, is flexible to support additional redistricting constraints, and can be applied to a wide array of other regionalization problems. In the largest ever ensemble study of congressional districts, we use our method to understand the range of possible expected outcomes and the implications of this range on potential definitions of fairness.
登录
查看更多内容
用于重新划分的平衡质心功率图
DOI：
10.1145/3274895.3274979
发表时间：
2018
期刊：
Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
影响因子：
--
作者：
Cohen-Addad, Vincent;Klein, Philip N.;Young, Neal E.
通讯作者：
Young, Neal E.
通过最佳传输的图分区的几何形状
影响因子：
3.1
作者：
Abrishami, Tara;Guillen, Nestor;Rule, Parker;Schutzman, Zachary;Solomon, Justin;Weighill, Thomas;Wu, Si
通讯作者：
Wu, Si
DOI：
10.1073/pnas.1617540114
发表时间：
2017-03-14
影响因子：
11.1
作者：
Chikina, Maria;Frieze, Alan;Pegden, Wesley
通讯作者：
Pegden, Wesley
公平的选区重划很难
影响因子：
1.1
作者：
Kueng, Richard;Mixon, Dustin G.;Villar, Soledad
通讯作者：
Villar, Soledad