| October 11, 2021

Fairmandering: Generating Fairness-optimized Political Districts

Figure 1. Example of census tracts, adjacency graph, and district plan with \(k=3\) for Nebraska. Figure courtesy of Wes Gurnee.

All representative democracies must have a method in place that enables voters to choose their representatives. In the U.S., voters elect most congressional, state, and local representatives in winner-take-all elections within single-member districts that are drawn by partisan officials. Because the choice of district boundaries can greatly impact election results, party figures are able to engineer electoral outcomes by manipulating district maps — a practice that is broadly known as gerrymandering. However, allowing politicians to pick their voters undermines voters’ ability to pick their politicians, thus necessitating a more objective approach to redistricting.

To frame redistricting as a computational problem, we begin with an adjacency graph of atomic geographic blocks (such as precincts or census tracts) that comprise the entire state. Each of these blocks is associated with a population, and two blocks share an edge in the adjacency graph if they are physically next to each other. One solution to the political districting problem (PDP) involves partitioning the adjacency graph into \(k\) equal-population and contiguous subgraphs that represent the districts; this partition is commonly called a district plan or map (see Figure 1).

Because the PDP is an NP-hard problem in theory [16] and a hugely consequential problem in practice [10, 19], a large body of related work bridges the computational and political sciences. The two dominant strains of research in computational redistricting follow ensemble methods [1, 3, 6, 14] and optimization methods [5, 13, 15, 17, 18, 20]. Ensemble methods generate a large sample of “neutral” plans, which one can use to identify anomalous plans [4, 8, 12] or quantify the impact of potential policy proposals [2, 7, 9]. Conversely, optimization methods attempt to identify the most extreme plan with respect to some objective function—usually compactness or (un)fairness—that is subject to legal constraints. We approach the PDP with a decoupled formulation that combines ideas from both methods to generate a large ensemble that is very efficient for optimization purposes.

Figure 2. An example branch of a sample tree of North Carolina with a fan-out width of three. Figure courtesy of Wes Gurnee.

At a high level, our generation method [11] involves breaking down a state into increasingly smaller randomized regions until the regions’ populations are equal to the desired population of a district (see Figure 2 and Animation 1). By randomly sampling many different partitions, we create a tree of contiguous regions where the root node is the whole state and the leaf nodes are equal-population contiguous regions (i.e., legal districts). This tree is special because regions that share a common parent partition are composable — that is, we can combine them to create a legal district plan. More concretely, if we split a state in two and generate a million partitions for each half, we can combine any partitions of the left and right halves to yield one trillion partitions for the entire state! We can also apply this trick recursively. To generate one million partitions for each half, we can split the halves into quarters and generate a thousand partitions for each quarter, and so on. This tactic allows us to efficiently represent a massive number of distinct district plans while only explicitly generating a far smaller number of partitions.

Animation 1. A depth-first enumeration of all distinct partitions in the sample tree. Note that every distinct partition of the right half (as marked by the red line) is composable with every distinct partition of the left half to create a distinct partition of the state. Applied recursively (e.g., as marked by the blue lines), this approach generates an exponential number of distinct district plans. Animation courtesy of Wes Gurnee.

The second step involves solving a set-partitioning optimization problem to select the final \(k\) districts among the basket that we generated (i.e., the leaf nodes of the tree). This optimization process of course requires a fairness-oriented objective. Using past statewide election data, we can estimate the probability that every district we generate will be occupied by a Democrat or a Republican. In addition to population balance and contiguity, we can integrate a long list of additional rules and recommendations that vary by state, office, and enforceability (e.g., geometric compactness, competitiveness, preservation of county or municipal boundaries, compliance with the 1965 Voting Rights Act, and a host of political fairness metrics) as either hard constraints or objective costs in the generation and/or optimization stage. Due to these many dimensions of fair representation, we often employ multi-objective optimization to generate a Pareto curve that represents the optimal tradeoff between two or more objectives to better understand the overall map design space.

Our decoupled and hierarchical algorithm design enables unprecedented scalability in redistricting optimization. We demonstrate the effectiveness of our approach by generating a large ensemble for all multidistrict states and utilizing the optimization capability to efficiently understand the average as well as the range of potential outcomes. This range is important because it shows the natural variability of neutrality-drawn districts, which are generated in a partisan-blind manner [3]. Our results demonstrate that by simply using such neutral districts, one could swing the partisan composition of the House of Representatives (in expectation) by 20 percent! Furthermore, the range varies significantly by state, depending on its size and the spatial distribution of partisan voters (see Figure 3). Such results are critical for informing the policy process and defining actionable and enforceable fairness metrics.

Figure 3. The distribution of Republican seat-shares that our algorithm generates for every state with three or more congressional districts compared to the actual seat fraction of the past decade. This distribution also shows the ideal seat-share under the efficiency-gap metric of fairness that measures the gap in wasted votes between parties. Figure courtesy of Wes Gurnee.

We believe that computational redistricting should put tools in the hands of policymakers to facilitate rapid iteration on different maps with different rules, demonstrate the inherent tradeoffs that are forced by geography, and ultimately enable a more grounded discussion of how to balance the competing aspects of representation. For instance, our latest paper [9] analyzes the use of multimember districts (MMDs) with different voting rules in all 50 states and explicitly analyzes the Fair Representation Act, which would require the use of MMDs in congressional elections. We extend an open invitation to policymakers to collaborate on the design and evaluation of regionally-tailored policies and build a more representative democracy for the future.

Wes Gurnee presented this research during a minisymposium at the 2021 SIAM Conference on Optimization, which took place virtually in July. This work was also a proceedings paper at the 2021 SIAM Conference on Applied and Computational Discrete Algorithms and won the best paper award.

References
[1] Autry, E.A., Carter, D., Herschlag, G., Hunter, Z., & Mattingly, J.C. (2020). Multi-scale merge-split Markov chain Monte Carlo for redistricting. Preprint, arXiv:2008.08054.
[2] Cain, B.E., Cho, W.K.T., Liu, Y.Y., & Zhang, E.R. (2017). A reasonable bias approach to gerrymandering: Using automated plan generation to evaluate redistricting proposals. Wm. & Mary L. Rev., 59(5), 1521.
[3] Chen, J., & Rodden, J. (2013). Unintentional gerrymandering: Political geography and electoral bias in legislatures. Q. J. Political Sci., 8(3), 239-269.
[4] Chikina, M., Frieze, A., & Pegden, W. (2017). Assessing significance in a Markov chain without mixing. PNAS, 114(11), 2860-2864.
[5] Cohen-Addad, V., Klein, P.N., & Young, N.E. (2018). Balanced centroidal power diagrams for redistricting. In Proceedings of the 26th ACM SIGSPATIAL international conference on advances in geographic information systems (pp. 389-396). Seattle, WA.
[6] DeFord, D., Duchin, M., & Solomon, J. (2019). Recombination: A family of Markov chains for redistricting. Preprint, arXiv:1911.05725.
[7] DeFord, D., Duchin, M., & Solomon, J. (2020). A computational approach to measuring vote elasticity and competitiveness. Stat. Public Policy, 7(1), 69-86.
[8] Duchin, M. (2018). Outlier analysis for Pennsylvania congressional redistricting. MGGG Redistricting Lab.
[9] Garg, N., Gurnee, W., Rothschild, D., & Shmoys, D. (2021). Combatting gerrymandering with social choice: The design of multi-member districts. Preprint, arXiv:2107.07083.
[10] Gelman, A., & King, G. (1990). Estimating the electoral consequences of legislative redistricting. J. Am. Stat. Assoc., 85(410), 274-282.
[11] Gurnee, W., & Shmoys, D.B. (2021). Fairmandering: A column generation heuristic for fairness-optimized political districting. Preprint, arXiv:2103.11469.
[12] Herschlag, G., Ravier, R., & Mattingly, J.C. (2017). Evaluating partisan gerrymandering in Wisconsin. Preprint, arXiv:1709.01596.
[13] Hess, S.W., Weaver, J.B., Siegfeldt, H.J., Whelan, J.N., & Zitlau, P.A. (1965). Nonpartisan political redistricting by computer. Oper. Res., 13(6), 998-1006.
[14] Liu, Y.Y., Cho, W.K.T., & Wang, S. (2016). PEAR: A massively parallel evolutionary computation approach for political redistricting optimization and analysis. Swarm Evol. Comput., 30, 78-92.
[15] Mehrotra, A., Johnson, E.L., & Nemhauser, G.L. (1998). An optimization based heuristic for political districting. Manag. Sci., 44(8), 1100-1114.
[16] Puppe, C., & Tasnádi, A. (2008). A computational approach to unbiased districting. Math. Comput. Model., 48(9-10), 1455-1460.
[17] Ricca, F., Scozzari, A., & Simeone, B. (2008). Weighted Voronoi region algorithms for political districting. Math. Comput. Model., 48(9-10), 1468-1477.
[18] Ricca, F., Scozzari, A., & Simeone, B. (2013). Political districting: From classical models to recent approaches. Ann. Oper. Res., 204, 271-299.
[19] Stephanopoulos, N.O. (2017). The causes and consequences of gerrymandering. Wm. & Mary L. Rev., 59(5), 2115.
[20] Swamy, R., King, D., & Jacobson, S. (2019). Multi-objective optimization for political districting: A scalable multilevel approach. Optimization Online.

	Wes Gurnee is a Ph.D. student in the Operations Research Center at the Massachusetts Institute of Technology. He is broadly interested in the use of mathematical modeling and optimization to improve sociotechnical systems, with an emphasis on fairness and sustainability.
	David Shmoys is the Laibe/Acheson Professor and director of the Center for Data Science for Enterprise and Society at Cornell University. The primary focus of his research is the design and analysis of efficient algorithms for discrete optimization problems, particularly approximation algorithms for NP-hard and other computationally intractable problems.