[EM] Fast Condorcet-Kemeny calculation times, clarification of NP-hardness issue
km_elmet at lavabit.com
Sat Mar 31 01:23:32 PDT 2012
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
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.)
More information about the Election-Methods