[EM] Dodgson and Kemeny "done right"?

[fsimmons at pcc.edu]

You're right, I forgot that Kemeny only needed the pairwise matrix.  And according to Warren 
Dodgson is summable. I don't see how.

----- Original Message -----
From: Kristofer Munsterhjelm 
Date: Thursday, September 15, 2011 12:14 pm
Subject: Re: [EM] Dodgson and Kemeny "done right"?
To: fsimmons at pcc.edu
Cc: Warren Smith , election-methods 

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