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 <[email protected]
<mailto:[email protected]>>
As previously promised, I am revealing how Condorcet-Kemeny
calculations can be done fast.
...
----
Election-Methods mailing list - see http://electorama.com/em for list info
