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
