Improved bounds for computing kemeny rankings


Journal Article

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 ( All rights reserved.

Duke Authors

Cited Authors

  • Conitzer, V; Davenport, A; Kalagitanam, J

Published Date

  • November 13, 2006

Published In

  • Proceedings of the National Conference on Artificial Intelligence

Volume / Issue

  • 1 /

Start / End Page

  • 620 - 626

Citation Source

  • Scopus