[EM] Advocacy of Kemeny's method

[Steve Eppley]

Mike R wrote:
> Michel Truchon gives the following description of XCC 
> (the Extended Condorcet Criterion):
> 
>    The usual Condorcet Criterion says that if an 
>    alternative is ranked ahead of all other 
>    alternatives by an absolute majority of voters, 

I'm sorry to quibble over wording, but that'll confuse
people unfamiliar with the Condorcet criterion, since
"ranked ahead of all other alternatives" literally
means "ranked first".  It reads as if there is only
one majority.

>    it should be declared the winner. The following
>    partial extension of this criterion to other ranks 
>    is proposed: If an alternative is "consistently" 
>    ranked ahead of another alternative by an absolute
>    majority of voters, it should be ahead in the final
>    ranking. The term "consistently" refers to the 
>    absence of cycles in the majority relation
>    involving these two alternatives.

MAM satisfies XCC.  If a (relative or absolute) majority
rank x over y, then MAM will socially order x over y
unless there exists a cycle that includes the x over y
majority in which every other majority is at least as 
large.

> Cycle removal just means that when you have a circular tie 
> with regular Condorcet voting -- Candidate A is preferred
> to B, Candidate B is preferred to C, and Candidate C is 
> preferred to A -- the Kemeny order will unwind the cycle 
> and put the candidates in a specific order without the
> need for a tie-breaker method.  Tie-breakers are fine, 
> I just find is more aesthetically pleasing this way.

But Kemeny can need a tiebreaker, since it's possible
that two or more social orderings are Kemeny-best.
Here are two examples:

   50:  A>B
   50:  B>A

   33:  A>B>C
   33:  B>C>A
   33:  C>A>B

I'll assume for the moment that Mike merely meant 
that Kemeny socially orders the alternatives, since 
orderings are acyclic by definition.  MAM socially 
orders the alternatives too.

> By "voting manipulation resistance," I mean it is difficult 
> for a voter to come up with a way to improve his outcome 
> over voting sincerely. Partly this is because it's a 
> NP-hard problem to solve and requires complete knowledge
> of voting preferences, partly because it disregards
> orders it considers outlandish compared to majority
> preferences (the people who actually do prefer
> Nader>Bush>Kerry lose out, but hey...).  Of course, 
> like any non-dictatorial method it's still 
> theoretically possible to manipulate.

Other than saying NP-hardness is desirable (which would
be a controversial claim, beyond this narrow context) 
this voting strategy "resistance" still hasn't been defined 
rigorously enough for me to evaluate whether MAM satisfies 
it.  MAM is not NP-hard to tally, so if Mike is really 
looking for NP-hard methods--the rest of his writing 
suggests otherwise--then MAM would be slightly 
disappointing.  On the other hand, MAM satisfies
some defensive strategy criteria promoted by some
members of this list, originated by Mike Ossipoff:
SDSC (nearly equivalent to Minimal Defense, described
at my website), WDSC (nearly equivalent to Non-Drastic 
Defense) and Truncation Resistance.

I don't understand what Mike means about Kemeny 
disregarding "outlandish" votes.  I would say Kemeny
does not disregard any votes.  Perhaps he meant 
that "outlandish" votes won't be consistent with
the Kemeny social ordering.  But that would seem
to be just a definition of outlandish, and hence 
tautological, so I'm sure I'm missing something.

> I've heard of MAM, even read a bit about it, and 
> it appears to be a fairly attractive system--
> especially the ease of calculation compared to 
> Kemeny. I haven't read it in depth enough to 
> compare it to Kemeny-Young, though (and to be 
> honest, a lot of the math involved in Kemeny is 
> beyond me to begin with), but I'll check it out 
> some more this weekend and see if I can get 
> a better feel for it.


--Steve