[EM] Election districts (was bicameral design poll)

Ernest Prabhakar drernie at mac.com
Wed Jan 7 08:33:06 PST 2004

Hi Matt,

Interesting.  I've been wondering what the best alternative to PR is 
for dealing with gerrymandering, and whether there was a mathematical 
definition that would provide a reasonable definition of locality yet 
be mostly immune from political biasing.

On Jan 6, 2004, at 4:49 PM, matt at tidalwave.net wrote:
> My suggestion is to utilize a mathematical optimization hueristic to 
> minimize the district boundary sizes.

It sounds like your proposal is to first minimize boundary size, and 
second to minimize variations between districts.  That is, the optimal 
'tiling' of the electorate would look something like hexagons, with 
small hexagons in cities and large ones in rural areas.

I don't think that such an algorithm is actually well-defined.   I 
believe you'd need some sort of initial conditions, and if you didn't 
specify them explicitly then they'd be determined implicitly by the way 
you ran the algorithm.  And any sort of random initial conditions would 
tend to lead to strange boundaries.  Which may not be any worse than 
now, but as pointed out earlier in this thread people like the idea of 
districts that represent 'their' community.

This raises the question of whether it is possible to come up with a 
reasonable initial condition for your boundary-minimization algorithm, 
without allowing much room for political jiggering.    My best guess 
would be to treat this is as a crystallization problem, where the goal 
(constraint) is to get 'grains' of equal size and minimal boundary.    
The most objective initial conditions, I would think, are to have 
initial grains for each existing political unit (village, city, county, 
etc.).    This would lead to some grains with 'holes', but that's just 
an internal boundary which would also need to be minimized.  Another 
option would be to follow 'topographical' lines on the demographic 
chart (e.g., follow natural population concentrations, rather than the 
political boundaries).

The algorithm would need two passes.  In the first, it would attempt to 
coalesce individual grains in such a way as to minimize variance.  This 
would probably be best done via some sort of genetic algorithm or 
simulated annealing, to try out various options to find out which is 


The second phase - after roughly-equal grains (districts) have been 
created - would be to adjust the boundaries to both minimize 
circumference and decrease variance.   This could probably use a more 
deterministic algorithm, rather than the probabilistic one above.    We 
could even add in an extra 'cost' for moving boundaries in a way that 
don't fit 'natural' demographic boundaries.

At least, that's what I consider a more realistic way to implement your 
proposal, based on both political and technical considerations.  Let me 
know what you think,

-- Ernie P.

On Jan 6, 2004, at 4:49 PM, matt at tidalwave.net wrote:

> Corection, where I said "linear program" below it should say "mixed 
> integer program" because the demographic information is integer.  
> There is no good reason in our current computer era that I am aware of 
> for not removing the politics from districting by using mathematical 
> optimize to objectively determine efficient (small boundary 
> circumference) districts.
> I previously wrote:
> My suggestion is to utilize a mathematical optimization hueristic to 
> minimize the district boundary sizes.  I think a linear programming 
> model will work.  Input the relevant demographic and geographic 
> information and the number of districts and the computer will output 
> the districts.  Initially compute results using largest legal maximum 
> district population size variances and then keep re-running with 
> smaller variances until the problem is infeasible or the districts are 
> all exactly the same size.
> ----
> Election-methods mailing list - see http://electorama.com/em for list 
> info
RadicalCentrism.org is an anti-partisan think tank near Sacramento, 
California, dedicated to developing and promoting the ideals of 
Reality, Character, Community and Humility as expressed in our Radical 
Centrist Manifesto: Ground Rules of Civil Society 

More information about the Election-Methods mailing list