[EM] A multiwinner election method based on Kemeny

[Jameson Quinn]

What if you have to elect two with the following voters:
99: A>B>C
1: C>B>A

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.

Jameson

2009/10/5 Kristofer Munsterhjelm <km-elmet at broadpark.no>

> I continue to tinker with vector quantization, and in doing so, I've
> found a multiwinner version of Kemeny. Some of the ideas for it, I've
> mentioned before, but it might still be useful.
>
> 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.
> 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.
>
> 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.
>
> 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.
>
> 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.
>
> -
>
> To rephrase that, the multiwinner Kemeny rule is:
>
> For some ranking p and q, define dist(p, q) equal to the Kemeny distance
> between p and q.
>
> 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.
>
> Define cdist(p, W) as the distance, according to dist, from p to the member
> in W that minimizes the result.
>
> Then determine W, subject to the rank constraint above, so that
>  sum(x = 1..i) cdist(b_x, W)
>
> is minimized.
>
> The winners are those first ranked on the rankings that constitute W.
>
> -
>
> 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).
>
> 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.
>
> 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).
>
> I don't know if it retains reinforcement. Also, it resists vote
> 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.
> 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.
>
>
>
> Let's show how it works by a (2,3) election using the PSC-CLE example
> where the Condorcet winner is far from those included in the STV winner
> set.
>
> 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).
>
> 33 A>D>B>C
> 33 B>D>A>C
> 32 C>D>A>B
> 2  D>A>B>C
>
> The Droop quota is 100/3, 33.33^, so no single candidate is supported by
> more than a Droop quota. STV elects {A, B}, and the CW is D.
>
> For the multiwinner Kemeny rule above, W is
>        a. C>D>A>B
>        b. D>A>B>C
> with sum of distances 99, because:
>
>  33: A>D>B>C is closest to b. with a dist. of 1, and 33 * 1 = 33
>  33: B>D>A>C is closest to b. with a dist. of 2, and 33 * 2 = 66
>  32: C>D>A>B is closest to a. with a dist. of 0, and 32 * 0 =  0
>  2: D>A>B>C is closest to b. with a dist. of 0, and  2 * 0 =  0
>
> Thus the winners are {C, D}. One might object that A is better than C,
> because C is ranked last on more ballots; however, this disagrees with
> the B>D>A>C and C>D>A>B voters. If W is:
>        a. A>D>B>C
>        b. D>C>A>B
> then
>  33: A>D>B>C is closest to a. with 33 * 0 =  0
>  33: B>D>A>C is closest to a. with 33 * 3 = 99
>  32: C>D>A>B is closest to b. with 32 * 1 = 32
>  2: D>A>B>C is closest to a. with  2 * 1 =  2
>
> and the sum is 133, which is greater than 99.
>
>
> Note that if we force A above the Droop quota by doing
>        34 A>D>B>C
>        33 B>D>A>C
>        32 C>D>A>B
>        1  D>A>B>C
> 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
>        35 A>D>B>C
>        32 B>D>A>C
>        32 C>D>A>B
>        1  D>A>B>C
> makes AC win (sum distance 97).
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20091005/694516d5/attachment-0003.htm>