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

[Matthew Dempsky]

Gervase Lam <gervase.lam at group.force9.co.uk> writes:

>> 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.

I think you misunderstood me.

What I meant was, with Kemeny's method you first calculate the
resultant matrix by averaging all of the vote matrices and then try to
determine the vote matrix that would best match that resultant matrix.
Sure, it's not the exact same as finding the line of best fit, but "it
seems similar in concept".

> 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".

The typical line of best fit equation is used to prefer a line that's
a little off from several points rather than a line that's way off
from just one or two.  Applying the same idea to finding a best fit
vote matrix would seem to give you the same result: a vote result
that's close to satisfactory to everyone without seriously
disenfranchising any single votes.

I'll give the disclaimer that I haven't spent any considerable time
thinking about it to see if it upholds all of the same advantages of
Condorcet methods.

>> 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.

It also makes it more difficult to verify who won.

>> 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.

How do you figure?  If everyone voted A>B=C, wouldn't it make sense
for the result to also be A>B=C?

> (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.

That's understandable for your example, but I was considering the more
general application.  (Your email was the first I'd heard about this
method.)

> 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.

I don't think you should leave out possibilities like A=B>C for the
same reason that Condorcet methods recognize that cycles can exist.
The fact that A=B>C isn't a problem with the voting method but instead
that two equal candidates ran.

>>  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.

Yeah, you want to find a single winner, but forcing a single winner on
a situation in which there might not be a single winner seems like a
bad idea.

>> 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).

No, I mean an election in which there are 4 options and a voter would
like to cast a ballot in which A>B and A>C>D are simultaneously
upheld.  In other words, the voter doesn't have any preference for B
over or under C or D.  You can't simply say B=C or B=D because then
those would imply B>D or D>B (respectively) which, in the situation I
described, does not accurately represent the voter's preferences.