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?

You had me until your final suggestion of statewide approval voting. That would be on the one hand highly majoritarian (one party and/or one race could win all seats) and highly prone to voters trying to game the system. Stick with more traditional forms of proportional representation like the single transferable vote or cumulative voting.

I admit that approval voting was merely a specific suggested example. As you point out, there are other options as well– although if STV is on the table, then I would prefer the Borda count as an even better alternative. If the voters are expected to be able to rank *some* of the candidates, then I think it is a short step beyond to ask them to rank *all* of the candidates. (This seems to be one of the largest gaps in practical acceptance among the various voting methods, those that require explicit rankings like STV, Borda, etc., and those that don’t, like approval/cumulative voting.)

At any rate, all of these suggestions share one common distinction from the current districting system: they are each a *single* procedure for selecting “k of n” representatives, rather than k separate procedures each for selecting a single representative.

Pingback: Fractional Representation | Possibly Wrong