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 ABCD (for four candidates) and n/2 have ABDC to get a
pairwise count, for AB, 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 AWXQRDF..., 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.)
Election-Methods mailing list - see http://electorama.com/em for list info
