direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

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.


Dominik Peters
TEL 512

Back to the research colloquium site.

To top

Zusatzinformationen / Extras