[EM] Kemeny update

[Jameson Quinn]

2011/9/24 Kristofer Munsterhjelm <km_elmet at lavabit.com>

> Warren Smith wrote:
>
>> To reiterate and/or answer some questions:
>>
>> 1. there is no way to find the Kemeny winner that is much faster than
>> finding the full Kemeny ordering. More precisely, both are NP-complete
>> tasks
>> so there is no poly-time algorithm for either unless P=NP.
>>
>> 2. Even if some benificent God helpfully informs you of the name of
>> the Kemeny winner,
>> or the full Kemeny ordering, then there is no easy way for you
>> to confirm or deny that claim.   No matter how much supporting information
>> God provides to you (if it is only a polynomially-bounded number of
>> bits) -- such
>> as a proof -- there remains no way to confirm or deny either claim that
>> runs in
>> polynomial time, unless NP=coNP.  In other words, no short proofs exist.
>>
>> 3. It IS possible to find both the Kemeny
>> ordering and Kemeny winner, in any election, if you are willing to
>> devote enough compute time to it.  But the amount of time needed will
>> exceed any polynomial in the #candidates.  Every currently known
>> algorithm in the papers I cited fails for easy-to-generate and fairly
>> natural
>> 40-candidate elections, no matter how much time they devote to it
>> within the limits of their finances.
>>
>> 4. The hardest elections have got Smith set = the full set of candidates.
>> This is asymptotically not a great restriction since random elections have
>> Smith set = full set, with probability -->1 in the limit as
>> #candidates --> infinity.
>>
>
> Is Kemeny independent of Smith-dominated alternatives? Toby said he thought
> he was. If it is, then Kemeny is feasible for practical elections because
> you can just restrict it to the Smith set (and the Smith set won't be very
> large in practice). That is, of course, unless the existence of advanced
> voting methods will make the public vote in ways that will lead to a greater
> Smith set (e.g. candidates who otherwise didn't want to split the vote now
> feel bold enough to show up). Still, even so, I can't imagine there would be
> a 27-member Smith set.
>
> Warren, I would like to see your response to this issue.

Jameson
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110924/0720e338/attachment-0004.htm>