[EM] Kemeny challenge

[Jameson Quinn]

2011/9/14 Toby Pereira <tdp201b at yahoo.co.uk>

> From what I understand it's independent of Smith-dominated alternatives. So
> ranking the Smith Set should be sufficient.
>
> Really? Then it's computable. Warren, are you really going to say that
you're objecting because of the possibility of a 50-candidate - or for that
matter a 28-candidate - Smith set?

JQ

>   *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<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/72399f93/attachment-0004.htm>