[EM] A computationally feasible method (algorithmic redistricting)

[Brian Olson]

On Sep 2, 2008, at 6:00 PM, Kristofer Munsterhjelm wrote:

> Your reference to a Cd variable to get population proportionality is  
> interesting. I think part of the problem that you're trying to fix  
> here comes from that clustering (such as by Lloyd's algorithm)  
> optimizes for energy instead of mass. Or in other words, it finds  
> districts so that the average distance for each voter to the closest  
> center is minimized (energy) rather than to find districts that have  
> equal proportions of people within their borders (analogous to equal  
> mass, if each voter is a point of unit mass).
>
> Unless I'm mistaken, your generalization of Voronoi cells (with  
> weights linked to the center nodes) is called power diagrams. Not  
> long ago, I stumbled across a paper (draft?) about automatic  
> redistricting involving power diagrams. It's here: http://www.stat.columbia.edu/%7Egelman/stuff_for_blog/fryer.pdf 
>  . The authors state that for a certain given compactness measure,  
> the optimally compact district map will consist of power diagrams.  
> They also give an algorithm for finding these optimal (or near- 
> optimal, since the compactness measure is computationally intensive)  
> power diagrams, but it's a bit too complex for my understanding.

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.

Anyway, what my pseudo-voronoi solver does is this:

Initialization:
	• Assign district centers to random points (block coordinates).
	• Assign census blocks to nearest district center.

Repeat until done:
	• Move district centers towards center of population they were  
actually assigned.
	• Adjust district weight, nudging weight up or down if there are too  
few or two many people assigned to it.
	• (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)
	• Fixup district contiguity (because straight-line-nearest can jump  
across water and other gaps in odd ways)

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

>>> I think it's worth repeating that I'd prefer to write the law with  
>>> a way of
>>> measuring what a good district mapping is, rather than writing the  
>>> law with
>>> a specific procedure for creating the district mapping. Specific  
>>> procedures
>>> get really complex, and I don't think in this case that a fair  
>>> procedure
>>> ensures a fair outcome.
>> Sounds reasonable.  However, people don't really like randomness.
>> There is considerable resistance to using randomness in elections and
>> people might consider a system where the solution isn't well defined
>> as somewhat random.
>> "You mean that the best solution mightn't be picked because nobody
>> could find it?"
>> Also, there could be issues if a better solution is found after the
>> deadline, especially, if it favoured one party over another.
>
> Perhaps the randomness complaint could be diminished by having a  
> default  map drawn according to some rules set in law. The  
> redistricting law could refer to that rule, where the rule is very  
> simple - perhaps splitline? Then a state commission or similar could  
> draw the default map so that one is ensured that the results won't  
> be too bad if the redistricting fails. As long as the rule is  
> neutral, the state can't rig the default map, either.

I guess my time in Computer Science land has left me pretty  
comfortable with the idea that there are lots of problems that are too  
hard to ever reliably get "the best solution". I don't know if there's  
a short-short popularizing explanation of how finding a good solution  
is Hard while measuring the quality of a solution is pretty quick.

If anybody asks and it's not the time, place, or audience for  
discussing NP Hard problems, I will wave my hands and say, "Hey, look  
over there! Good results, on my one puny computer! With more it'd only  
get better!"


Brian Olson
http://bolson.org/