To reiterate and/or answer some questions: 1. there is no way to find the Kemeny winner that is much faster than finding the full Kemeny ordering. More precisely, both are NP-complete tasks so there is no poly-time algorithm for either unless P=NP.
2. Even if some benificent God helpfully informs you of the name of the Kemeny winner, or the full Kemeny ordering, then there is no easy way for you to confirm or deny that claim. No matter how much supporting information God provides to you (if it is only a polynomially-bounded number of bits) -- such as a proof -- there remains no way to confirm or deny either claim that runs in polynomial time, unless NP=coNP. In other words, no short proofs exist. 3. It IS possible to find both the Kemeny ordering and Kemeny winner, in any election, if you are willing to devote enough compute time to it. But the amount of time needed will exceed any polynomial in the #candidates. Every currently known algorithm in the papers I cited fails for easy-to-generate and fairly natural 40-candidate elections, no matter how much time they devote to it within the limits of their finances. 4. The hardest elections have got Smith set = the full set of candidates. This is asymptotically not a great restriction since random elections have Smith set = full set, with probability -->1 in the limit as #candidates --> infinity. 5. I posed as a challenge, a certain randomized class of 27-candidate elections which I designed to be hard. It seemed plausible to me that these 27-candidate elections might be too hard for current algorithms to reliably provably find the Kemeny winner. I of course do not know the winners of my challenge elections, since if I did, then a short proof would exist, which it cannot in maximally hard elections. So far, nobody has convinced me they are able to answer the Kemeny challenge, but Kristofer Munsterhjelm has preliminarily claimed in email that he's been able to solve one election sampled from my class -- which causes him to be optimistic that he can answer the challenge. We'll see -- if that is true, I don't see why K.M. hasn't completed the job, since it seems like if he's done what he thinks he has, then he's done 99% of the programming work and the remaining 1% is for some reason holding him up. In the event KM or somebody else successfully answers the challenge, then I'll be reasonably impressed, but then I probably can create harder challenges with greater numbers of candidates -- the goal is to try to identify the borderline between "hard" and "easy." 6. Richard Fobes has told me and the election methods group in emails that he's got various wonderful answers to all these issues, which he sadly has never found the time to explain, including in his privately published book on the subject. I (a) just don't believe him. (b) some of his "great solutions" seem to be now to recommend a hybrid of about 3 different election methods -- which he has nowhere fully defined. This hybrid method no longer can claim either simplicity or any attractive package of nice logical properties, but it should at least make it always feasible to compute the winner.. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step) ---- Election-Methods mailing list - see http://electorama.com/em for list info
