<br><br><div class="gmail_quote">2011/9/14 Richard Fobes <span dir="ltr"><<a href="mailto:ElectionMethods@votefair.org">ElectionMethods@votefair.org</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

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 class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>
Richard Fobes<div><div></div><div class="h5"><br>
<br>
<br>
On 9/12/2011 12:00 PM, Warren Smith wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
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" 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" target="_blank">http://electorama.com/em</a> for list info<br>
</blockquote></div><br>