Locally Fair Partitioning

Pankaj K. Agarwal, Shao-Heng Ko, Kamesh Munagala, Erin Taylor

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.

Figure 1: A 1D voter distribution where a group D forms a potential deviating district, illustrating a 'justified complaint' against the existing partition.

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.

Figure 2: Visualization of district sizing constraints and the slack parameter ε used to define allowable partitions.

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

Abstract

We model the societal task of redistricting political districts as a partitioning problem: Given a set of $n$ points in the plane, each belonging to one of two parties, and a parameter $k$, our goal is to compute a partition $Π$ of the plane into regions so that each region contains roughly $σ= n/k$ points. $Π$ should satisfy a notion of ''local'' fairness, which is related to the notion of core, a well-studied concept in cooperative game theory. A region is associated with the majority party in that region, and a point is unhappy in $Π$ if it belongs to the minority party. A group $D$ of roughly $σ$ contiguous points is called a deviating group with respect to $Π$ if majority of points in $D$ are unhappy in $Π$. The partition $Π$ is locally fair if there is no deviating group with respect to $Π$. This paper focuses on a restricted case when points lie in $1$D. The problem is non-trivial even in this case. We consider both adversarial and ''beyond worst-case" settings for this problem. For the former, we characterize the input parameters for which a locally fair partition always exists; we also show that a locally fair partition may not exist for certain parameters. We then consider input models where there are ''runs'' of red and blue points. For such clustered inputs, we show that a locally fair partition may not exist for certain values of $σ$, but an approximate locally fair partition exists if we allow some regions to have smaller sizes. We finally present a polynomial-time algorithm for computing a locally fair partition if one exists.
BibTeX
@inproceedings{agarwal2022locally,
  author = {Pankaj K. Agarwal and Shao-Heng Ko and Kamesh Munagala and Erin Taylor},
  title = {{Locally Fair Partitioning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20401},
}

Loading related content...

Figure