Carnegie Mellon researchers combat partisan gerrymandering

Credit: Paola Mathus/ Credit: Paola Mathus/

In the United States, as one of the first countries founded on the basis of democratically electing government officials, the practice of gerrymandering, defined as drawing election districts in a way that favors one political party over another, is almost as old as the country itself, starting with some of the first elections in this country. In 1788, Patrick Henry and his Anti-Federalist allies tried to draw districts in such a way to keep James Madison out of the U.S. House of Representatives, although they were unsuccessful.

More recently, the GOP has increasingly been criticized for using sophisticated algorithms to draw districts in such a way that heavily favors their own party, using methods such as packing minority voters (who tend to vote Democratic) in as few districts as possible, or splitting opponents’ voters into as many districts as possible so the opponents are in the minority. Currently, the Supreme Court is in the midst of a case related to Wisconsin’s redistricting practices that some have criticized as unconstitutional.

In order to alleviate this problem, some states have hired independent commissions to draw districts. But Carnegie Mellon researchers see another solution without involving independent commissions. Ariel Proccacia, associate professor of computer science, and Wesley Pegden, associate professor of mathematics, recently submitted a paper detailing an algorithm using computational social choice theory to ensure fair division, research that was supported by the National Science Foundation, the Sloan Foundation and the Office of Naval Research, according to a university press release.

The algorithm can be thought of as an extension of the method children use to divide a cake into two — one child cuts the cake in half while the other child takes his or her preferred piece, reducing envy. Applied to gerrymandering, the algorithm would entail having one party divide up the districts, then having the other party choosing one district to “freeze” — or finalize so that no one can subsequently change it — and re-mapping the remaining districts according to its preferences, and so on until all the districts are “frozen”.

In their paper, Proccacia, Pegden, and Dingli Yu, a visiting student from China’s Tsinghua University, detailed a mathematical proof of why this division protocol puts both parties on equal footing.
“If one party attempts to pack districts, for instance, the other party can simply not choose to freeze a packed district [one where specific concentrations of voters are packed into a district]. And because that party can then re-map the districts to eliminate the packing, the first party would not get the opportunity to freeze a packed district either,” details a university press release regarding the intuition behind the fairness of the algorithm.

In an interview with The Tartan, Pegden detailed the motivation behind the project and why he and the team wanted to apply cake-cutting techniques in particular. “The mathematics of fair division is all about leveraging competition between two sides to get a fair outcome; cake cutting is the classic example. If we want to be able to draw fair districts and we don’t know how to find truly independent agents, then fair division algorithms were a natural thing to aim for,” explained Pegden, who had previously done research on detecting gerrymandering.

Proccacia saw gerrymandering as a natural extension of the ideas behind cake-cutting. “The viewpoint [behind cake-cutting] seems natural in the context of redistricting (replacing ‘good’ with ‘state’), as we would like to see the two parties interact in a way that gives rise to a districting both sides perceive as fair,” said Proccacia.

Pegden and Proccacia’s goal is that ultimately, states will adopt this protocol as their method of redistricting. They hope to promote this method through more press coverage and start a grassroots national conversation surrounding fair redistricting techniques.