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