I want to clear up a couple things, and further comment on "algorithmic" or "automated" disctricting solutions. I have several major topics here:
1) Choosing subdistrict "atoms" for nodes of planar graph 2) Feasibility of assigning weights to edges of the graph 3) Finding optimal or near-optimal solutions 4) Discussion of alternate non-graph-based algorithms 5) On the importance of PR Before reading this message, you should be familiar with my recent post on the subject on the RV list: http://groups.yahoo.com/group/RangeVoting/message/205 Anyway, on to the topics. 1 - CHOOSING SUBDISTRICT "ATOMS" FOR NODES OF PLANAR GRAPH I suggested using census blocks as the "atoms" of districting. This was just because they are very small and therefore difficult to manipulate for political purposes. However, they are in fact smaller than we need, since there are thousands of census blocks in a single congressional district. A much more granular smallest sub-district "atom" would still be large enough to allow for fairly regularly-shaped districts. I have two ideas for "atoms" that would allow for simpler computation while still being difficult to manipulate: a) zip codes b) school districts - boundaries of high school or middle school districts Both of these are very much tied to real divisions of geography, population density, and ease of transportation. Both are also much larger than census blocks while still being small enough to allow the algorithm to balance populations effectively. And since these have very practical purposes, it's unlikely that they could be easily manipulated for political reasons. 2 - FEASIBILITY OF ASSIGNING WEIGHTS TO THE EDGES OF THE GRAPH I said earlier that I think the "bandwidth" of the transportation links connecting two nodes should be the weight of that edge. I still think this is the best measure, since if shows how linked the two nodes are in a real sense, and since it automatically respects natural boundaries such as rivers and mountains. One criticism of this approach was that it would be difficult to characterize and subject to manipulation. My responses would be: a) The information about the nature of a transportation link (pedestrian path, single lane road, road w/sidewalk, multi-lane road, limited access highway, rail line) is maintained and updated by a state's department of transportation, and is readily available. So the actual collection of the data is not difficult. b) The actual assigned weights to every sort of transportation link would indeed be subject to some manipulation. But the question is, would such manipulation actually effect any control over the final result of the algorithm? In a system as complicated as this, I really doubt it. To avoid even the possibility of such manipulation, however, it would be good if some standard approach to weighting of transportation lanes was included in the algorithm. 3 - FINDING OPTIMAL AND NEAR-OPTIMAL SOLUTIONS This is a planar graph, so from a computational perspective, making incremental changes to a solution, or checking the value of a solution, are trivial tasks for a computer. As such, the partitioning of the graph into districts is a good candidate for a genetic algorithm or other iterative approach to tackle. But the fact remains that finding the optimal solution is essentially an intractable problem. Forest Simmons provided an extremely simple and elegant solution to this problem - let anyone submit a solution, and take the one that performs best. Again, checking a solution is a trivial task. Simply publish the data for the node and edge weights, and allow a few months for the submission of solutions. 4 - DISCUSSION OF ALTERNATE NON-GRAPH-BASED ALGORITHMS Warren Smith has proposed an alternate solution, which has been brought up before on the EM list, of simply dragging a "cutting edge" across the state to make a division at the proper population ratio, and then iterate on the "slices" until you've divided the state into the required number of districts. Other solutions that attempt to create maximally convex districts have been thrown about quite a lot as well. The problem with these approaches is that they will tend to produce somewhat odd shaped or illogical boundaries. Tightly-bound neighborhoods may be divided in two, and neighborhoods divided by formidable natural boundaries may be thrown together. The use of actual municipal district boundaries, and a meaningful measure of how closely-bound these districts are, allows us to generate districts with logical and meaningful boundaries that will appeal to people on a gut level. 5 - ON THE IMPORTANCE OF PR As much as we can talk about getting rid of Gerrymandering, a more important advance toward truly democratic representation in congress would be to implement some form of proportional representation. My favored forms of PR are PAV and STV. I've been involved in discussions about ways to make voting easy with STV, as well as discussions of ways to implement a PR version of Condorcet voting. But even simple methods of PR like cumulative voting or single non-transferable vote can work well. Even having two representatives per district makes Gerrymandering dramatically less successful. With Cumulative voting or STV with a Droop Quota, you must have a two-thirds majority to sweep the seats. By the time you get to five representatives per district, the election-to-election variance in voting patterns is enough to render Gerrymandering nearly useless. This is not to say that I wouldn't support automated districting even if we had PR. I would just suggest using it for determining the large "meta-districts" that large population states would be divided into. How many meta-districts are needed depends on what you think the ideal number of representatives per district is. Since I think 5-7 is ideal, I'd probably break things down like this: 1-8 representative state: 1 district 9-14 representative state: 2 districts 15-20 representative state: 3 districts 21-26 representative state: 4 districts ... and so on. Texas gets 5 meta-districts, California gets 9 meta-districts. Again, while I still think automated districting is a useful enhancement to democracy, proportional representation is ultimately more valuable. Automated districting is still important, if for no other reason than that it is probably easier to get district drawing changed than it is to get our entire election method changed. ---- Election-methods mailing list - see http://electorama.com/em for list info