An impossibility theorem for gerrymandering

I just posted my latest paper on the arXiv, this one co-authored with Boris Alexeev. In this paper, we study a new technique that is currently being reviewed by the Supreme Court to detect unconstitutional gerrymandering. Recall that gerrymandering refers to the process whereby electoral district boundaries are manipulated in order to reduce or increase the voting power of a certain group of people. Gerrymandered districts are frequently detected by their bizarre shape. Here are some noteworthy examples (from Wikipedia):

Last year, the Supreme Court found NC-1 and NC-12 (the first two districts above) to be the result of unconstitutional racial gerrymandering. We’ll discuss IL-4 (the district on the right) later.

The Court is currently evaluating a proposal for systematically detecting unconstitutional partisan gerrymandering, where the gerrymander significantly benefits one party over the other. The proposed measure, called the efficiency gap, quantifies how disproportionately voters from the two parties cast “wasted” votes in an election. In particular, if a party wins a district with (50+x)% of the vote, then the x% were wasted, since they weren’t needed to get a majority. Meanwhile, if a party loses a district, then all votes cast in that district were wasted. The efficiency gap is the difference between the number of votes wasted by the left and right divided by the total number of votes. If the proposal goes through, any efficiency gap above 8% would implicate unconstitutional partisan gerrymandering. I highly recommend this paper by Bernstein and Duchin for a detailed discussion of efficiency gap; this episode of More Perfect is also worth a listen.

Our paper proves that in some cases, it’s impossible to get a small efficiency gap without drawing bizarrely shaped districts. Suppose for example that the voters are distributed as follows:

Here, each 3-by-3 square contains 5 blue voters and 4 red voters. Now suppose you are tasked with drawing 5 districts for this region. You might decide to ignore the voters’ preferences and run the shortest splitline algorithm. Doing so would produce the following districts:

In this case, the districts don’t exhibit irregular shape, but blue wins every single district—even though red makes up 44% of the vote! The efficiency gap here is a whopping 38% in favor of blue. Alternatively, you could hunt for clusters of red to draw new districts like the following:

The efficiency gap is now only 2% in favor of blue, but at the price of a bizarre-looking district that the Washington Post might criticize. Our main result establishes that this is a fundamental tradeoff between shape and symmetry that can’t be removed.

But is this a problem? Let’s return to IL-4. While the bizarre shape certainly suggests that the map maker had intentions, it doesn’t necessarily demonstrate bad intentions. In this case, the district was “gerrymandered” to connect two majority Hispanic parts of Chicago so as to provide a common voice to this demographic (the region between these “earmuffs” is majority African-American). Likewise, since “partisan symmetry” might be an ideal worth pursuing, our result suggests that geometry probably shouldn’t have the final say in the gerrymandering debate. (This conclusion isn’t new, by the way; see for example John Oliver’s take on the issue, which might not be safe for work.)