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

[Jameson Quinn]

2012/3/31, Kristofer Munsterhjelm <km_elmet at lavabit.com>:
> On 03/31/2012 08:24 AM, Richard Fobes wrote:
>
>> So, wrapping up this explanation:
>>
>> If the Condorcet-Kemeny problem were in the field of encryption, then of
>> course only an exact solution would be relevant.
>>
>> But the Condorcet-Kemeny problem is an optimization problem -- or it can
>> be regarded as a sorting problem -- where the goal is to check various
>> sequences and find the one (or ones in the case of ties) that move the
>> biggest pairwise counts into the upper-right triangular area of a
>> matrix, while moving the smallest pairwise counts into the lower-left
>> triangular area.
>
> I think the argument against that can be quite easily stated like this:
>
> - If there exists an election profile where exhaustive Kemeny gives a
> different result (winner) than VoteFair, then VoteFair isn't Kemeny.
> - On the other hand, if there exists no such profile, then VoteFair
> solves an NP-complete problem in the cryptographic sense.
>
> Hence, either VoteFair isn't Kemeny or it proves that P = NP, which
> would be huge.

Clearly, we must assume the former. In that case, we have two
possibilities for implications.

- VoteFair ≠ Kemeny with some unknown random probability p. In that
case, no matter how low p is, we can basically never trust VoteFair to
be Kemeny.
- There is some significant, knowable portion of the domain where
VoteFair = Kemeny. For instance, VoteFair = Kemeny if the Smith set
has fewer than 10 members or something like that. In that case, we
could consider a Smith set of over 10 members to be comparable to a
tie under a normal polytime voting system, and accept that we'll get
essentially random results in that case.

Since K-Y is independent of Smith-dominated alternatives (ISDA), I
think the latter is more likely to be the case. So, Richard: instead
of making verbal arguments about traveling salesman cases or visual
inspection of matrices, your job is to give a rigorous proof that
VoteFair = Kemeny for a Smith set of up to N candidates, where N>4
(the largest suspected Smith set from real-world election/polling
data).

Jameson