On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering

Tanima Chatterjee (), Bhaskar DasGupta (), Laura Palmieri (), Zainab Al-Qurashi () and Anastasios Sidiropoulos ()
Additional contact information
Tanima Chatterjee: University of Illinois at Chicago
Bhaskar DasGupta: University of Illinois at Chicago
Laura Palmieri: University of Illinois at Chicago
Zainab Al-Qurashi: University of Illinois at Chicago
Anastasios Sidiropoulos: University of Illinois at Chicago

Journal of Combinatorial Optimization, 2020, vol. 40, issue 2, No 11, 512-546

Abstract: 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. Recently, 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 article 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: (a) 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. Specifically, we prove the following results for the formalized minimization problem: (i) We show that the efficiency gap measure attains only a finite discrete set of rational values. (observations of similar nature but using different arguments were also made independently by Cho and Wendy (Univ Pa Law Rev 166(1), Article 2, 2017). (ii) We show that, assuming P $$\ne \textsf {NP}$$ ≠ NP , for general maps and arbitrary numeric electoral data the minimization problem does not admit any polynomial time algorithm with finite approximation ratio. Moreover, we show that the problem still remains $$\textsf {NP}$$ NP -complete even if the numeric electoral data is linear in the number of districts, provided the map is provided in the form of a planar graph (or, equivalently, a polygonal subdivision of the two-dimensional Euclidean plane). (iii) Notwithstanding the previous hardness results, we show that efficient exact or efficient approximation algorithms can be designed if one assumes some reasonable restrictions on the map and electoral data. Items (ii) and (iii) mentioned above are the first non-trivial computational complexity and algorithmic analyses of this measure of gerrymandering. (b) 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.

Keywords: Gerrymandering; Efficiency gap measure; Efficient algorithms; Computational complexity; 68Q17; 68Q25; 68W20; 68W25; 68W40; 90C59 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00589-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:40:y:2020:i:2:d:10.1007_s10878-020-00589-x

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00589-x

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().