[EM] Re: Election-methods Digest, Vol 4, Issue 13
Gervase Lam
gervase.lam at group.force9.co.uk
Thu Oct 14 14:41:24 PDT 2004
> 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.
More information about the Election-Methods
mailing list