Answer: \(\text{NP-hard}\)
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problem of determining the winning ordering for a (j, k)-Kemeny election is NP-hard if j ≥3 and k ≥3 both hold or if j = L and k ≥3 both hold. In particular winner determination is NP-hard for (3, 3)-Kemeny.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given
m
alternatives and
\tau
trichotomous weak-order types with positive binary-rational masses
\mu_t
summing to one, compute a trichotomy
P
maximizing
S_\mu(P)=\sum_{a\succ_P b}\Delta_\mu(a,b)
, where
\Delta_\mu(a,b)=\sum_t\mu_t(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a])
; measure complexity in
m,\tau
, and the mass bit length.
Let \(A\) contain \(m\ge 3\) alternatives. A trichotomy is an ordered partition \(T\succ M\succ B\) of \(A\) into exactly three nonempty indifference classes; strict preference holds precisely between classes in that order.
A society is given by its support: a list of \(\tau\ge 1\) distinct trichotomous weak-order types, each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types; let \(L\) be the total bit length of the masses.
Define \(\Delta_\mu(a,b)=\sum_{t=1}^{\tau}\mu_t\bigl(\mathbf{1}[a\succ_t b]-\mathbf{1}[b\succ_t a]\bigr)\) and \(S_\mu(P)=\sum_{a\succ_P b}\Delta_\mu(a,b)\). Compute any trichotomy \(P\) maximizing \(S_\mu(P)\); no tie-breaking among maximizers is required.
Is computing a maximizing trichotomy polynomial-time solvable in \(m,\tau,L\), or is it NP-hard?
For finite voter profiles, computing a maximizing trichotomy from trichotomous ballots is NP-hard. For integer-weighted tournaments, the corresponding threshold problem over ordered partitions into three nonempty classes is NP-complete, even for purely cyclic weights or transitive positive-weight comparisons. These results do not separately classify the rational-mass formulation.
Computing any maximizing trichotomy is NP-hard, using the finite-profile hardness premise supplied in the question. The reduction has polynomial output size and works even when all masses must be dyadic rationals.
Let a finite profile contain \(N\ge 1\) trichotomous ballots. Merge identical ballots, obtaining distinct types \(R_1,\ldots,R_\tau\) with positive integer multiplicities \(c_1,\ldots,c_\tau\), where \(\sum_{t=1}^{\tau}c_t=N\).
For each feasible output trichotomy \(P\), define its score against type \(R_t\) by
\( g_t(P)=\sum_{a\succ_P b}\bigl(\mathbf{1}[a\succ_{R_t}b]-\mathbf{1}[b\succ_{R_t}a]\bigr). \)
The unnormalized finite-profile objective is therefore
\( F(P)=\sum_{t=1}^{\tau}c_tg_t(P). \)
This is an integer. Set \(\mu_t=c_t/N\). These masses are positive and sum to one. Interchanging the two finite sums in the definition of \(S_\mu\) gives
\( S_\mu(P)=\sum_{t=1}^{\tau}\mu_tg_t(P)=F(P)/N. \)
Thus \(S_\mu\) and \(F\) have exactly the same maximizers, including all ties. The feasible outputs also coincide: both require exactly three nonempty classes.
The transformation is polynomial-time. Each ballot can be represented by its class assignment to the \(m\) alternatives, so identical ballots can be grouped in polynomial time. Moreover, \(\tau\le N\), and each numerator and denominator has \(O(\log(N+1))\) bits. Consequently, the total mass encoding length is \(O(\tau\log(N+1))\), polynomial in the explicit finite-profile input size.
A polynomial-time algorithm for the rational-mass problem would therefore compute an optimum for the finite-profile problem: transform the input, call the algorithm once, and return its output unchanged. By the supplied finite-profile hardness premise, this proves NP-hardness when arbitrary rationals are encoded in binary.
If “binary-rational” specifically requires terminating binary expansions, the fractions \(c_t/N\) need not qualify. The following construction closes that possible encoding gap.
Put \(p_t=c_t/N\) and \(C=\binom{m}{2}\). Choose a power of two \(D\) satisfying
\( D>8NC\tau. \)
For \(t<\tau\), define
\( q_t=\frac{\lfloor Dp_t\rfloor}{D}, \)
and define
\( q_\tau=1-\sum_{t<\tau}q_t. \)
These are dyadic masses summing to one. They are strictly positive: since \(D>N\) and \(c_t\ge 1\), each \(\lfloor Dp_t\rfloor\) is at least one; also,
\( q_\tau=p_\tau+\sum_{t<\tau}(p_t-q_t)\ge p_\tau>0. \)
The total rounding error satisfies
\( \sum_{t=1}^{\tau}|q_t-p_t| =2\sum_{t<\tau}(p_t-q_t) \le \frac{2(\tau-1)}{D} <\frac{2\tau}{D}. \)
For every feasible \(P\), at most one orientation of each unordered pair occurs in the sum defining \(g_t(P)\), and every summand belongs to \(\{-1,0,1\}\). Hence \(|g_t(P)|\le C\). It follows uniformly over all feasible outputs that
\( \left|S_q(P)-\frac{F(P)}{N}\right| =\left|\sum_t(q_t-p_t)g_t(P)\right| \le C\sum_t|q_t-p_t| <\frac{1}{4N}. \)
Now suppose \(F(P)>F(Q)\). Since both scores are integers, \(F(P)-F(Q)\ge 1\), and therefore
\( S_q(P)-S_q(Q) >\frac{F(P)-F(Q)}{N}-\frac{1}{2N} \ge\frac{1}{2N}>0. \)
Thus every strict finite-profile score comparison is preserved. In particular, every maximizer of \(S_q\) maximizes \(F\): otherwise, a trichotomy with larger \(F\)-score would also have larger \(S_q\)-score. Rounding may distinguish original ties, which is harmless because no tie-breaking among original maximizers is required.
Choosing the smallest power of two above \(8NC\tau\) gives
\( \log D=O(\log(N+1)+\log m+\log(\tau+1)). \)
Each mass has an \(O(\log D)\)-bit numerator and denominator. The construction consequently has polynomial running time and output size. This proves NP-hardness even under the stricter dyadic interpretation.
The supplied finite-profile hardness result transfers to the support-based rational-mass formulation. Distinct support types, positive masses, normalization, and polynomial bit length are all preserved by the reduction. The integer-weighted tournament hardness results are unnecessary for this conclusion.
Hence computing a maximizing trichotomy is NP-hard; a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves the task. The reduction transfers the supplied finite-profile NP-hardness to the support-based formulation, including when “binary-rational” means dyadic rational. No major or minor mathematical issues were found.
The proof uses the finite-profile hardness statement as a premise supplied by the task. It does not need the separate tournament hardness results.
Grouping identical ballots produces distinct trichotomous types with positive integer multiplicities \(c_t\), satisfying \(\sum_t c_t=N\). This meets the target’s requirement that support types be distinct.
The expression
\[
F(P)=\sum_{t=1}^{\tau}c_tg_t(P)
\]
correctly represents the finite-profile score obtained by summing the pairwise contributions of every ballot. Each contribution is an integer, so \(F(P)\) is an integer.
With \(\mu_t=c_t/N\), exchanging the two finite sums gives
\[
S_\mu(P)=F(P)/N.
\]
Because \(N>0\), this preserves every comparison and every tie. The feasible outputs remain ordered partitions into exactly three nonempty classes. Thus any returned target maximizer solves the finite-profile instance.
The encoding argument is valid for an explicitly listed finite profile: grouping ballots takes polynomial time, \(\tau\le N\), and every numerator and denominator has \(O(\log(N+1))\) bits. Consequently, the target input has polynomial size. This establishes the reduction when arbitrary rationals are encoded in binary.
Here \(m\ge3\), so \(C=\binom{m}{2}\ge3\). Together with \(N,\tau\ge1\), the condition \(D>8NC\tau\) implies \(D>N\).
For every \(t<\tau\),
\[
Dp_t=Dc_t/N>1,
\]
so \(\lfloor Dp_t\rfloor\ge1\), establishing positivity of those masses. The displayed identity for \(q_\tau\) establishes its positivity as well. Every mass is a multiple of \(1/D\), and their sum is exactly one.
The support-size-one case is also covered: the sums over \(t<\tau\) are empty, and \(q_1=p_1=1\).
For \(t<\tau\), rounding downward gives
\[
0\le p_t-q_t<1/D.
\]
The final coordinate absorbs exactly the accumulated deficit. Therefore the stated identity
\[
\sum_t|q_t-p_t|=2\sum_{t<\tau}(p_t-q_t)
\]
is correct, including when \(\tau=1\). Its subsequent upper bounds are valid.
For any feasible \(P\), each unordered pair contributes at most one summand to \(g_t(P)\), and each summand has absolute value at most one. Hence \(|g_t(P)|\le C\). The triangle inequality then yields the claimed uniform perturbation bound:
\[
\left|S_q(P)-F(P)/N\right|
<2C\tau/D<1/(4N).
\]
The constants and strict inequalities are correct.
If \(F(P)>F(Q)\), integrality gives \(F(P)-F(Q)\ge1\). Applying the uniform error bound to both outputs yields
\[
S_q(P)-S_q(Q)>
\frac{F(P)-F(Q)}{N}-\frac{1}{2N}
\ge\frac{1}{2N}>0.
\]
Thus every strict original comparison is preserved.
The conclusion about maximizers follows: an output with suboptimal \(F\)-score has a competitor with strictly larger \(F\)-score, hence strictly larger \(S_q\)-score. It cannot maximize \(S_q\).
Original ties may be broken, but this does not invalidate the reduction because the task permits any original maximizer.
The smallest power of two above \(8NC\tau\) has the stated logarithmic bit length. Computing its value, the integer floors, and the residual numerator requires polynomial-time integer arithmetic. All output masses have polynomial encoding length.
Accordingly, a polynomial-time algorithm in \(m,\tau,L\) would solve the supplied NP-hard finite-profile problem after a polynomial-time transformation. The claimed NP-hardness follows under either interpretation of binary-rational masses.
No additional clarification or repair is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.