Kemeny Rank Aggregation is NP-Hard for Three Voters

Dominik Peters

REVIEW 2 major objections 4 minor 1 cited by

Kemeny Rank Aggregation is NP-Hard for Three Voters

T0 review · 2 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Kemeny rank aggregation is NP-complete even with just three voters.

desk verdict If the contiguity lemma gets a correct proof, this closes a 25-year-old open problem; the manuscript has a real gap but deserves peer review. read the letter →

arxiv 2607.25540 v1 pith:O2QLVQRL submitted 2026-07-28 cs.GT

Dominik Peters This is my paper

classification cs.GT MSC 68Q1705C2091B14

keywords KemenyrankaggregationNP-completenessthreevotersfeedbackarcsetontournamentsMAXCUTmajoritygraphgadgetreductioncomputationalsocialchoice

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that computing a Kemeny-optimal ranking is NP-hard even when the input is a set of exactly three rankings. The result answers a question that had been open since 2001, when hardness was known for every even number of voters but the case of three voters was unresolved. The proof reduces a restricted form of MAX CUT to the three-voter Kemeny decision problem, building a unit-weight tournament that can be realized by exactly three linear orders. If correct, this completes the classification of the Kemeny problem for fixed voter counts: easy for one or two voters, NP-hard for every n ≥ 3.

What carries the argument

The load-bearing object is the six-supercandidate vertex gadget, whose internal tournament contains two collections of three arc-disjoint 3-cycles. Any near-optimal ranking must be wrong on exactly one arc in each cycle of both collections, which forces exactly two possible internal orders: ABCDEF (encoding that the vertex is on the left side of the cut) or DAEBFC (right side). The 'long even edges' condition forces each edge candidate into one of a few possible gaps inside the endpoint gadgets, making the marginal cost difference between a cut and a non-cut edge exactly one unit of M. A separate contiguity lemma, cited from earlier work, is used to treat the M members of each supercandidate

What would settle it

Evaluate the random-blocking process in the paper's sketch of the contiguity lemma on a supercandidate whose internal order is reversed relative to the output: the internal Kemeny cost is 1 initially but always 0 after the process, disproving the claimed expectation equality. Finding such a configuration would show the contiguity lemma is false as stated and would break the reverse direction unless a corrected proof is given.

Watch

Extended reading notes

Core claim

The central claim of the paper is that KEMENY SCORE with three voters is NP-complete: given three linear orders and a bound b, it is NP-hard to decide whether a ranking exists with total Kendall-tau distance at most b. The reduction starts from SIMPLE MAX CUT on graphs whose edges join vertices at distance at least 6 with even index sums (the 'long even edges' restriction). For each graph vertex, the construction creates a gadget of six blocks of M indistinguishable candidates called supercandidates, arranged in a tournament with three intentionally reversed arcs; for each graph edge, it creates two edge candidates ℓ_e and r_e. The entire unit-weight tournament is then realized by three expl

Load-bearing premise

The reverse direction assumes that in an optimal ranking the many identical candidates inside each block-gadget can always be made consecutive in their natural order without increasing the score, and the paper's proof of that lemma contains an incorrect step.

Editorial extensions

If this is right

Kemeny score becomes NP-hard for every fixed number of voters n ≥ 3: for odd n by adding pairs of completely reversed rankings to a three-voter profile, and for even n by combining with the known n = 4 case.
The fixed-voter complexity of Kemeny aggregation is now fully settled: polynomial for n = 1,2 and NP-hard from n = 3 onward.
Problems whose hardness was proved by reducing from four-voter Kemeny, such as Egalitarian Kemeny detection, Squared Kemeny computation, and near-single-peakedness detection, now inherit hardness with one fewer voter.
The Kemeny winner-determination problem, already known to be Θ_2^p-complete for fixed even and for n = 7 voters, is likely also Θ_2^p-complete for n = 3.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's own sketch of the contiguity lemma (in a footnote) contains an expectation calculation that is false for reversed two-member blocks: the original internal cost is 1 while the randomized process always yields 0. Until a correct proof of contiguity is supplied, the reverse direction rests on an unverified lemma; it may well be repairable by a different exchange argument.
The 'long even edges' restriction is a convenience for the case analysis rather than a structural necessity, so a version of the reduction without it is likely derivable by a finite case check, which would give a more direct reduction from plain MAX CUT.
Because the paper reports that the gadget was found by an automated search over candidate tournaments, a testable extension is that similar automated search over small gadgets could resolve remaining open complexity questions in voting theory, provided the search space and scoring heuristics are chosen tightly.
The three-voter realization of a tournament that encodes MAX CUT may be reusable: any pairwise rule whose decision problem depends only on the majority graph (such as Slater's rule) might inherit three-voter hardness from the same construction, subject to the same contiguity caveat.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline is simple: this paper claims to prove that Kemeny rank aggregation is NP-hard with exactly three voters, resolving the case Dwork et al. left open in 2001. I think the claim is very likely true. The reduction is genuinely new: it starts from SIMPLE MAX CUT with a 'long even edges' restriction, builds a six-supercandidate vertex gadget, and then gives three explicit voter orders that realize the resulting tournament. Section 5's construction is concrete and I could not find an error there. The forward direction, from a cut to a low-cost Kemeny ranking, is worked out in detail and the cost calculations add up. The large parameter M is chosen sensibly.

The soft spot is in the reverse direction, Section 4.2. The proof needs every supercandidate to appear as a contiguous block in some optimal ranking. The paper cites Conitzer (2006) for this and includes a proof sketch in Footnote 4. That sketch is wrong. The random-sampling argument does not preserve expected Kemeny cost: a simple example with a two-member supercandidate reversed in the ranking shows the claimed equality fails. The same happens for non-contiguous clones. So as written, the contiguity step is unproven. This matters because the rest of the reverse direction reads the cut directly off the internal order of each gadget; without contiguity, that reading does not follow. The paper mentions a Lean formalization of the reduction's correctness, which is encouraging, but it is not included in the manuscript. A correct proof may well exist — Conitzer's theorem might exactly supply it — but the paper does not provide it.

The citation pattern is fine. The author's own earlier work with Bachmeier et al. is cited appropriately; the new result goes beyond it. The self-referential note about using LLMs to find the reduction is unusual but transparent, and it does not affect the math.

My sense: the result is important enough that the right move is to send it to peer review, not desk reject. A good referee should either find a correct proof of the contiguity lemma or ask the author to make the Lean formalization available. If that gap is closed, the paper is a major contribution to computational social choice. I'd bring it to the reading group while it's still in flux, and I'd cite it once it clears review.

Referee Report

2 major / 4 minor

Summary. The paper gives a polynomial-time reduction from SIMPLE MAX CUT (with the "long even edges" restriction) to KEMENY SCORE with exactly three voters. For each vertex of the input graph it constructs a gadget of six supercandidates, each of size M, and for each edge it adds two edge candidates. It proves a forward direction by explicitly building a Kemeny ranking of cost at most b from any cut of size k, and a reverse direction by showing that any ranking of cost at most b must have each vertex gadget in one of two possible internal orders, from which a cut is read off. Section 5 then realizes the constructed majority tournament by three explicit linear orders. The main theorem states that KEMENY SCORE with three voters is NP-complete, resolving a question of Dwork et al. (2001).

Significance. If correct, this is a substantial result: it resolves a well-known open problem and completes the fixed-voter-number complexity classification for Kemeny rank aggregation. The reduction is explicit, the cost computations in Section 4.1 are detailed and checkable, and the three-voter realization in Section 5 is elegant. The authors also state that the reduction has been formalized in Lean, which, if made available, would be an additional strength. The main obstacle to accepting the paper as written is the treatment of the clone-contiguity lemma in the reverse direction.

major comments (2)

[§4.2 (reverse direction), Footnote 4] The assertion that supercandidates can be assumed contiguous and internally in the natural order is load-bearing for the reverse direction, since the cut is read from the internal order of each gadget. The paper cites Conitzer (2006) Theorem 1, but does not state the theorem or prove that its hypotheses hold here. The proof sketch in Footnote 4 is not correct as written: if the replacement block is ordered by the fixed natural order of the supercandidate, the claimed expectation equality already fails for a two-member supercandidate X={x1,x2} with arc x1→x2 ranked in reverse order (original internal cost 1, after the process 0). If the intended block order is the order inherited from the original ranking, the equality can be repaired, but this must be stated and proved. Also, Conitzer's theorem provides existence of some optimal ranking with contiguity; the proof should explicitly choose
[§1 (Introduction)] The paper states that the correctness of the reduction has been formalized in Lean (DominikPeters/KemenyHardnessLean), but this artifact is not included in the submission. If the formalization covers the contiguity lemma and the finite check in §4.2, it could close the gap identified above; otherwise the manuscript must be self-contained. Please clarify the status of the repository and state exactly which lemmas are formalized.

minor comments (4)

[§5, three-voter realization] The definition of the barred notation V_i[σ] for internally reversed supercandidates is introduced, but the displayed voter 3 uses unbarred V_i[CDEABF]; the text says voter 3 reverses the internal order. The display should use the barred notation to avoid confusion.
[References] There are two name typos: 'Atri Rurda' should be 'Atri Rudra' in the Coppersmith et al. entry, and 'Caresten Thomassen' should be 'Carsten Thomassen' in the Bang-Jensen and Thomassen entry.
[Footnote 5] The remark that enumerating all 720 orderings 'will find' exactly two optima is informal. If the cycle-incidence argument is retained, consider removing the enumeration claim or providing a machine-checked certificate for the finite case.
[Abstract and §1] The provenance account naming specific LLMs is unconventional in an abstract. Consider moving this material to an acknowledgements section or an appendix, and keeping the abstract focused on the mathematical result.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the hardness result rests on an independent MAX CUT reduction; the flawed Footnote 4 sketch is a correctness gap, not circularity.

full rationale

The central claim (Theorem 1) is established by an explicit polynomial-time reduction from SIMPLE MAX CUT with long even edges: Section 3 constructs a unit-weight tournament, Section 5 shows three concrete linear orders induce it, and Sections 4.1–4.2 prove correctness by two-directional cost accounting with the budget b taken to be exactly the forward-direction cost of the ranking built from a cut. No parameter is fitted to Kemeny outputs, no target quantity is defined in terms of the claimed result, and the reverse direction derives a cut from an optimal ranking and compares cM with kM via M > n⁴. There is no self-definitional step, no fitted input called a prediction, and no renaming of a known result. The reverse direction's contiguity assumption for supercandidates is imported from “Theorem 1 of Conitzer (2006)”, an external AAAI paper by a different author, so the “uniqueness imported from authors” and “ansatz smuggled via citation” patterns do not apply. Per the reviewing rule I flag that the only in-manuscript support for that lemma, Footnote 4, asserts “the expected Kemeny cost of ≻′′ equals the Kemeny cost of ≻”, which appears false (internal pairs of a supercandidate misordered in ≻ contribute zero in the expectation, since selected blocks are always reordered transitively). This makes the contiguity step, within the manuscript, dependent on the external citation and a defective sketch — a correctness/verification gap, not circularity, because the lemma is not defined in terms of the target result. Self-citations exist (Bachmeier et al. 2019 and Lederer et al. 2024 include the author), but they are used only as background for n=7 hardness and Squared Kemeny hardness, and are not load-bearing for Theorem 1. The stated Lean formalizations (DominikPeters/…Lean) are mentioned but not included; again an assurance limitation, not circularity. Verdict: no definitional, fitted, or self-citation circularity; score 2 reflects only the presence of minor non-load-bearing self-citations.

Assumptions & free parameters 1 free parameters · 2 assumptions · 2 invented entities

The central claim rests on standard NP-hardness of MAX CUT and on the clone-contiguity theorem. The only hand-set constant is M. The gadgets are explicit and fully constructed, so there are no hidden postulated entities beyond the proof devices themselves.

free parameters (1)

M = 1000(n+1)^4 = 1000(n+1)^4
Chosen by hand to be very large. It makes within-gadget costs dominate edge-edge costs and forces minimum-cost rankings to respect vertex-gadget order. The proof requires M large enough that (3n+1)M^2 > b and n^4 < M; the explicit constant 1000 is enough.

assumptions (2)

standard math SIMPLE MAX CUT (unweighted, undirected) is NP-complete, and the 'long even edges' restriction remains NP-complete via vertex relabeling and isolated filler vertices (Section 2).
This is the source problem for the reduction. The paper gives a short proof of the restricted variant's hardness from the known NP-completeness of SIMPLE MAX CUT (Garey et al., 1976).
domain assumption Conitzer's Theorem 1: a set of 'clones' or supercandidates with identical outside relations can be assumed to appear contiguously and in internal tournament order in an optimal ranking (Section 4.2, Footnote 4).
The reverse direction depends on this lemma. The paper does not prove it correctly: the Footnote 4 sketch asserts a false expectation equality. A correct proof is not supplied in the text.

invented entities (2)

Supercandidate blocks (six per graph vertex: A_i,...,F_i, each of size M)
purpose: Make the tournament induced by three voters encode vertex side (L/R) and force contiguous blocks in optimal rankings.
Internal reduction device; no external falsifiable handle. The proof constructs fresh candidates, so the entity is fully specified within the reduction.
Edge candidates l_e and r_e
purpose: Detect whether edge e is cut; their optimal placement in a consensus ranking incurs a penalty iff both endpoints lie on the same side of the cut.
Internal reduction gadget; no independent evidence by design.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Kemeny Rank Aggregation is NP-Hard for Three Voters." pith.science (2026). https://pith.science/paper/O2QLVQRL

@misc{pith2026260725540,
  author       = {Pith},
  title        = {Pith review of: Kemeny Rank Aggregation is NP-Hard for Three Voters},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O2QLVQRL}},
  note         = {Machine review of arXiv:2607.25540}
}

abstract

Rank aggregation is the task of combining $n$ input rankings (linear orders) of alternatives into a single output ranking. The Kemeny rank aggregation rule selects the output ranking that minimizes the total Kendall-tau distance to the input rankings, i.e., the total number of adjacent swaps that need to be performed across input rankings so that they are all equal to the output ranking. Dwork et al. (2001) proved that the problem of computing such a ranking is NP-complete for every even $n \ge 4$ and asked whether hardness holds even for $n = 3$. We give a hardness reduction from MAX CUT that proves the problem is NP-complete for $n = 3$. The reduction was found in July 2026 by GPT 5.6 Sol Ultra and simplified in part with help from Claude Fable 5.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

The Complexity of Kemeny Aggregation with Three Rankings
cs.GT 2026-07 accept novelty 8.0 of 10

Kemeny Score is NP-complete for three all-2-to-1 rankings; winner/precedence problems are Θ₂ᵖ-complete and recognition is coNP-complete, with a sharp 2/3 support dichotomy for every fixed profile size.

Reference graph

Works this paper leans on

35 extracted references · 1 canonical work pages · cited by 1 Pith paper

[1]

Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI) , pages =

Zack Fitzsimmons and Edith Hemaspaandra , title =. Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI) , pages =. 2021 , doi =

2021
[2]

Discrete Applied Mathematics , volume=

Weighted majority tournaments and Kemeny ranking with 2-dimensional Euclidean preferences , author=. Discrete Applied Mathematics , volume=. 2022 , doi=

2022
[3]

and Guo, Jiong and Niedermeier, Rolf and Rosamond, Frances A

Betzler, Nadja and Fellows, Michael R. and Guo, Jiong and Niedermeier, Rolf and Rosamond, Frances A. , title =. Theoretical Computer Science , volume =. 2009 , doi =

2009
[4]

and Rurda, Atri , title =

Coppersmith, Don and Fleischer, Lisa K. and Rurda, Atri , title =. ACM Transactions on Algorithms (TALG) , volume =. 2010 , doi =

2010
[5]

, title =

van Zuylen, Anke and Williamson, David P. , title =. Mathematics of Operations Research , volume =. 2009 , doi =

2009
[6]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC) , pages =

Kenyon-Mathieu, Claire and Schudy, Warren , title =. Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC) , pages =. 2007 , doi =

2007
[7]

Mathematical Social Sciences , volume =

Can, Burak and Storcken, Ton , title =. Mathematical Social Sciences , volume =. 2013 , doi =

2013
[8]

Games and Economic Behavior , volume =

Walter Bossert and Yves Sprumont , title =. Games and Economic Behavior , volume =. 2014 , doi =

2014

Show all 35 references

[9]

Peyton Young , title =

H. Peyton Young , title =. Journal of Economic Perspectives , volume =. 1995 , doi =

1995
[10]

Bernard Debord , title =. Math. 1987 , url =

1987
[11]

The complexity of

Hemaspaandra, Edith and Spakowski, Holger and Vogel, J. The complexity of. Theoretical Computer Science , volume =. 2005 , doi =

2005
[12]

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS) , pages =

Michael Lampis , title =. Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS) , pages =. 2022 , doi =

2022
[13]

European Journal of Operational Research , volume =

Olivier Hudry , title =. European Journal of Operational Research , volume =. 2010 , doi =

2010
[14]

2025 , doi =

Piotr Faliszewski and Piotr Skowron and Arkadii Slinko and Krzysztof Sornat and Stanisław Szufa and Nimrod Talmon , title =. 2025 , doi =

2025
[15]

, title =

McGarvey, David C. , title =. Econometrica , volume =. 1953 , doi =

1953
[16]

2019 , publisher =

Bachmeier, Georg and Brandt, Felix and Geist, Christian and Harrenstein, Paul and Kardel, Keyvan and Peters, Dominik and Seedig, Hans Georg , title =. 2019 , publisher =. doi:10.1016/j.jcss.2019.04.005 , url =

2019 doi
[17]

and Deng, Xiaotie , title =

Biedl, Therese and Brandenburg, Franz J. and Deng, Xiaotie , title =. Discrete Mathematics , volume =. 2009 , publisher =. doi:10.1016/j.disc.2007.12.088 , url =

2009 doi
[18]

Proceedings of the 10th International Conference on World Wide Web (WWW) , pages =

Dwork, Cynthia and Kumar, Ravi and Naor, Moni and Sivakumar, Dandapani , title =. Proceedings of the 10th International Conference on World Wide Web (WWW) , pages =. 2001 , publisher =

2001
[19]

The Squared Kemeny rule for averaging rankings , booktitle =

Lederer, Patrick and Peters, Dominik and W. The Squared Kemeny rule for averaging rankings , booktitle =. 2024 , doi =

2024
[20]

, title =

Kemeny, John G. , title =. Daedalus , volume =. 1959 , publisher =

1959
[21]

Garey and David S

Michael R. Garey and David S. Johnson and Larry Stockmeyer , title =. Theoretical Computer Science , volume =. 1976 , doi =

1976
[22]

1989 , publisher =

Voting schemes for which it can be difficult to tell who won the election , journal =. 1989 , publisher =

1989
[23]

Weighted majority tournaments and

Escoffier, Bruno and Spanjaard, Olivier and Tydrichov. Weighted majority tournaments and. Discrete Applied Mathematics , volume =. 2022 , doi =

2022
[24]

Weighted tournament solutions , booktitle =

Felix Fischer and Olivier Hudry and Rolf Niedermeier , editor =. Weighted tournament solutions , booktitle =. 2016 , publisher =

2016
[25]

Discrete Applied Mathematics , volume=

On weakly and strongly popular rankings , author=. Discrete Applied Mathematics , volume=. 2023 , doi=

2023
[26]

Journal of the ACM (JACM) , volume =

Ailon, Nir and Charikar, Moses and Newman, Alantha , title =. Journal of the ACM (JACM) , volume =. 2008 , publisher =

2008
[27]

SIAM Journal on Discrete Mathematics , volume =

Noga Alon , title =. SIAM Journal on Discrete Mathematics , volume =. 2006 , doi =

2006
[28]

Proceedings of the 21st National Conference on Artificial Intelligence (AAAI) , pages =

Vincent Conitzer , title =. Proceedings of the 21st National Conference on Artificial Intelligence (AAAI) , pages =. 2006 , url =

2006
[29]

, editor =

Karp, Richard M. , editor =. Reducibility among combinatorial problems , booktitle =. 1972 , publisher =

1972
[30]

SIAM Journal on Discrete Mathematics , volume=

A polynomial algorithm for the 2-path problem for semicomplete digraphs , author=. SIAM Journal on Discrete Mathematics , volume=. 1992 , doi=

1992
[31]

Proceedings of the 29th International Workshop on Combinatorial Algorithms (IWOCA) , pages=

Median of 3 permutations, 3-cycles and 3-hitting set problem , author=. Proceedings of the 29th International Workshop on Combinatorial Algorithms (IWOCA) , pages=. 2018 , doi=

2018
[32]

Peyton and Levenglick, Arthur , title =

Young, H. Peyton and Levenglick, Arthur , title =. 1978 , doi =

1978
[33]

2026 , eprint=

Bribery's influence on ranked aggregation , author=. 2026 , eprint=

2026
[34]

Theoretical Computer Science , volume=

Multiple genome rearrangement by swaps and by element duplications , author=. Theoretical Computer Science , volume=. 2007 , doi=

2007
[35]

Computational aspects of nearly single-peaked electorates , journal =

G\'. Computational aspects of nearly single-peaked electorates , journal =. 2017 , doi =

2017

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [1]

Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI) , pages =

Zack Fitzsimmons and Edith Hemaspaandra , title =. Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI) , pages =. 2021 , doi =

2021

[2] [2]

Discrete Applied Mathematics , volume=

Weighted majority tournaments and Kemeny ranking with 2-dimensional Euclidean preferences , author=. Discrete Applied Mathematics , volume=. 2022 , doi=

2022

[3] [3]

and Guo, Jiong and Niedermeier, Rolf and Rosamond, Frances A

Betzler, Nadja and Fellows, Michael R. and Guo, Jiong and Niedermeier, Rolf and Rosamond, Frances A. , title =. Theoretical Computer Science , volume =. 2009 , doi =

2009

[4] [4]

and Rurda, Atri , title =

Coppersmith, Don and Fleischer, Lisa K. and Rurda, Atri , title =. ACM Transactions on Algorithms (TALG) , volume =. 2010 , doi =

2010

[5] [5]

, title =

van Zuylen, Anke and Williamson, David P. , title =. Mathematics of Operations Research , volume =. 2009 , doi =

2009

[6] [6]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC) , pages =

Kenyon-Mathieu, Claire and Schudy, Warren , title =. Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC) , pages =. 2007 , doi =

2007

[7] [7]

Mathematical Social Sciences , volume =

Can, Burak and Storcken, Ton , title =. Mathematical Social Sciences , volume =. 2013 , doi =

2013

[8] [8]

Games and Economic Behavior , volume =

Walter Bossert and Yves Sprumont , title =. Games and Economic Behavior , volume =. 2014 , doi =

2014