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.
----
Election-Methods mailing list - see http://electorama.com/em for list info
