Answer: —
Theorem 13 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any α, ϵ > 0, there is no ϵ-DP (α, 0.01m2)-approximation algorithm for rank aggregation in the central model for n = o(m/ϵ).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given (m), a society (\mu)\in\Delta(S_m)), (\eta>0), (\epsilon>0), and (\alpha)\ge1), design a polynomial-time randomized ranking mechanism (M) minimizing the worst-case (\beta) such that it is (\epsilon)-DP for every valid (\eta)-neighbor (\mu'=\mu+\eta(e_{\pi'}-e_{\pi})) and satisfies (\mathbb{E}[K_\mu(M(\mu))]\le\alpha\operatorname{OPT}(\mu)+\beta) for every (\mu).
Let \(S_m\) be the rankings of \(m\) items. A society is a rational, finitely supported distribution \(\mu\in\Delta(S_m)\), given by its support and weights. Define \(K_\mu(\sigma)=\sum_{\pi\in S_m}\mu(\pi)K(\sigma,\pi)\) and \(\operatorname{OPT}(\mu)=\min_{\sigma\in S_m}K_\mu(\sigma)\), where \(K\) is Kendall tau distance.
A valid \(\eta\)-neighbor is \(\mu'=\mu+\eta(e_{\pi'}-e_\pi)\in\Delta(S_m)\). A randomized mechanism \(M\) is \(\epsilon\)-DP if, for every valid neighbor pair and \(T\subseteq S_m\), \(\Pr[M(\mu)\in T]\le e^\epsilon\Pr[M(\mu')\in T]\). Its additive error is the least \(\beta\ge0\) such that \(\mathbb{E}[K_\mu(M(\mu))]\le\alpha\operatorname{OPT}(\mu)+\beta\) for every \(\mu\).
Is finding a polynomial-time \(\epsilon\)-DP ranking mechanism minimizing its worst-case additive error polynomial-time solvable, or is it NP-hard?
For finite profiles, Theorem 13 of the supplied source proves that, for every \(\alpha,\epsilon>0\), no central \(\epsilon\)-DP \((\alpha,0.01m^2)\)-approximation exists when \(n=o(m/\epsilon)\).
The target does not presently define a finite computational problem, so it cannot rigorously be classified as polynomial-time solvable or \(\mathsf{NP}\)-hard. The supplied Theorem 13 is an information-theoretic privacy–utility lower bound, not a computational hardness result.
Nevertheless, several relevant claims can be proved:
A computational problem requires a family of finitely encoded instances. Here \(M\) is itself an algorithm defined on every rational society, and its objective is
\(\sup_\mu\bigl(\mathbb E[K_\mu(M(\mu))]-\alpha\operatorname{OPT}(\mu)\bigr)\).
Thus “finding \(M\)” quantifies over algorithms rather than asking for an output associated with a finite input. The following information is missing:
In particular, “polynomial-time mechanism” is an asymptotic semantic property of an algorithm. It is not a finite constraint that can simply be included in an optimization problem.
The value of \(\eta\) also changes the adjacency structure substantially. Along every path of valid \(\eta\)-neighbors, each coordinate changes by an integral multiple of \(\eta\). Therefore, if \(\mu\) and \(\nu\) lie in the same connected component, then
\(\nu(\rho)-\mu(\rho)\in\eta\mathbb Z\)
for every \(\rho\in S_m\). Moreover, if every nonzero weight of \(\mu\) is strictly smaller than \(\eta\), then \(\mu\) is isolated: no coordinate can lose mass \(\eta\), and if another society transferred mass into \(\mu\), the receiving coordinate of \(\mu\) would have weight at least \(\eta\). If societies and their neighbors are required to remain rational, an irrational \(\eta\) yields no neighbor edges at all.
Consequently, a relationship such as \(\eta=1/n\) and a restriction to empirical \(n\)-voter societies is essential.
Fix \(n\in\mathbb N\), put \(\eta=1/n\), and define the empirical grid
\(\mathcal D_{m,n}=\{\mu:\mu(\pi)=h_\pi/n,\ h_\pi\in\mathbb Z_{\ge0},\ \sum_\pi h_\pi=n\}\).
Given a profile \(\Pi=(\pi_1,\ldots,\pi_n)\), let \(\mu_\Pi\) be its empirical distribution.
Suppose \(M\) is \(\epsilon\)-DP under the stated \(1/n\)-transfer adjacency. Define a finite-profile mechanism by
\(A(\Pi)=M(\mu_\Pi)\).
If \(\Pi'\) is obtained from \(\Pi\) by replacing one ranking \(\pi\) with \(\pi'\), then
\(\mu_{\Pi'}=\mu_\Pi+\frac1n(e_{\pi'}-e_\pi)\).
Thus \(\mu_\Pi\) and \(\mu_{\Pi'}\) are valid neighbors, so \(A\) is centrally \(\epsilon\)-DP. Furthermore,
\(K_{\mu_\Pi}(\sigma)=\frac1n\sum_{i=1}^nK(\sigma,\pi_i)\),
and hence the utility guarantees of \(M\) and \(A\) coincide on empirical societies.
It follows directly from [Theorem 13 of Alabi, Ghazi, Kumar, and Manurangsi](https://arxiv.org/abs/2112.14652) that, asymptotically when \(n=o(m/\epsilon)\), no mechanism on the full rational-distribution domain can have additive error at most \(0.01m^2\), for any fixed \(\alpha,\epsilon>0\).
This conclusion is information-theoretic: it excludes even computationally unbounded mechanisms. It does not establish \(\mathsf{NP}\)-hardness of finding the optimum mechanism.
Let \(U\) ignore its input and output a uniformly random element of \(S_m\). Because its output distribution is input-independent, \(U\) is \(0\)-DP and therefore \(\epsilon\)-DP for every \(\epsilon\ge0\).
Put \(C=\binom m2\). For every fixed \(\pi\in S_m\) and every unordered pair of items, a uniformly random ranking disagrees with \(\pi\) on that pair with probability \(1/2\). By linearity of expectation,
\(\mathbb E_{\sigma\sim U}[K(\sigma,\pi)]=C/2\).
Averaging over \(\pi\sim\mu\) gives
\(\mathbb E[K_\mu(U(\mu))]=C/2=\frac{m(m-1)}4\)
for every society \(\mu\). Since \(\operatorname{OPT}(\mu)\ge0\), the mechanism has additive error at most \(C/2\).
This value is exact: for a point mass \(\mu=e_\pi\), one has \(\operatorname{OPT}(\mu)=0\), while the expected loss remains \(C/2\). Thus the additive error of \(U\) is exactly
\(\frac12\binom m2=\frac{m(m-1)}4\).
Uniform sampling of a permutation is polynomial-time.
Let \(\pi\) be any ranking and let \(\bar\pi\) be its reverse. Then \(K(\pi,\bar\pi)=C\).
The point masses \(e_\pi\) and \(e_{\bar\pi}\) are joined in \(\mathcal D_{m,n}\) by the path
\(\mu_k=(1-k/n)e_\pi+(k/n)e_{\bar\pi}\),
where \(0\le k\le n\). Consecutive societies are valid \(1/n\)-neighbors. By composing the DP inequalities along this path, the output laws \(P=M(e_\pi)\) and \(Q=M(e_{\bar\pi})\) satisfy
\(P(T)\le e^{n\epsilon}Q(T)\)
and
\(Q(T)\le e^{n\epsilon}P(T)\)
for every \(T\subseteq S_m\).
Set \(R=e^{n\epsilon}\). Pointwise, the two inequalities imply
\(|P(\sigma)-Q(\sigma)|\le\frac{R-1}{R+1}\bigl(P(\sigma)+Q(\sigma)\bigr)\).
After summing over \(\sigma\), this gives
\(\operatorname{TV}(P,Q)\le\frac{R-1}{R+1}\).
Take a maximal coupling \(X\sim P\), \(Y\sim Q\), so that
\(\Pr[X\ne Y]=\operatorname{TV}(P,Q)\).
The triangle inequality and the diameter bound \(K(X,Y)\le C\mathbf 1_{\{X\ne Y\}}\) imply
\(C\le K(\pi,X)+K(X,Y)+K(Y,\bar\pi)\).
Taking expectations yields
\(\mathbb E[K(\pi,X)]+\mathbb E[K(Y,\bar\pi)]\ge C\bigl(1-\operatorname{TV}(P,Q)\bigr)\ge\frac{2C}{R+1}\).
Both point-mass societies have optimum zero. Therefore, if \(M\) has additive error \(\beta\), each expectation on the left is at most \(\beta\). Consequently,
\(\beta\ge\frac{C}{e^{n\epsilon}+1}\).
For \(\epsilon=0\), this lower bound is \(C/2\), matching the uniform mechanism. Hence:
Exact zero-privacy result. For \(\eta=1/n\), every \(\alpha\ge0\), and \(\epsilon=0\), the minimum possible worst-case additive error is exactly
\(\frac12\binom m2=\frac{m(m-1)}4\).
Computing \(\operatorname{OPT}(\mu)\), or an attaining ranking, is \(\mathsf{NP}\)-hard even when \(\mu\) has polynomial support.
Use the standard \(\mathsf{NP}\)-hard Minimum Feedback Arc Set in Tournaments problem; deterministic \(\mathsf{NP}\)-hardness is proved by [Charbit, Thomassé, and Yeo](https://perso.ens-lyon.fr/stephan.thomasse/liste/feedback.pdf).
Let \(T\) be a tournament on \(m\) vertices and let \(C=\binom m2\). For each arc \(a\to b\), choose an arbitrary ordering \(R_{ab}\) of the other \(m-2\) vertices and create the two rankings
\(a\succ b\succ R_{ab}\)
and
\(\operatorname{rev}(R_{ab})\succ a\succ b\).
These two rankings contribute pairwise margin \(2\) in favor of \(a\) over \(b\). Their contributions cancel for every other pair:
Taking these two rankings for every tournament arc produces \(N=2C\) rankings. Let \(\mu_T\) be their uniform distribution.
For every tournament arc \(a\to b\), exactly \(N/2+1\) profile rankings put \(a\) before \(b\), while \(N/2-1\) put \(b\) before \(a\). Let \(b_T(\sigma)\) be the number of tournament arcs directed backward in the order \(\sigma\). The contribution of a pair to the total Kendall loss is \(N/2-1\) when \(\sigma\) agrees with the tournament and \(N/2+1\) when it disagrees. Therefore,
\(N K_{\mu_T}(\sigma)=C(N/2-1)+2b_T(\sigma)\).
Thus \(\sigma\) minimizes \(K_{\mu_T}\) if and only if it minimizes \(b_T(\sigma)\), which is precisely Minimum Feedback Arc Set in Tournaments. The construction contains \(O(m^2)\) rankings of length \(m\) and has polynomial encoding length.
This proves \(\mathsf{NP}\)-hardness of the benchmark computation. It does not prove hardness of optimal private-mechanism synthesis, because that problem optimizes a single mechanism simultaneously over all societies and couples its behavior through DP constraints.
Let \(\mathcal X\) be a finite, explicitly listed set of societies, let \(E\) be its explicitly listed symmetric adjacency relation, and let the privacy multiplier \(\lambda\ge1\) be rational. For every \(x\in\mathcal X\) and \(\sigma\in S_m\), introduce a variable \(p_{x,\sigma}\), together with \(\beta\).
The optimal unrestricted mechanism is given by the linear program minimizing \(\beta\), subject to
\(p_{x,\sigma}\ge0\),
\(\sum_{\sigma\in S_m}p_{x,\sigma}=1\),
\(p_{x,\sigma}\le\lambda p_{y,\sigma}\) for every \((x,y)\in E\),
and
\(\sum_{\sigma\in S_m}p_{x,\sigma}K_x(\sigma)\le\alpha\operatorname{OPT}(x)+\beta\).
Singleton DP inequalities are equivalent to inequalities for arbitrary output events: summing the singleton inequalities proves the event inequality, while singleton events give the converse.
Hence this finite explicit problem is solvable in polynomial time in the size of the displayed LP. However, for the complete empirical domain,
\(|\mathcal D_{m,n}|=\binom{n+m!-1}{m!-1}\),
and the LP has \(|\mathcal D_{m,n}|m!\) probability variables. It is therefore not polynomial in the succinct parameters \(m\) and \(\log n\). Moreover, the LP describes an explicit lookup table and does not enforce that the mechanism have a succinct polynomial-time evaluator.
The rigorous conclusion is not that the requested mechanism-design problem is in \(\mathsf P\), nor that it is \(\mathsf{NP}\)-hard. As stated, it lacks the finite encoding needed for either classification.
The nearest established facts point in different directions: explicit finite mechanism design is a linear program, computing the underlying Kemeny optimum is \(\mathsf{NP}\)-hard, and Theorem 13 gives an unconditional utility lower bound. A new formulation and a reduction that handles the global DP constraints are required to obtain the requested complexity dichotomy.
⟨structured verdict parsed — rendered above⟩
The prover correctly identifies that the target, as stated, lacks the finite instance and output encodings required for a standard complexity classification. It therefore does not establish either polynomial-time solvability or \(\mathsf{NP}\)-hardness of optimal private-mechanism synthesis.
The ancillary mathematical results are mostly correct. The transfer of Theorem 13, the universal error calculation, the endpoint privacy lower bound, and the tournament reduction all withstand checking. There are several minor rigor defects, most notably a missing constraint in the finite-domain linear program and an unspecified randomness model for exact uniform sampling.
Accordingly, this is genuine but partial progress.
The diagnosis is substantively correct.
The target does not specify:
Without these, “polynomial-time solvable” and “\(\mathsf{NP}\)-hard” do not refer to a definite language or finite optimization problem.
The sentence asserting that quantification over algorithms itself prevents a computational classification is slightly overstated: algorithm- or circuit-synthesis problems can be finite computational problems once suitable encodings and size bounds are supplied. The subsequent list of missing data, however, supplies the real reason the present target is under-specified.
The observations about adjacency components are correct for nontrivial neighbor edges. Literally, the definition does not state \(\pi\ne\pi'\), so taking \(\pi=\pi'\) always gives the reflexive pair \(\mu'=\mu\). Thus “no neighbor edges at all” for irrational \(\eta\) should read “no edges between distinct societies,” unless distinct transferred rankings are incorporated into the definition.
This argument is correct.
For \(\eta=1/n\), replacing one profile ranking \(\pi\) by \(\pi'\) changes the empirical distribution by exactly
\[ \frac1n(e_{\pi'}-e_\pi). \]
Consequently, \(A(\Pi)=M(\mu_\Pi)\) inherits central \(\epsilon\)-DP from \(M\). The identity between normalized profile loss and distributional loss is also exact.
The cited statement of [Theorem 13](https://arxiv.org/abs/2112.14652) is accurately reproduced: for any \(\alpha,\epsilon>0\), no central \(\epsilon\)-DP \((\alpha,0.01m^2)\)-approximation exists when \(n=o(m/\epsilon)\). Restricting a mechanism defined on all rational societies to the empirical grid therefore gives the claimed information-theoretic obstruction.
The prover correctly does not infer computational hardness from this result.
The error calculation is correct.
With \(C=\binom m2\), a uniformly random ranking reverses each pair relative to a fixed ranking with probability \(1/2\). Hence its expected Kendall loss is \(C/2\) against every society. A point-mass society has optimum zero, proving that the worst-case additive error is exactly \(C/2=m(m-1)/4\).
Privacy is immediate because the output law is input-independent.
There is, however, a computational-model ambiguity. On a standard probabilistic Turing machine using fair random bits and required to halt in worst-case polynomial time, exact uniform sampling from \(m!\) outcomes is not automatic when \(m!\) is not a power of two. Rejection sampling gives expected polynomial time but unbounded worst-case time. The prover must state the randomness and running-time model under which “uniform sampling of a permutation is polynomial-time.”
This proof is correct.
The path from \(e_\pi\) to \(e_{\bar\pi}\) has \(n\) valid neighbor steps. Group privacy along this path gives the two likelihood-ratio inequalities with \(R=e^{n\epsilon}\).
For each output \(\sigma\), those inequalities imply
\[ |P(\sigma)-Q(\sigma)| \le \frac{R-1}{R+1}(P(\sigma)+Q(\sigma)). \]
Summation gives the stated total-variation bound. The maximal-coupling identity, Kendall triangle inequality, and diameter estimate then yield
\[ \mathbb E[K(\pi,X)]+\mathbb E[K(Y,\bar\pi)] \ge \frac{2C}{R+1}. \]
Because each point mass has optimum zero, each expectation is at most \(\beta\), so
\[ \beta\ge\frac{C}{e^{n\epsilon}+1}. \]
At \(\epsilon=0\), this equals \(C/2\), matching the upper bound.
The heading “zero-privacy result” is misleading: \(\epsilon=0\) is perfect privacy, not absence of privacy. The formula and argument themselves are unaffected.
The reduction is correct.
For every tournament arc \(a\to b\), the two constructed rankings contribute margin \(2\) toward \(a\succ b\) and cancel on every other unordered pair. Therefore the resulting profile has pairwise margin exactly \(2\) in the direction of each tournament arc.
With \(N=2C\), an order agreeing with an arc contributes \(N/2-1\) to total loss on that pair, while disagreement contributes \(N/2+1\). Hence
\[ N K_{\mu_T}(\sigma) = C(N/2-1)+2b_T(\sigma). \]
Thus exact computation of \(\operatorname{OPT}(\mu_T)\), or of an optimizer, determines a minimum-backward-arc ordering. The cited result of [Charbit, Thomassé, and Yeo](https://www.cambridge.org/core/journals/combinatorics-probability-and-computing/article/abs/minimum-feedback-arc-set-problem-is-nphard-for-tournaments/042E28CA7AA5E6555592DEEE671EA3FA) confirms deterministic \(\mathsf{NP}\)-hardness for tournaments.
One routine equivalence is omitted: the prover should explicitly justify that minimizing backward arcs over vertex orders is equivalent to minimum feedback arc set in a tournament. This is standard but is the exact bridge needed to apply the cited theorem.
The prover correctly notes that benchmark hardness does not imply hardness of globally optimal DP-mechanism synthesis.
The privacy and normalization constraints correctly encode a randomized mechanism on a finite explicitly enumerated domain. Because the output space is finite, singleton privacy inequalities are equivalent to event inequalities.
There is one concrete error: the linear program omits the required constraint
\[ \beta\ge0. \]
This matters for arbitrary finite domains. For example, if the domain contains a single society with positive optimum and \(\alpha>1\), the displayed LP can attain a negative \(\beta\), whereas additive error was defined as the least nonnegative value satisfying the guarantee. Thus the displayed LP does not always compute the defined additive error.
The polynomial-time statement is otherwise appropriately limited to the size of the fully displayed LP. The factorial number of outputs and the stars-and-bars count
\[ |\mathcal D_{m,n}|=\binom{n+m!-1}{m!-1} \]
are correct. This explicit lookup-table formulation does not provide a succinct polynomial-time evaluator.
The prover does not answer the requested dichotomy. It establishes neither:
This is not concealed: the conclusion explicitly acknowledges that a new finite formulation and additional complexity argument are required. The response therefore contains substantial valid progress but leaves the target unresolved.
To make the current write-up fully verifiable on its own terms, the prover must:
⟨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.