Can math solve the congressional districting problem?

Lost amidst the frenzy of coverage of the Supreme Court’s rulings about the Affordable Care Act and same-sex marriage was a case involving the constitutionality of an independent commission to draw congressional districts in Arizona.

Through a ballot measure in 2000, the state amended its constitution to create a nonpartisan group to draw up new districts; the ultimate goal is to reduce gerrymandering. Named for the salamander-shaped district drawn by Massachusetts governor Elbridge Gerry in 1812, gerrymandering occurs when a state legislature draws voting district lines in a manner that benefits the ruling party at the expense of the opposition.

The goal is to consolidate power for the party in control, making it effectively impossible for the opposition to gain seats. Many state legislatures have engaged in this process recently, prompting grassroots movements advocating independent commissions to draw districts. The Supreme Court ruled 5–4 that Arizona’s commission is constitutional.

This begs the question: is there a truly unbiased method for drawing fair districts that yield more competitive elections?

As it turns out, there are mathematical methods that could fit the bill.

Requirements of congressional districts

There are three primary requirements in federal law when drawing congressional districts: they must distribute population evenly, be connected and be “compact.” The last term has never been rigorously defined. The Voting Rights Act of 1965 also insists on some guarantees of representation for minority voters.

Over the years state legislatures have employed various strategies to meet all these criteria – which has led to some interesting districts.

Florida’s 5th Congressional District.US Dept. of the Interior

For instance, Florida’s 5th Congressional District is one of the nation’s most gerrymandered. It is connected geographically (barely), but it’s probably not what most reasonable people would call compact since it stretches 140 miles from parts of Jacksonville in the north to Orlando in the south. A portion of its border runs along West 13th Street in Gainesville, dividing the college town in half.

Florida’s 3rd Congressional District.US Dept. of the Interior

My own district, Florida’s 3rd, shares that border along 13th Street in Gainesville. Because the lines are drawn this way, the western half of the city, which generally votes for Democratic candidates in local elections, is included in a large rural district represented by Ted Yoho, one of the most conservative Republican members of the House. Geographically, however, the 3rd district looks completely reasonable.

Little wonder the Florida Supreme Court ruled this summer that the 5th district, as well as several others in the state, must be redrawn without political bias.

Of course, gerrymandering is not restricted to any particular political party. Legislatures controlled by the Democratic Party have abused their power to draw districts (for example, Illinois' 4th Congressional District).

Most people agree that gerrymandering is bad, but it’s not obvious what to do about it.

Splitline districting

One might approach voting reform by either changing the way we tabulate votes (for instance, via score voting, or fair majority voting) or by drawing the districts differently.

One unbiased way to draw districts is via the shortest splitline algorithm. It works like this. Suppose a state is to be divided into N districts. Let A be the largest integer less than or equal to N/2 and let B be the smallest integer greater than or equal to N/2. Then N = A + B (for example, 9 = 4 + 5).

Now find the shortest straight line that divides the population of the state into the ratio A:B. Ties are broken by choosing the line that is closest to north–south (other choices are possible). You then have two “substates” that need to be divided into A and B districts, respectively. Repeat the algorithm until the state is divided completely. Below, compare the actual (top) and splitline (bottom) districts for Florida as they were in 2009.

Florida’s congressional districts, 2009.Florida Office of Economic & Demographic Research

Florida shortest splitline districts, 2009.Center for Range Voting, algorithm by Warren D Smith, software by Ivan Ryan

It’s not so easy to see, but, particularly in South Florida, there are some rather bizarre boundaries to the existing districts. The splitline algorithm eliminates these.

One obvious downside to this approach is that it ignores natural and political boundaries. There may be good reasons to put an entire city into one district, for example, but the algorithm might not make that happen.

One obvious advantage, however, is that the algorithm has no political loyalties or biases; it simply divides the population evenly into polygonal chunks on a map.

Drawing districts randomly

In a 2014 paper, mathematicians Jonathan Mattingly and Christy Vaughn introduced a probabilistic method for drawing districts. They were motivated by the fact that in North Carolina’s 2012 election, a majority of voters selected Democratic candidates, yet only four of the state’s 13 districts had a Democratic winner.

Their method considers the set of all possible divisions of the state into 13 districts with roughly equal population such that each district is connected and “compact.” They also toss out those districts that are not “simply connected” in the sense that they entirely enclose another district – imagine a circular district containing another circular district.

They then define a class of probability measures on the set. This is a function that essentially gives the likelihood of a particular element of the set being chosen at random. Think of rolling a die – the probability measure assigns the value one-sixth to each of the six outcomes. The number of such divisions of the state is unimaginably large (on the order of 10²⁷⁸⁵), so it’s effectively impossible to compute the probability distribution exactly. But, there are methods to estimate the function and therefore obtain useful results.

With these estimates in place, Mattingly and Vaughn ran simulations using the actual votes cast in 2012 to determine the outcome of the election using various randomly chosen redistrictings. Of 100 such maps, more than half had either seven or eight Democratic representatives, and all of them had between six and nine.

They estimate the probability of only four Democrats being elected in a particular districting – remember, that’s the actual election outcome in real life – to be very small, raising the question of whether the current congressional district map of North Carolina results in representation that reflects the “will of the people.”

Should we bother?

One approach is to do nothing and leave the system as it is, accepting the current situation as part of the natural ebb and flow of the political process. But when one political party receives a majority of votes nationally yet does not have control of the House of Representatives – as occurred in the 2012 election – one begins to wonder if the system needs some tweaks.

The advantage of using mathematics is that it’s built on cold logic rather than political heat. But, there is no perfect algorithm (and there are others not mentioned here), so the optimal solution will likely require a mixture of science and art.