[EM] Dodgson and Kemeny "done right"?

[Kristofer Munsterhjelm]

fsimmons at pcc.edu wrote:
> A fourth common problem with Dodgson and Kemeny that I failed to
> mention is their common lack of efficient precinct summability.  

Is that true? My implementation of Kemeny uses a variant of integer 
program #3 from "Improved Bounds for Computing Kemeny Rankings", and 
this integer program only needs access to the graph itself to find the 
minimum feedback arc set.

In voting terms, that means that the integer program only needs the 
Condorcet matrix to determine who the winner is. In optimization terms, 
the problem consists of finding the transitive sequence "C_1 beats C_2 
beats ... beats C_n" so that the sum of [C_1 beats C_2] + [C_2 beats 
C_3] + ... + [C_(n-1) beats C_n] is maximized. (Equivalently, one could 
phrase it as minimizing the number of upsets - sum of "C_k beats C_(k-1)".)

Thus, unless I'm wrong, the precinct summability is the same as any 
other Condorcet method, except to the extent that Kemeny is not summable 
because it doesn't give the winners in polytime. However, Kemeny can't 
give the winners in worst case polytime, not even if you have the 
ballots themselves, unless P = NP.