[EM] A computationally feasible method (algorithmic redistricting)

[Raph Frank]

On 9/3/08, Brian Olson <bql at bolson.org> wrote:
>  I'm looking at fryer.pdf and maybe the notation is a little thick for me
> but it looks like the pi(V_s) equation number 1 in section 3.2 is summing,
> for each district, the distance between every voter in the district and
> every other voter in that district. This is a little counterintuitive to me
> since for so long I've been summing the distance of voters to the center of
> their district. On the other hand, it does kinda make sense too.

That seems to be similar to finding the average resident location and
summing distance to that.  It works on population location rather the
district shape.

>  Anyway, what my pseudo-voronoi solver does is this:
>
>  Initialization:
>         • Assign district centers to random points (block coordinates).

I was thinking that a good way of picking the points would be to do
PR-STV between all the residents.  Each resident's ranking would
effectively be to rank all other residents in terms of distance.

However, it turns out to be a killer to actually perform the election.
 If there are 600k blocks, that is 600k rounds.

I am thinking that (an approx version of) CPO-STV could be used more
efficiently than full PR-STV.

1) Set the current district centres to a random set of points
2) set d to some initial value (maybe sqrt( State area ) )
3) For each of the current district centres pick a point inside the
State within d of it
4) Set the test district centres to the points from 2
5) Compare the test and current district centres using the CPO-STV comparison
6) If the test district is better,
  d = d * 1.01
  current points = test points
Otherwise
  d = d * 0.99
7) goto 3, unless d < some value

Effectively, it tests lots of arrangements of centres.  However, once
the current one starts being better on average than the ones being
tested against, it will start searching smaller regions around the
current best configuration.  That should hopefully speed up
convergence.

The CPO comparison is actually simple when none of the points match.
You just assign each voter to the nearest district centre (testing
against both the current and test centres).  There is no need to do
transfers as none of the 'candidates' are in both solutions.

You then just sum up the votes for all the current centre points and
if that is more than the sum for the test centre points, then the
current points are considered to have won.

Once that is done, an algorithm could be run to set the weights so as
to make the districts equal.  This is pretty easy and (I think) gives
a unique result.

It would be possible to allow people to submit possible configurations
and then the CPO-STV winner of those submissions would be the final
set of points.  It would require a condorcet completion method to be
decided.

>         • Assign census blocks to nearest district center.
>
>  Repeat until done:
>         • Move district centers towards center of population they were
> actually assigned.

Is this guaranteed to improve the district quality?

In fact, do you only make an update if that improves quality by your measure?

>         • Adjust district weight, nudging weight up or down if there are too
> few or two many people assigned to it.

Do you do this until it completely converges, or just 1 nudge?

>         • (optional) Nudge district centers away from underpopulated
> district centers and towards overpopulated district centers.
>         • For each census block, assign census block to the district with
> the lowest ((distance to block from district center) * weightd)

You would get straight edges if you used

lowest( (distance^2) - weight )

This also saves you having to do a square-root, though I guess your
method could be implemented as

lowest( (distance^2)*(weight)^2 )

This would speed up the calculations as there would be no need for
finding the square root of the distance, while still giving the same
result.

>         • Fixup district contiguity (because straight-line-nearest can jump
> across water and other gaps in odd ways)

I think water counts as part of a district, so technically that isn't
a breech of contiguity.

What could be an issue if if a State has a concave boundary.

Btw, do you parse the block geography file to work out which blocks
border each other?

>
>  (That's now enshrined here:
> http://code.google.com/p/redistricter/wiki/NearestNeighborSolver
> )
>
>  Oh, and when it's done (an hour or two for most states), start it over
> again with a different random starting state because it may have gotten
> stuck in a local optimum.

My splitline software was able to do all the States in one evening.
That is the benefit of a non-search algorithm.