The Complexity of Kemeny Aggregation with Three Rankings
2026-07-30 • Computer Science and Game Theory
Computer Science and Game TheoryComputational ComplexityDiscrete Mathematics
AI summaryⓘ
The authors study the Kemeny rule, which combines multiple rankings into one by minimizing disagreement measured by Kendall-tau distance. They show that calculating the Kemeny score is computationally hard (NP-complete) even with just three rankings split in a specific way. They also classify related problems (like finding winners or recognizing optimal aggregates) into distinct complexity classes, providing a full picture depending on parameters like support size. Their results extend to related ranking methods and include constructions proving hardness in special symmetric cases.
Kemeny ruleKendall-tau distanceNP-completemajority tournamentcomplexity classesSlater orderpermutation medianmaximum likelihoodMallows model
Authors
Péter Madarasi
Abstract
The Kemeny rule aggregates rankings by minimizing their total Kendall-tau distance from an aggregate order. We prove that Kemeny Score is NP-complete for exactly three unweighted rankings, even when every candidate pair is split $2$-to-$1$. On the same profiles, the winner, unique-winner, and possible- and necessary-precedence problems are $Θ_2^p$-complete, while recognizing a Kemeny-optimal or uniquely Kemeny-optimal aggregate is coNP-complete. The hard instances induce tournaments of majority dimension exactly $3$. The reduction also determines the exact maximum-cut value from the optimal Kemeny score and recovers a maximum cut from any Kemeny-optimal aggregate. For every fixed $q\geq3$ and $\lceil q/2\rceil\leq s\leq q$, minimum pairwise support $s$ yields a sharp dichotomy: the score problem is NP-complete, the winner and precedence problems are $Θ_2^p$-complete, and the recognition problems are coNP-complete when $3s\leq2q$; for $3s>2q$, the majority tournament is transitive and its unique topological order is the unique Kemeny-optimal aggregate. Exact support $s$ suffices in the hard case when $s>q/2$, and supports in ${s,s+1}$ suffice when $s=q/2$. These results give complete fixed-profile-size classifications and transfer to Slater orders, permutation medians, and maximum-likelihood central rankings in the Mallows model. Finally, a six-copy construction proves NP-completeness of both Kemeny Score and Kendall--Tau Center for three pairwise-equidistant rankings that still split every pair $2$-to-$1$. For $N$ output candidates, their common distance is $\frac23\binom N2$, the largest possible for an equidistant triple. The construction gives affine formulas for both optimal values, characterizes all Kemeny-optimal output orders, and shows that the output has a unique Kemeny-optimal order and a unique center exactly when the input has a unique Kemeny-optimal order.