You Can Have Your Cake and Redistrict It Too

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 geography-related 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.

Funding: This work was supported in part by the National Science Foundation Graduate Research Fellowship Program [Grant DGE1745303] and also by a Google PhD fellowship.

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2023.0443.