[EM] Re: Election-methods Digest, Vol 4, Issue 13

[Gervase Lam]

> From: Matthew Dempsky
> Subject: Re: [EM] Re: Election-methods Digest, Vol 4, Issue 13
> Date: Thursday 14 October 2004 02:09 am

> On Mon, 2004-10-11 at 20:45, Gervase Lam wrote:
> > Kemeny can be basically described as follows:

> > [...example elided...]
>
> It seems similar in concept to finding the line of best fit, which I'll
> note tries to minimize the sum of squared differences rather than simply
> the sum of absolute differences.  Has that alternative been considered?

I don't think so, no.  However, the only way I can think of using this is 
possibly for multi-winner (e.g. a panel of candidates) election.  See <>.  
However, it talks about cardinal social utilities.  Condorcet methods 
don't have cardinal utilities as the input.

Other than possibly for that, I don't see the point of using square 
differences.  It could give a different ranking in comparison to normal 
Kemeny.  In which case, I would prefer the normal Kemeny winner as "one 
pairwise vote" directly represents what a voter voted for rather than 
being fiddled by "squaring it".

> Also, the method doesn't seem to scale very well.  Unless there's some
> simpler trick to determining the closest Result Matrix than brute force,
> it's an O(N!) algorithm at best.

Yes.  That is the problem with this method.  I don't think anybody has 
found a trick to do this.  There may not be a trick to do this.

However, this is one of the reasons why some people like Kemeny.  The 
difficulty in doing the calculation (at least at the moment) means that 
strategising is more difficult.

> Finally, what about considering rankings such as A>B=C or A=B>C?

I did consider posting tied rankings, even though this is really not a 
part of Kemeny.  However, there are two reason why I did not:

(1) I get the feeling trying tied rankings to see how close they are to 
the result matrix makes Kemeny more prone to truncation.
(2) I only wanted to use it get an idea of whether the C > A win could be 
honoured.  It could, but it would have meant sacrificing the A > B win, 
which was more of a sacrifice than sacrificing the C > A win.

Also, if I were to test tied rankings, I would avoid rankings like A=B>C.  
After all, the method really needs to find a single winner.  There is no 
single winner in the A=B>C ranking.  Also, it is possible to have multiple 
rankings, which have no ties, having the same Kemeny score.

>  Also,
> what about relations that can't be expressed in that limited notation
> such as (simultaneously) A>B>C and A>D>E>C (i.e. B is indifferent from D
> and E, but D is preferred to E).  I think any irreflexive,
> anti-symmetric, transitive relation on the set of candidates would be
> valid.

>From the point of view using this for a single winner, I don't think it is 
worthwhile.  Trying to find which normal ranking is the Kemeny ranking is 
difficult enough.

However, I was thinking whether this type of idea could be used to get 
multiple winners.  Or may be subtract the pairwise matrix for the Kemeny 
ranking away from the result matrix and then find the Kemeny ranking of 
this new matrix.  However, I don't think it is anywhere near good enough 
for getting multiple winners.

> On that note, is there any reason (other than to avoid confusing
> voters), to restrict votes to total orderings rather than partial
> orderings?

I don't think so, no.  Just create the result matrix the way you would 
normally do for tied rankings (e.g. Neither A>B nor B>A are true, 
therefore zero is added to those pairwise results).

Thanks,
Gervase.