[EM] Kemeny challenge

[Toby Pereira]

>From what I understand it's independent of Smith-dominated alternatives. So ranking the Smith Set should be sufficient.


From: Jameson Quinn <jameson.quinn at gmail.com>
To: ElectionMethods at votefair.org
Cc: election-methods at electorama.com
Sent: Wednesday, 14 September 2011, 18:21
Subject: Re: [EM] Kemeny challenge





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

----
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/a52935af/attachment-0004.htm>