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?
----
Election-Methods mailing list - see http://electorama.com/em for list info
