You can have your cake and redistrict it too
Files
First author draft
Date
DOI
Authors
Benadè, Gerdus
Procaccia, Ariel
Tucker-Foltz, Jamie
Version
First author draft
OA Version
Citation
Johannes Gerdhardus Benade, Ariel Procaccia, Jamie Tucker-Foltz. "You can have your cake and redistrict it too." ACM Transactions on Economics and Computation,
Abstract
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 the 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 the worst and best partitions of the state; but we extend this notion to allow the two parties to compute their targets with respect to different election datasets. Our theoretical contribution is twofold: we introduce a new model of redistricting that closely mirrors the classic model of cake-cutting and we prove the feasibility of the geometric target in this model. Our empirical results, which use real election data and maps of six US states, demonstrate that the geometric target is feasible in practice and that imposing it as a fairness constraint comes at almost no cost to three well-studied optimization objectives.