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

[Richard Fobes]

On 12/22/2011 12:27 AM, Jameson Quinn wrote:
 > ...
 > If you aren't 100% sure you have the right answer, you probably don't
 > have the right answer 100% of the time.

Keep in mind that I am allowing for cases in which there are 50 or 100 
choices _and_ it is important for every single one of the choices to be 
correctly ranked.

In real life there are cases that involve lots of candidates -- in fact 
I recently heard about an election involving 46 candidates -- but only 
the top few choices are important.  (Maybe as many as the top half win 
seats.)  The correct ranking for the obviously losing candidates is not 
needed.

Specifically I don't want to claim -- without proof -- that every one of 
the obviously losing candidates -- say the bottom 5 candidates out of 50 
candidates -- is accurately ranked with respect to each other. 
(Actually in this case the lack of statistical significance of the 
collected data is a bigger issue.)

Remember that other single-winner voting methods only identify a single 
winner.  The VoteFair popularity ranking software will always correctly 
identify the correct single winner according to the Condorcet-Kemeny 
criteria.

My uncertainty is about the correct ranking of every single choice when 
there are 50 or 100 choices.

Keep in mind that the software easily (quickly) calculates all the 
sequence scores if there are up to 6 choices, so those results can be 
used to accurately identify the winner -- which is all that is usually 
wanted anyway.

My statement ...
 >    But as far as I know, the algorithm always finds the highest
 >    score, even in the most complex cases.
... is not expressed as having 100% certainty because I do not have a 
_proof_ that it always finds the largest sequence score.

I have run calculations for thousands of rankings (based on real-life 
data, plus unusual cases that I've collected), and I have compared those 
rankings to the method that calculates every sequence score (if there 
are no more than 6 choices), and I have not found any cases in which the 
described algorithm fails to find the highest score.

Again I'll say that my concerns about the validity of the results relate 
to odd kinds of ties, which are not relevant to the Condorcet-Kemeny method.

That last sentence needs clarification.  Similar to the way that the 
"Condorcet method" does not specify what should happen when there is no 
Condorcet winner, the Condorcet-Kemeny method does not specify what 
should happen when more than one sequence has the same highest score. 
Those are the cases where I know I have correctly identified the implied 
ties for simpler cases, but there are complex (such as non-symmetrical) 
cases for which others might argue for a different tie structure.

Richard Fobes


On 12/22/2011 12:27 AM, Jameson Quinn wrote:
>
>
> 2011/12/22 Richard Fobes <ElectionMethods at votefair.org
> <mailto:ElectionMethods at votefair.org>>
>
>       But as far as I know, the algorithm always finds the highest
>     score, even in the most complex cases.
>
>
> If you aren't 100% sure you have the right answer, you probably don't
> have the right answer 100% of the time.
>
>
>
>     Yes, a _proof_ that the highest sequence score has been found may be
>     NP-hard.  Yet, as the calculation descriptions point out, that
>     becomes an issue only in situations that are like finding the
>     highest sand dune in a desert.  In such cases different experts will
>     argue about which candidate really should have won.
>
>
> I understand that you're claiming that the only cases where your
> algorithm might not give the right answer are unrealistic cases where
> the "wrong" answer is not actually very wrong. Still, if you can't prove
> you have the right answer, you possibly don't.
>
> So your own claims contradict themselves. It would seem that you do not
> have a polytime algorithem for finding the Kemeny-Young winner, but just
> for probably finding that winner. I would not be surprised if your
> algorithm was right >99.9% of the time. But if the alternative when your
> algorithm is wrong is a 10% chance of a civil war which kills millions,
> then that still could be an unacceptable risk. And your claim to have
> solved the problem, when you haven't, actually reduce my confidence that
> you've even solved it 99% of the time.
>
> Jameson
>