"I-Cut-You-Choose" Cake-Cutting Protocol Inspires Solution to Gerrymandering

CMU Researchers Say Fair Redistricting Possible Even With Partisan Maneuvering

Wednesday, November 1, 2017 - by Byron Spice (SCS) and Jocelyn Duffy (MCS)

A new study from CMU researchers shows that having two political parties divide up a state in an "I-Cut-You-Freeze" protocol would minimize gerrymandering.

Getting two political parties to equitably draw congressional district boundaries can seem hopeless, but Carnegie Mellon University researchers say the process can be improved by using an approach children use to share a piece of cake.

Just as having one child cut the cake and giving the second child first choice of the pieces avoids either feeling envious, having two political parties sequentially divide up a state in an "I-Cut-You-Freeze" protocol would minimize the practice of gerrymandering, where a dominant political party draws districts to maximize its electoral advantage.

The CMU protocol, developed by Ariel Procaccia, associate professor of computer science, and Wesley Pegden, associate professor of mathematical sciences, is the first to allow a fair division of a state into political districts without independent agents. It calls for one political party to divide a map of a state into the allotted number of districts, each with equal numbers of voters. Then the second party would choose one district to "freeze," so no further changes could be made to it, and remap the remaining districts as it likes.

The first party then would choose a second district to freeze from this map and proceed to redraw the remaining districts as it sees fit. This back-and-forth process would continue until all of the districts are frozen. For a state such as Pennsylvania with 18 congressional districts, this would require 17 cycles.

Pegden and Procaccia, along with Dingli Yu, a visiting computer science student from China's Tsinghua University, developed mathematical proofs that show their protocol does not give the first player an advantage over the second and that neither player can concentrate specific populations of voters into a district against the wishes of the other player. They have submitted a scientific paper on the results to a journal for publication.

"In the real world, you still might expect the results to be less than perfect," Pegden said. "But this would be much, much, much more fair and balanced than having one party do essentially whatever it wants."

Gerrymandering is a hot political topic, as politicians in control of state legislatures have used increasingly sophisticated computational tools to heighten their advantages during the redistricting that follows each U.S. census. Critics maintain the practice undermines democracy and some lower courts have struck down what they consider overly partisan redistricting plans.

The U.S. Supreme Court recently heard arguments in a case challenging Wisconsin's electoral map. An analysis co-authored by Pegden, which found Pennsylvania's congressional district maps are almost certainly the result of gerrymandering, has been cited in an amicus brief filed in the Wisconsin case.

Some states have tried to reduce gerrymandering by turning over the redistricting task to non-partisan commissions that include independent agents, as well as party regulars. However, determining who is independent is problematic and, though it may result in more equitable districting, the process still tends to protect incumbents.

"The big selling point for our approach is you don't have to rely on independent agents," said Procaccia, whose research in artificial intelligence focuses on the use of social choice and game theory for collective decision-making. "We can leverage the competition between republicans and democrats to produce an equitable result. Each party can pursue a strategy that guarantees it something that it wants."

Common gerrymandering tactics include "packing" districts by concentrating opponents' voters or specific minority populations in as few districts as possible, and "cracking" districts by splitting an opposing party's voters across multiple districts where they are in the minority. Under the CMU protocol, either party can prevent the other from packing a specific population into a single district. The net effect of packing and cracking districts, the researchers proved, will be balanced between the two players in the final districting.

If one party attempts to pack districts, for instance, the other party can simply not choose to freeze a packed district. And because that party can then remap the districts to eliminate the packing, the first party would not get the opportunity to freeze a packed district either.

Pegden and Procaccia acknowledge that their analysis assumes an idealized setting, but believe their protocol would have similar properties in the real world. It would be of little use, however, in states that have very few congressional districts.

"We don't know what the chances are that any state is going to implement our protocol," Procaccia said. "But it's important to recognize that competition between political parties doesn't have to mean that the division into districts can't be fair."

The National Science Foundation, the Sloan Foundation and the Office of Naval Research supported this research.

Read the Washington Post op-ed on gerrymandering by Pegden and Procaccia.

For more information, Contact:
Byron Spice | 412-268-9068 | bspice@cs.cmu.edu