[EM] connection between multiwinner voting systems & districting problems

[Warren Smith]

I daresay this has been pointed out before, but I do not think much analysis has
been done before, of this idea:

If you want to have V voters elect W winners, that can be considered as the
same, or anyhow a highly related, problem as the problem of drawing W
equipopulous districts on a map.

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.]

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.
   However, if we then ignored the actual groupings of people Jennings
produced and just kept the winners (district centers) and found the
best (re)assignment of people to those district centers, it would do
better.

Next consider PR-STV.  With STV, every person would rank themselves top
causing an exact V-way tie in the top-ranking counts.  This would be a pathetic
start.

Next consider RRV.  RRV ought to do pretty well at first, acting
similar to Jennings.
But eventually the fact that all the voters not in your district,
would play a considerable role in choosing your district, would hurt
it.

So it seems likely to me that all three of these multiwinner voting
algorithms would
do badly as districting algorithms.  Probably Jennings would do the
least-worst of the three.  I suspect the "jury method" of simply
choosing W people at random as district centers, would likely do
comparably well, or better, than all three voting methods!

The "Monroe" voting method would do extremely well as a districting
method... except it'd be computationally infeasible to carry it out.

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.

-- 
Warren D. Smith
http://RangeVoting.org  <-- add your endorsement (by clicking
"endorse" as 1st step)