Redistricting—the process of drawing electoral boundaries—is frequently at the center of political controversy. While many fairness metrics focus on "global" proportionality (ensuring a party's seat share matches its vote share), these metrics often ignore geographic realities. A minority party might be so dispersed that no fair map can grant them a seat, or so clustered that "packing" them into a single district is inevitable. This research introduces a novel "local" fairness criterion for political redistricting, inspired by the concept of the core in cooperative game theory.
Defining Local Fairness
The authors propose that a partition is fair if no group of "unhappy" voters (those in a district dominated by the opposing party) can form a new, geographically contiguous, and population-balanced district where they would become the majority. If such a group exists, they have a "justified complaint."
In the 1D case, voters are modeled as points on a line. A partition is considered $(\epsilon, \beta)$-locally fair if no group of size approximately equal to a target population $\sigma$ (controlled by a slack parameter $\epsilon$) exists where at least $\beta \sigma$ voters are currently unhappy but would be the majority in their new hypothetical district.
Theoretical Thresholds and Existence
A central contribution of the paper is characterizing the conditions under which a fair partition is guaranteed to exist. The authors identify a sharp mathematical transition at the $\beta = 1 - \epsilon$ threshold. For small population deviations (e.g., $\epsilon \le 1/5$), if the required majority for a complaint ($\beta$) is high enough, a simple uniform partitioning strategy works. However, if $\beta < 1 - \epsilon$, the authors prove that adversarial voter distributions exist where no locally fair partition can ever be drawn.
In more "benign" or clustered settings—where voters live near others of the same party—local fairness is much easier to achieve. If monochromatic "runs" of voters are at least twice the size of a district ($2\sigma$), a fair partition almost always exists, provided a tiny fraction of the population is allowed to reside in "unbalanced" districts.
Algorithmic Solutions
Finding a fair partition is non-trivial even on a simple line because moving one boundary can create a ripple effect, potentially generating new justified complaints elsewhere. To solve this, the authors developed a dynamic programming (DP) algorithm. This algorithm decides if a fair partition exists in $O(n\sigma^3)$ time for $\epsilon < 1/3$ and $O(n\sigma^4)$ for larger $\epsilon$. This polynomial complexity makes the approach computationally feasible for 1D instances.
Limitations and Future Work
The most significant limitation of the current work is its focus on the 1D case. While the authors note that their negative results (lower bounds) translate to 2D, the 2D partitioning problem is significantly more complex because points are not linearly ordered and "nicely shaped" districts (compactness) are harder to define. Future research may explore adapting these DP techniques to hierarchical 2D decompositions or extending the model to multi-party systems.
Summary updated