Using Optimization to Support Minority Representation in Voting Rights Act Cases

Author note. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation or Oklahoma State University.

In June 2023, the U.S. Supreme Court announced its decision in the case Allen v. Milligan, finding in favor of Evan Milligan and other Black voters. As a result, Alabama’s congressional districts would need to be redrawn. In its opinion [1], the Supreme Court mentioned mathematics professor and districting expert Moon Duchin by name 46 times. Why? What did Duchin do? In short, she used computer optimization methods to help draw districting plans.

By now, we are all familiar with the practice of gerrymandering, in which those in power draw districts to favor themselves or their party. This is not what Duchin used optimization for; she was hired to draw alternative maps that could be used to challenge an enacted map in court. Alabama’s enacted map divided voters from Alabama’s Black Belt (a region with black fertile soil that was farmed by Black slaves for many years) across multiple districts. Consequently, although 27% of the state had marked “Black or African American” on their 2020 census form, only one in seven districts (14%) was likely to elect Black voters’ preferred candidates. In such circumstances, plaintiffs can sue under Section 2 of the Voting Rights Act (VRA) as a vote dilution claim. This federal law formed the legal basis for the Milligan plaintiffs.

To bring their lawsuit, the Milligan plaintiffs first needed to satisfy the Gingles preconditions. These preconditions were established by the Supreme Court in the 1986 case Thornburg v. Gingles. The first precondition that the plaintiffs must show is compactness, i.e., that “the minority group… is sufficiently large and geographically compact to constitute a majority in a single-member district.” These demonstration districts are needed to show that it is possible for the minority group to achieve better representation in an alternative districting plan. The second and third preconditions require the plaintiffs to demonstrate the existence of racially polarized voting. That is, they must show that the minority group is politically cohesive (tending to vote together) but that their preferred candidates typically lose elections to the majority group’s preferred candidates. Given that Alabama has some of the nation’s most pronounced racially polarized voting, the second and third preconditions are relatively easy to establish.

Drawing Demonstration Districts

However, lead plaintiff Evan Milligan found it difficult to meet the first Gingles precondition when drawing demonstration districts by hand [2]:

“Our team had tried to, you know, using Maptitude and Dave’s Redistricting – by our team, I’m talking about my co-worker and some of the – some of the other folks that had taken map-making training courses, had attempted to make a congressional map that would provide two districts that were majority Black or majority non-white, and weren’t able to do so successfully.”

Only later did Milligan learn that drawing a second Black-majority district was even possible:

“I was able to… read a letter that was submitted to the apportionment committee by a group of Civil Rights advocate organizations that featured maps prepared by [the NAACP Legal Defense and Educational Fund] and also a reference to a racial-polarization study that they… hired a researcher to conduct. And that was my first time actually seeing that data and being able to look at the maps and have a better understanding of what was really possible with our demographic data. And that convinced me that… those were the maps that most closely aligned… with our organization's concerns with regards to the voting rights of… Black voters throughout the state.”

This is when mathematician Moon Duchin enters the picture. Her testimony describes her map-drawing process [3]:

“As a first step… I used algorithms developed in my lab to… generate large numbers of different possibilities that would show me if it was possible to find two majority-Black districts. And I found that it was possible. My randomized algorithms found plans with two majority-Black districts in literally thousands of different ways. Convinced that that was possible, I then turned to drawing by hand.”

Duchin’s randomized algorithms follow a Markov chain Monte Carlo (MCMC) approach that repeatedly and randomly moves from one districting plan to a similar or “neighboring” districting plan. Optimizers will notice similarities to local search. In particular, Duchin’s local search neighborhood is called “recombination” in which two adjacent districts are merged into a double district, a spanning tree is drawn over their nodes, and a tree edge is deleted at random to divide the tree into two new districts. Her testimony also speaks the language of optimization, with terms such as “constraints” and her “objective function” that credited one point to a majority-minority district and partial points to others (e.g., a 47% Black district would receive 0.47 points).

Reasonably Configured Districts

To pass legal muster, political districts should satisfy several properties. For example, traditional redistricting principles dictate that districts should have equal populations, be contiguous on the map, have reasonably compact shapes and preserve political subdivisions such as counties. Otherwise, if race is seen as a “predominant factor” to the subordination of these principles, then the districting plan could be deemed a racial gerrymander, in violation of the Equal Protection Clause of the 14th Amendment, per the Supreme Court’s ruling in Shaw v. Reno (1993). In Shaw, the Supreme Court remarked that redistricting “is one area in which appearances do matter” and overturned a district that had a Polsby-Popper compactness score of just 0.01 on a scale from zero (least compact) to one (most compact).

So, Duchin could not draw just any districting plan with two Black-majority districts. The districts also had to be “reasonably configured,” comporting with traditional redistricting principles. Indeed, her expert report [3] focuses on this question, providing four alternative plans, each having two Black-majority districts and performing as well (or better) than the enacted plan on other criteria. For example, Alabama’s enacted plan had an average Polsby-Popper compactness score of 0.222, worse than the 0.249 score of Duchin’s plan. Both plans split counties a total of six times.

Aided by Duchin’s demonstration districts, the plaintiffs could continue with their lawsuit, Milligan v. Merrill, against defendant John Merrill, then Alabama Secretary of State. The case was heard by a three-judge District Court who ruled in favor of the Milligan plaintiffs. The Court found that the question of whether Alabama’s enacted plan violated Section 2 of the VRA was not a “close one” and required any remedial plan “to include two districts in which Black voters either comprise a voting-age majority or something quite close to it.”

Alabama immediately appealed to the Supreme Court who heard oral arguments in October 2022. Then, in June 2023, the Supreme Court ruled in favor of the Milligan plaintiffs (and against Alabama’s new Secretary of State Wes Allen), affirming 40 years of precedent and the Gingles framework. Alabama was then supposed to draw a new VRA-compliant map but defied the Court by drawing just one Black district. At the time of this writing, a court-appointed Special Master is drawing three remedial plans for the District Court to consider.

Optimization-Assisted Districting

In a recent paper, Pietro Belotti, Soraya Ezazipour and I propose optimization methods that can be used to draw demonstration districts for VRA cases [4]. To satisfy the first Gingles precondition, these districts must be reasonably configured, and the minority group should constitute a numerical majority (>50%) among the Voting Age Population (VAP), per the Supreme Court’s opinion in Bartlett v. Strickland (2009).

We can build a single majority-minority district using a mathematical optimization model as follows. Create a binary variable for each geographic unit i (e.g., county, census tract, census block) indicating whether it is selected in the district. To impose that the particular minority group forms a majority among the voting age population, we can write

,

where is the VAP of unit i and is its minority group’s VAP. To ensure that district has a nice shape, we can choose to maximize its Polsby-Popper score, which is the most popular compactness score in the redistricting literature and expert testimony. This score takes the form

,

where A is the district’s area and P its perimeter. Equivalently, we can minimize the inverse score , which can be captured in a second-order cone program as:

min z

s.t. ,

where z, A and P are variables. We point the reader to the full paper for the rest of the mixed-integer second-order cone programming (MISOCP) model, which also includes contiguity and population balance constraints.

With the MISOCP, we can find an optimally compact Black-majority district for Alabama. Or, we can find an optimally compact Black-majority “double district” by doubling the population bounds L and U, under the hypothesis that it could subsequently be split into two Black-majority districts. With a handful of other logical constraints (e.g., to promote county preservation), we arrive at the double district depicted in Figure 3. Interestingly, it largely follows the Black-majority districts 2 and 7 from Duchin’s Plan D. One difference is that Duchin’s plan better preserves the state’s Black Belt, an important community of interest, by including Barbour and Russell Counties.

We can extend the approach to draw districting plans with a desired number of majority-minority districts [4]. Ultimately, we find an alternative to Duchin’s Plan D that also splits counties a total of six times, but has an average Polsby-Popper score of 0.3068, a 40% improvement over the enacted plan and a 22% improvement over Duchin’s Plan D. This is not to say that it is better, but does demonstrate that it is compatible with traditional districting principles for Alabama to draw two Black-majority districts.

What This Means for the Future

In Allen v. Milligan, the Supreme Court affirmed the Gingles framework and greenlit the use of computer optimization methods to draw demonstration districts. Several other VRA cases are currently pending across the country, e.g., challenging congressional districts in Georgia and Louisiana and state legislative districts in Michigan and Washington. Heuristic optimization techniques (in the form of randomized MCMC algorithms) have been used in several of them to satisfy the first Gingles precondition. Circumstances may arise in which these heuristics fail to find a reasonably configured set of demonstration districts. Will this be because none exist, or because the heuristic was unlucky? We envision mathematical optimization techniques being used to definitively answer these questions and shed light on the tradeoffs between districting criteria.

References

1. https://www.supremecourt.gov/opinions/22pdf/21-1086_1co6.pdf
2. https://www.supremecourt.gov/DocketPDF/21/21-1086/221826/20220425150822178_42140%20pdf%20Bowdre%20IV%20Volume%202.pdf
3. https://www.supremecourt.gov/DocketPDF/21/21-1086/221826/20220425150837756_42140%20pdf%20Bowdre%20IV%20Supplemental%20JA.pdf
4. https://optimization-online.org/2023/05/political-districting-to-optimize-the-polsby-popper-compactness-score/