Computer science · Combinatorics · Question
Kemeny rank aggregation for three voters
Is finding a best consensus ranking computationally hard even for exactly three voters?
ProvedOpenMath assessment · Oct 14, 2026
- Literature: 1 preprint
- Formal: None linked
- Computation: 1 explicit witness
- Review: Not yet reviewed
Frontier 1 report →
Earlier version 5 of this page. View current →
Overview
Known
The cited preprint establishes threshold decision NP-completeness for exactly three complete ballots, and hence optimization NP-hardness. This is a worst-case complexity result, not a proof that P differs from NP.
Related open questions
Review the reduction and its precise score translation; practical algorithms, approximation and structural restrictions remain distinct research directions.
Latest
Exactly three complete ballots; alternatives vary in number. Compare decision and optimization without conflating their classifications.
Precise statement · Exact conventions and hypotheses
All three voters supply strict complete linear orders on the same finite set A of alternatives; |A| is unbounded. A consensus order minimizes the sum of pairwise disagreements, equivalently total Kendall-tau distance, to the three ballots. The decision problem adds an integer score threshold; computing an optimum is a separate optimization task.
Definitions
- Kendall-tau distance
- Count each pair of alternatives once when the two orders disagree on which comes first. This equals the minimum number of adjacent swaps transforming one order into the other.
- Majority margin
- For alternatives a,b, n_ab counts voters placing a ahead of b and m_ab = n_ab − n_ba. With three voters every margin is odd: ±1 or ±3, so the majority graph is a tournament.
Question paraphrased by OpenMath. Original wording is available in the sources.
Landscape
Figures and explorable examples. Selecting a statement opens its exact wording.
Visual setup
Hardness by number of voters
With two ballots either ballot is an optimal consensus. With three it is already NP-complete, and every fixed number from four up is NP-hard.
Reading boundary. Hardness is about worst-case instances. Small or structured profiles, like the three-ballot example, can be easy to solve.
Voters r
Finding a best consensus
Voters r 2: Easy: solved directly.Either ballot● Proved under stated assumptions
Voters r 3: Hard: NP-complete or NP-hard.NP-complete● Proved under stated assumptions
Voters r 4+: Hard: NP-complete or NP-hard.NP-hard● Proved under stated assumptions
✓ Easy: solved directly✗ Hard: NP-complete or NP-hardEach cell links to its statement and status
Visual setup
Three ballots, one consensus
An illustrative three-alternative profile: the displayed consensus has total Kendall-tau score 4.
Reading boundary. A small solvable profile is an explanation of the score, not the large reduction establishing worst-case hardness.
Kendall-tau distance counts the pairs two orders rank differently; A > B > C disagrees with ballots 2 and 3 on two pairs each.
Three ballots with a cyclic majority
Compare consensus orders
- Voter 1: A > B > C
- Voter 2: B > C > A
- Voter 3: C > A > B
Distances to the ballots: 0 + 2 + 2 = 4. This order is optimal for this example.
3 of 6 orders attain the minimum 4.
This finite comparison illustrates the objective; it does not verify the general hardness proof.
Results
The question 2
- ProvedDecision NP-completeness for three complete ballotsPeters 2026
KT counts unordered pairs whose relative orders disagree.
Theorem · Primary formulation
ProvedPeters 2026Decision NP-completeness for three complete ballots
Given exactly three strict complete linear orders π₁, π₂, π₃ on a finite set A and an integer B, deciding whether there exists an order π with is NP-complete.Assumptions
- KT counts unordered pairs whose relative orders disagree. The paper’s majority-margin threshold b is translated by the computable profile constant ∑{a,b} min(n_ab,n_ba).
- Input
- Three strict complete ballots plus integer B
- Output
- Yes/no: is a total score at most B achievable?
In this problem
KT counts unordered pairs whose relative orders disagree. The paper’s majority-margin threshold b is translated by the computable profile constant ∑{a,b} min(n_ab,n_ba).
Proof outline
From a cut threshold to a ranking threshold
Polynomial-time reduction and explicit three-ballot realization
The construction turns a restricted SIMPLE MAX CUT instance into a tournament with unit margins, then realizes that tournament by three ballots. The forward and reverse directions relate cut size to disagreement cost; a proposed ranking’s score is polynomial-time checkable.
A tiny ballot example explains the objective but does not establish the hardness reduction. The paper’s scores differ by an explicitly computable constant.
Proved: Three-voter decision NP-completeness proved in the preprint ↗ · source dated Jul 28, 2026 · observed Oct 14, 2026. Strict complete ballots, unbounded number of alternatives, integer score threshold.
Independent mathematical assessment of an argument remains separate from the statement’s attributed status.
Sources
- ProvedOptimization NP-hardness for three votersPeters 2026
This is a function/optimization task; NP-completeness is stated for the threshold decision language.
Theorem · Alternative answer
ProvedPeters 2026Optimization NP-hardness for three voters
Computing a linear order minimizing the sum of Kendall-tau distances to exactly three strict complete ballots is NP-hard.Assumptions
- This is a function/optimization task; NP-completeness is stated for the threshold decision language. Worst-case hardness does not prove P ≠ NP.
- Input
- Three strict complete ballots
- Output
- A consensus order of minimum total score
In this problem
This is a function/optimization task; NP-completeness is stated for the threshold decision language. Worst-case hardness does not prove P ≠ NP.
Sources
Related advances 1
- ProvedHardness for every fixed voter count at least threePeters 2026
The source combines the three-voter result, the older even-voter result and addition of a pair of reversed ballots.
Theorem · Related result
ProvedPeters 2026Hardness for every fixed voter count at least three
For every fixed integer r ≥ 3, minimizing total Kendall-tau disagreement for r strict complete ballots is NP-hard.Assumptions
- The source combines the three-voter result, the older even-voter result and addition of a pair of reversed ballots. It does not concern incomplete ballots or weighted voters.
In this problem
The source combines the three-voter result, the older even-voter result and addition of a pair of reversed ballots. It does not concern incomplete ballots or weighted voters.
Sources
Background 1
- ProvedThe two-voter case is polynomial-time solvablePeters 2026
The triangle inequality yields a lower bound equal to the distance between the two inputs, attained by either input.
Theorem · Supporting result
ProvedPeters 2026The two-voter case is polynomial-time solvable
For two strict complete ballots, either input order minimizes the sum of Kendall-tau distances to the two ballots.Assumptions
- The triangle inequality yields a lower bound equal to the distance between the two inputs, attained by either input. This does not extend to three voters.
In this problem
The triangle inequality yields a lower bound equal to the distance between the two inputs, attained by either input. This does not extend to three voters.
Sources
Compare statements · 2
Each row is a separate assertion. Its assumptions determine which question it answers.
| Statement | Input | Output |
|---|---|---|
| Decision NP-completeness for three complete ballots → Proved Exact statement & sources | Three strict complete ballots plus integer B | Yes/no: is a total score at most B achievable? |
| Optimization NP-hardness for three voters → Proved Exact statement & sources | Three strict complete ballots | A consensus order of minimum total score |
Optimization NP-hardness for three voters →
Constructions · 1
Three ballots with a cyclic majority
Explore this construction in the Landscape ↑
- Ballots
- A > B > C; B > C > A; C > A > B
- Pairwise majorities
- A beats B, B beats C, C beats A, each by 2 votes to 1
- Best total disagreement
- 4; three of the six consensus orders achieve it
- Score conventions
- For this profile the constant is 3, so total Kendall-tau score = 3 + majority-disagreement score.
OpenMath’s small illustrative profile is not the paper’s MAX CUT instance or a certificate of NP-hardness.
Decision NP-completeness for three complete ballots →Connections
Analogues and related questions 1
Threshold decision related to Consensus optimization.
Scope comparisonDecision and optimization. A consensus optimizer would also answer score-threshold questions; the two tasks have different complexity classifications.
Limit NP-completeness concerns the decision language; optimization is described as NP-hard.
Sources & review
- Kemeny Rank Aggregation is NP-Hard for Three Voters ↗Theorem 1; Sections 2–5
- Kemeny Rank Aggregation is NP-Hard for Three Voters ↗Sections 1 and 6
Independent relationship review: not recorded. Link to this connection
Consequences 1
Assuming Threshold decisionProved
Three ballots already reach the hardness boundary
Under stated assumptionsThe new three-voter theorem combines with the known even-voter theorem and the reversed-pair construction to give worst-case optimization hardness for every fixed voter count at least three.
Limit Exact algorithms and approximation methods can still be useful on particular instances; no P ≠ NP conclusion follows.
- Hardness for every fixed voter count at least threeProved
- The two-voter case is polynomial-time solvableProved
Sources & review
Supporting statements
- Hardness for every fixed voter count at least three →
- The two-voter case is polynomial-time solvable →
- Kemeny Rank Aggregation is NP-Hard for Three Voters ↗Sections 1 and 6
Source-grounded explanation · independent explanation review: pending.
Timeline
A three-ballot reduction is publishedRelated result
Peters publishes the MAX CUT reduction and its explicit realization by three voters.
This is a selected source-supported milestone, not an exhaustive history.
- Decision NP-completeness for three complete ballotsProved
- Optimization NP-hardness for three votersProved
- Kemeny Rank Aggregation is NP-Hard for Three Voters ↗Theorem 1; Sections 2–5
- Kemeny Rank Aggregation is NP-Hard for Three Voters ↗Sections 1 and 6
The three-list boundary is left openFoundation
Dwork and coauthors prove even-voter hardness and ask about three complete lists.
This is a selected source-supported milestone, not an exhaustive history.
- Kemeny Rank Aggregation is NP-Hard for Three Voters ↗Section 1; Dwork et al. (2001)
Kemeny introduces the aggregation ruleFoundation
The paper traces the distance-minimizing consensus rule to Kemeny’s work.
This is a selected source-supported milestone, not an exhaustive history.
- Kemeny Rank Aggregation is NP-Hard for Three Voters ↗Section 1; Dwork et al. (2001)
Evidence
| Literature | Status OpenMath assessment · Oct 14, 2026.
|
|---|---|
| Formal | None linked Reported in sources: No complete Lean, Isabelle or other proof-assistant artifact was identified in the selected manuscript; a mathematical reduction is supplied. |
| Computation | |
| Review | Not yet reviewed OpenMath assessment: The cited preprint establishes threshold decision NP-completeness for exactly three complete ballots, and hence optimization NP-hardness. This is a worst-case complexity result, not a proof that P differs from NP. Source comparison and presentation; independent mathematical review remains pending. OpenMath pilot collection · OpenMath source curation · assessed Oct 14, 2026 · review due Jan 14, 2027 Collection last checked Oct 14, 2026. |
Sources
Choose a starting point below. Each result links to its exact statement, cited passages and checks.
Start here
- Original question
Kemeny Rank Aggregation is NP-Hard for Three Voters →Read the definition, score translation and original three-list question.
- Proof source
Kemeny Rank Aggregation is NP-Hard for Three Voters →Follow both directions of the reduction and the three-ballot realization.
Bibliography 1
- Kemeny Rank Aggregation is NP-Hard for Three Voters →
Dominik Peters · Preprint · Jul 28, 2026
Theorem 1; Sections 1–6, especially the MAX CUT reduction and three-ballot realization.
Selected literature; source observations and coverage limits are retained in the publication details.
Contributors
Dominik Peters authored the paper, checked and simplified the reduction, supplied mathematical improvements and wrote the manuscript. He attributes reduction discovery to GPT-5.6 Sol Ultra and part of the simplification to Claude Fable 5. Kemeny introduced the aggregation rule; Dwork and coauthors posed the three-list complexity question.
Authors & roles
Kemeny Rank Aggregation is NP-Hard for Three Voters →
Dominik Peters
Peters credits GPT-5.6 Sol Ultra with finding the reduction, Claude Fable 5 with part of the simplification, and his own mathematical simplification and manuscript writing.
These are source credits; they do not imply OpenMath accounts, endorsements or independent mathematical review.
Record details
- Record version
- 5
- Classification
- MSC2020 68Q17 / 91B14
- Prerequisite level
- undergraduate
Independent mathematical review is pending. External certificates and manuscript proofs are attributed to their sources.
Source observations & version history →