[EM] Kemeny challenge

[Richard Fobes]

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.

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
> 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?
>
>
>