[EM] connection between multiwinner voting systems & districting problems

[Kristofer Munsterhjelm]

Warren Smith wrote:
> 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.

I'd note that this shares a property with k-medoids in that the centers 
will end up being some of the points over which one is doing the 
clustering. In k-means, that need not be true - a local optimal center 
can be a coordinate that is not one of the points.

One could try to make a k-means version by adding virtual points. As 
before, all the voters rank the points in order of distance, where the 
difference is that the virtual points have no votes of their own. 
However, then the method will have to deal with a case of more 
candidates than voters.

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

What would the different multiwinner methods optimize? Say you had an 
optimal multiwinner method that would draw good maps of this sort. Would 
it find the optimum "sum of distances to closest center" map, the 
optimum "sum of squared distances to closest center" map, or something 
else entirely?

It might be interesting to try, just to see what it does optimize.