2011/9/14 Toby Pereira <[email protected]> > From what I understand it's independent of Smith-dominated alternatives. So > ranking the Smith Set should be sufficient. > > Really? Then it's computable. Warren, are you really going to say that you're objecting because of the possibility of a 50-candidate - or for that matter a 28-candidate - Smith set?
JQ > *From:* Jameson Quinn <[email protected]> > *To:* [email protected] > *Cc:* [email protected] > *Sent:* Wednesday, 14 September 2011, 18:21 > *Subject:* Re: [EM] Kemeny challenge > > > > 2011/9/14 Richard Fobes <[email protected]> > > Large pairwise-count numbers do not increase the likelihood of a longer > computation time. They just test the processor's integer limit, or the > language-specified integer limit, or the efficiency of big-integer > algorithms. > > Based on lots and lots of calculations using lots and lots of real data, > I've learned that just a few ballots (which corresponds to small > pairwise-count numbers) are more likely to increase the computation time. > This makes sense when you stop and think about it. > > If you come up with a ballot-based version of this challenge (rather than > this pairwise-count version), I'd like to try it out. > > Regardless of the results, remember that real elections only require > identifying the winner, whereas here we are discussing the computation time > for producing a full ranking. > > > Is there any way to prove that X is the winner, if they aren't the CW and > you don't have the full ranking? > > JQ > > > Richard Fobes > > > > On 9/12/2011 12:00 PM, Warren Smith wrote: > > KEMENY CHALLENGE > ================= > > Here is an attempt by me to intentionally create small elections for > which it is difficult to determine the Kemeny winner. > > Consider this pairwise matrix: > > http://www.RangeVoting.org/**Tourn27.html<http://www.rangevoting.org/Tourn27.html> > and replace all the +1s by random numbers in the interval > [A, B] > and all the -1s by ditto but negated, to get the pairwise margins matrix > for a 27-candidate election. > Here B>A>0 are two parameters chosen by the Devil to try to cause > these problems to be hardest [I'd originally suggested A=9million > B=10million, but maybe some other choice like A=0 and B=10billion > would tend to make it harder]. Also of course randomly permute the 27 > candidate-names in a way unknown to the solver, before giving the > problem to the solver [equivalently permute both the rows and columns > of the 27x27 matrix by one random permutation]. > > THE CHALLENGE: Find the Kemeny winner or order... can anybody do > either reliably for 27-candidate elections of this class, or is this > usually beyond humankind's abilities? > > > > > > ---- > Election-Methods mailing list - see http://electorama.com/em for list info > > > > ---- > Election-Methods mailing list - see http://electorama.com/em for list info > > >
---- Election-Methods mailing list - see http://electorama.com/em for list info
