[EM] RE: Clarifications/commentary on solutions to Gerrymandering.

[Simmons, Forest]

Under the heading

4 - DISCUSSION OF ALTERNATE NON-GRAPH-BASED ALGORITHMS


Adam said ...


"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."

I agree with Adam.  Nevertheless, these "cake cutting" procedures can yield a good starting point for genetic algorithms to improve upon, and if the state has few natural boundaries, such solutions might even be competitive among other submissions in the contest.

Before Adam's idea I thought that the best measure of compactness of a district would be the average travel distance or average estimated travel time between residents within the district.  These distances and times can be obtained by typing in pairs of addresses into Mapquest, so they cannot be too hard to come by.

But in this context an individual residence is like a quark or some other subatomic partical.  I like Adam's atoms better.

[That reminds me of a short Ogden Nash poem ,  "Adam had 'em," entitled "Fleas."   But that was a different Adam.]

Also I like Adam's suggestion for adapting PAV to Range Ballots by generalizing  the harmonic sum

                1 + 1/2 + ... + 1/k

as    R_1 + R_2 /2 +...+ R_k /k , where the R's have been labeled in descending order of magnitude.

Another simple way to adapt would be to use the sum

          1 + 1/2 + ... + 1/floor(S)  +  (S -floor(S))/ceil(S)

where S is the sum of the R's divided by maxR.

Another approach is to replace the harmonic sum with 

          Integral((1-t^S)/(1-t), t=0..1),

which can be approximated by 

            log(1+1.7*S)

I suspect that it would be extremely rare for any of these approaches to yield different winners, since it was reported recently on the AV list that in a large run of random cases, even PAV and sequential PAV always yielded the same winners.  In other words, our examples of contrasting results for PAV and sequential PAV  were not found randomly.

Forest



-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/ms-tnef
Size: 6331 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20050822/dc3ebdeb/attachment-0001.bin>