[EM] Displaying intermediate results in Condorcet-based elections

[Gervase Lam]

> Date: Wed, 29 Oct 2003 19:10:06 -0800
> From: Rob Brown <rob at hypermatch.com>
> Subject: Re: [EM] Displaying intermediate results in Condorcet-based
>   elections (re: Rob Brown's original question)

> My original request was to suggest a way to produce a single scalar
> score per candidate which enhances, but does not conflict with, a simple
> ordered ranking.

Since only one method of doing this has been mentioned so far, I think 
I'll give it a go.  This is a much more consistent method than the other 
method.  It uses Kemeny-Young Condorcet.

I've changed things slightly so that a higher score means a better score.  
Kemeny-Young is usually explained so that the lower the score, the better 
the score.

(1) List all of the possible permutations (i.e. rankings) the 
candidates can be arranged in to.

(2) For each permutation, pick a ballot.  For each pairwise/head-to-head 
comparison in the permutation that does not contradict the 
pairwise/head-to-head comparison on the ballot, increase the score of the 
permutation by one.  Repeat this permutation scoring procedure for each of 
the remaining ballots.

(3) Repeat step 2 for each of the remaining permutations.

The permutation (i.e. ranking) with the largest score is the 'winning' 
ranking.

The above describes Kemeny-Young.  Hopefully I got the explanation right.

Now comes getting some scalar scores.  In what follows, I assume that the 
'winning' permutation has been committed.  In other words, nothing changes 
the ranking of the candidates.  So, when I say the 2nd place candidate, I 
mean the 2nd place candidate according to the 'winning' permutation.

(4) Sort the list of permutations in order of decreasing permutation 
scores.

(5) Start from the top most permutation on the list (i.e. the one with the 
highest score).  Give the 1st place candidate this permutation's score.

(6) Starting from the next permutation on the list, go down the list until 
a permutation is reached that includes the 2nd place candidate in the 
permutation's top 2 places.  Give the 2nd place candidate this 
permutation's score.

(6) Starting from the next permutation on the list, go down the list until 
a permutation is reached that includes the 3rd place candidate in the 
permutation's top 3 places.  Give the 3rd place candidate this 
permutation's score.

...and so on until all of the candidates have a score.  I must admit, the 
way the scalar scores are given to the candidates is a bit of a fudge.  

I get the feeling that the further down the 'winning' ranking you go, the 
closer the scores get to each other.  I had thought of other ways of doing 
it using scores from Kemeny-Young.  But this meant that I had to overcome 
contradictions in a similar fashion to the first Condorcet-to-Scalar 
method.  Either that or there was the possibility that there would not be 
enough permutations.

Kemeny-Young (steps 1 to 3) is a brute force method.  In this case this is 
good as writing a computer program for it is more straight forward in 
comparison with writing a beat-path algorithm.  The down side is that the 
number of permutations can really hog the CPU.  For example, if there were 
10 candidates, there would be about 3.5 million = 10! permutations to go 
through.  I don't know whether there is enough CPU power to do this in a 
reasonable amount of time given the context of this thread.

I think that 10 is reasonable limit to the number of candidates allowed.  
15 candidates gives you 1.3 * 10^12 permutations!

At first, I thought that you needed to keep all of the ballots verbatim in 
order to do Kemeny-Young.  But I then remembered that a few months ago I 
had noticed that all that needs to be done for Kemeny-Young is to compare 
the results matrix with each permutation, which has been converted to a 
matrix.  I'm sure other people have already noticed or know about this.

Thanks,
Gervase.