On 7/22/64 2:59 PM, Warren Smith wrote:
Dodgson, by the way, is not merely NP-hard. It is higher in the polynomial hierarchy and has been shown to be complete for P^NP (parallel access to NP oracles). Probably worse than Kemeny!Dodgson and Kemeny done right (F.W.Simmons) ---------Warren D. Smith, Sept 2011----------------------Simmons claims he had posted something called "Dodgson done right" which gets around the problem that with Dodgson voting it is NP-hard to find the winner, and supposedly Kemeny has a similar fix. I failed to find his post, but reading between the lines am attempting to try to determine what Simmons probably had in mind by reverse engineering, and/or the fact I had similar thoughts of my own a long time back. DODGSON: votes are rank-orderings of the N candidates. Output ordering: the one such that the smallest total candidate motion (distance moved, summed over all candidates on all ballots) is required to convert the input orders into the output order.
-- Andrew
<<attachment: andru.vcf>>
---- Election-Methods mailing list - see http://electorama.com/em for list info
