Improved Bounds for Computing Kemeny Rankings

Vincent Conitzer, Andrew Davenport, Jayant Kalagnanam

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.

Subjects: 7.1 Multi-Agent Systems; 15.7 Search

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.