Proved
Two-voter baseline recalled ↗
Either input order minimizes the total Kendall-tau score for two voters.
Kemeny Rank Aggregation is NP-Hard for Three Voters · Sections 1 and 6 →
Source dated Jul 28, 2026 · Observed Oct 14, 2026
Theorem · version 1
The two-voter case is polynomial-time solvable
Statement
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.
Evidence
Source reports
Connections
In this problem · publication v1 · Selected context
Kemeny rank aggregation for three voters →
Supporting result · Proved
Relationship not independently reviewed. This concerns its use in this problem.
In this problem · publication v5
Kemeny rank aggregation for three voters →
Supporting result · Proved
Relationship not independently reviewed. This concerns its use in this problem.
Sources
Kemeny Rank Aggregation is NP-Hard for Three Voters →
- Sections 1 and 6 → · Original passage ↗
Recorded wording
Computing an optimum is NP-hard for three voters. The paper also explains extensions to every fixed voter count at least three and recalls the polynomial-time two-voter case.
paraphrase · Linked proof prose is not republished. Any copied graph data is CC0, as specified by its archive.
Dominik Peters · Preprint · Publication date Jul 28, 2026
Source-reported results and external checks are separate from independent OpenMath assessment.
Revision & attribution
Source revision: v1. Observed Oct 14, 2026.
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.
History
Statement versions
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Proved
Two-voter baseline recalled ↗
Either input order minimizes the total Kendall-tau score for two voters.
Source dated Jul 28, 2026 · Observed Oct 14, 2026 · Source passage →
Record details
- Claim ID
- claim-kemeny-two-voters
- Statement version
- 1
- SHA-256
- ce86761c7802c203c9a02937206905e55e293c1d2352eb0056cf95c4a11edac1