[EM] Fast Condorcet-Kemeny calculation times, clarification of NP-hardness issue

[Jameson Quinn]

Remember that K-Y is Condorcet compliant, and I believe consistent as well
(that is, you can generalize from Condorcet to Smith and even ignore the
effects of the candidates outside the Smith set). So the set of cases where
the problem is easy is at least somewhat well-defined in that sense, and
probably includes (for instance) all the elections I've ever voted in. And
so I believe that Richard's "my algorithm usually gets it right" is not
totally content-free.

But Warren is also very right that, when things start to go wrong, it's
impossible to know whether you have the right answer, the almost-right
answer, or something totally wrong. And if some algorithm said "Jameson's
favorite is probably not the winner, though I can't prove it", I don't
think I'd be very inclined to accept that "probably"on Richard's say-so.
Part of the whole point of democracy is to guarantee that there will be a
clear winner with some legitimacy, since a civil war is usually a lot worse
than the second-best option.

Jameson

2012/3/4 Andrew Myers <andru at cs.cornell.edu>

> On 3/4/12 5:44 PM, Warren Smith wrote:
>
>> On Sun, Mar 4, 2012 at 3:44 PM, Richard Fobes
>> <ElectionMethods at votefair.org>  wrote:
>>
>>> Finally, after reading the articles cited by Warren Smith (listed at the
>>> bottom of this reply) plus some related articles, I can reply to his
>>> insistence that Condorcet-Kemeny calculations take too long to calculate.
>>>  Also, this reply addresses the same claim that appears in Wikipedia
>>> both in
>>> the "Kemeny-Young method" article and in the comparison table within the
>>> Wikipedia "Voting systems" article (in the "polynomial time" column that
>>> Markus Schulze added).
>>>
>>> One source of confusion is that Warren, and perhaps others, regard the
>>> Condorcet-Kemeny problem as a "decision problem" that only has a "yes" or
>>> "no" answer.  This view is suggested by Warren's reference (below and in
>>> other messages) to the problem as being NP-complete, which only applies
>>> to
>>> decision problems.  Although it is possible to formulate a decision
>>> problem
>>> based on one or more specified characteristics of the Condorcet-Kemeny
>>> method, that is a different problem than the Condorcet-Kemeny problem.
>>>
>> --the optimization problem is at least as hard as the decision
>> problem.You are erroneously creating the impression I somehow
>> was unaware of this, or that you somehow have here got some new
>> insight.  Neither is true.
>>
> I might try to say all this in a more friendly way than Warren does, but
> he is 100% right about all the technical issues here. This is basic
> computer science. Nothing fancy and no judgment calls are involved.
>
> -- Andrew
>
>
> ----
> 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/20120304/87b5e32b/attachment-0004.htm>