Removing partisan bias in redistricting: computational complexity meets the science of gerrymandering

Abstract: Partisan gerrymandering is a major cause for voter disenfranchisement in United States. However, convincing US courts to adopt specific measures to quantify gerrymandering has been of limited success to date. Stephanopoulos and McGhee in several papers introduced a new measure of partisan gerrymandering via the so-called "efficiency gap" that computes the absolute difference of wasted votes between two political parties in a two-party system; from a legal point of view the measure was found legally convincing in a US appeals court in a case that claims that the legislative map of the state of Wisconsin was gerrymandered. The goal of this talk is to formalize and provide theoretical and empirical algorithmic analyses of the computational problem of minimizing this measure. To this effect, we show the following:

1. On the theoretical side, we formalize the corresponding minimization problem and provide non-trivial mathematical and computational complexity properties of the problem of minimizing the efficiency gap measure. These are the first non-trivial computational complexity and algorithmic analyses of this measure of gerrymandering.

2. On the empirical side, we provide a simple and fast algorithm that can "un-gerrymander" the district maps for the states of Texas, Virginia, Wisconsin and Pennsylvania (based on the efficiency gap measure) by bring their efficiency gaps to acceptable levels from the current unacceptable levels. To the best of our knowledge, ours is the first publicly available implementation and its corresponding evaluation on real data for any algorithm for the efficiency gap measure. Our work thus shows that, notwithstanding the general worst-case approximation hardness of the efficiency gap measure as shown by us, finding district maps with acceptable levels of efficiency gaps could be a computationally tractable problem from a practical point of view. Based on these empirical results, we also provide some interesting insights into three practical issues related the efficiency gap measure.

Joint work with Tanima Chatterjee, Laura Palmieri, Zainab Al-Qurashi and Anastasios Sidiropoulos.

data structures and algorithmsgame theorycomputational economicsoptimization and control

Audience: researchers in the discipline

( paper )

---

LA Combinatorics and Complexity Seminar

Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm

---