2011/9/24 Kristofer Munsterhjelm <[email protected]> > Warren Smith wrote: > >> 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. >> > > Is Kemeny independent of Smith-dominated alternatives? Toby said he thought > he was. If it is, then Kemeny is feasible for practical elections because > you can just restrict it to the Smith set (and the Smith set won't be very > large in practice). That is, of course, unless the existence of advanced > voting methods will make the public vote in ways that will lead to a greater > Smith set (e.g. candidates who otherwise didn't want to split the vote now > feel bold enough to show up). Still, even so, I can't imagine there would be > a 27-member Smith set. > > Warren, I would like to see your response to this issue.
Jameson
---- Election-Methods mailing list - see http://electorama.com/em for list info
