A Computational Study of the Kemeny Rule for Preference Aggregation

We consider from a computational perspective the problem of how to aggregate the ranking preferences of a number of alternatives by a number of different voters into a single consensus ranking, following the majority voting rule. Social welfare functions for aggregating preferences in this way have been widely studied since the time of Condorcet (1785). One drawback of majority voting procedures when three or more alternatives are being ranked is the presence of cycles in the majority preference relation. The Kemeny order is a social welfare function which has been designed to tackle the presence of such cycles. However computing a Kemeny order is known to be NP-hard. We develop a greedy heuristic and an exact branch and bound procedure for computing Kemeny orders. We present results of a computational study on these procedures.

By: Andrew Davenport, Jayant Kalagnanam

Published in: Proceedings of the Nineteenth National Conference on Artificial Intelligence and Sixteenth Innovative Applications of Artificial Intelligence Conference. Menlo Park, CA, , AAAI Press. , p.697-702 in 2004

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to reports@us.ibm.com .