Wesley Pegden, an associate professor of mathematical sciences at Carnegie Mellon University, appeared as an expert witness in the gerrymandering case in Pennsylvania. Ariel D. Procaccia is an associate professor of computer science at Carnegie Mellon University.
Once a relatively obscure phenomenon, gerrymandering is having its moment. In the past year, there have been legal challenges to election district lines in Wisconsin, Maryland, North Carolina and in our home state of Pennsylvania.
Regardless of the outcome of these cases, it’s clear the methods we use to draw our political maps are broken. Where new maps are drawn by state legislatures, majority parties have few checks on their ability to shape districts as they please, creating a circular process that keeps them in power, even when winning a minority of statewide votes. One alternative is to give responsibility to independent commissions, as states such as Alaska, Arizona, California, Idaho, Montana and Washington have done. But this solution hinges on having workable procedures to identify truly independent commissioners who can resist manipulation from savvy politicians.
There’s another way to solve the problem — one that draws fairer maps by leveraging the competition between Democrats and Republicans rather than by developing mechanisms to circumvent it. And it is as simple and intuitive as dividing up a cake.
Even children eventually learn that there is an easy and fair method for dividing a good between two people. To share a cake, one child can divide the cake into two pieces he views as equally desirable, and then the second child can choose her preferred slice. This classic “I cut, you choose” protocol guarantees the fairness of the outcome: The first child is indifferent between the two pieces, so he is happy with his share. And the second child is obviously content because she receives her preferred piece.
Now think of a state that is being redistricted as the cake, and of our two great political parties as, sadly, the children. This analogy inspired a redistricting protocol, “I cut, you freeze,” which we developed in a recent paper with our co-author Dingli Yu. To understand how it works, suppose the goal is to divide Wisconsin into its eight congressional districts. The first party divides the state into eight districts (in a way that satisfies all legal requirements) and hands the map to the second party. The second party freezes one of the eight districts drawn by the first party and then divides the unfrozen part of the state into seven new districts. The second party then returns the map to the first party, which then freezes one of the seven new districts, draws six more and hands it back to the second party. This process continues until, after seven rounds, all eight districts have been frozen.
Why is the “I cut, you freeze” protocol fair to both parties? Intuitively, neither party is able to unilaterally shape districts, as each party can only freeze districts drawn by the other party. In fact, we establish mathematically that this protocol can prevent one party from packing a targeted group of voters into a district. This property holds when both parties employ their best possible strategies, which might make use of sophisticated algorithms and detailed information about voters.
Our protocol also dramatically moderates the advantage that any party has in the process. When one party controls the redistricting process, it can be possible in principle for the party to draw a map in which it wins a majority of seats even if it only wins just more than 25 percent of the vote. Our protocol ties seat performance back to vote performance for both parties.
For any proposed solution to gerrymandering, the devil is certainly in the details, and our protocol has a few weaknesses. First, it is useless when a state has only two districts (as is the case in five states) and offers only a limited advantage when the number of districts is not much larger. And for states with many districts, it would be sensible to allow modifications to our protocol so that multiple districts can be frozen on each round, to speed up the process. But the key advantage of our protocol is simply that it can be used without having to figure out who can be trusted to really be fair.
The future of political districting has never been more uncertain. Will the Supreme Court find that partisan gerrymandering violates the Constitution? Will we achieve and defend fair and democratic maps in the courtroom, in citizens’ commissions or in the legislatures themselves? We don’t know the answers to these questions. But mathematics shows us that we can sometimes achieve fairness, perhaps unexpectedly, in purely adversarial settings. In today’s hyper-partisan climate, this is very good news.