[EM] NP hardness cites for Kemeny

[Richard Fobes]

Thank you Warren!  I will study these articles.

I think I know what the misunderstanding is, but I want to be sure 
before I formally reply.

I expect the reply to take at least a month because of all the projects 
I'm juggling.

One such project is helping to gain further attention for the 
"Declaration of Election-Method Reform Advocates".  I hope to announce 
something about that soon.

Richard Fobes


On 12/24/2011 10:25 AM, Warren Smith wrote:
> Rank Aggregation Revisited
> Cynthia Dwork, Ravi Kumar, Moni Naor, D. Sivakumar
> http://www.eecs.harvard.edu/~michaelm/CS222/rank2.pdf
>
> J. J. Bartholdi, C. A. Tovey, and M. A. Trick: Voting schemes for
> which it can be difficult to tell who won the
> election, Social Choice and Welfare, 6(2):157–165, 1989.
>
> A Computational Study of the Kemeny Rule for Preference Aggregation
> Andrew Davenport and Jayant Kalagnanam
> http://www.aaai.org/Papers/AAAI/2004/AAAI04-110.pdf
>
> Cohen, W.; Schapire, R.; and Singer, Y. 1999. Learning to order
> things. Journal of Artificial Intelligence Research 10:213-270.
> http://www.jair.org/media/587/live-587-1788-jair.ps
>
> etc
> and it should be noted that it is NP-complete to find an ordering better than X,
> and also NP-hard merely to find the Kemeny winner...
>