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