<br><br><div class="gmail_quote">2011/9/24 Kristofer Munsterhjelm <span dir="ltr"><<a href="mailto:km_elmet@lavabit.com">km_elmet@lavabit.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

<div class="im">Warren Smith wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
To reiterate and/or answer some questions:<br>
<br>
1. there is no way to find the Kemeny winner that is much faster than<br>
finding the full Kemeny ordering. More precisely, both are NP-complete tasks<br>
so there is no poly-time algorithm for either unless P=NP.<br>
<br>
2. Even if some benificent God helpfully informs you of the name of<br>
the Kemeny winner,<br>
or the full Kemeny ordering, then there is no easy way for you<br>
to confirm or deny that claim.   No matter how much supporting information<br>
God provides to you (if it is only a polynomially-bounded number of<br>
bits) -- such<br>
as a proof -- there remains no way to confirm or deny either claim that runs in<br>
polynomial time, unless NP=coNP.  In other words, no short proofs exist.<br>
<br>
3. It IS possible to find both the Kemeny<br>
ordering and Kemeny winner, in any election, if you are willing to<br>
devote enough compute time to it.  But the amount of time needed will<br>
exceed any polynomial in the #candidates.  Every currently known<br>
algorithm in the papers I cited fails for easy-to-generate and fairly natural<br>
40-candidate elections, no matter how much time they devote to it<br>
within the limits of their finances.<br>
<br>
4. The hardest elections have got Smith set = the full set of candidates.<br>
This is asymptotically not a great restriction since random elections have<br>
Smith set = full set, with probability -->1 in the limit as<br>
#candidates --> infinity.<br>
</blockquote>
<br></div>
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.<div class="im">

<br></div></blockquote><div>Warren, I would like to see your response to this issue.</div><div><br></div><div>Jameson </div></div>