Built on Facts

Whew! Interesting day around here yesterday, no? There’s more controversial topics out there: abortion, health care, gay marriage, Iraq, and a few others. But not many. It’s good for sparking discussion, but I also know that some large (probably majority!) fraction of you would prefer to hear about physics. Which is good because generally I prefer writing physics, and I know that I can get irritated when my otherwise favorite nonpolitical blogs go off on political crusades for causes I dislike. So as always I’ll try to continue to keep the partisan politics to relatively rare and easily skipped posts.

How about some of the mathematics of politics instead? I promise it’s not partisan!

As you know, the various states are divided into congressional districts which each have their own representative in congress. These districts are drawn in very arcane and shady ways, with the majority trying to carve out districts in a way to give them the most votes, the minority trying to do the opposite, and politicians of any party pushing those considerations to the side to give their particular district the greatest possible incumbency advantage for themselves. Gerrymandering is nothing new, but it’s especially bad these days.

There have been a number of mathematical proposals to fix this and take out any possibility of district manipulation. One of my favorite is the splitline algorithm, which works in the following way:

1. Start with the boundary outline of the state.

2. Let N=A+B where A and B are as nearly equal whole numbers as possible.
(For example, 7=4+3. More precisely, A = ⌈N/2⌉, B=⌊N/2⌋.)

3. Among all possible dividing lines that split the state into two parts with population ratio A:B, choose the shortest. (Notes: since the Earth is round, when we say “line” we more precisely mean “great circle.” If there is an exact length-tie for “shortest” then break that tie by using the line closest to North-South orientation, and if it’s still a tie, then use the Westernmost of the tied dividing lines. “Length” means distance between the two furthest-apart points on the line, that both lie within the district being split.)

4.We now have two hemi-states, each to contain a specified number (namely A and B) of districts. Handle them recursively via the same splitting procedure.

My own state is a stellar example of gerrymandering:

Using the splitline algorithm, the districts would be much more fairly and sensibly placed:

The algorithm only takes into account the geometry of the state and the density of the population, and produces a unique result. It does so in a transparent way, and prevents any tweaking by elected officials. Certainly it would immediately result in true contests for many formerly entrenched officeholders. I doubt we’ll ever see anything like this implemented, but it’s an interesting application of mathematics to the process of fair governance even if it remains purely theoretical.

Comments

#1 Zifnab
November 13, 2009

I was just going to say screw it all and go to a parlimentary method. Assign the state X reps, give everyone one vote, and let the top X vote getters be the reps.

But if you’re going to cling to districts as a component of the representative government, its nice to see math has a clean solution for us, should we ever be tempted to use it.
#2 Tim Gaede
November 13, 2009

How could one quantify how gerrymandered a particular district is? One such a “Gerry index” could be the ratio of the perimeters of the district to an equal-area circular district. Another such index would be the ratio of the average distance between two random points within the district to that within an equal-area circular district.
#3 TomS
November 13, 2009

One thing I wonder about is how to recognize geographical barriers in such a system. I can imagine that it would group together people who were separated by a mountain range (or even superhighway).

I like Zifnab’s suggestion, but I wonder what happens when a representative leaves office before the end of term. How do you fill that vacancy?

And I can’t resist mentioning the most outrageous “gerrymander” – the Senate.
#4 Thad
November 13, 2009

A Voronoi diagram would result in more natural looking districts, with the added bonus or being able to accommodate geographic features. Start with a number of lat/long points of highest density, and grow circles of increasing radius until they collide with each other, or a geographical boundary or state’s edge.
#5 Eric Lund
November 13, 2009

@Tim: This Slate article discusses some measures. A particularly interesting one is the probability that a straight path (lying within the state, so that districts along irregular state boundaries are not penalized) between two randomly chosen residents of the district lies entirely within the district. Values close to 1, which the above districting algorithm produces, are considered good, while low values indicate gerrymandering.

This algorithm is a good starting point, but there are also good reasons for other choices. For instance, it is often desirable for district boundaries to coincide with county or municipal boundaries. In New Hampshire this is a requirement: cities can be split on ward boundaries, but towns and unincorporated townships cannot be split (every square millimeter of the state is included in one of those three types of municipality). One possible pathology of the described algorithm is apparent in how it splits up the DFW metroplex: it appears that the cities of Dallas and Fort Worth are split, with one district combining western Dallas with eastern Fort Worth. (It’s hard to be sure without the actual city locations drawn on the map.) I’m also skeptical of splitting Houston into five districts the way it is done by this algorithm; while the city is big enough that it would have to be split, this algorithm appears to dilute the influence of city residence in favor of suburban and rural voters more than is necessary.
#6 Matt Springer
November 13, 2009

#3, In fairness the state lines were drawn and fixed many years ago, and were in any case presumably not drawn primarily on senate electability considerations which probably would be obsolete today anyway. That said, senate reelection rates are even higher than the house.

If you view this as a Bad Thing (I do), a few possible solutions might be term limits or repeal of the 17th amendment providing for the direct election of senators. Of course that later possibility would merely indirectly gerrymander the senate unless objective state legislative districts were also part of the proposal.
#7 Dale Sheldon
November 13, 2009

I wrote a bit about this back in June:

http://leastevil.blogspot.com/2009/06/25-majority-census-governors-and.html

I found two other interesting proposals, one of which shares the “unique solution that politicians can’t argue over” solution, while accounting for municipal borders:

http://www.stealingourvotes.com/pages/3/index.htm

And the other which uses a semi-random method (which gives results that don’t look entirely unlike the Voronni diagrams another commenter suggested):

http://bolson.org/dist/
#8 Dale Sheldon
November 13, 2009

At least one state boundary was drawn with Senate electability as a first priority: the *existence* of a border between North and South Dakota was put there to get four votes, instead of just two, for the Republicans.

Interestingly, a potential better solution than term limits is on the same site you found the splitline algorithm: range voting!

http://leastevil.blogspot.com/2009/09/term-limits.html
#9 Dale Sheldon
November 13, 2009

Huh; I tried to post this earlier, but it seems it got eaten.

I wrote about gerrymandering in June:
http://leastevil.blogspot.com/2009/06/25-majority-census-governors-and.html

And, in addition to this splitline algorithm, found another method that creates a unique-solution (and therefore non-politikable) and also respects existing municipal boundaries:
http://www.stealingourvotes.com/pages/3/index.htm
#10 Scott
November 13, 2009

Re: #2.
Isn’t there some fractal dimension that defines the ratio of the perimeter to the area of an object? It has seemed to me that the “easiest” thing to do would be to pass a law that says that the fractal dimension (or “Gerry Index”) can be no greater than “X”. This would still allow the politicians some leeway to still play politics, without going overboard.
#11 Sam K.
November 13, 2009

Another interesting result I remember from my algorithms class is that if you know the distribution of voters, you can optimally gerrymander (i.e. get better voting results) in O(n^4) time.
#12 Ty Marx
November 13, 2009

As a bonus, if you stare at the edges of it, it looks like it spreads bigger.

Freaky visual trickery and unreliable ways of light perception.
#13 MPL
November 13, 2009

@3,

The splitline algorithm is likely to throw together some people who are geographically isolated—but gerrymandering does so with a vengeance. There are people in Austin who are in the same district as Midland, but not their friends a few blocks away (assuming I’m reading the map right).

However, whatever weird results the splitline algorithm produces (and it turns out really weird on Colorado— http://rangevoting.org/SSHR/co_final.png ), it’s not easy to manipulate, because it’s completely determined by demographics.
#14 warren d smith
November 13, 2009

hi, I’m inventor of this algorithm.

The “probability two random voters yield line segment lying entirely inside district” is 100% if district is convex; however, merely requiring convexity is a very weak demand (still permits long thin districts) and nowhere near assures “optimality.” So this idea is a silly quality-metric.

The stealingourvotes.com URL given gives a picture which it implies is uniquely optimal, but it plainly is not optimal, not even to local changes. It presumably is true there IS some generally uniquely optimal districting… but I see no reason to believe that guy can find it in less than the age of the universe.

Zifnab’s suggestion can result in a 99:1 dem:repub parliament, in a state with one well known republican candidate, a lot of poorly known republican canddts, and a lot of moderately-known democrats. It will probably cause money to become very important. However, there are “proportional representation” schemes intended to do what (I think) Zifnab intended, without the downside. You still end up with a gazillion candidates, which makes the election kind of silly since few voters can process that amount of info. Israel parliament elected thus and it is generally regarded as a disaster and great example of how not to design a government.

I do not know what the O(n^4) algorithm for “optimum (pessimum?) gerrymandering” is supposed to be. I’d be interested to know what you mean; feel free to email me.

The ideas here about quality metrics based on perimeter and other things are not new; and also are good ideas.

You all might be interested in the democracy-related-math
problems collection, which includes some open problems and
some gerrymandering-related problems, here:
http://rangevoting.org/PuzzlePage.html

please email me your solutions to open ones (and/or send me new puzzle-answer pairs…)
–Warren D. Smith
warren.wds AT gmail.com
#15 John
November 14, 2009

Texas is fun and all, but to get some really awesome gerrymandering to have to head northeast. I give you my home district:

http://upload.wikimedia.org/wikipedia/en/b/bb/Pa12_109.gif
#16 ppnl
November 14, 2009

This is a slight change of subject but still has a math dimension.

The best way to do away with gerrymandering is to do away with voting districts entirely. And do away with the stupid primaries as well. Use a rank voting system with an instant runoff. This would greatly reduce the power of the parties. But then that’s why it will never happen.
#17 Clay Shentrup
November 14, 2009

MATT SPRINGER,

Great to see your enthusiasm for Warren’s proposal.

Here’s how you can actually HELP US promote it.

Join the Election Science Foundation.

http://groups.google.com/group/electionsciencefoundation

And even consider DONATING a little cash to help our efforts. We need to incorporate as a 501(c)(3) and any help you can offer would be great.

Best,
Clay Shentrup
206.801.0484
#18 Clay Shentrup
November 14, 2009

ppnl,

Instant Runoff Voting is a very poor voting method, according to Warren Smith’s Bayesian regret calculations (and for lots of other practical reasons).

Score Voting is a better system. Check out
http://ScoreVoting.net/
#19 Jon Claerbout
November 14, 2009

Why not use a more natural metric like travel time?
#20 Jay Goldfarb
November 14, 2009

Voronoi polygons would also give a unique solution. Generating points would be assigned by population.
#21 Ketil Tveiten
November 15, 2009

@13: The Israeli parliament has very low (if any) cut-off limits for parliament seats, and so is a bad example. Compare instead, say, the scandinavian countries. Most countries that practise parliamentarianism have a cut-off, i.e. a party needs to get at least N% to get in, and then seats are distributed proportionally among those parties that pass the cut-off. Too high or too low cut-offs each have their problems.
#22 CCPhysicist
November 15, 2009

I’d like to see an election probability analysis of that Texas map done by 538.com. Might tell us why rational minds rarely prevail in that business.

Otherwise, the only problem I see with that method is it doesn’t respect census area boundaries, but that could be fixed.

I don’t get the comment about areas being divided by a freeway. The point of the “compact” approach is really just to minimize (and equalize) the fractal dimension of the districts. The claim about uniform demographics made on that page is unsupported and the implication that most people in southern California walk most places while talking to their neighbors is laughable.

Besides, there was reportedly some district where a freeway right-of-way (with no residents) was used to connect two distant parts of one district. Or maybe that was just a proposal that got rejected. If anyone wants to go looking, check out
http://www.govtrack.us/congress/findyourreps.xpd

senate reelection rates are even higher than the house

I thought the fraction of seats that are truly contested is far lower in the House because of gerrymandering, but the main effect is to distort the political influence of one group or another. Look no further than the states that have balance in the Senate but an imbalance in the House.

One really clever move in the past decades is to use “minority” districts to create nearly 100% single-party areas and leave behind many more districts that have a safe (but modest) party preference the other way.
#23 Walabio
November 15, 2009

Posted by: Zifnab | November 13, 2009 12:57 PM:

> I was just going to say screw it all and go to a parlimentary method. Assign the state X reps, give everyone one vote, and let the top X vote getters be the reps.

That would be terribly unproportional. Assetvoting would be much better:

http://rangevoting.org/Asset.html
#24 llewelly
November 15, 2009

Texas is fun and all, but to get some really awesome gerrymandering to have to head northeast. I give you my home district:

http://upload.wikimedia.org/wikipedia/en/b/bb/Pa12_109.gif

It looks like an obscene gesture made by a fractal alien.
#25 J.J.E.
November 18, 2009

Small pedantic quibble:

Senate reelection rates are substantially lower than the house.

http://www.opensecrets.org/bigpicture/reelect.php
#26 RWA
November 21, 2009

Fermilab physicist and member of the Illinois legislature Mike Fortner has proposed a new means of improving the redistricting process as well:

http://www.fortner.ilhousegop.org/2009/06/fortner-proposes-plan-to-reform-redistricting-methods/
#27 Jerry
January 12, 2010

I came up with a suggested method a few years ago. 1) Divide each state into as many districts as allowed by number of representatives. 2) Increase or decrease the boundaries so that each contains the approx. same number of voters. 3) Measure the area, perimeter and the longest distance between sides while staying within the district. 4) Divide the product of the perimeter and longest distance by the area. Allow all groups to work to lower that factor for any districts they choose without raising it for other districts more than their lowering accomplishes.

The theoretical minimum would be for a circle, that is, 4.0. A square would be 4 X the square root of 2. As the gerrymandering is increased the factor goes up rapidly.

Of course, minor rules like avoiding making jagged boundaries, or diagonals that cut across someone’s property would be needed.

It wouldn’t take long for all districts to be as compact as possible. Sure, a few would be made up of homogeneous groups of voters, and a few would seem to disenfranchise some, but most of the present districts do that already, and it’s something that no system can avoid.
#28 ball valves
March 27, 2011

The unveiling truth about this blog post is, that it spoke to me greatly. Thank you for sharing your thoughts and concerns.