Complexity of Kemeny ranking for three voters
Follow the latest progress by email.
Given exactly three unweighted complete voter rankings, how hard is it to find a consensus ranking of minimum total Kendall distance, or decide whether a given Kemeny-score bound is achievable?
Why it matters and what counts as progress
Why it matters: The three-voter case lies between tractable one- and two-voter problems and earlier hardness with more voters.
What counts as progress: A polynomial-time algorithm or NP-completeness proof for exactly three complete rankings, preserving unweighted voters and the score decision model.
How the problem developed
- 1989 · Hardness result [1]
J. J. Bartholdi III, C. A. Tovey and M. A. Trick Established NP-hardness for Kemeny-style rank aggregation when the voter count is unrestricted.
- 2001 · Fixed-voter hardness [2]
Cynthia Dwork, Ravi Kumar, Moni Naor and D. Sivakumar Showed NP-completeness with four voters and asked whether three voters suffice.
- 28 Jul 2026 · Resolution [3]
Dominik Peters Proved that Kemeny score is NP-complete for exactly three unweighted rankings, via a reduction from SIMPLE MAX CUT.
AI contribution
Kemeny Rank Aggregation is NP-Hard for Three Voters
KEMENY SCORE is NP-complete for exactly three unweighted complete rankings. Peters reduces from SIMPLE MAX CUT with long even edges to a unit-margin majority tournament realizable by three voters.
Sources
- Bartholdi, Tovey and Trick · The computational difficulty of manipulating an election (1989)
- Dwork, Kumar, Naor and Sivakumar · Rank aggregation methods for the Web (2001)
- Dominik Peters · Kemeny rank aggregation is NP-hard for three voters (2026)
- Peters’s three-voter Kemeny proof
- Certified Lean reduction
- Madarasi’s independent proof
Website timeline
Publication dates and editorial changes.