[EM] A computationally feasible method (algorithmic redistricting)

[Kristofer Munsterhjelm]

Michael Rouse wrote:
> 
> There was a discussion of district-drawing algorithms on the 
> election-methods list a few years back. I've always thought that taking 
> centroidal Voronoi cells with equal populations was an elegant way to do 
> it. Here's an example of standard Voronoi cells and the centroidal 
> version I pulled off of Google:
> http://www.mrl.nyu.edu/~ajsecord/npar2002/html/stipples-node2.html

To find the district centers (centroids), you have to do what's 
effectively vector quantization. The voters make up the points, and you 
want to choose n codebook points so that the average distance to the 
closest codebook point, for all points, is minimized.

To my knowledge, optimal vector quantization is NP-hard. The good news 
is that there are approximation methods that have proven worst-case time 
complexity. However, they'll not give you the absolutely best possible 
arrangement.

One such algorithm is described here: 
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.3529

A simpler algorithm, though one that doesn't give any worst-case bounds, 
is Lloyd's algorithm. Start with random center points, then calculate 
the centroids for the current Voronoi cells. Move the center points 
towards the centroid (shifting the Voronoi cell somewhat) and repeat. Do 
so until they settle. This can get stuck in a local optimum.

> The other possibility I liked was allowing voters to vote for the 
> districts they wanted -- either for the next election, or more 
> entertainingly, the current one. People have a pretty good feel for what 
> mapping is compact and reasonable, and which ones are ridiculous, 
> especially if they can compare them. You could have certain criteria 
> that must be met -- like all districts must be contiguous  -- and sort 
> the maps by some metric, like from shortest to longest aggregate 
> perimeter. You could have all qualifying parties submit a map, as well 
> as any group that gets above a certain number of signatures in a petition.

Those maps could be pruned so that only the Pareto front remains. That 
is, if there's some map that's worse on all metrics with regards to some 
other map, then that first map isn't included. As long as there are 
enough metrics to give a reasonable choice on the Pareto front, this 
should exclude the worst of the gerrymandered proposals and keep the 
voters from being swamped with millions of frivolous proposals.

I don't think it's necessary to make it that complex, though. If you 
favor actual people doing the final choice, an independent commission 
(like the redistribution commissions of Canada and Australia) could make 
the choice of which nondominated map to use.