I find social choice problems very interesting. Voting, fair division, and today’s subject, gerrymandering, are all good examples. I think they are a source of a lot of interesting mathematics, in particular mathematics that is very accessible to students at many levels. Oh yeah, and I suppose politicians and we as voters could also stand to inject some logic into our views on the process of government.
Gerrymandering seems to be rather like pornography: it is difficult to define, but you usually know it when you see it. North Carolina’s 12th district is one of the more glaring examples, both by the eyeball norm as well as several other more objectively measurable critieria, which we’ll get to shortly. Two questions arise: first, can we define it? And second, can we prevent it?
An article in the most recent College Mathematics Journal (Hodge, Marshall, and Patterson, Gerrymandering and Convexity) provides some interesting analysis of the first question. The authors use convexity of a district as a measure of “extent” of gerrymandering. Recall that a set S is convex if, for any pair of points x and y in S, the line segment joining x and y is contained entirely within S. Rather than simply determining whether a district is convex or not, they consider the probability that the segment joining a randomly selected pair of points is contained within the district. This provides a metric with a range of values corresponding, presumably, to a range of extents of gerrymandering.
There are some practical problems to consider, with interesting and elegant solutions. (What if the state itself is not “very convex”? What about population distribution? How hard is it to compute these probabilities in the first place?) From a pedagogical standpoint, this seems like a great practical experiment, given the wealth of data that is publicly available, including state and district boundaries, as well as population distributions, all from the U.S. Census.
Now for the second question: can we prevent gerrymandering? It seems to me there are two possible approaches here. One is to get the humans out of the loop. That is, provide a procedure, an algorithm for constructing district boundaries, considering state boundaries and population distributions, but not necessarily political demographics. One interesting proposal is the so-called “Shortest Split-Line Algorithm.” The Center for Range Voting has a good site with examples of the results.
The idea is pretty simple: suppose you want to divide up a state into 15 districts. Split the state’s population in half, using the shortest possible line segment through the state’s area. These two halves will make up 7 and 8 districts, respectively. Then perform the same splitting process recursively on each half.
Sounds good, right? The resulting districts are “very convex.” The problem is that convexity is not the whole story, being neither necessary nor sufficient for a district to be free from gerrymandering. Another interesting paper (Humphreys, Can Compactness Constrain the Gerrymander?) provides some interesting examples of results that show just how out of whack things can get even when all districts are convex.
So, is there any way out of this mess? To leave the clean mathematics behind and jump into the political swamp, it is not clear to me how necessary districting is at all anymore. We have cleared a lot of technological and logistic hurdles in the last couple of hundred years, to the point that having a single designated representative that is geographically close to a subset of residents is no longer a requirement for efficient communication with or election of those representatives. Why not use statewide approval voting as a means of electing representatives?