[EM] Fast Condorcet-Kemeny calculations -- in polynomial time

[Richard Fobes]

On 12/21/2011 1:39 PM, Jameson Quinn wrote:
> This algorithm, at first read, seems that it could still be NP-hard if
> all candidates were part of a (three-candidate???) cycle with all other
> candidates. Which is, of course, a case which would hardly ever arise in
> real life; but one which must be considered in giving a worst-case
> execution time order for the algorithm.
>
> Jameson


Complex cycles do require more calculation time -- if they have the same 
sequence score -- because the algorithm has to determine which choices 
are tied.

Remember that this is a challenge for VoteFair popularity ranking, but 
is not a problem for the Condorcet-Kemeny method because the C-K method 
does not specify how to handle tied sequence scores.

Running lots of real-life data through the algorithm revealed an odder 
scenario.  In this scenario there were two isolated and significantly 
different sequences that had sequence scores that were different by only 
a single count.  In one of these sequences a specific choice was ranked 
near the top, and in the other sequence it was ranked near the bottom. 
Some earlier (simplistic) calculation methods failed to find both of 
these "peaks".

If the algorithm has any deficiencies, they are likely to be in choosing 
when choices are tied instead of differently ranked.  Again I'll repeat 
that this only happens when more than one sequence has the same highest 
score, and the C-K method does not specify how to resolve such cases.

Something to keep in mind is that the algorithm does not repeat beyond a 
specified number of cycles.  In other words, the calculation time is 
always no more than a polynomial function of N, where N is the number of 
choices.  The constants for the function would be chosen to handle 
complex scenarios.  Of course simpler scenarios (such as each choice 
pairwise beating all lower-ranked choices) take much less computation time.

If someone finds a case -- either using real-life data or using an 
intentionally complex scenario -- in which the algorithm fails to find 
the highest sequence score, then I want to hear about that.  But as far 
as I know, the algorithm always finds the highest score, even in the 
most complex cases.

Richard Fobes



> 2011/12/21 Richard Fobes <ElectionMethods at votefair.org
> <mailto:ElectionMethods at votefair.org>>
>
>     As previously promised, I am revealing how Condorcet-Kemeny
>     calculations can be done fast.
>...