Skip to main content

Improved bounds for computing kemeny rankings

Publication ,  Journal Article
Conitzer, V; Davenport, A; Kalagitanam, J
Published in: Proceedings of the National Conference on Artificial Intelligence
November 13, 2006

Voting (or rank aggregation) is a general method for aggregating the preferences of multiple agents. One voting rule of particular interest is the Kemeny rule, which minimizes the number of cases where the final ranking disagrees with a vote on the order of two alternatives. Unfortunately, Kemeny rankings are NP-hard to compute. Recent work on computing Kemeny rankings has focused on producing good bounds to use in search-based methods. In this paper, we extend on this work by providing various improved bounding techniques. Some of these are based on cycles in the pairwise majority graph, others are based on linear programs. We completely characterize the relative strength of all of these bounds and provide some experimental results. Copyright © 2006, American Association for Artificial Intelligence (www.aaai.org). All rights reserved.

Duke Scholars

Published In

Proceedings of the National Conference on Artificial Intelligence

Publication Date

November 13, 2006

Volume

1

Start / End Page

620 / 626
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Conitzer, V., Davenport, A., & Kalagitanam, J. (2006). Improved bounds for computing kemeny rankings. Proceedings of the National Conference on Artificial Intelligence, 1, 620–626.
Conitzer, V., A. Davenport, and J. Kalagitanam. “Improved bounds for computing kemeny rankings.” Proceedings of the National Conference on Artificial Intelligence 1 (November 13, 2006): 620–26.
Conitzer V, Davenport A, Kalagitanam J. Improved bounds for computing kemeny rankings. Proceedings of the National Conference on Artificial Intelligence. 2006 Nov 13;1:620–6.
Conitzer, V., et al. “Improved bounds for computing kemeny rankings.” Proceedings of the National Conference on Artificial Intelligence, vol. 1, Nov. 2006, pp. 620–26.
Conitzer V, Davenport A, Kalagitanam J. Improved bounds for computing kemeny rankings. Proceedings of the National Conference on Artificial Intelligence. 2006 Nov 13;1:620–626.

Published In

Proceedings of the National Conference on Artificial Intelligence

Publication Date

November 13, 2006

Volume

1

Start / End Page

620 / 626