What if you have to elect two with the following voters:<div><br></div><div>99: A>B>C</div><div>1: C>B>A</div><div><br></div><div>The two winning orders are A>B>C and C>B>A - sum of distances is 0. So A and C win. Yet I think most of us would agree that the correct proportional winners are A and B.</div>
<div><br></div><div>Jameson<br><br><div class="gmail_quote">2009/10/5 Kristofer Munsterhjelm <span dir="ltr"><<a href="mailto:km-elmet@broadpark.no">km-elmet@broadpark.no</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
I continue to tinker with vector quantization, and in doing so, I've<br>
found a multiwinner version of Kemeny. Some of the ideas for it, I've<br>
mentioned before, but it might still be useful.<br>
<br>
As with Kemeny, we define the Kemeny distance metric between two orders to be the sum of pairs where the orders' preferences differ: that is, for all pairs of candidates listed, add one to the distance if one of the orders rank the first candidate ahead of the other whereas the other does not, or vice versa.<br>
To phrase it differently, consider a tournament matrix generated from each order. The matrix for A vs B is 1 if A beats B, -1 if B beats A, and 0 if they're equally ranked. Then the Kemeny distance is equal to the number of differing fields in the orders' tournament matrices.<br>
<br>
The single-winner Kemeny rule proceeds by finding the ranking (social ordering) that is the geometric median of the orders given in the supplied ballots, with the metric in question being Kemeny distance.<br>
<br>
Here's where the vector quantization idea comes into play: for multiwinner Kemeny with k winners, find k points (orders) so that the sum of the distances between each ballot and its closest point (order) is minimized.<br>
<br>
Left to itself, the top ranked candidates in these n "winner orders" should provide a good council. However, there is one constraint that would have to be imposed: a single member can't be assigned more than one seat. Thus, the top rank of each of these orders must be unique: no candidate must be ranked top on more than one winner order.<br>
<br>
-<br>
<br>
To rephrase that, the multiwinner Kemeny rule is:<br>
<br>
For some ranking p and q, define dist(p, q) equal to the Kemeny distance between p and q.<br>
<br>
When electing k members from n candidates using i ballot rankings (b_1 ... b_i), a winner ranking set W is a vector of k rankings so that no candidate is ranked top on more than one of these k rankings.<br>
<br>
Define cdist(p, W) as the distance, according to dist, from p to the member in W that minimizes the result.<br>
<br>
Then determine W, subject to the rank constraint above, so that<br>
sum(x = 1..i) cdist(b_x, W)<br>
<br>
is minimized.<br>
<br>
The winners are those first ranked on the rankings that constitute W.<br>
<br>
-<br>
<br>
This method makes no mention of quotas, nor is it an "elect and punish" method (except indirectly, in that a ballot only counts against its closest winner ranking, not all of them). Yet, it seems to be fairly proportional, and it retains some of the Condorcet qualities of Kemeny (as I'll show in an example below).<br>
<br>
On the other hand, it is very hard to determine the actual winners. Since a winner rank can be any of the n! possible rankings (I have not tried this with equal-rank), it's even worse than combinatorial methods like Schulze STV. Perhaps integer programming could be used to speed up the multiwinner method, since that has been used to find Kemeny winners more quickly.<br>
<br>
Also, since Kemeny is a special case of this multiwinner method (with k=1), it inherits the flaws of Kemeny: vulnerability to clones, for instance. Furthermore, like many PR methods, it's not summable (at least not that I can see, because it's unclear ahead of time which the members of W are going to be).<br>
<br>
I don't know if it retains reinforcement. Also, it resists vote<br>
management for the example on Wikipedia's Schulze STV page, but since it can't strictly satisfy the DPC without an appropriate tiebreaker, it can't be weakly invulnerable to vote management either.<br>
I'm not sure if it satisfies DPC in the weak sense that winner vectors satisfying the DPC will always either win or be tied at top.<br>
<br>
<br>
<br>
Let's show how it works by a (2,3) election using the PSC-CLE example<br>
where the Condorcet winner is far from those included in the STV winner set.<br>
<br>
For the sake of computational efficiency, the reported distances are half of the actual distances (since if p has A > B and q has B > A, dist(p,q) would report 2 - one for p's A>B value not matching q's A>B value, and one for p's B>A value not matching q's B>A value, whereas one can make the check quicker by only checking A>B in this case).<br>
<br>
33 A>D>B>C<br>
33 B>D>A>C<br>
32 C>D>A>B<br>
2 D>A>B>C<br>
<br>
The Droop quota is 100/3, 33.33^, so no single candidate is supported by<br>
more than a Droop quota. STV elects {A, B}, and the CW is D.<br>
<br>
For the multiwinner Kemeny rule above, W is<br>
a. C>D>A>B<br>
b. D>A>B>C<br>
with sum of distances 99, because:<br>
<br>
33: A>D>B>C is closest to b. with a dist. of 1, and 33 * 1 = 33<br>
33: B>D>A>C is closest to b. with a dist. of 2, and 33 * 2 = 66<br>
32: C>D>A>B is closest to a. with a dist. of 0, and 32 * 0 = 0<br>
2: D>A>B>C is closest to b. with a dist. of 0, and 2 * 0 = 0<br>
<br>
Thus the winners are {C, D}. One might object that A is better than C,<br>
because C is ranked last on more ballots; however, this disagrees with<br>
the B>D>A>C and C>D>A>B voters. If W is:<br>
a. A>D>B>C<br>
b. D>C>A>B<br>
then<br>
33: A>D>B>C is closest to a. with 33 * 0 = 0<br>
33: B>D>A>C is closest to a. with 33 * 3 = 99<br>
32: C>D>A>B is closest to b. with 32 * 1 = 32<br>
2: D>A>B>C is closest to a. with 2 * 1 = 2<br>
<br>
and the sum is 133, which is greater than 99.<br>
<br>
<br>
Note that if we force A above the Droop quota by doing<br>
34 A>D>B>C<br>
33 B>D>A>C<br>
32 C>D>A>B<br>
1 D>A>B>C<br>
then we have a tie between AC (A>D>B>C C>D>A>B) and CD (C>D>A>B D>A>B>C) with sum distance 100. Forcing it further to<br>
35 A>D>B>C<br>
32 B>D>A>C<br>
32 C>D>A>B<br>
1 D>A>B>C<br>
makes AC win (sum distance 97).<br>
----<br>
Election-Methods mailing list - see <a href="http://electorama.com/em" target="_blank">http://electorama.com/em</a> for list info<br>
</blockquote></div><br></div>