<html><body><div style="color:#000; background-color:#fff; font-family:times new roman, new york, times, serif;font-size:12pt"><div style="RIGHT: auto"><SPAN style="RIGHT: auto">From what I understand it's independent of Smith-dominated alternatives. So ranking the Smith Set should be sufficient.<VAR id=yui-ie-cursor></VAR><BR style="RIGHT: auto" class=yui-cursor></SPAN></div>
<div><BR></div>
<DIV style="FONT-FAMILY: times new roman, new york, times, serif; FONT-SIZE: 12pt">
<DIV style="FONT-FAMILY: times new roman, new york, times, serif; FONT-SIZE: 12pt"><FONT size=2 face=Arial>
<DIV style="BORDER-BOTTOM: #ccc 1px solid; BORDER-LEFT: #ccc 1px solid; PADDING-BOTTOM: 0px; LINE-HEIGHT: 0; MARGIN: 5px 0px; PADDING-LEFT: 0px; PADDING-RIGHT: 0px; HEIGHT: 0px; FONT-SIZE: 0px; BORDER-TOP: #ccc 1px solid; BORDER-RIGHT: #ccc 1px solid; PADDING-TOP: 0px" class=hr readonly="true" contenteditable="false"></DIV><B><SPAN style="FONT-WEIGHT: bold">From:</SPAN></B> Jameson Quinn <jameson.quinn@gmail.com><BR><B><SPAN style="FONT-WEIGHT: bold">To:</SPAN></B> ElectionMethods@votefair.org<BR><B><SPAN style="FONT-WEIGHT: bold">Cc:</SPAN></B> election-methods@electorama.com<BR><B><SPAN style="FONT-WEIGHT: bold">Sent:</SPAN></B> Wednesday, 14 September 2011, 18:21<BR><B><SPAN style="FONT-WEIGHT: bold">Subject:</SPAN></B> Re: [EM] Kemeny challenge<BR></FONT><BR>
<DIV id=yiv1979285422><BR><BR>
<DIV class=yiv1979285422gmail_quote>2011/9/14 Richard Fobes <SPAN dir=ltr><<A href="mailto:ElectionMethods@votefair.org" rel=nofollow target=_blank ymailto="mailto:ElectionMethods@votefair.org">ElectionMethods@votefair.org</A>></SPAN><BR>
<BLOCKQUOTE style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class=yiv1979285422gmail_quote>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.<BR><BR>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.<BR><BR>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.<BR><BR>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.<BR></BLOCKQUOTE>
<DIV><BR></DIV>
<DIV>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?</DIV>
<DIV><BR></DIV>
<DIV>JQ </DIV>
<BLOCKQUOTE style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class=yiv1979285422gmail_quote><BR>Richard Fobes
<DIV>
<DIV></DIV>
<DIV class=yiv1979285422h5><BR><BR><BR>On 9/12/2011 12:00 PM, Warren Smith wrote:<BR>
<BLOCKQUOTE style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class=yiv1979285422gmail_quote>KEMENY CHALLENGE<BR>=================<BR><BR>Here is an attempt by me to intentionally create small elections for<BR>which it is difficult to determine the Kemeny winner.<BR><BR>Consider this pairwise matrix:<BR> <A href="http://www.rangevoting.org/Tourn27.html" rel=nofollow target=_blank>http://www.RangeVoting.org/<U></U>Tourn27.html</A><BR>and replace all the +1s by random numbers in the interval<BR> [A, B]<BR>and all the -1s by ditto but negated, to get the pairwise margins matrix<BR>for a 27-candidate election.<BR>Here B>A>0 are two parameters chosen by the Devil to try to cause<BR>these problems to be hardest [I'd originally suggested A=9million<BR>B=10million, but maybe some other choice like A=0 and B=10billion<BR>would tend to make it harder]. Also of course randomly permute the
27<BR>candidate-names in a way unknown to the solver, before giving the<BR>problem to the solver [equivalently permute both the rows and columns<BR>of the 27x27 matrix by one random permutation].<BR><BR>THE CHALLENGE: Find the Kemeny winner or order... can anybody do<BR>either reliably for 27-candidate elections of this class, or is this<BR>usually beyond humankind's abilities?<BR><BR><BR><BR></BLOCKQUOTE><BR><BR></DIV></DIV>----<BR>Election-Methods mailing list - see <A href="http://electorama.com/em" rel=nofollow target=_blank>http://electorama.com/em</A> for list info<BR></BLOCKQUOTE></DIV><BR></DIV><BR>----<BR>Election-Methods mailing list - see <A href="http://electorama.com/em" target=_blank>http://electorama.com/em</A> for list info<BR><BR><BR></DIV></DIV></div></body></html>