d4-conf-aaai-2021-0257 (d4-conf-aaai-2021-0257)

Given a finite support \(S\) of rankings over \(m\) candidates, with positive binary-rational masses \(\mu_R\) summing to \(1\), compute a ranking \(W\) minimizing \(\sum_{R\in S}\mu_R\,\mathrm{KT}(W,R)\).

Let \(m\ge 3\) candidates be given. A society is given by its support \(S\): the list of its \(\tau=|S|\) distinct types, each a strict linear order with positive binary-rational mass \(\mu_R\), where \(\sum_{R\in S}\mu_R=1\). The support size \(\tau\) is not the number \(m!\) of possible types; let \(L\) be the total input bit length.
Compute a strict linear order \(W\) minimizing \(\sum_{R\in S}\mu_R\,\mathrm{KT}(W,R)\), using unnormalized Kendall tau distance. Any minimizing ranking is acceptable.

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

For discrete Kemeny ranking, polynomial expected runtime under independent Mallows perturbations with fixed dispersion \(\varphi\in(0,1)\), uniformly over central profiles, would imply \(\mathrm{NP}=\mathrm{RP}\). [Source](https://arxiv.org/abs/2010.13020)
Computing a Kemeny optimum is NP-hard even for four equally weighted complete rankings. [Source](https://www.wisdom.weizmann.ac.il/~naor/PAPERS/rank_www10.html)

The optimization problem is \(\mathrm{NP}\text{-hard}\), even when \(\tau\le 4\) and every mass belongs to \(\{1/4,1/2,3/4,1\}\). Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\). Here \(m\) varies as part of the input; for fixed \(m\), enumerating all \(m!\) rankings suffices.

• Known hardness theorem. Dwork, Kumar, Naor, and Sivakumar prove that, given four complete strict rankings \(R_1,R_2,R_3,R_4\) on a common candidate set, computing a strict ranking minimizing

\(\displaystyle D(W)=\sum_{i=1}^{4}\mathrm{KT}(W,R_i)\)
is \(\mathrm{NP}\text{-hard}\). Their corresponding threshold decision problem is \(\mathrm{NP}\text{-complete}\). These are complete rankings, and Kendall distance counts disagreeing candidate pairs, as required here. [Theorem 11, Appendix B](https://www.wisdom.weizmann.ac.il/~naor/PAPERS/rank_www10.html).

• Reduction to a support representation. Take such a four-ranking instance. Let \(S\) contain exactly its distinct rankings. For each \(R\in S\), define its multiplicity and mass by

\(\displaystyle c_R=|\{i\in\{1,2,3,4\}:R_i=R\}|,\qquad \mu_R=c_R/4.\)

This is a valid instance of the requested problem: the support entries are distinct complete strict rankings, \(\tau\le 4\), every mass is positive and binary-rational, and
\(\displaystyle \sum_{R\in S}\mu_R=\frac14\sum_{R\in S}c_R=1.\)
In particular, the construction works even if the four original rankings contain repetitions.

Comparing the four lists and recording their multiplicities takes polynomial time. After relabeling candidates by integers from \(1\) through \(m\), the resulting input has bit length \(L=O(m\log m)\), because it stores at most four rankings and constant-length masses.

• Exact preservation of minimizers. For every strict ranking \(W\), its weighted objective satisfies

\(\displaystyle F(W)=\sum_{R\in S}\mu_R\,\mathrm{KT}(W,R)=\frac14\sum_{R\in S}c_R\,\mathrm{KT}(W,R)=\frac14D(W).\)

Multiplication by the positive constant \(1/4\) preserves all comparisons between objective values. Therefore
\(\displaystyle \operatorname*{arg\,min}_W F(W)=\operatorname*{arg\,min}_W D(W).\)
Thus any minimizing ranking returned for the constructed support instance solves the original four-ranking optimization problem.

• Complexity consequence. Suppose the requested algorithm ran in time polynomial in \(m,\tau,L\). On the constructed instances, \(\tau\le 4\) and \(L=O(m\log m)\), so its runtime would be polynomial in the original input length. Given an integer threshold \(B\), compute its output \(W^\star\), evaluate \(D(W^\star)\) by counting disagreeing pairs, and accept exactly when \(D(W^\star)\le B\). This decides the cited \(\mathrm{NP}\text{-complete}\) threshold problem in polynomial time, implying \(\mathrm{P}=\mathrm{NP}\).

The reduction uses only the listed support, with at most four types; it never constructs a table of all \(m!\) possible types.

⟨structured verdict parsed — rendered above⟩

The prover’s claim is proved. The cited hardness theorem applies, the reduction respects the support representation, and it preserves every minimizing ranking. No major or minor mathematical issues were found.

• The cited theorem is applicable.

Appendix B, Theorem 11 of Dwork, Kumar, Naor, and Sivakumar states hardness for an even number of complete rankings, including four, and states that the corresponding decision problem is NP-complete. Thus the prover correctly identifies a hard source problem with four complete strict rankings on a common candidate set. [Theorem 11, Appendix B](https://www.wisdom.weizmann.ac.il/~naor/PAPERS/rank_www10.html).

The source’s Kendall distance is the pairwise disagreement distance. Any uniform normalization of distance or averaging across the four rankings leaves the minimizers unchanged, so the prover’s unnormalized sum is compatible with the cited optimization theorem.

• The constructed instance satisfies every input restriction.

Grouping identical rankings produces exactly the distinct support types. Each multiplicity \(c_R\) is an integer between \(1\) and \(4\), so each mass \(\mu_R=c_R/4\) is positive, binary-rational, and belongs to the claimed set \(\{1/4,1/2,3/4,1\}\).

Every original ranking occurs in exactly one group, giving \(\sum_{R\in S}c_R=4\). Consequently, the displayed mass sum is exactly \(1\), and \(1\le\tau\le4\). Repetitions cause no difficulty.

The restriction \(m\ge3\) does not obstruct the hardness application: instances on fewer than three candidates have a bounded number of possible output rankings and can be handled directly.

• The reduction and encoding bounds are polynomial.

Comparing four explicitly listed rankings, merging duplicates, and recording multiplicities require polynomial time. Relabeling candidates preserves all pairwise comparisons and hence all Kendall distances.

With labels in \(\{1,\ldots,m\}\), each ranking requires \(O(m\log m)\) bits. There are at most four rankings, and each mass has constant encoding length. Therefore the asserted bound \(L=O(m\log m)\) is valid under the ordinary explicit-list encoding.

• The objective identity is exact and universally quantified.

For every feasible strict ranking \(W\), grouping the four summands according to identical input rankings gives precisely the prover’s identity \(F(W)=D(W)/4\).

Both problems optimize over the same finite set of strict rankings. Since the factor \(1/4\) is positive, it preserves strict comparisons and equalities. The claimed equality of minimizer sets follows. In particular, the argument correctly handles nonunique optima: any returned minimizer solves the source instance.

• The complexity consequence follows.

A runtime polynomial in \(m,\tau,L\) becomes polynomial in the explicit source input length on these constructed instances.

Evaluating the returned ranking’s four unnormalized Kendall distances requires only polynomially many pair comparisons. The resulting integer is exactly the minimum source objective. Comparing it with the supplied threshold therefore decides the source threshold problem, giving the stated implication \(\mathrm{P}=\mathrm{NP}\).

The use of a non-strict threshold is harmless because the objective is integer-valued; strict and non-strict integer threshold conventions are equivalent by shifting the threshold.

• The output resolves the assigned question.

The proof establishes hardness for the requested support encoding, already with at most four types and constant-length masses. It never relies on enumerating all possible types. The fixed-\(m\) enumeration remark is correct and does not conflict with hardness when \(m\) varies.

The Mallows perturbation statement is unnecessary for this worst-case reduction. Its omission creates no gap.

Actionable feedback: No repair or additional mathematical clarification is required.

⟨structured verdict parsed — rendered above⟩