Mathematics of political redistricting

SUMMARY: Mathematical algorithms are used in the process of redistricting and to help evaluate whether or not gerrymandering has occurred.

Introduction

Changes to political district boundaries, or redistricting, can be a complex and contentious issue. In democratic societies, the basic aim of redistricting is to assign voters to equipopulous geographical districts from which they will elect representatives, in order to reflect communities of interest and to improve representation. In the United States, congressional and legislative redistricting occurs every ten years, following the decennial census. Like many political tools, however, redistricting is subject to various influences and biases, whether intentional or unintentional.

Much of the controversy over redistricting involves so-called gerrymandering, in which district boundaries are selected to produce an outcome that is improperly favorable to some group. While gerrymandering is generally legal in the US (except for manipulation explicitly based on racial discrimination), it is deeply controversial. Many experts have examined the practice to better understand how it works and how it might be countered in the interest of fairer government. A mathematical approach may be useful in both these endeavors.

Both gerrymandering and redistricting in general can be characterized as mathematical optimization functions. For good-government redistricting, the optimization function is based on measures of representation and fair political outcomes. These measures may include the number of expected majority-minority districts and the number of competitive districts as well as bias and responsiveness of the expected seats-votes response curve. In contrast, a gerrymander may aim to minimize the number of districts in which a racial or ethnic minority can elect a representative, maximize the number of partisan seats, protect incumbents by creating districts that are not competitive, or obtain some other improper advantage.

Forms of Redistricting

Redistricting is the process of dividing a larger geographical unit into a fixed number of regions (known as districts). The formal aim of redistricting is to create the set of districts that yields the optimal results—as measured by some cost/benefit criteria—while at the same time meeting a set of constraints. The generalized redistricting problem applies to a variety of fields, including the assignment of sales territory; the site selection for warehouses, fire stations, and schools; and the division of political territories into election districts.

In political redistricting, a larger political unit, such as a state, is divided into a number of districts containing roughly equal numbers of people (or, in some jurisdictions, voters). The voters in each district will have the right to elect a fixed number of candidates to represent that district. In addition, the district plan must satisfy various legal requirements such that districts are geographically contiguous; composed of undivided subunits, such as counties, or census blocks; be nonempty; and do not overlap.

Mathematical Representation

In mathematical terms, both redistricting and gerrymandering are readily represented as a type of combinatoric partitioning problem. (The optimization problem is combinatoric because the rules for redistricting typically require that districts be constructed only from whole census blocks.) There are many specific formulations of this problem—all equivalent—including set-partitioning, integer-programming, polygon-divisioning, and graph-partitioning.

The law typically requires that each district is contiguous and has roughly equal population. For legislative districts, equal population may be within 10% of the “ideal” population; for congressional districts, only minimal differences are permitted. Thus, a common characterization of the redistricting problem is the weighted graph partition problem: find a partition of the entire graph (for example, state to be redistricted) that induces connected subgraphs (guaranteeing contiguity) of equal node-weight (guaranteeing equal population) and that maximizes some goal function.

The choice of goal function depends on the objectives of the redistricter. For example, a redistricter intent on creating a partisan gerrymander might use a goal function that estimates the expected probability of one party controlling the legislature under a given plan, or alternatively, the expected number of party-controlled seats—a crude estimate of this is the number of districts with party registration over 55%. In contrast, the goal function for a more fair-minded redistricter might be the number of expected competitive seats, the expected bias of the expected seats-vote curve, or another measure of political representation.

Computational Issues

The behavior and characteristics of a district can be readily predicted based on the properties of the units it contains. For example, it is relatively straightforward—using modern statistical modeling and computational methods—to predict the number of seats each party is likely to capture in the next election, given a particular districting plan.

However, although each plan may be easy to evaluate, and the problem of choosing the “best” plan is easy to formulate, actually finding the best plan is extremely difficult. In fact, it is provably “NP-complete.” NP-complete problems are generally considered by computer scientists and mathematicians to be computationally intractable. Surprisingly common forms of redistricting to optimize neutral, good-government, or partisan objectives (including compact, contiguous, equipopulous plans, proportionally representative plans, and partisan-seat maximizing plans) are all computationally intractable.

While algorithms exist to solve these problems precisely, reliably, and with certainty, the time required to obtain such a solution grows exponentially as the number of problems grow. Thus, it is impossible to use reliable solution methods for practical problems. Redistricting problems are instead solved computationally using heuristics (problem-solving procedures that provide no guarantees of yielding “good” solutions, although they may produce acceptable solutions in certain circumstances). In other words, when districts are created manually or with a computer, one usually cannot know whether these are the best districts possible.

Distinguishing Gerrymandering and Redistricting

In theory, and in US law, a gerrymander is distinguished by its effect and the intent of the redistricter. If the intent of the redistricter is to produce an improper outcome and is effective in achieving that outcome, a gerrymander has occurred. In practice—except in more extreme cases—distinguishing gerrymanders from ordinary redistricting is challenging for three reasons. First, although it may seem easy to identify gerrymanders by district shape alone (and many measures of shape “compactness” have been proposed), in fact, none of these measures is related strongly either theoretically or empirically to improper political intent or effect. Politically relevant groups are not uniformly distributed in space. Further, partisanship and demographics are often strongly correlated. For example, members of some parties tend to live in cities, and the poor are often clustered in neighborhoods. As a result, geographical compactness measures that may seem neutral on their face have predictable political biases when applied. Thus both scholars and the courts have declined to accept measures of geographical compactness for gerrymander detection.

Second, it is not feasible to determine the optimal plan for a given objective, or the statistical distribution of possible redistricting plans, because the problem is too difficult to compute. This makes it challenging to determine whether a redistricter intended or achieved maximization of a particular goal, or not. Third, there is generally a lack of consensus on how to measure the various dimensions of political representation. Thus even good-government redistricters may disagree as to the best “goal function” to use when creating a plan. These three issues makes it challenging to use statistical and quantitative methods to determine whether the properties of a proposed plan are extreme, to determine the intent of the redistricter, and to determine whether a particular plan has unambiguously violated representational values.

Bibliography

Altman, M. “A Bayesian Approach to Detecting Electoral Manipulation.” Political Geography 22, no.1 (2002).

Altman, M. “Is Automation the Answer? The Computational Complexity of Automated Redistricting.” Rutgers Computer and Technology Law Journal 23, no. 1 (1997).

Altman, M., and M. McDonald. “The Promises and Perils of Computers in Redistricting.” Duke Constitutional Law and Policy Journal 5 (2010).

Bischoff, Manon. "Geometry Reveals the Tricks Behind Gerrymandering." Scientific American, 10 Nov. 2022, www.scientificamerican.com/article/geometry-reveals-the-tricks-behind-gerrymandering/. Accessed 19 Mar. 2024.

Butler, D., and B. Cain. Congressional Redistricting: Comparative and Theoretical Perspectives. New York: Macmillan Publishing, 1992.

Cortona, P. G. di, C. Manzi, A. Pennisi, F. Ricca, and B. Simeone. Evaluation and Optimization of Electoral Systems. Society for Industrial & Applied Math Press, 1999.

Puppe, Clemens and Attlia Tasnadi. “A Computational Approach to Unbiased Districting.” Mathematical and Computer Modeling 48, nos. 9–10 (November 2008).

Puppe, Clemens and Attlia Tasnadi. “Optimal Redistricting Under Geographical Constraints: Why ‘Pack and Crack’ Does Not Work.” Economics Letter 105 (2009).

Roberts, Siobhan. "Mathematicians Are Deploying Algorithms to Stop Gerrymandering." MIT Technology Review, 12 Aug. 2021, www.technologyreview.com/2021/08/12/1031567/mathematicians-algorithms-stop-gerrymandering/. Accessed 19 Mar. 2024.