[EM] Fast Condorcet-Kemeny calculation times, clarification of NP-hardness issue

[Kristofer Munsterhjelm]

On 03/05/2012 02:49 AM, Jameson Quinn wrote:
> Remember that K-Y is Condorcet compliant, and I believe consistent as
> well (that is, you can generalize from Condorcet to Smith and even
> ignore the effects of the candidates outside the Smith set). So the set
> of cases where the problem is easy is at least somewhat well-defined in
> that sense, and probably includes (for instance) all the elections I've
> ever voted in. And so I believe that Richard's "my algorithm usually
> gets it right" is not totally content-free.
>
> But Warren is also very right that, when things start to go wrong, it's
> impossible to know whether you have the right answer, the almost-right
> answer, or something totally wrong. And if some algorithm said
> "Jameson's favorite is probably not the winner, though I can't prove
> it", I don't think I'd be very inclined to accept that "probably"on
> Richard's say-so. Part of the whole point of democracy is to guarantee
> that there will be a clear winner with some legitimacy, since a civil
> war is usually a lot worse than the second-best option.

It seems a very simple way exists to clear all of this up. Namely: take 
Fobes's algorithm (if it's been implemented somewhere). Also take an 
algorithm known to give the Kemeny ordering, if NP-hard -- e.g. 
something like the integer linear programming formulation my voting 
simulator uses. Then run them with millions of random ballot set 
instances. If there's at least one ballot set where the "known good" 
algorithm gives an ordering with a better Kemeny score (sum of number of 
voters agreeing with the pairwise contests), then we're done, that 
proves that Fobes's algorithm is not Kemeny. If there are none, then 
that's weird -- it would give a statement of "Fobes's algorithm usually 
agrees with Kemeny when there are less than n candidates and v voters" 
-- and if n and v are small enough, it can even be exhaustively checked.