Multiobjective Optimization for Politically Fair Districting: A Scalable Multilevel Approach

References

• Abramowitz AI, Alexander B, Gunning M (2006) Incumbency, redistricting, and the decline of competition in U.S. House elections. J. Politics 68(1):75–88.Crossref, Google Scholar
• Adams WP, Sherali HD (1990) Linearization strategies for a class of zero-one mixed integer programming problems. Oper. Res. 38(2):217–226.Link, Google Scholar
• Bacao F, Lobo V, Painho M (2005) Applying genetic algorithms to zone design. Soft Comput. 9(5):341–348.Crossref, Google Scholar
• Ballotpedia (2020) Missouri Senate Joint Resolution No. 38. Accessed January 28, 2021, https://legiscan.com/MO/text/SJR38/2020.Google Scholar
• Benadè G, Procaccia AD, Tucker-Foltz J (2021) You can have your cake and redistrict it too. ACM Transactions on Economics and Computation.Google Scholar
• Bernstein M, Duchin M (2017) A formula goes to court: Partisan gerrymandering and the efficiency gap. Notices Amer. Math. Soc. 64(9):1020–1024.Crossref, Google Scholar
• Bozkaya B, Erkut E, Laporte G (2003) A tabu search heuristic and adaptive memory procedure for political districting. Eur. J. Oper. Res. 144(1):12–26.Crossref, Google Scholar
• Browdy MH (1990) Simulated annealing: An improved computer model for political redistricting. Yale Law Policy Rev. 8(1):163–179.Google Scholar
• Buluç A, Meyerhenke H, Safro I, Sanders P, Schulz C (2016) Recent advances in graph partitioning. Algorithm Engineering (Springer, Berlin), 117–158.Crossref, Google Scholar
• Chambers CP, Miller AD, Sobel J (2017) Flaws in the efficiency gap. J. Law Politics 33:1.Google Scholar
• Chatterjee T, DasGupta B, Palmieri L, Al-Qurashi Z, Sidiropoulos A (2020) On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering. J. Combinatorial Optim. 40:512–546.Crossref, Google Scholar
• Chen J, Rodden J (2013) Unintentional gerrymandering: Political geography and electoral bias in legislatures. Quart. J. Political Sci. 8(3):239–269.Crossref, Google Scholar
• Chiandussi G, Codegone M, Ferrero S, Varesio FE (2012) Comparison of multi-objective optimization methodologies for engineering applications. Comput. Math. Appl. 63(5):912–942.Crossref, Google Scholar
• D’Amico SJ, Wang SJ, Batta R, Rump CM (2002) A simulated annealing approach to police district design. Comput. Oper. Res. 29(6):667–684.Crossref, Google Scholar
• De Silva J, Gales B, Kagy B, Offner D (2018) An analysis of a fair division protocol for drawing legislative districts. Preprint, submitted November 14, https://arxiv.org/abs/ 1811.05705.Google Scholar
• DeFord D, Dhamankar N, Duchin M, Gupta V, McPike M, Schoenbach G, Sim KW (2020) Implementing partisan symmetry: Problems and paradoxes. Preprint, submitted August 16, https://arxiv.org/abs/200806930.Google Scholar
• DeFord D, Duchin M (2019) Redistricting reform in Virginia: Districting criteria in context. Virginia Policy Rev. 12(2):120–146.Google Scholar
• DeFord D, Duchin M, Solomon J (2019) Recombination: A family of Markov chains for redistricting. Preprint, submitted October 31, https://arxiv.org/abs/ 191105725.Google Scholar
• Drexl A, Haase K (1999) Fast approximation methods for sales force deployment. Management Sci. 45(10):1307–1323.Link, Google Scholar
• Duchin M (2018) Gerrymandering metrics: How to measure? What’s the baseline? Preprint, submitted January 6, https://arxiv.org/abs/ 1801.02064.Google Scholar
• Edmonds J (1965) Paths, trees, and flowers. Canadian J. Math. 17:449–467.Crossref, Google Scholar
• Eppstein D (2003) Find maximum cardinality matching in general undirected graph. Accessed May 5, 2020, https://www.ics.uci.edu/eppstein/PADS/CardinalityMatching.py.Google Scholar
• ESRI (2021) Efficiency gap (measure of partisan gias in redistricting) by state, 2016. Accessed October 27, 2021, https://www.arcgis.com/home/item.html?id=563f61cd84a344deb707eed3e0b258bd.Google Scholar
• Fifield B, Higgins M, Imai K, Tarr A (2020) Automated redistricting simulation using Markov chain Monte Carlo. J. Comput. Graphical Statist. 29(4):715–728.Google Scholar
• Friedman JN, Holden RT (2009) The rising incumbent reelection rate: What’s gerrymandering got to do with it? J. Politics 71(2):593–611.Crossref, Google Scholar
• Gabow HN, Tarjan RE (1988) Algorithms for two bottleneck optimization problems. J. Algorithms 9(3):411–417.Crossref, Google Scholar
• Garey MR, Johnson DS (1978) “Strong” NP-completeness results: Motivation, examples, and implications. J. ACM 25(3):499–508.Crossref, Google Scholar
• Garfinkel RS, Nemhauser GL (1970) Optimal political districting by implicit enumeration techniques. Management Sci. 16(8):B–495.Link, Google Scholar
• Gentry S, Chow E, Massie A, Segev D (2015) Gerrymandering for justice: Redistricting U.S. liver allocation. Interfaces 45(5):462–480.Link, Google Scholar
• Gill et al. v. Whitford et al. (2018) U.S. Supreme Court Case No. 16-1161, U.S. https://www.supremecourt.gov/opinions/17pdf/16-1161_dc8f.pdf.Google Scholar
• Grofman B (1983) Measures of bias and proportionality in seats-votes relationships. Political Methodology 9(3):295–327.Google Scholar
• Grofman B, Cervas JR (2020) The terminology of districting. Preprint, submitted March 25, https://dx.doi.org/10.2139/ssrn.3540444.Google Scholar
• Grofman B, King G (2007) The future of partisan symmetry as a judicial test for partisan gerrymandering after LULAC v. Perry. Election Law J. 6(1):2–35.Google Scholar
• Haase K, Müller S (2014) Upper and lower bounds for the sales force deployment problem with explicit contiguity constraints. Eur. J. Oper. Res. 237(2):677–689.Crossref, Google Scholar
• Hendrickson B, Leland RW (1995) A multi-level algorithm for partitioning graphs. Brent R, Duke D, eds. Proc. ACM/IEEE Conf. on Supercomputing (ACM Digital Library, New York), 1–14.Google Scholar
• Hess S, Weaver J, Siegfeldt H, Whelan J, Zitlau P (1965) Nonpartisan political redistricting by computer. Oper. Res. 13(6):998–1006.Link, Google Scholar
• Jackman S (1994) Measuring electoral bias: Australia, 1949–93. British J. Political Sci. 24(3):319–357.Crossref, Google Scholar
• Jones PE (2013) The effect of political competition on democratic accountability. Political Behav. 35(3):481–515.Crossref, Google Scholar
• Joshi D, Soh J, Samal A (2012) Redistricting using constrained polygonal clustering. IEEE Trans. Knowledge Data Engrg. 24(11):2065–2079.Crossref, Google Scholar
• Kalcsics J, Ríos-Mercado RZ (2019) Districting problems. Laporte G, Nickel S, Saldanha da Gama F, eds. (chapter 25), Location Science (Springer, Cham, Switzerland), 705–743.Crossref, Google Scholar
• Karypis G, Kumar V (1998) A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1):359–392.Crossref, Google Scholar
• Katz JN, King G, Rosenblatt E (2020) Theoretical foundations and empirical evaluations of partisan fairness in district-based democracies. Amer. Political Sci. Rev. 114(1):164–178.Crossref, Google Scholar
• Kennedy L, Corriher B, Root D (2016) Redistricting and representation. Accessed October 27, 2021, https://www.americanprogress.org/issues/democracy/reports/2016/12/05/294272/redistricting-and-representation/.Google Scholar
• Kernighan BW, Lin S (1970) An efficient heuristic procedure for partitioning graphs. Bell Systems Tech. J. 49(2):291–307.Crossref, Google Scholar
• King DM, Jacobson SH, Sewell EC (2015) Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning. Math. Programming 149(1–2):425.Crossref, Google Scholar
• King G, Grofman B, Gelman A, Katz JN (2006) Brief of Amici Curiae Professors Gary King, Bernard Grofman, Andrew Gelman, and Jonathan N. Katz, in Support of Neither Party. Amici Brief for U.S. Supreme Court Case Nos. 05-204, 05-254, 05-276, 05-439. https://law.osu.edu/electionlaw/litigation/documents/Brief_Amici_Curiae_Professors_King_Grofman_Gelman_Katz.pdf.Google Scholar
• Landau Z, Su FE (2014) Fair division and redistricting. The Mathematics of Decisions, Elections, and Games (American Mathematical Society), 17–36.Google Scholar
• Lavrov M (2019) Is there a polynomial time algorithm for min max maximal matching problem? Mathematics Stack Exchange, Accessed November 30, 2019, https://math.stackexchange.com/q/3456687.Google Scholar
• Liu YY, Cho WKT, Wang S (2016) PEAR: A massively parallel evolutionary computation approach for political redistricting optimization and analysis. Swarm Evolution Comput. 30:78–92.Crossref, Google Scholar
• Ludden IG, Swamy R, King DM, Jacobson SH (2022) A bisection protocol for political redistricting. Technical report, University of Illinois at Urbana-Champaign, Urbana.Google Scholar
• Magleby DB, Mosesson DB (2018) A new approach for developing neutral redistricting plans. Political Anal. 26(2):147–167.Crossref, Google Scholar
• Mann TE (2005) Redistricting reform. The National Voter. Accessed December 25, 2020, https://www.brookings.edu/articles/redistricting-reform/.Google Scholar
• McCarty N, Poole KT, Rosenthal H (2009) Does gerrymandering cause polarization? Amer. J. Political Sci. 53(3):666–680.Crossref, Google Scholar
• McDonald MP (2006) Drawing the line on district competition. PS Political Sci. Politics 39(1):91–94.Crossref, Google Scholar
• McGovern T (2017) United States general election presidential results by county from 2008 to 2016. Accessed December 25, 2020, https://github.com/tonmcg/US_County_Level_Election_Results_08-16.Google Scholar
• Megiddo N, Supowit KJ (1984) On the complexity of some common geometric location problems. SIAM J. Comput. 13(1):182–196.Crossref, Google Scholar
• Mehrotra A, Johnson E, Nemhauser G (1998) An optimization based heuristic for political districting. Management Sci. 44(8):1100–1114.Link, Google Scholar
• MGGG (2021) The geospatial toolkit for redistricting data. Accessed October 24, 2021, https://github.com/mggg/maup.Google Scholar
• Micali S, Vazirani VV (1980) An O(|V||E|) algoithm for finding maximum matching in general graphs. Book RV, ed. Proc. 21st Annual Sympos. on Foundations of Comput. Sci. (IEEE, New York), 17–27.Google Scholar
• National Conference of State Legislatures (2020) Redistricting criteria. Accesssed December 25, 2020, https://www.ncsl.org/research/redistricting/redistricting-criteria.aspx.Google Scholar
• Oehrlein J, Haunert JH (2017) A cutting-plane method for contiguity-constrained spatial aggregation. J. Spatial Inform. Sci. 2017(15):89–120.Google Scholar
• Office of the Governor (2019) Executive Order 66: Relating to Creating the People’s Maps Commission (The State of Wisconsin). Legal document, https://evers.wi.gov/Documents/EO/EO066-PeoplesMapsCommission.pdf.Google Scholar
• Pegden W, Procaccia AD, Yu D (2017) A partisan districting protocol with provably nonpartisan outcomes. Preprint, submitted October 24, https://arxiv.org/abs/ 1710.08781.Google Scholar
• Ricca F, Simeone B (2008) Local search algorithms for political districting. Eur. J. Oper. Res. 189(3):1409–1426.Crossref, Google Scholar
• Ricca F, Scozzari A, Simeone B (2008) Weighted Voronoi region algorithms for political districting. Math. Comput. Modeling 48(9-10):1468–1477.Crossref, Google Scholar
• Ricca F, Scozzari A, Simeone B (2013) Political districting: From classical models to recent approaches. Ann. Oper. Res. 204(1):271.Crossref, Google Scholar
• Royden L, Li M (2017) Extreme maps (Brennan Center for Justice at New York University School of Law). Accessed May 2, 2018, https://www.brennancenter.org/sites/default/files/publications/Extreme%20Maps%205.16_0.pdf.Google Scholar
• Salazar-Aguilar MA, Ríos-Mercado RZ, González-Velarde JL (2011) A bi-objective programming model for designing compact and balanced territories in commercial districting. Transportation Res., Part C Emerging Tech. 19(5):885–895.Crossref, Google Scholar
• Shirabe T (2009) Districting modeling with exact contiguity constraints. Environmental Planning B Plannning Design 36(6):1053–1066.Crossref, Google Scholar
• Silverberg K (1995) Illegitimacy of the incumbent gerrymander. Texas Law Rev. 74:913.Google Scholar
• Stephanopoulos NO, McGhee EM (2015) Partisan gerrymandering and the efficiency gap. Univ. Chicago Law Rev. 82(2):831–900.Google Scholar
• Stephanopoulos NO, McGhee EM (2018) The measure of a metric the debate over quantifying partisan gerrymandering. Stanford Law Rev. 70(5).Google Scholar
• Swamy R (2022) Code companion for multi-objective optimization for politically fair districting: A scalable multilevel approach. https ://github.com/rahul-swamy/Multi-Objective-Politically-Fair-Districting.Google Scholar
• Tapp K (2018) Measuring political gerrymandering. Preprint, submitted January 8, https://arxiv.org/abs/ 1801.02541.Google Scholar
• The Guardian (2018) U.S. 2012 election data. Accessed May 5, 2018, https://www.theguardian.com/news/datablog/2012/nov/07/us-2012-election-county-results-download.Google Scholar
• Thoreson JD, Liittschwager JM (1967) Computers in behavioral science. Legislative districting by computer simulation. Behav. Sci. 12(3):237–247.Crossref, Google Scholar
• U.S. Census Bureau (2010) Census block tallies by state or state equivalent. Accessed December 27, 2017, https://www.census.gov/data.html.Google Scholar
• Validi H, Buchanan A, Lykhovyd E (2021) Imposing contiguity constraints in political districting models. Oper. Res. 70(2):867–892.Link, Google Scholar
• Veomett E (2018) Efficiency gap, voter turnout, and the efficiency principle. Election Law J. Rules Political Policy 17(4):249–263.Google Scholar
• Vickrey W (1961) On the prevention of gerrymandering. Political Sci. Quart. 76(1):105–110.Crossref, Google Scholar
• Walshaw C (2000) A multilevel algorithm for force-directed graph drawing. Marks J, ed. Proc. Internat. Sympos. on Graph Drawing (Springer, Berlin, Germany), 171–182.Google Scholar
• Walshaw C (2002) A multilevel approach to the travelling salesman problem. Oper. Res. 50(5):862–877.Link, Google Scholar
• Warrington GS (2018) Quantifying gerrymandering using the vote distribution. Election Law J. 17(1):39–57.Crossref, Google Scholar
• Wesberry et al v Sanders, Governor of Georgia, et al. (1964) U.S. Supreme Court Case 376 U.S. 1., No. 22. Accessed March 31, 2021, https://www.law.cornell.edu/supremecourt/text/376/1.Google Scholar
• Young HP (1988) Measuring the compactness of legislative districts. Legislative Studies Quarterly 13(1):105–115.Crossref, Google Scholar