[EM] Kemeny Condorcet method. Apparently not a good choice for those of us who want to know who won in our lifetimes.

[Kristofer Munsterhjelm]

Warren Smith wrote:
> I have on this thread at the CES
>    http://groups.google.com/group/electionscience/t/b135bdc214c39ffa
> reviewed some known theoretical and empirical facts about the Kemeny Condorcet
> voting method.
> 
> In particular, it appears based on my literature review that humanity,
> using 2006-2011 era hardware and software, is currently unable to
> reliably determine the Kemeny winner from the votes in 5-voter,
> 50-candidate test elections generated by certain reasonable kinds of
> random vote-generating processes.
> 
> The Wikipedia article
>   http://en.wikipedia.org/wiki/Kemeny%E2%80%93Young_method
> is somewhat misleadingly worded on this point.   It makes it sound
> like no problem,
> but actually the very paper they cite says quite the opposite.
> 
> Further comments will be welcome.

Well, I can only speak from experience, but I've implemented the 
Kemeny-Young method in quadelect as an integer program, and the vast 
majority of the time (more than 90%), the LP linearization gives an 
optimal result.

NP-complete problems usually have phase transitions, i.e. there are some 
regions of the problem that are easy and some that are very hard. It 
seems that at least for the ballots generated by my opinion-space model, 
the Kemeny instances tend to end up on the easy side.

I could be wrong, of course, so any independent verification would be 
welcome.