Congressional districts determined by computer

A Thought…

If you can’t be a good example, then you’ll just have to be a horrible warning.

— JP Steve, Sherman’s Lagoon comic letters

Congressional districts determined by computer

Posted on 2019-Aug-18 at 18:13:06 by Phil
Last update on 2022-Dec-08 at 15:48:00 by Phil

In the U.S., the lower house of Congress, the House of Representatives, has one or more representatives from each state. Although there is nothing in the Constitution prohibiting “at large” (statewide) representation, traditionally each representative has been assigned a fixed geographic district to represent the people there. No doubt this custom dates back to the days of slow travel via horseback or carriage, and could be done away with today. Each state’s legislature redraws districts after the decennial census, even if the number of districts in a state has not changed (up or down).

While the Constitution originally specified one representative for every 30,000 free persons (with each slave counting as 3/5 of a person, and untaxed Indians not counted), with a population in excess of 320 million, such a legislative body would be a bit unwieldy. It would take a small stadium to hold everyone, and conducting business would take forever (not that it would necessarily be a bad thing for nothing to get done…). On the bright side, the Senate could fit under one corner of the stands, and the President’s office (the “Oval Office”, due to its current shape) under another. More than a century ago, the size of the House was capped at 435 members, as that’s all there’s room for in the main chamber of the House. Each state starts with one representative, and in a round-robin cycle the state with the most citizens per representative gets the next seat. It is up to each state to assign districts to its House members. This is where the problems start.

The two main political parties naturally want to draw the districts to their own advantage, and historically they have. They want to maximize the chances that one of their own will be elected to any given seat (Representatives are up for election every two years, on even-numbered years). They can carve out “safe seats” for their own, where members of their party are likely to be in the majority, and relegate voters of the enemy party to a small number of districts. Over history, this has led to some bizarrely shaped Congressional districts, including the archetypal Massachusetts district around the city of Boston, in the early 19^th century. Created at the behest of Governor Elbridge Gerry, and in shape bearing a remarkable resemblance to a salamander, such drawing of districts like “Gerry’s Salamander” led to the term “gerrymandering”*.

Gerrymandering draws lots of complaints, but rarely have the courts intervened. Only in the most blatant cases, where people can reasonably claim to be discriminated against (denied their due representation), have courts ordered redistricting re-dos. Barring the adoption of at-large representation, the best choice would be to remove redistricting decisions from political hacks (whoever controls a state legislature) and doing it with computers (using a public algorithm), blind to which party is likely to win a given district that results.

We have many thousands of small census districts per state, with population count, and we know how many people should be in each House district. What is the best way for a computer to draw a district, to minimize (or better, eliminate) any human input into the process? Human decisions, even by technicians sworn to be impartial, will always be regarded with suspicion by those on the losing end. Is there an impartial algorithm that would result in reasonable districts, with minimal disconnected pieces and reasonably “compact” (ideally, approaching round)? Besides political advantage, districts have usually been drawn with an eye towards not having small “beachheads” of one district across a major river or out on part of an island. Cities have traditionally been kept together in one district, often resulting in a “bulls eye” pattern of districts around major cities. I would argue that this is a bad way to do things, as Representatives end up with a very homogeneous constituencies, and can therefore place themselves further from the political center than is really good for the country (less partisanship would be better).

A blindly drawn House district, cutting across inner city, suburb, and rural areas, would be far more heterogeneous in makeup than current districts, presumably leading to the election of Representatives who are closer to the political center, as they have to appeal to a wide range of constituents to get elected. Centrist politicians from both parties would stand a better chance of getting useful work done in Congress, with less extreme positions and posturing.

So, how could computers help? It’s nothing that couldn’t be done manually, but has the advantage of no potentially partisan people being involved. The basic approach would be what is known as “annealing”, as a district grows outward from its starting point, absorbing more census tracts until the desired size is reached. There are a number of refinements and variations on this, which will be discussed. A very important point is to start at some [outer] border of the state, either on a coastline, an international border, or a border with another state. A sharp corner as a starting point might be preferable to some arbitrary point in the middle of the outer border, and certainly better than an interior point, if the idea is to get all the resulting districts as compact (“roundish”) as possible. You definitely do not want to start in the center of a city, which leads to a bulls-eye pattern. Typically, census tracts are attached one at a time along the active (growing) edge of the district, shuttling back-and-forth between the ends of the edge, rather than taking on a number of of tracts at once (and growing outward by a large amount).

Once one district is done (has met its population goal), preferably start the next district at where the district just done meets the border (a new “corner”). A second choice would be where that district meets another district, somewhere in the state’s interior. At all costs avoid a starting point at some random interior point of the unallocated part of the state. An alternative would be to start at \(N\) outside corners of the state, where \(N\) is not to exceed the number of districts to be drawn, and simultaneously grow \(N\) districts towards each other. The districts would grow towards each other, with possibly the last one being somewhat oddly shaped, being the leftovers (so long as it’s not in two or more non-adjacent pieces). Perhaps a number of maps could be drawn, with different starting points for the first district, and different choices for the start of each subsequent district, and the legislature must select one of them within a certain time limit.

So, what might go wrong with this process? That is, other than that political partisans are likely to be unhappy that their party can’t gain a solid advantage? The idea is that no human intervention should be allowed, so the process should be very robust. This would include how specifically to flow between disconnected parts of the state, such as offshore islands like Nantucket and Martha’s Vineyard in Massachusetts, or the Upper and Lower Peninsulas of Michigan. It’s possible that the annealing front (edge) could head up a peninsula or panhandle, and end up leaving a small unallocated area at the tip. Assuming it’s not small enough to simply bury it in the just-made district (going a little over size), the people there need to be represented, but what you would end up with is a part of a district with a long jump to the rest of the district elsewhere in the state (which is quite undesirable). Perhaps the algorithm could backtrack to drop some census districts off one edge, and pick up the otherwise orphaned area? You want to be careful that you don’t end up with long skinny connections between sections of a district. You also want to minimize the distance of jumps across bodies of water. Drawing districts might become something of an iterative process, until the constraints are met. Multiple starting points (\(N > 1\)) might help with this problem. Finally, some will be unhappy that their city or county or town or neighborhood is split right across the middle, or that another district has a beachhead on their side of the river — that’s a feature, not a bug. The intent is to make a district’s population as heterogeneous as possible, to promote politial centrism.

I know there have been people looking at some sort of annealing process using census data. Can anyone speak on what the results were, or provide some sources of papers and reports? Here are a few links I’ve accumulated:

Washington Post 2016-01-13 (behind paywall)
Washington Post 2017-06-19 (behind paywall)
A Slate article on expanding legislatures, to fix gerrymandering
A computer system for automated (computerized) redistricting based on census data
A video proposal on redistricting and preventing gerrymandering

Finally, Donald Knuth and Michael Plass’s algorithm for “paragraph shaping” in text layout, to assign penalties for things like widows and orphans, excessive runs of split words on adjacent lines, and “rivers” of wide gaps; might be adaptable to district shapes, separations, and corridors (object: assign penalties to undesirable characterstics, and find the configuration to minimize the total penalties).

* pronounced with a hard “G” (guh, not juh sound)