[EM] Dodgson and Kemeny "done right"?

[fsimmons at pcc.edu]

"Borda done right" is detailed here:

http://lists.electorama.com/pipermail/election-methods-electorama.com/2011-July/028043.html

"Dodgson done right" was sketched here:

http://lists.electorama.com/pipermail/election-methods-electorama.com/2011-July/027888.html

The version of Dodgson I was addressing does not attempt to output a social order like Kemeny does.  (I agree with your treatment of Kemeny below.)

The usual version of Dodgson modifies the ballots minimally to create a pairwise beats-all candidate without saying who came in second, etc.

My versions of "{ranked method} done right" also include the clone free conversion of ordinal ballots to cardinal ballots, as detailed most thoroughly in the first link above. 

A fourth common problem with Dodgson and Kemeny that I failed to mention is their common lack of efficient precinct summability.  In my "done right" versions this is taken care of by "faction 
amalgamation" which is easy to do with cardinal ballots, but requires two "rounds" in the case of ordinal ballots; the first round sums all of the first place preferences to make this information available for 
the clone free conversion of ordinal ballots to cardinal ballots.  Then the second round can also go forward summably by making use of the cardinalized ballots.

In the case of Dodgson, once the factions have been amalgamated, if there is no pairwise beats-all candidate, all interested parties can submit modifications of these faction scores.  The minimal 
modification that yields a beats-all candidate determines the winner.





----- Original Message -----
From: Warren Smith 
Date: Tuesday, September 13, 2011 5:29 pm
Subject: Dodgson and Kemeny "done right"?
To: electionscience at googlegroups.com, election-methods , fsimmons at pcc.edu

> 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)
>