You Can Have Your Cake and Redistrict It Too

• 成果类型: Article
• 署名作者: Benade, Gerdus; Procaccia, Ariel D.; Tucker-Foltz, Jamie
• 署名单位: Boston University; Harvard University; Yale University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0443
• 发表日期: 2026
• 关键词: Gerrymandering; political redistricting; fairness; price of fairness; geometric target; contiguity; EFFICIENCY

摘要

The design of algorithms for political redistricting generally takes one of two approaches: optimize an objective such as compactness or, drawing on fair division, construct a protocol whose outcomes guarantee partisan fairness. We aim to have the best of both worlds by optimizing an objective subject to a binary fairness constraint. As a fairness constraint, we adopt the geometric target, which requires the number of seats won by each party to be at least the average (rounded down) of its outcomes under its worst and best possible partitions of the state. Like proportionality, geometric targets cannot be guaranteed in the general graph redistricting model. We introduce a simplified model of redistricting, which closely mirrors the classic cake-cutting model. This model has two innovative features. First, in any part of the state, there is an underlying density of voters with political leanings toward any given party, making it impossible to finely separate voters for different parties into different districts. This captures a realistic geographyrelated constraint without explicitly needing to specify the detailed geography of the state. Second, parties may disagree on the distribution of voters-whether by genuine disagreement or attempted strategic behavior. In the absence of a ground truth distribution, a redistricting algorithm must therefore aim to simultaneously be fair to each party with respect to its own reported data. Our main theoretical result is that, surprisingly, the geometric target is always feasible in this model with respect to arbitrarily diverging data sets on how voters are distributed. A standard for fairness is only useful if it can be readily satisfied in practice. Empirically, we consider real election data and maps of six U.S. states. Despite the existence of worst-case constructions in which the geometric target cannot be guaranteed, in all these practical instances, we find that the geometric target is feasible, as our state-cutting model predicts. Moreover, imposing it as a fairness constraint comes at almost no cost to three common optimization objectives.