Kemeny rank aggregation for three voters

Dwork et al. (2001) established hardness for fixed even numbers of voters with $n \ge 4$ and asked about exactly three. The three-voter case was subsequently reported as $\mathrm{NP}$-complete via a reduction from $\mathrm{MAX\text{-}CUT}$, so computing an optimal aggregate is $\mathrm{NP}$-hard.

Known results

• Dwork et al., 2001: hardness for every fixed even $n \ge 4$.
• The cases $n \in \\{1,2\\}$ are easy.

July 2026 three-voter hardness result

Dominik Peters’s preprint reports $\mathrm{NP}$-completeness for Kemeny Score with exactly three complete rankings. An independent manuscript reports the same result, even under a strong pairwise restriction, and gives further complexity consequences. The first paper says the reduction was found by GPT 5.6 Sol Ultra and partly simplified with Claude Fable 5.

Current status (as of July 2026): Two independent arXiv manuscripts report a proof that the exactly-three-voter decision problem is $\mathrm{NP}$-complete, hence the optimization problem is $\mathrm{NP}$-hard; no part of the stated problem remains open.