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

On Sat, Sep 24, 2011 at 10:50 AM, Kristofer Munsterhjelm<br>
<div class="im"><<a href="mailto:km_elmet@lavabit.com">km_elmet@lavabit.com</a>> wrote:<br>
</div><div><div></div><div class="h5">> Warren Smith wrote:<br>
>><br>
>> 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<br>
>> 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<br>
>> 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<br>
>> 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>
><br>
> Is Kemeny independent of Smith-dominated alternatives? Toby said he thought<br>
> he was. If it is, then Kemeny is feasible for practical elections because<br>
> you can just restrict it to the Smith set (and the Smith set won't be very<br>
> large in practice). That is, of course, unless the existence of advanced<br>
> voting methods will make the public vote in ways that will lead to a greater<br>
> Smith set (e.g. candidates who otherwise didn't want to split the vote now<br>
> feel bold enough to show up). Still, even so, I can't imagine there would be<br>
> a 27-member Smith set.<br>
<br>
</div></div>--seems to me, KM is correct; if the Smith Set has less than about 20<br>
members (and if this also is true recursively upon removing it), then<br>
it always will be feasible to find the Kemeny order.<br>
<br>
How often will a (>=20)-member Smith set arise in practice?<br>
<br>
I do not know.   KM "can't imagine" it will happen, but that's his guess.<br>
I think if you take a 100-candidate election with random-uniform<br>
votes, it'd happen pretty often. Such elections have Condorcet winners<br>
about 9-12% of the time (says my computer), which leads me to guess<br>
that they have (>=20)-member Smith sets about 10% of the time.  See<br>
also puzzles<br>
25 and 26 here for some theorems about the closely related problem of<br>
random "round robin tournaments" rather than random "elections":<br>
   <a href="http://www.rangevoting.org/PuzzlePage.html" target="_blank">http://www.rangevoting.org/PuzzlePage.html</a><br>
<br>
But it could be argued/hoped that 100-candidate elections, when they<br>
occur, will have vote distributions quite dissimilar to<br>
random-uniform.<br>
It could be counterargued that humanity's experience with<br>
100-candidate elections is small, and with 100-candidate<br>
rank-order-ballot<br>
elections is even smaller, so there is little basis for KM's guess.<br>
<br>
Tideman in his book has got a statistical semiempirical model, based<br>
on real election statistics, of rank-order ballot elections.  His<br>
model is described/corrected/recalculated here:<br>
    <a href="http://rangevoting.org/TidemanElModel.html" target="_blank">http://rangevoting.org/TidemanElModel.html</a><br>
and it finds the probability, in a 100-canddt election,that a<br>
Condorcet Winner exists, is 27%, and for a 200-canddt<br>
Tideman-statistics election this probability is 5.6%.<br></blockquote><div><br></div><div>At a very, very rough estimate, the average size of the Smith set should be about 1/prob(CW). That is, take the prob(CW) as the recursive probability that the Smith set "stops at size n" for any n. (This is obviously very rough, because for instance a 2-member Smith set is impossible. But I'm just going for generalities here)</div>

<div><br></div><div>So, a 100-candidate election in Tideman's model would have a Smith set around 4 members, and 95% of the time (1/e^3), would have a smith set under 12. In this model, a 20-member Smith set would happen about once per 150 elections.</div>

<div><br></div><div>I'd say that this is (extremely) weak evidence that Kemeny could handle a 100-member election. I'd also guess that Tideman's model is probably "pessimistic" for such very-large elections in that it overestimates the strength of non-top-tier candidates. So in this sense, I would be inclined to give Kemeny the benefit of the doubt.</div>

<div><br></div><div>Also note that it is extremely probable that a 5-25 member Smith set would happen at least once before any >25-member Smith sets ever happened. That would give much stronger data from which to evaluate the "risk" of an irresolvable Kemeny election, before such a crisis occurred.</div>

<div><br></div><div>hoping-that-someone-else-is-better-with-beta-functions-than-I-am-ly y'rs,</div><div>JQ</div></div>