[EM] Dodgson and Kemeny "done right"?

[Andrew Myers]

On 7/22/64 2:59 PM, Warren Smith wrote:
> 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.
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!

-- Andrew
-------------- next part --------------
A non-text attachment was scrubbed...
Name: andru.vcf
Type: text/x-vcard
Size: 267 bytes
Desc: not available
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20110914/85ac0324/attachment-0004.vcf>