[EM] Clarifications/commentary on solutions to Gerrymandering.

[Adam Tarr]

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.