Formally verified AI-led

Kemeny rank aggregation shown NP-hard for three voters

Computing a Kemeny-optimal aggregate ranking is NP-hard when the input is exactly three complete rankings, closing the minimal open case left by hardness results for even voter counts.

Lab: Independent
Model: GPT-5.6 Sol Ultra, Claude Fable 5
Field: Computer science
Date: 2026-07-28
Human collaborators: Dominik Peters
Problem posed: 2001 · open 25 yrs

Sources

Original work

arXivKemeny Rank Aggregation is NP-Hard for Three Voters↗

Independent commentary

arXivMadarasi, The complexity of Kemeny aggregation with three rankings↗

What was found

Kemeny aggregation asks for the ranking minimizing total disagreement with a set of input rankings. Hardness was known for every even number of voters $n$ at least 4, while $n = 2$ is solvable in polynomial time, leaving three voters as the minimal open case since 2001. GPT-5.6 Sol Ultra found the reduction from MAX CUT; Claude Fable 5 helped simplify parts of it. Combined with the earlier results, every fixed number of voters $n$ at least 3 is now known to be hard. The reduction is Lean-checked alongside an author-written preprint.

Novelty check

The complexity of Kemeny aggregation for three voters is a specifically tracked open case in the computational social choice literature, following Dwork, Kumar, Naor and Sivakumar's 2001 work establishing hardness for four voters and the subsequent extension to all even counts. The odd cases, and three in particular, were repeatedly noted as open. No prior hardness proof for exactly three voters appears. Péter Madarasi posted an independent proof of the same hardness result on 2026-07-30, two days after this one.

Caveats and known objections

Not peer-reviewed. The Lean check covers the reduction; it is author-produced and had no independent audit at announcement. Autonomy graded ai-led rather than autonomous: the model found the reduction, but the human author posed the problem, reviewed the argument and wrote the paper.

Independent checks

Péter Madarasi (independent proof): Proved independently, two days later, that Kemeny Score is NP-complete for exactly three unweighted rankings, even when every candidate pair is split 2-to-1, which corroborates the result by a separate argument. · link ↗

The open problem

MathDBKemeny rank aggregation for three voters

315674

Nothing mechanically. It records what a problem says, what is known about it, and the standing of any claimed solution.

Also recorded at

vibemathedKemeny Rank Aggregation for Three Voters

kemeny-three-voters

Nothing mechanically. It is a parallel listing of the same result, carrying its own verification label rather than an independent check.

Disagree with these grades?

Bring a citation: a grade moves on evidence, not on argument.

Challenge this grade Submit a check

Or on GitHub: submit a check challenge the grade send a correction or send a pull request

History of this entry

2026-09-24CheckedRecorded Péter Madarasi's independent proof that Kemeny aggregation is NP-complete for three rankings, posted two days after this result. source ↗
2026-08-19CorrectedRecorded the vibemathed and MathDB records for this result as registrations. The vibemathed link it replaces pointed at that site's home page rather than at this result, and was classified as commentary, which a registry listing is not.
2026-08-11AddedEntered the registry graded Formally verified and AI-led.

Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.

Graded formally verified for verification and ai-led for autonomy. What these mean.

Cite this entry

Plain text

whataifound.org. (2026). Kemeny rank aggregation shown NP-hard for three voters. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2026-07-28-kemeny-three-voters

BibTeX

@misc{whataifound-independent-2026-voters,
  title        = {Kemeny rank aggregation shown NP-hard for three voters},
  author       = {{whataifound.org}},
  year         = {2026},
  howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
  note         = {Result by Independent. Verification: Formally verified. Autonomy: AI-led.},
  url          = {https://whataifound.org/finding/2026-07-28-kemeny-three-voters}
}

Related findings

Formally verifiedNear-quadratic lower bound for derivative-free convex optimizationIndependent · 2026-07-14 ClaimedExponential lower bound for the bit pigeonhole principle in unrestricted resolution over paritiesIndependent · 2026-09-15 Author verifiedA quantum oracle separating QMA(2) from QMAMIT / Columbia / University of Washington · 2026-09-02

lean complexity-theory computational-social-choice

← All computer science findings in the registry