2012/3/31, Kristofer Munsterhjelm <[email protected]>: > 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 ---- Election-Methods mailing list - see http://electorama.com/em for list info
