d4-conf-atal-2009-0144 (d4-conf-atal-2009-0144)

Given \(m\) candidates, a finite support \(T_+\) of strict rankings with positive rational masses \(\mu_t\) summing to \(1\), and a rational threshold \(B\), decide whether there is a strict ranking \(\ell\) such that \(r_a(\mu)\le 2\) and \(\sum_{t\in T_+}\mu_t\,\mathrm{KT}(\ell,t)\le B\), where \(r_a(\mu)=\frac{1}{m}\sum_c\left(1+\max_{t\in T_+}\operatorname{pos}_t(c)-\min_{t\in T_+}\operatorname{pos}_t(c)\right)\).

Let \(C\) contain \(m\ge 1\) candidates. A society is given by its support: a nonempty list \(T_+\) of \(\tau\) distinct strict rankings of \(C\), each with positive binary rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Let \(\operatorname{pos}_t(c)\in\{0,\ldots,m-1\}\) be the position of \(c\), with the best candidate at position \(0\), and let \(\mathrm{KT}\) denote Kendall–Tau distance. Define \(r_a(\mu)=\frac1m\sum_{c\in C}(1+\max_{t\in T_+}\operatorname{pos}_t(c)-\min_{t\in T_+}\operatorname{pos}_t(c))\).
Given this society and a positive binary rational threshold \(B\), decide whether there exists a strict ranking \(\ell\) of \(C\) satisfying both \(r_a(\mu)\le 2\) and \(\sum_{t\in T_+}\mu_t\mathrm{KT}(\ell,t)\le B\). Instances with \(r_a(\mu)>2\) are rejected; any qualifying ranking is allowed.

Is this decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For explicitly listed unweighted votes, Kemeny Score is NP-complete even under the restriction \(r_a\le 2\). [Betzler et al.](https://aamas.csc.liv.ac.uk/Proceedings/aamas09/pdf/01_Full%20Papers/11_25_140_FP_0418.pdf)
No result explicitly treating this precise rational-mass formulation was identified in the literature search.

Result

The problem is \(\mathrm{NP}\)-complete. Consequently, a polynomial-time algorithm in \(m,\tau,L\) exists if and only if \(\mathrm{P}=\mathrm{NP}\).

Here, “binary rational” means a rational number whose numerator and denominator are encoded in binary.

Polynomial-time reduction

Use the stated hardness result for explicitly listed unweighted votes with average range at most \(2\). The range definition in [Betzler et al., Section 2 and Theorem 3](https://aamas.csc.liv.ac.uk/Proceedings/aamas09/pdf/01_Full%20Papers/11_25_140_FP_0418.pdf) agrees with the definition in the question: their candidate range is \(1+\max_v\operatorname{pos}_v(c)-\min_v\operatorname{pos}_v(c)\).

Let a source instance consist of \(n\ge 1\) explicitly listed votes \(v_1,\ldots,v_n\) over \(m\) candidates and a positive integer threshold \(k\). Its question is whether some ranking \(\ell\) satisfies \(\sum_{i=1}^{n}\mathrm{KT}(\ell,v_i)\le k\).

Group identical votes. Let \(T_+\) be the resulting list of \(\tau\) distinct rankings, and let \(n_t\) be the number of occurrences of ranking \(t\). Construct the target instance by setting
\(\mu_t=n_t/n\) and \(B=k/n\).

These masses are positive, and \(\sum_{t\in T_+}\mu_t=1\). The threshold is positive.

The range restriction is preserved exactly. For every candidate \(c\), removing repeated copies of rankings changes neither its minimum nor its maximum position. Hence
\(r_a(\mu)=\frac1m\sum_{c\in C}(1+\max_i\operatorname{pos}_{v_i}(c)-\min_i\operatorname{pos}_{v_i}(c))\).
Thus the source restriction \(r_a\le 2\) holds precisely when the target restriction does.

The score condition is preserved exactly. For every ranking \(\ell\),
\(\sum_{t\in T_+}\mu_t\mathrm{KT}(\ell,t)=\frac1n\sum_{t\in T_+}n_t\mathrm{KT}(\ell,t)=\frac1n\sum_{i=1}^{n}\mathrm{KT}(\ell,v_i)\).
Since \(n>0\), the target score is at most \(B=k/n\) if and only if the source score is at most \(k\). This proves both directions of the reduction.

The construction has polynomial size and running time. Write \(L_{\mathrm{src}}\) for the source input length. Because the votes are explicitly listed, \(n\le L_{\mathrm{src}}\). Sorting the rankings, counting their multiplicities, and writing the fractions take polynomial time in \(L_{\mathrm{src}}\). Each mass requires \(O(\log(n+1))\) bits, and the threshold requires \(O(\log(k+1)+\log(n+1))\) bits. After numbering candidates, the target length satisfies
\(L=O(\tau m\log(m+1)+\tau\log(n+1)+\log(k+1)+\log(n+1))\).
In particular, the output is polynomially bounded in the source length.

The problem is therefore \(\mathrm{NP}\)-hard.

Membership in \(\mathrm{NP}\)

A certificate is a strict ranking \(\ell\), encoded in \(O(m\log(m+1))\) bits. Verify that it contains every candidate exactly once.

Compute all input positions and their extrema. The range condition is equivalent to the integer inequality
\(\sum_{c\in C}(1+\max_t\operatorname{pos}_t(c)-\min_t\operatorname{pos}_t(c))\le 2m\).
It is therefore checked exactly, without rational arithmetic.

For each \(t\), compute \(d_t=\mathrm{KT}(\ell,t)\) by counting unordered candidate pairs whose orders differ. This uses \(O(\tau m^2)\) pair comparisons, and \(0\le d_t\le \binom m2\).

Write \(\mu_t=p_t/q_t\) and \(B=a/b\), with positive integer denominators. Define \(Q=b\prod_{t\in T_+}q_t\). Because the total denominator encoding length is at most \(L\), the bit length of \(Q\) is \(O(L)\). The score condition is exactly
\(\sum_{t\in T_+}p_t d_t(Q/q_t)\le a(Q/b)\).
Every division is exact. Since the masses are positive and sum to \(1\), the left side is at most \(Q\binom m2\); all arithmetic therefore uses \(O(L+\log(m+1))\)-bit integers.

Using ordinary integer arithmetic, a sufficient bound for certificate verification is
\(O((\tau m^2+\tau+m)(L+\log(m+1))^2)\)
bit operations. This is polynomial in \(m,\tau,L\), proving membership in \(\mathrm{NP}\).

Conclusion

Combining the reduction with certificate verification proves \(\mathrm{NP}\)-completeness for the precise support-based rational-mass formulation. The transfer uses aggregation and normalization of explicitly listed votes; it does not require expanding arbitrary rational masses into individual votes.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The reduction preserves both conditions exactly, and the certificate verification uses polynomially bounded integer arithmetic. No major or minor mathematical issues were found.

• The cited hardness result applies.

The source problem uses strict rankings, the sum of Kendall–Tau distances, and a positive integer threshold. These match the prover’s source-instance description. Section 2 defines positions starting at zero and candidate range as the maximum absolute difference of positions plus one, which equals the range in USER_TASK. Theorem 3 supplies the required hardness under average range at most \(2\); its construction actually produces average range strictly below \(2\). Thus the citation supports the restriction used in the reduction. [Betzler et al., Sections 2 and 5.2](https://aamas.csc.liv.ac.uk/Proceedings/aamas09/pdf/01_Full%20Papers/11_25_140_FP_0418.pdf)

There is no mismatch involving a zero threshold: the cited source problem explicitly requires a positive integer threshold.

• The constructed target instance is valid.

Grouping identical votes produces a nonempty support of distinct strict rankings. Each multiplicity \(n_t\) is positive, and their sum is \(n\). Consequently, the proposed masses \(\mu_t=n_t/n\) are positive rationals summing to \(1\).

Because \(k>0\) and \(n>0\), the proposed threshold \(B=k/n\) is positive. Both masses and threshold have binary numerator–denominator encodings, consistent with the explicitly stated interpretation of “binary rational.”

• The range restriction is preserved exactly.

For each candidate, grouping repeated rankings leaves the set of occurring positions unchanged. It therefore preserves both extrema and their difference. The displayed equality for \(r_a(\mu)\) is correct.

This step uses only the support, as required by USER_TASK. It does not mistakenly weight candidate ranges by vote multiplicities or rational masses.

• The score equivalence holds for every possible certificate.

The identity
\[ \sum_{t\in T_+}\mu_t\mathrm{KT}(\ell,t) =\frac1n\sum_{i=1}^{n}\mathrm{KT}(\ell,v_i) \]
correctly accounts for every occurrence of each source vote.

Multiplication by the positive integer \(n\) preserves the inequality direction. Hence the target score condition with threshold \(k/n\) is equivalent to the source score condition with threshold \(k\), for every strict ranking \(\ell\). This establishes both directions of the existential equivalence.

• The reduction has polynomial size and running time.

Explicit listing makes \(n\) polynomially bounded by the source input length. Grouping rankings and counting multiplicities are polynomial-time operations.

Each fraction \(n_t/n\) requires \(O(\log(n+1))\) bits, and \(k/n\) requires \(O(\log(k+1)+\log(n+1))\) bits. The displayed target-length bound accounts for the rankings and rational encodings and is polynomial in the source length.

No expansion of arbitrary target rational masses into votes is needed. The reduction constructs masses directly from explicitly listed source votes.

• The certificate and range checks are correct.

A strict ranking has the stated polynomial certificate length. Checking that every candidate occurs exactly once verifies certificate validity.

The range test is equivalent to the displayed integer inequality because \(m>0\). Computing positions and extrema over the nonempty support is well-defined, including when \(m=1\) or \(\tau=1\).

• The Kendall–Tau computation and exact rational comparison are correct.

Counting disagreeing unordered candidate pairs gives precisely Kendall–Tau distance. The bound \(0\le d_t\le\binom m2\) is correct.

Every denominator divides \(Q=b\prod_t q_t\), so the displayed divisions are exact. Clearing denominators by this positive integer preserves the score inequality.

The bit length of \(Q\) is bounded by the sum of the denominator encoding lengths, hence is \(O(L)\). Normalization gives the stated bound on the left-hand side. Its summands and partial sums are nonnegative, so they satisfy that bound as well. The right-hand side also has \(O(L)\) bits, since both \(a\) and \(Q\) have \(O(L)\) bits.

• The verification bound and conclusion follow.

Ordinary integer arithmetic on the stated operand sizes fits within
\[ O\bigl((\tau m^2+\tau+m)(L+\log(m+1))^2\bigr) \]
bit operations. This proves membership in \(\mathrm{NP}\).

Combined with the valid hardness reduction, it establishes \(\mathrm{NP}\)-completeness of the precise formulation in USER_TASK. The claimed equivalence between polynomial-time solvability and \(\mathrm{P}=\mathrm{NP}\) follows.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩