[EM] Advocacy of Kemeny's method

[mrouse1 at mrouse.com]

Sorry it's taken so long to respond -- that'll teach me to download mail 
at a remote location. :)

Steve Eppley wrote:

>
> Kemeny finds the "best" social ordering by finding
> the ordering that maximizes the sum of sizes of majorities that agree 
> with it.  That makes it vulnerable to clone manipulation.  MAM is 
> equivalent
> to analogous method that finds the "best" social ordering by using the 
> maxlexmax comparitor rather than the sum comparitor, so it's 
> independent of clones.
>
> Here's an example to consider, involving Kemeny's
> vulnerability to clone alternatives. (I hope I have the example 
> straight.  I whipped it up fairly fast.)
>
>   9 voters, 3 alternatives:
>      4: A>B>C
>      3: B>C>A
>      2: C>A>B
>
>   There are 3 majorities:
>      6 voters rank A over B.
>      7 voters rank B over C.
>      5 voters rank C over A.
>
> Nearly every method elects A here, yes?  Kemeny and MAM pick A>B>C as 
> the social ordering.  Kemeny picks A>B>C because it agrees with 13 
> (the majority of 6 who voted "A>B" + the majority of 7 who voted 
> "B>C").  Note that the social ordering B>C>A agrees with only 12 (the 
> 7 "B>C" majority + the 5 "C>A" majority).
>
> (There's another definition of Kemeny that finds the social ordering 
> that maximizes the sum of pairwise preferences that agree with it, 
> rather than the sum of sizes of majorities that agree with it, but its 
> principle is nearly equivalent, and a similar example illustrates its 
> problem with clones.)
>
> Now add in one or more clones of C.  Each clone added in adds another 
> majority of size 5 to the Kemeny-best social ordering that ranks C 
> over A than to the Kemeny-best social ordering that ranks A over C.  
> Thus, adding a clone of C, say C', causes either B>C>C'>A or B>C'>C>A 
> to become the Kemeny-best social ordering, changing the outcome from A 
> to B.  On informational grounds this is illogical, since no 
> information about A or B is gained when voters also rank alternatives 
> that are nearly identical to C.  Worse, it creates incentives to 
> manipulate the outcome by strategic nomination, and it could even lead 
> to routine farces where each faction nominates as many (clone) 
> alternatives as they can find that will pairwise-beat the 
> alternative(s) that will pairwise-beat their favorite(s).
>
This is a problem with Kemeny ordering -- and it's definitely illogical 
-- but I don't think it's *that* serious. (heh, if that doesn't get a 
response, nothing will). If candidate B were to use it to manipulate the 
election, he would not only have to support a competitor (C) but a clone 
of a competitor, both of which are preferred to A. If B's support were 
slightly less or C/C' slightly more the cycle would break and B would 
lose outright -- and if C's policies and platform were preferable to A 
to begin with, why wouldn't competitor B take them as his own if he is 
that Machiavellian?

Of course if the clones C and C' were to join the race on their own, 
they could influence the outcome in favor of B, though generally it 
wouldn't be to their benefit so there would be little incentive to run 
separate campaigns (though perhaps there might be an argument on who 
would be the top of the ticket).

On the other hand, according to Michel Truchon (referring to Young and 
Levenglick, which you mentioned in a previous email) -- 
http://citeseer.ist.psu.edu/cache/papers/cs/11707/http:zSzzSzwww.ecn.ulaval.cazSzw3zSzrecherchezSzcahierszSz1998zSz9814.pdf/truchon98figure.pdf 
-- Kemeny satisfies a weaker version he calls local independence of 
irrelevant alternatives (LIIA) *and* satisfies reinforcement (where two 
distinct groups have the same order, this is the same as the consensus 
ranking for both groups together). According to Truchon, Kemeny is the 
only rule that satisfies them both.

I'm not sure if this is true (not having the math required to prove it 
either way), but it would certainly be an illogical result to have two 
groups with the same preference order adding up to a different 
preference order. I'm not sure if it would be possible to use it for 
political manipulation -- some weird form of gerrymandering, perhaps -- 
but it's certainly a logical conundrum. And of course, according to 
Arrow there is no such thing as a perfect system, we just have to pick 
which flaws we can live with. :) (BTW, I saw your mention of the 
reinforcement issue, I just think it would be more difficult to 
influence an election by adding clone candidates of a competitor than it 
would be for politicians to redraw districts. My personal preference 
would be to have the voters choose the electoral map they want at the 
same time they vote for the candidate they want, that would keep 
politicians on their toes)

In addition, I like the fact that the Kemeny order is a good method for 
reducing spam in search-engine results -- trying to push a website up 
the rankings is somewhat analogous to strategic voting. (MAM is probably 
pretty good, plus it's easier to compute, but local Kemenization is 
computationally cheap as well).

BTW, I think I lost the email (or it's on my other computer) but did you 
say that MAM satisfies the extended Condorcet criteria? If so, the 
difference (in results, at least) between Kemeny and MAM must be very 
small, and the major benefit would be the ease of calculation (not an 
insignificant factor). It would be kind of fun to test both systems with 
real-world examples -- not just voting, but spam prevention, character 
recognition, and the like.

Mike
mrouse1 at mrouse.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20040924/a8039924/attachment-0003.htm>