CMU Algorithm Sniffs Out Gerrymandering

Wesley Pegden, professor of mathematical sciences at Carnegie Mellon University, proved that Pennsylvania’s congressional map was a partisan gerrymander—in fact, he showed that if you made trillions of districtings by making small random perturbations to the map, 99.9999999% of them of them would be fairer than the existing map, a property which is mathematically impossible to be typical for a Congressional districting, regardless of the political geography of a state. His expert testimony during a lawsuit led to the Pennsylvania supreme court throwing out the old map.

Gerrymandering is a political issue that gets a lot of people fired up. It’s become a key issue for voices on both sides of the political spectrum from former president Barack Obama to former governor of California Arnold Schwarzenegger. And, of course, many everyday voters, too.

Every 10 years, following each U.S. census, new congressional district boundaries are drawn. The legislative process of redistricting differs state by state, but in many states the maps are drawn by partisans of the majority party. Gerrymandering is a tactic that involves drawing district boundaries with the intent of benefiting one political party over another and/or disadvantaging a particular bloc of voters. 

The legality of the practice has recently been challenged in lawsuits across the country. Recently, the Supreme Court heard cases that challenged the district maps in Wisconsin and Maryland. And there are currently efforts to enact redistricting reform in many states, including ballot initiatives this year in Michigan, Missouri, and Utah. And other states, such as Ohio, have already taken action to make their elections more fair. 

Gerrymandering became a very hot issue in Pennsylvania earlier in 2018. The League of Women Voters brought a lawsuit against the state to argue that the congressional map, drawn by the state’s Republican-controlled General Assembly after the 2010 census, was an unconstitutional gerrymander. That lawsuit was ultimately successful, and the state adopted a new map in 2018.

Expert testimony played a major role in proving the League of Women Voters’ case. Wesley Pegden, professor of mathematical sciences at CMU’s Mellon College of Science, argued in court that math could be used to demonstrate that the Pennsylvania’s congressional map was unfairly biased.

Pegden created an algorithm that could rigorously test the fairness of congressional maps. His gerrymandering test does not rely solely on lopsided election outcomes or odd district shapes to determine bias. Instead, his model uses randomness and math to evaluate whether district boundaries have been “carefully crafted” to achieve partisan bias.

The model made small random changes to Pennsylvania’s map trillions of times (not a typo…trillions of times) and demonstrated that of the maps generated through these small random changes, less than 00.0000001% of the maps were as unfair as the original map. That staggering figure showed clear intent to produce a biased map, Pegden argued.

Moreover, in Pegden’s paper with co-authors Alan Frieze and Maria Chikina, they proved a theorem which implies that it is impossible, even in principle, for the political geography of a state to cause typical districtings of the state to exhibit fragile partisan bias. There might be states where the geographical distribution of Democrats and Republicans gives a natural districting advantage to one party, but in these cases, this advantage will not consistently evaporate when small random changes are made, as happens with the Pennsylvania districting.

Pegden’s work is a perfect example of how data and technology can be used to shift debates and re-shape policy. While experts and lawmakers often use data analytics to implement gradual improvements in programs and processes, sometimes arguments crafted with data and technology can disrupt the status quo and bring about rapid change. 

Pegden additionally advocates for a change in redistricting policy that would follow an “I-Cut-You-Choose” protocol involving both parties rather than simply the majority party. Pegden and CMU computer science professor Ariel Procaccia, together with a visiting student Dingli Yu, proved that the “I-Cut-You-Choose” method results in fairer maps. 

Check out the videos below, in which Pegden discusses his expert testimony for this case. The first video is a shorter TEDx talk at CMU, providing an overview of his findings; for a more in-depth explanation of his methods and Q&A, check out the second video of a presentation Pegden gave for Constitution Day 2018, hosted by Carnegie Mellon University Libraries.