Inhalt des Dokuments
Complexity of Kemeny's and Kemeny-like Rules
Dominik Peters (University of Oxford)
We consider the problem of finding a consensus ranking given an input preference profile. Kemeny's rule is the most popular proposal for such a procedure. This rule is NP-hard to calculate, and it is known that hardness remains for cases in which there is a fixed even number of voters of at least 4. We show that hardness also holds for a constant odd number of voters (at least 7). The proof proceeds by analysing weighted majority tournaments.
We use the same technique to study the complexity of other rules, including Baldwin's rule and Zwicker's (k)-Kemeny rule. The latter returns a (k)-chotomous output ranking. We discuss several challenging open problems about the complexity of the (k)-Kemeny rule for structured preferences, and from a parameterized perspective.
Back to the research colloquium site.