Gerrymandering under Uncertain Preferences (Student Abstract)

Benjamin KellyAAAI 2022 · DOI

Introduction

Gerrymandering—the strategic manipulation of district boundaries to favor a specific political party—is a persistent challenge in democratic systems. Traditional computational models often treat voter preferences as fixed and perfectly predictable. However, real-world voting behavior is inherently uncertain, influenced by shifting political climates and individual volatility. This research addresses this gap by formalizing gerrymandering as a probabilistic optimization problem.

North Carolina's 2016 Contingent Congressional Plan illustrates the complex, often non-intuitive boundaries resulting from traditional gerrymandering efforts.

The PROB-GERRY Problem

The author introduces PROB-GERRY, a new decision problem that moves beyond deterministic assumptions. In this model, voters are represented as nodes in a graph where edges denote geographic proximity. Instead of a single certain vote, each voter is assigned a probability distribution over candidate rankings.

A valid solution to PROB-GERRY must partition the graph into connected districts that satisfy three primary conditions:

  1. The target candidate must have a minimum probability ($P_1$) of winning a specified number of districts.
  2. The target candidate must have a maximum probability ($P_2$) of losing a specified number of districts.
  3. The "ratio cap" (the size difference between the largest and smallest districts) must remain within a predefined limit to satisfy legal requirements for population balance.

Complexity and Algorithmic Approach

The research proves that PROB-GERRY is NP-Hard, establishing that finding an optimal solution is computationally intensive. When the number of candidates is constant and voter weights are bounded, the problem is shown to be NP-Complete.

To tackle this complexity, the author proposes a greedy algorithm. This heuristic approach starts with an empty set of edges and iteratively adds connections that maximize the probability of the target candidate achieving the desired electoral outcome, while strictly adhering to district size constraints.

Experimental Results

The algorithm was evaluated using 1,000 synthetic random graphs, each with 100 voters positioned in a 2D ideological space. Voter preferences were generated using the Plackett-Luce model, which correlates preference probabilities with the distance between voters and candidates.

A key finding of the study is the significant impact of the "ratio cap" on the feasibility of gerrymandering. As legal constraints on district size variation are loosened, the ability to successfully gerrymander increases dramatically.

The success rate of the greedy algorithm improves significantly as the allowed ratio cap (r-value) increases, demonstrating how population balance requirements act as a check on gerrymandering.

At a strict ratio cap of 2, the algorithm succeeded in only about 20% of cases. However, when the cap was increased to 8, the success rate climbed to nearly 80%. This highlights that the requirement for roughly equal-sized districts is one of the most effective barriers against sophisticated gerrymandering techniques.

Conclusion and Future Work

While the greedy algorithm provides a path forward, it remains computationally expensive, particularly as the number of candidates grows. Future research will focus on more efficient ways to handle the ratio cap and applying these probabilistic models to the complex, non-uniform geometries of actual states. Moving from synthetic graphs to real-world geographic data will be essential for developing tools that can better detect and prevent unfair redistricting in practice.

Summary updated

BibTeX
@inproceedings{kelly2022gerrymandering,
  author = {Benjamin Kelly},
  title = {{Gerrymandering under Uncertain Preferences (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i11.21626},
}
Figure