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. KEMENY: votes are rank-orderings of the N candidates. Output ordering: the one with the fewest total number of disagreements with the input orders about candidate-pairs (summed over all candidate-pairs on all ballots) ATTEMPT TO REPAIR/REDEFINE: Make the ballots instead be range-voting style RATINGS ballots. Output now also is a ratings-style "ballot." For ratingified Dodgson, output is a ballot with minimum total candidate motion required to convert all the input ballots into the output ballot (total distance traveled along the ratings axis, summed over all candidates and all ballots). For ratingified Kemeny, output is the ballot with minimum total 2-candidate travel distance summed over all candidate-pairs on all input ballots, where that candidate pair has to travel along the ratings axis so instead of their original directed separation, they now have the same separation (in same direction) as the output ballot. THEOREM: Ratingified Dodgson is no longer NP-hard to find, in fact it is easy, in fact it is just this: each candidate's output score is the median of his input scores. PROOF: Easy. REMARK: If instead we were minimizing the sum of the SQUARES of the travel distances, then ratingified Dodgson would just become average-based range voting, the output score is the mean of that candidate's input scores. THEOREM: Ratingified Kemeny is by this definition the same thing as ratingified Dodgson. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step) ---- Election-Methods mailing list - see http://electorama.com/em for list info
