[EM] A computationally feasible method (algorithmic redistricting)

[Kristofer Munsterhjelm]

Jonathan Lundell wrote:
> I haven't been following this thread in great detail, but I do have a 
> question: what is the distance function actually trying to measure and 
> minimize? What exactly are we trying to optimize when we minimize 
> "distance", by whatever measure? I might be close in a crow's-flight 
> sense to a neighbor on the other side of a river or freeway with a 
> driving distance of several miles.
> 
> OK, we could solve that in principle (though not too quickly) by using 
> Google Maps driving time, or the like. But what does driving time have 
> to do with grouping voters (unless we're drawing a precinct and 
> measuring travel time t the polling place)? Maybe we mean communication: 
> two people with telephones are closer in this sense than people without 
> (and people with unlimited long distance are close in this sense 
> independent of cartesian distance).
> 
> I live in several voting districts where geographical lines make 
> sense--my local fire district is a case in point, as would water and 
> sewerage (except that I provide my own in those cases, as it happens). 
> But legislative districts? I can't think what I'm trying to optimize for 
> which straight-line vs manhattan distance would be relevant. I've never 
> met my representatives on business; I communicate with them via email or 
> telephone, and I neither know nor care where there local offices are.

Proper redistricting has a few rules: the districts must be contiguous 
(no empty spaces, exclaves or enclaves), and the districts must carry 
similar population (otherwise "one person, one vote" suffers, and it 
appears that United States court precedent have judged population 
dissimilarity very strictly).

Minimizing over some distance is a side benefit. If you minimize over 
Euclidean distance (or Haversine, if you want to be picky), the 
districts are going to look compact - like squares or hexagons - rather 
than the sort of contorted shape that "obviously gerrymandered" 
districts have.

The underlying reason is that while there are very many ways of drawing 
gerrymander-shaped districts, there are much fewer ways of drawing 
districts that minimize with regard to some distance. Therefore, 
gerrymandered districts (having no constraint on compactness) would 
much more likely be gerrymander-shaped than compact. While there's no 
direct reason to have districts that look nice on a map, it serves a 
function similar to using expansions of pi or e in cryptographic 
primitives: to show that no trickery is being done, because the 
selection is so limited that finding trickery that's compatible with the 
appearance (or the rules of the optimization) becomes nearly impossible.

By this reasoning, one could also turn your argument on its head. There 
are various functions that leave too little to chance to be effectively 
gerrymandered. If you pick Manhattan distance, fine enough; but if you 
pick Euclidean or Haversine distance, then at least you have the added 
improvement, however small, that if geographical lines *do* matter, then 
the assignment optimizes for it, and that bonus is essentially free.

One could try to make districts that fit geographical lines even better 
by weighting according to steepness (delta altitude; since it's hard to 
cross mountains), or by using street distance (Google Maps driving 
time). However, the methods discussed would need the distance metric to 
be defined for all pairs of points, and I don't think there's street 
distance data for that -- for instance, what's the driving time if you 
start on a mountain peak?

(I wonder if candidates would try to make roads to nowhere to game the 
metric :-)