[EM] connection between multiwinner voting systems & districting problems

[Andy Jennings]

On Thu, Jul 28, 2011 at 6:50 AM, Warren Smith wrote:

> To draw districts using a multiwinner voting system:
> Let there be V people, whose coordinates are known.
> Let the "candidates" be the same set as the people (V candidates).
> Each voter "votes" by ranking the "candidates" in order of increasing
> distance
> away from her, or somehow scoring them (in a score-based voting
> system) using some decreasing function of distance.   (Actually, all
> these votes are fake in the
> sense that they are automatically generated from the coordinates; no
> humans actually vote.)  We then "elect" W winners.
> These winners will be the centers of the districts.  [Once the
> district centers are selected there is a known polytime algorithm for
> finding the best assignment of the people to the districts such that
> the sum of the distances (or squared distances) to the district
> centers is minimized subject to the equipopulousness constraint.]
>

Good idea.  Hadn't thought of it that way before.


> We can now attempt to evaluate various multiwinner voting systems by
> asking how well they would perform for districting purposes.
>
> Consider, e.g, Andy Jennings' "greedy algorithm"
> which selects the candidate whose Tth highest score is greatest (where
> T is the district target population) and removes the T voters who
> scored him with the T highest scores, as "district #1" -- then
> continues on with the remaining voters.
>   It would work pretty well at first, removing chunks of people in
> dense cities, each chunk having population equal to a district target
> population.  However, as it proceeded, eventually your country would
> start to look like swiss cheese, with many removed "holes."
> The late districts Jennings produced, would necessarily be quite bad,
> large,
> containing a lot of scattered people, and with a lot of holes in the
> middle of those districts.
>

Interestingly enough, people in Arizona wanted it that way at one point.
 Some people think Arizona's 1st district (
http://en.wikipedia.org/wiki/Arizona's_1st_congressional_district) is the
way it is because of gerrymandering, but I'm pretty sure it was a
non-partisan committee who designed it that way so rural interests could be
combined and have their own representative.

Then again, it was the district that elected Rick Renzi, accused of being
one of the most corrupt congressmen at the time.  Does this reflect
negatively on the swiss cheese idea?  In any case, I agree that most people
would reject swiss cheese districts.


> Now consider (Lewis Carroll's form of) "asset voting."
> Here each voter names, e.g. their 3 favorite candidates.  Candidate with
> least votes (assets) is eliminated and transfers his assets to whomever he
> likes (according to his own vote).   Continue on.
> Eventually we have only W candidates left,
> who win.   In the districting application, "favorite" means "nearest."
> I actually suspect this method would work quite well as a districting
> method.
> There would be a lot of random tiebreaking going on, though, making its
> results depend to a large extent on random chance.
> But if each voter cast weighted votes for their top three (weightings
> chosen using
> distances according to some suitable scheme so the sum is 3 and they
> decrease with distance) then there would generically be no ties and no
> randomness.
>
> To boil that down to a simple districting algorithm:
> 1. input locations of all P people in country.
> 2. compute for each person v, its nearest neighbor NN(v).
> 3. for(v=1 to P){ asset(v)=1; }
> 4. for(v=1 to P){ increment asset(NN(v)); }
> 5. while(P>W){
> 5a.        find v minimizing asset(v);
> 5b.        eliminate v (decrementing P)  and transfer her assets to NN(v);
> }
> 6. the W remaining people are the winners, i.e. become district centers.
>
> In step 5a, ties could be broken deterministically using some function
> of distances,
> or just randomly.
> It is possible to implement the above algorithm to run in O(PlogP) time by
> using fast all-nearest-neighbor algorithms in step 2 and implementing
> step 5 with the aid of a "heap" (also called "priority queue") data
> structure.
> Those improve over the naive runtime which would have been O(P^2).
>
> With this algorithm, if the people in step 1 come in "census blocks" then
> it is easy to start out with "weighted people" where each block is
> replaced by a person at its center with weight (i.e. assets) equal to
> the block population
> in step 3, and in step 4 you increment by the weight of v not just by +1.
>
> So this has been a simple, efficient, and flexible districting
> algorithm, which probably usually doesn't perform horribly badly.
>

I agree that it definitely deserves to be simulated.  Might do quite well...

- Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110728/65d13643/attachment-0004.htm>