[EM] Re: [RangeVoting] Ballot Initiative feedback from Lomax

[Adam Tarr]

On 8/18/05, wds at euclid.math.temple.edu <wds at euclid.math.temple.edu> wrote:

> I would also like to see the district drawn by a bipartisan or
> nonpartisan agency.  I believe some states (Maine?) have such
> a requirement.  I was not sure how to define that concept however.
> If anybody knows how Maine or wherever defined it, can you tell us?

> > As to rivers, what about other areas impassable by ordinary transportation?
> 
> --I could add a few like "lakes".  Basically, I want as few
> exceptions as possible.  The plan of convex-districts-only
> permits a good deal of freedom but outlaws fractal-shaped districts
> like they just drew in Texas.  If they have to keep the boundaries
> going straight or left in the middle of lakes, probably a good thing,
> no need to let them turn right.
> This whole measure will not really abolish gerrymandering
> but it will keep it from being really outrageous.

Warren,

As with many topics, this has been covered extrensively before in the
EM archives.  As far as non-partisan districting goes, an idea that
has gotten a lot of mileage is some sort of specific algorithm that is
used to determine districts.  I'll try to describe one approach below:

--------------------

The "atoms" of districts are census blocks.  Census blocks are drawn
up in a nonpartisan fashion, and since they are much, much smaller
than congressional districts, it is extremely difficult to manipulate
the process by re-drawing them.

Consider the census blocks in a given state to be the nodes of a
graph.  There are links between all nodes where the census blocks are
geographically adjacent.

The nodes have weights equal to the population therein.  The links
have weights equal to the number of lanes of transportation connecting
the two nodes.  A single lane of surface road is worth one.  Limited
access highway lanes can be made to count double or triple.  Railroad
and subway lines can be weighted more heavily than a single lane, and
sidewalks less heavily.  If the border between two census blocks is
formed by a road, then any lanes that "T" into that road count half as
much as usual.  (So a road that cuts through counts regular.)

(Note that natural boundaries such as rivers and mountains tend to
have few ways to cross them, so they will naturally end up as
boundaries.)

If the state is to be divided into N districts, then the graph must be
divided into N unconnected sub-graphs by severing links in the graph. 
The problem is:

minimize: total weight of severed links

subject to: total node weight of each of the N sub-graphs must be
within 5% (or some small acceptable error) of one another.

I beleive this is an NP problem, but a good genetic algorithm could
come up with an acceptable solution given enough time to crank away.