[EM] A computationally feasible method (algorithmicredistricting)

[Terry Bouricius]

I would argue that developing a genuinely neutral redistricting procedure 
is of little value as long as single-seat winner-take-all election methods 
are used. Although, it is easy to create redistricting plans that are 
clearly UNfair, there is no such thing as a genuinely "fair" districting 
plan.

Are folks on this list familiar with the Proportional Representation 
Society of Australia's redistricting roulette wheel (you can find a 
wonderful graphic example here http://www.fairvote.org/wheel/ )? Using 
this wheel, you can draw compact, equal-population district boundaries, in 
a "fair" way, and end up with any partisan balance desired.

After studying redistricting in the U.S., the Vermont League of Women 
Voters adopted this position:

"The emphasis on geographic representation in legislative bodies in the 
U.S. may be anachronistic. It is more important that voters be represented 
by elected officials who reflect their political views, than happen to 
live nearby. Single-seat winner-take-all elections, regardless of method 
of redistricting, elevate the representation of geography above political 
philosophy, and other priority voter self-identities.



"It is impossible to redistrict single-seat districts in such a way as to 
promote BOTH competitive elections AND a highly representative delegation 
(as these two priorities are in  inherent conflict in single-seat 
districts). Therefore,



"The League of Women Voters of Vermont supports the principle of 
legislative districts using alternative voting methods, such as 
proportional representation in multi-seat districts, as a way of achieving 
both competitive elections and fair representation of both majorities and 
minorities within a district."


-Terry Bouricius, Vermont USA


----- Original Message ----- 
From: "Kristofer Munsterhjelm" <km-elmet at broadpark.no>
To: "Michael Rouse" <mrouse1 at mrouse.com>
Cc: <election-methods at lists.electorama.com>
Sent: Monday, September 01, 2008 7:28 AM
Subject: Re: [EM] A computationally feasible method 
(algorithmicredistricting)


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.
----
Election-Methods mailing list - see http://electorama.com/em for list info