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}\), 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}\)-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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Even though measuring partisan bias is a non-trivial issue, it has nonetheless been observed that two frequent indicators for partisan bias are cracking (Pierce et al. 2011) (dividing supporters of a specific party between two or more districts when they could be a majority in a single district) and packing (Pierce et al. 2011) (filling a district with more supporters of a specific party as long as this does not make this specific party the winner in that district). Other partisan bias indicators include hijacking (Pierce et al. 2011) (re-districting to force two incumbents to run against each other in one district) and kidnapping (Pierce et al. 2011) (moving an incumbent’s home address into another district).
See Sect. 2.4 regarding the impact of the SCOTUS gerrymandering ruling on 06/27/2019 on future gerrymandering studies.
Observations of similar nature but using different arguments were also made independently in Cho (2017).
In fact, we did try a more traditional simulated annealing approach that is more in tune with some of the previous researchers, but it did not give good results.
VTDs are the smallest units in a state for which the election data are available.
Occam’s razor principle (Ockham’s Razor 2010) states that “Entia non sunt multiplicanda praeter necessitatem” (i.e., more things should not be used than are necessary). It is also known as rule of parsimony in biological context (Fitch 1971). Overfitting is an example of violation of this principle.
Note that our notation uses the absolute value for \(\textsf {Effgap}_{\kappa }({\mathscr {P}},{\mathscr {Q}}_1,\dots ,{\mathscr {Q}}_\kappa )\) but not for individual \(\textsf {Effgap}({\mathscr {Q}}_j)\)’s.
Alternatively, one can think of the input being given as an arbitrary (not necessarily rectilinear) simple polygon \({\mathscr {P}}\), and the cells are arbitrary sub-polygons (without holes) inside \({\mathscr {P}}\) that form a partition of \({\mathscr {P}}\).
Past Court rulings seem to suggest that the courts may allow a maximum value of \(\varepsilon \) in the range of 0.05 to 0.1 (cf. US Supreme Court ruling in Karcher v. Daggett 1983).
As commonly done by researchers in gerrymandering of two-party systems, we ignore negligible “third-party” votes, i.e., votes for candidates other than the democratic and republican parties.
Virginia is one of the most gerrymandered states in the country, both on the congressional and state levels, based on lack of compactness and contiguity of its districts. Virginia congressional districts are ranked the 5th worst in the country because counties and cities are broken into multiple pieces to create heavily partisan districts (see footnote 12).
References
Aarts E, Lenstra JK (eds) (2003) Local search in combinatorial optimization. Princeton University Press, Princeton
Alon N, Spencer JH (2016) The probabilistic method. Wiley Inc., Hoboken
Altman M (2002) A Bayesian approach to detecting electoral manipulation. Polit Geogr 21:39–48
Baker BS (1994) Approximation algorithms for NP-complete problems on planar graphs. J Assoc Comput Mach 41(1):153–180
Balcazar JL, Diaz J, Gabarró J (1995) Structural complexity I. Springer, Berlin
Burnham KP, Anderson DR (2002) Model selection and multimodel inference. Springer, Berlin
Cain EB (1985) Simple vs. complex criteria for partisan gerrymandering: a comment on Niemi and Grofman. UCLA Law Rev 33:213–226
Chen J, Rodden J (2015) Cutting through the thicket: redistricting simulations and the detection of partisan gerrymanders. Elect Law J 14(4):331–345
Cho WKT (2017) Measuring partisan fairness: how well does the efficiency gap guard against sophisticated as well as simple-minded modes of partisan discrimination?. Univ Pa Law Rev 166(1), Article 2
Cho WKT, Liu YY (2016) Toward a talismanic redistricting tool: a computational method for identifying extreme redistricting plans. Elect Law J Rules Polit Policy 15(4):351–366
Cirincione C, Darling TA, O’Rourke TG (2000) Assessing South Carolina’s 1990s congressional redistricting. Polit Geogr 19:189–211
Cook SA (1971) The complexity of theorem proving procedures. In 3rd annual ACM symposium on the theory of computing, pp 151-158
DasGupta B, Liang J (2016) Models and algorithms for biomolecules and molecular networks. Wiley, Hoboken
Davis v. Bandemer (1986) 478 US 109
Doyle S (2015) A graph partitioning model of congressional redistricting. Rose-Hulman Undergr Math J 16(2):38–52
Faigman DL (1989) To have and have not: assessing the value of social science to the law as science and policy. Emory Law J 38:1005–1095
Fifield B, Higgins M, Imai K, Tarr A (2018) A new automated redistricting simulator using Markov chain Monte Carlo. Princeton University, Princeton
Fitch WM (1971) Toward defining the course of evolution: minimum change for a specified tree topology. Syst Zool 20(4):406–416
Garey MR, Johnson DS (1979) Computers and intractability–a guide to the theory of NP-completeness. W. H. Freeman & Co., San Francisco
Garey MR, Johnson DS, Stockmeyer L (1976) Some simplified NP-complete graph problems. Theor Comput Sci 1:237–267
Gelman A, King G (1994) A unified method of evaluating electoral systems and redistricting plans. Am J Polit Sci 38(2):514–554
Gill v. Whitford (2017) US Supreme Court docket no 16-1161, decision pending
Herschlag G, Ravier R, Mattingly JC (2017) Evaluating partisan gerrymandering in Wisconsin. arXiv:1709.01596
Jackman S (1994) Measuring electoral bias: Australia, 1949–93. Brit J Polit Sci 24(3):319–357
Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum, New York, pp 85–103
League of United Latin American Citizens v. Perry, 548 US 399 (2006)
Liu YY, Wendy K, Cho T, Wang S (2016) PEAR: a massively parallel evolutionary computational approach for political redistricting optimization and analysis. Swarm Evolut Comput 30:78–92
McGhee E (2014) Measuring partisan bias in single-member district electoral systems. Legis Stud Q 39(1):55–85
Motwani R, Raghavan P (1995) Randomized algorithms. Cambridge University Press, Cambridge
Niemi RG, Grofman B, Carlucci C, Hofeller T (1990) Measuring compactness and the role of a compactness standard in a test for partisan and racial gerrymandering. J Polit 52(4):1155–1181
Niemi RG, Deegan J (1978) A theory of political districting. Am Polit Sci Rev 72(4):1304–1323
“Ockham’s Razor”, Encyclopædia Britannica (2010)
Pierce O, Larson J, Beckett L (2011) Redistricting, a devil’s dictionary. ProPublica, Manhattan
“Redrawing the map on redistricting 2010: a national study” (Azavea White Paper, Azavea, 2009; https://cdn.azavea.com/com.redistrictingthenation/pdfs/Redistricting_The_Nation_White_Paper_2010.pdf)
Rucho et al. v. Common Cause et al., No. 18-422, argued March 26, 2019—decided June 27
Ryan JE (2003) The limited influence of social science evidence in modern desegregation cases. N C Law Rev 81(4):1659–1702
Stephanopoulos N, McGhee E (2015) Partisan gerrymandering and the efficiency gap. Univ Chicago Law Rev 82(2):831–900
Thoreson J, Liittschwager J (1967) Computers in behavioral science: legislative districting by computer simulation. Behavioral Science 12:237–247
Acknowledgements
T.C. and B.D. thankfully acknowledge support from NSF Grants IIS-1160995 and IIS-1814931. A.S. thankfully acknowledges support from NSF CAREER Award 1453472 and NSF Grant CCF-1423230. The raw data reported in this paper are tabulated in the Supplementary Materials and archived at http://www.cs.uic.edu/~dasgupta/gerrymander/index.html. The source code of our implemented program will also be made freely available from the same website.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Chatterjee, T., DasGupta, B., Palmieri, L. et al. On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering. J Comb Optim 40, 512–546 (2020). https://doi.org/10.1007/s10878-020-00589-x
Published:
Version of record:
Issue date:
DOI: https://doi.org/10.1007/s10878-020-00589-x