On Sat, Sep 24, 2011 at 10:50 AM, Kristofer Munsterhjelm <[email protected]> wrote: > 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.
--seems to me, KM is correct; if the Smith Set has less than about 20 members (and if this also is true recursively upon removing it), then it always will be feasible to find the Kemeny order. How often will a (>=20)-member Smith set arise in practice? I do not know. KM "can't imagine" it will happen, but that's his guess. I think if you take a 100-candidate election with random-uniform votes, it'd happen pretty often. Such elections have Condorcet winners about 9-12% of the time (says my computer), which leads me to guess that they have (>=20)-member Smith sets about 10% of the time. See also puzzles 25 and 26 here for some theorems about the closely related problem of random "round robin tournaments" rather than random "elections": http://www.rangevoting.org/PuzzlePage.html But it could be argued/hoped that 100-candidate elections, when they occur, will have vote distributions quite dissimilar to random-uniform. It could be counterargued that humanity's experience with 100-candidate elections is small, and with 100-candidate rank-order-ballot elections is even smaller, so there is little basis for KM's guess. Tideman in his book has got a statistical semiempirical model, based on real election statistics, of rank-order ballot elections. His model is described/corrected/recalculated here: http://rangevoting.org/TidemanElModel.html and it finds the probability, in a 100-canddt election,that a Condorcet Winner exists, is 27%, and for a 200-canddt Tideman-statistics election this probability is 5.6%. You also may enjoy the following easy exercise about the random tournament model. Consider N=A+B candidates. Suppose for any pair of candidates, which one wins pairwise, is determined by a coin flip. [(N-1)*N/2 independent coin flips in all.] QUESTION: what is the probability P that an A-member Smith set exists, i.e that there exists some subset of A of the N candidates, so that these A pairwise-defeat each of the remaining B candidates? ANSWER: P = binomial(N,A) * 2^(-A*B) QUESTION: what is the probability that ANY nontrivial Smith set exists? I.e. what is the chance that there exists ANY nonempty nonfull subset of the N candidates, whose members pairwise defeat all nonmembers? ANSWER (arises since summing the above answer from A=1 to N-1 using B=N-A yields an upper bound on this probability...): Prob(Nontrivial Smith Set) --> 0 when N--> infinity In particular for N=20 candidates we find Prob(Nontrivial Smith Set) < 0.0000763 and for N=100 candidates we find Prob(Nontrivial Smith set) < 3.2 * 10^(-28). The random-votes election model is harder to calculate with than the random tournament model but it usually has the same qualitative behavior. > I think I solved a few instances of Warren's 27x27 matrix on [0...1 > billion], but I can't be sure since I can't confirm that my Kemeny cost is > indeed the least possible. I am, however, assuming that it is, and so I'm > looking at larger sizes. Since these will be harder, I've thought of adding > an initialization step where the program tells the IP solver of a reasonably > low-cost guess. This could speed up the process, --certainly it could. If you use some nonrigorous heuristic to find a good order, then you could then use the fact that the optimal order must be at least that good, to help "prune" a subsequent exhaustive search. Lower bounds (i.e. in the other direction) can also be used for pruning (if you have any). If you have an integer program it can sometimes happen that the optimal solution of the linear program (without constraint of having to have integers) happens by luck to be all-integer. In such a case, that proves it is optimal for the integer program too. However, in general integer programming is NP-hard and such luck cannot be guaranteed. Sometimes you can get partial such luck, e.g. you exhaustively try all integer possibilities for the first two variables, and then you get lucky as above about all the remaining variables in each case. That also would find the optimum and yield an optimality proof. If that is what happened for KM, then we could ask: what is the "success rate," i.e. what percentage of the time do his integer programs enjoy these kinds of luck? -- 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
