Operations Research v. Gerrymandering

Sam Gutekunst

by Sam Gutekunst
FIRST PRIZE in OR/MS Tomorrow Student Writing Competition 2019
Samuel Gutekunst is a fourth year PhD Student in the School of Operations Research and Information Engineering at Cornell University.

The U.S. legal system is facing a flood of court cases that argue that certain political districts have been drawn to provide partisan advantage. Such a phenomenon is known as partisan gerrymandering, but demonstrating partisan gerrymandering has proved difficult. In the words of Justice Ginsburg, “the court...has not found a manageable, reliable measure of fairness for determining whether a partisan gerrymander violates the Constitution” (Liptak, 2017). Operations research is being applied to meet this challenge.

Figure 1, modified from Ingraham (2015), illustrates gerrymandering and its impact. Fifty people are to be split into five equally-sized, contiguous districts. Each person belongs to either party S (smiley-faces) or party A (angry-faces), and Figure 1 shows two districting plans with extremal outcomes. Districts where S wins are shaded. In the left plan, party S wins 100% of the districts despite having only 60% of the votes. Conversely, in the right plan party A wins a majority of the districts despite having a minority of the votes.

 Figure 1

Notice that, in the right plan, party A is able to systematically waste S votes. In the three non-shaded districts that A wins, the four losing S votes are wasted: they could be used to win other districts. In the two shaded districts, party S only needs five votes to win (or, at least, tie); the four extra S votes in each are again wasted. This example begs the question: can we use analytics to measure if district lines are fair?

Stephanopoulos and McGhee recently proposed the efficiency gap as a litmus test for partisan gerrymandering (Stephanopoulos and McGhee, 2015). Their proposed formula accounts for wasted votes exactly as above: In districts where a party loses, every vote cast for that party is wasted. In districts where a party wins, every vote cast for that party beyond the 50% threshold for winning is wasted. In every single district of the S-favored plan of Figure 1, for example, party S wastes one vote while party A wastes four. Let WA and WS respectively denote the number of wasted votes for A and S across an entire districting plan, and let T denote the total number of votes cast. The efficiency gap then compares the proportion of votes wasted by each party:


An efficiency gap near zero indicates a plan where the votes of neither party are being systematically wasted; Stephanopoulos and McGhee propose that an efficiency gap of 0.08 or more indicates that party A is being gerrymandered against.1 In the left plan of Figure 1, the efficiency gap is EG=(20-5)/50=0.3 and indicates that party A is being gerrymandered against. In the right plan, in contrast, the efficiency gap is EG=(5-20)/50=-0.3 and indicates that party S is being gerrymandered against.

It is a rare phenomenon, however, that a single number can capture all of the context necessary for making a decision. For example, since the 90’s Massachusetts has had either nine or ten seats in the U.S. House of Representatives. Despite a sizable proportion of Republican voters (roughly 30%-40%), no Massachusetts Republican has won a seat in the House since 1994. Such an extreme outcome naturally raises suspicions of gerrymandering, but the issue Republican voters face in Massachusetts is instead based on their geographic distribution throughout the state. As a toy example, consider Figure 2 which has 50 towns to be split into five districts of ten towns each. Every town has 2/3 support for S; any district composed of ten towns will have 2/3 support for party S; despite 1/3-map-wide support for A, party A will not win a single seat!

 Figure 2

The political distribution in Massachusetts is less contrived, but the situation is analogous: the locales with majority Republican support are not numerous or clustered. Under election data from several recent state-wide elections, Duchin et al. (2018) uses analytics to argue that there is not a possible districting plan that would give the Republicans a single seat in the U.S. House. Moreover, there is no possible districting plan that produces an efficiency gap of less than 11%. The question thus becomes: how can the efficiency gap account for local geography and politics so that it can be used in complex, real-world settings?

One tool to put metrics like the efficiency gap into context is Markov chain Monte Carlo (MCMC) simulation. Here MCMC simulation starts from a proposed districting plan and generates a large collection of random plans (an “ensemble”). Generally, these procedures start with a proposed plan and iteratively make small, random adjustments (e.g. moving a small number of voters from one district to another). Such adjustments are constrained to only happen when they preserve traditional districting principles (e.g. keeping districts contiguous).

As part of a recent case in the Pennsylvania Supreme Court, Duchin used MCMC to generate an ensemble with billions of possible districting plans similar to a suspicious plan and computed the efficiency gap of each (Duchin, 2018); the resulting histogram is shown in Figure 3 (modified from Duchin (2018)) where the red line indicates the efficiency gap of the suspicious plan Duchin was evaluating. Figure 3 provides strong evidence that the suspicious plan was drawn with partisan intent: it seems highly unlikely that a plan designed without partisan intent would have such an extreme, large efficiency gap.

 Figure 3

The efficiency gap is an exciting and powerful tool for identifying partisan gerrymandering. It is most useful when it can be evaluated in the proper political and geographical context; sophisticated analytics tools from the operations research community do just that. Many open questions remain, from developing and strengthening metrics for identifying gerrymandering to developing algorithms that draw fair districts. As progress on these questions continues, operations research will play a pivotal role in evaluating and disseminating these tools for use in the real world.

 1This rule of thumb is specifically for state legislative districting plans where a large efficiency gap is likely to persist through multiple election cycles. Symmetrically, a gap less than -0.08 indicates A is gerrymandering Stephanopoulos and McGhee (2015).


 [1] M. Duchin. Outlier analysis for Pennsylvania congressional redistricting, 2018.
 [2] M. Duchin, T. Gladkova, E. Henninger-Voss, B. Klingensmith, H. Newman, and H. Wheelen. Locating the representational baseline: Republicans in Massachusetts. arXiv:1810.09051, 2018.
 [3] C. Ingraham. This is the best explanation of gerrymandering you will ever see. The Washington Post, 2015. Image originally attributed to Stephen Nass.
 [4] A. Liptak. On Justice Ginsburg’s summer docket: Blunt talk on big cases. The New York Times, 2017.
 [5] N. O. Stephanopoulos and E. M. McGhee. Partisan gerrymandering and the efficiency gap. University of Chicago Law Review, 82:831, 2015.