[EM] Kemeny challenge

[Jameson Quinn]

2011/9/14 Richard Fobes <ElectionMethods at votefair.org>

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110914/3730c27e/attachment-0004.htm>