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

[Kristofer Munsterhjelm]

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.

Now, if you're saying that VoteFair isn't Kemeny but it's close enough 
for all practical purposes, then that's another matter. Or if VoteFair, 
like my integer linear programming implementation, is exponential time 
but the constants mean the actual runtime doesn't become ugly until you 
have >20-30 candidates, then that would also work.

> Speaking of which, I'm still looking forward to Warren supplying a
> 40-candidate or 50-candidate case (as ballot preferences, not pairwise
> counts because they might not correlate with a real ranking scenario)
> that he thinks would take a long time to calculate, and I'll be happy to
> measure the calculation time. And I'll share the sorted pairwise counts
> in matrix form so that anyone can visually verify that the full ranking
> sequence is correct, and that if there is a deserving winner then that
> candidate is correctly ranked in first place.

You can turn any pairwise matrix into a set of preferences. If every 
pairwise count is even and positive, then you just make n/2 people 
having A>B>C>D (for four candidates) and n/2 have A>B>D>C to get a 
pairwise count, for A>B, of n. I think you can do similar things for the 
more general case, and if you have equal-rank and truncation, it becomes 
easier still.

The other problem is that I'm not aware of any trapdoor function for 
Kemeny. That is, while Warren can make a 50-candidate case which takes a 
very long time for say, my ILP implementation, there's no way to tell, 
if you answer "oh, the ordering is A>W>X>Q>R>D>F...", whether that it is 
actually the optimum. If we had a trapdoor function, that'd let us 
generate a hard Kemeny instance where the optimal ordering is already 
known -- and then you could check if you got the same thing out of VoteFair.

So if VoteFair is a good approximation, it might give something with a 
good Kemeny score (just as Ranked Pairs would, or Schulze), but it 
wouldn't give the optimum - and we'd have no way of knowing, short of 
running the hard instance through Kemeny itself and comparing the result.

(The upshot of which, I guess, is that I really should get off my behind 
and do some Monte Carlo to see if I can find a ballot set where VoteFair 
gives a different winner than something I know finds the Kemeny optimum. 
But I've been busy.)