Answer: polynomial-time solvable
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet P ∈ (Pn(ψ, r, A) ∩PST n ) be the true underlying preference ma- trix according to which the pairwise comparison dataset S = {(i, j, {yk ij})} is generated.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(n\) alternatives with known item features and a rational finite-support society \(\mu\) over complete rankings, accessible through independent type samples, define \(P^\mu_{ij}=\Pr_{t\sim\mu}[i\succ_t j]\). If \(P^\mu\in\mathcal P_n(\psi,r,A)\cap\mathcal P_n^{ST}\) and satisfies the theorem's margin and conditioning assumptions, how many uniformly sampled item pairs and independent type samples per pair suffice for an algorithm to return a ranking whose normalized pairwise disagreement with \(P^\mu\) is at most \(\varepsilon\) with probability at least \(1-\delta\)?
There are \(m\ge2\) alternatives. A society is given by its support: \(\tau\) strict complete rankings with positive binary-rational masses summing to \(1\); \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length.
Known features form a full-row-rank matrix \(A\in\mathbb Q^{d\times m}\), where \(1\le d\le m\). A fixed strictly increasing bijection \(\psi:(0,1)\to\mathbb R\), and its inverse, are computable to requested precision in polynomial time.
Define \(P_{ij}=\Pr_{t\sim\mu}[i\succ_t j]\) for \(i\ne j\), and \(P_{ii}=1/2\). Promise that \(\psi(P)=A^\top B A\) entrywise for some real \(B\in\mathbb R^{d\times d}\) with \(\operatorname{rank}(B)\le r\le d\), and that \(P_{ij}>1/2\) and \(P_{jk}>1/2\) imply \(P_{ik}>1/2\).
Require \(p_{\min}=\min_{i\ne j}P_{ij}>0\), \(\Delta=\min_{i\ne j}|\psi(P_{ij})-\psi(1/2)|>0\), and that \(\psi\) is \(\ell\)-Lipschitz on \([p_{\min}/2,1-p_{\min}/2]\). Write \(\kappa=\sigma_{\min}(A)/\sigma_{\max}(A)>0\), with \(\kappa^4\le C_2d\) for the fixed universal constant appearing below.
A sampling experiment chooses \(s\le\binom m2\) distinct unordered pairs uniformly without replacement. Each selected pair receives \(K\ge1\) fresh independent draws from \(\mu\), each yielding its binary comparison outcome; draws are independent across pairs as well.
For a strict output ranking \(\sigma\), define \(D(\sigma,P)=\binom m2^{-1}\sum_{i<j}\mathbf1\{\sigma\text{ places the majority-preferred alternative below the other}\}\). Let \(0<\varepsilon,\delta<1\); state running times in \(m,\tau,L,d,r,s,K\) and the accuracy, confidence, margin, Lipschitz, and conditioning parameters.
Is producing \(\sigma\) with \(D(\sigma,P)\le\varepsilon\) with probability at least \(1-\delta\) polynomial-time solvable, or NP-hard? What budgets \(s\) and \(K\) of uniformly sampled pairs and independent type samples per pair suffice?
The [known algorithmic guarantee](https://arxiv.org/pdf/1702.02661) asserts error at most \(\varepsilon\), with failure probability at most \(3/m^3\), when \(s>48C_2^2d^2\log(m)(1+\gamma)^2/(\kappa^8\varepsilon^2\Delta^4)\) and \(K\ge16(1+\gamma)s\ell^2\log(m)/(m^2\Delta^2\varepsilon)\), using \(\gamma=5\).
That guarantee is formulated for independent binary observations with means \(P_{ij}\), without requiring a finite list of agents. Independent type sampling has this observation law, so the distributional sampling model is already within its stated scope.
The promised problem is polynomial-time solvable. Because the support and its masses are explicitly given, an exact majority-consistent ranking can be computed deterministically in polynomial time.
For the intended learning interpretation, where the algorithm uses only the sampled comparisons, the following budgets also suffice for every \(\varepsilon,\delta\in(0,1)\). Write \(N=\binom m2\), and take
\(\displaystyle s=\min\left\{N,\left\lceil\frac{m\log m+\log(2/\delta)}{\varepsilon}\right\rceil\right\},\)
\(\displaystyle K=\max\left\{1,\left\lceil\frac{\ell^2}{2\Delta^2}\log\frac{2s}{\delta}\right\rceil\right\}.\)
A polynomial-time algorithm then produces \(\sigma\) satisfying \(D(\sigma,P)\le\varepsilon\) with probability at least \(1-\delta\).
These are sufficient budgets, without a claim of optimality. The supplied feature-based guarantee gives an additional budget in its feasible confidence regime, stated in Section 5.
Define \(i\succ^\star j\) to mean \(P_{ij}>1/2\).
Every supported ranking is strict and complete, so \(P_{ij}+P_{ji}=1\). Moreover, \(\Delta>0\) and strict monotonicity of \(\psi\) imply \(P_{ij}\ne1/2\) whenever \(i\ne j\). Consequently, exactly one of \(i\succ^\star j\) and \(j\succ^\star i\) holds.
The promised transitivity condition is precisely transitivity of \(\succ^\star\). Thus \(\succ^\star\) is a strict total order. Let \(\sigma^\star\) denote its unique ranking. By definition,
\(\displaystyle D(\sigma^\star,P)=0.\)
This is the property that makes the present promise problem computationally tractable.
Let the supported rankings be \(\rho_1,\ldots,\rho_\tau\), with masses \(w_1,\ldots,w_\tau\). Compute
\(\displaystyle P_{ij}=\sum_{t=1}^{\tau}w_t\,\mathbf1\{i\succ_{\rho_t}j\}.\)
All comparisons with \(1/2\) can be performed exactly using rational arithmetic.
For completeness, write \(w_t=a_t/b_t\), and choose the common denominator \(Q=\prod_{t=1}^{\tau}b_t\). Its bit length is at most the sum of the denominator bit lengths, hence \(O(L)\). The integers \(W_t=Qw_t\) satisfy \(\sum_t W_t=Q\). Therefore,
\(\displaystyle P_{ij}>1/2\quad\Longleftrightarrow\quad 2\sum_{t=1}^{\tau}W_t\mathbf1\{i\succ_{\rho_t}j\}>Q.\)
No evaluation of \(\psi\), recovery of \(B\), or numerical margin estimation is needed.
After computing the majority relation, assign each alternative its number of majority wins and sort decreasingly. An alternative in position \(k\) of the strict total order has exactly \(m-k\) wins, so this recovers \(\sigma^\star\).
Using schoolbook integer arithmetic, a conservative running-time bound is \(O(\tau m^2L^2)\) bit operations. The algorithm is deterministic and returns error zero. Its runtime has no dependence on inverse accuracy, margin, or conditioning parameters.
Thus the literal explicit-support problem requires no samples. If the sampling experiment must nevertheless be executed, any permitted sample budget can be ignored by this algorithm.
Define
\(\displaystyle g=\min_{i\ne j}|P_{ij}-1/2|.\)
The complementarity identity implies \(P_{ij}\in[p_{\min},1-p_{\min}]\). Both \(P_{ij}\) and \(1/2\) therefore belong to the interval on which \(\psi\) is \(\ell\)-Lipschitz. Hence, for every distinct pair,
\(\displaystyle \Delta\le|\psi(P_{ij})-\psi(1/2)| \le\ell|P_{ij}-1/2|.\)
It follows that \(g\ge\Delta/\ell>0\).
A certified upper bound on \(\ell\) and a certified positive lower bound on \(\Delta\) may replace their exact values in the budget.
Let \(S\) be the uniformly sampled set of \(s\) unordered pairs.
For each selected pair, estimate its comparison probability by its empirical mean over the \(K\) draws. Orient an edge according to the empirical majority, breaking an empirical tie by a fixed rule.
If the resulting directed graph is acyclic, output any topological ordering. Otherwise, output an arbitrary strict ranking.
We prove that, with probability at least \(1-\delta\), the graph is acyclic and every one of its topological orderings has the required error.
Fix the selected set \(S\). For any selected pair, its observations are independent Bernoulli random variables with the corresponding mean \(P_{ij}\).
The one-sided Hoeffding inequality states that the probability an empirical mean deviates from its expectation by at least \(t>0\) in a specified direction is at most \(\exp(-2Kt^2)\). An incorrect orientation, including an unfavourably broken empirical tie, requires such a deviation with \(t=|P_{ij}-1/2|\). Therefore,
\(\displaystyle \Pr(\text{incorrect orientation for this pair}\mid S) \le e^{-2Kg^2} \le e^{-2K\Delta^2/\ell^2}.\)
The stated choice of \(K\) makes this at most \(\delta/(2s)\). A union bound gives
\(\displaystyle \Pr(\text{some sampled orientation is incorrect})\le\delta/2.\)
When all orientations are correct, the graph is a subgraph of the strict total order \(\sigma^\star\), so it is acyclic.
Fix a ranking \(\sigma\) with \(D(\sigma,P)>\varepsilon\). Let \(T_\sigma\) be its set of inverted pairs relative to \(\sigma^\star\), and write \(t=|T_\sigma|\). Then \(t>\varepsilon N\).
If \(s>N-t\), the sampled set must intersect \(T_\sigma\). Otherwise, sampling without replacement gives
\(\displaystyle \Pr(S\cap T_\sigma=\varnothing) =\frac{\binom{N-t}{s}}{\binom Ns} =\prod_{a=0}^{s-1}\left(1-\frac{t}{N-a}\right) \le\left(1-\frac{t}{N}\right)^s \le e^{-st/N} \le e^{-\varepsilon s}.\)
There are \(m!\) strict rankings. Thus
\(\displaystyle \Pr\bigl(\exists\sigma:\ D(\sigma,P)>\varepsilon,\ S\cap T_\sigma=\varnothing\bigr) \le m!e^{-\varepsilon s}.\)
If the stated choice of \(s\) is smaller than \(N\), then \(\log(m!)\le m\log m\) shows that this probability is at most \(\delta/2\). If \(s=N\), the event is impossible.
With probability at least \(1-\delta\), both of the following hold:
On this event, the algorithm returns a topological ordering and hence reverses no sampled edge. The second property forces its error to be at most \(\varepsilon\).
This proves the claimed guarantee.
The number of independent type draws is \(sK\), with
\(\displaystyle sK=O\left( s\left[1+\frac{\ell^2}{\Delta^2}\log\frac{2s}{\delta}\right] \right).\)
With comparison observations supplied, constructing empirical means and topologically sorting the graph take polynomial time in \(m,s,K\). A straightforward implementation, including uniform-pair generation, uses expected
\(\displaystyle O\left( L+m^2\log(m+1)+sK\log(K+1)+(m+s)\log(m+1) \right)\)
bit operations.
If draws are simulated from the given support, first store each ranking’s position array and the cumulative integer masses \(W_t\). A draw can then be generated by selecting a uniform integer in \(\{0,\ldots,Q-1\}\), locating its cumulative-mass interval, and looking up the pair’s order. Exact rejection sampling and binary search give expected \(O(L\log(\tau+1))\) bit operations per draw. The resulting total runtime remains polynomial in \(m,\tau,L,s,K\).
These sampling budgets depend polynomially on \(\varepsilon^{-1}\) and \(\ell/\Delta\), and logarithmically on \(\delta^{-1}\). They require no dependence on \(d,r,\kappa\). If the probability margin is exponentially small in \(L\), this observation-only sample budget can be exponential in \(L\); the deterministic explicit-support algorithm remains polynomial in \(L\).
Using the guarantee stipulated in the question, with \(\gamma=5\), define
\(\displaystyle T_{\mathrm{FLR}} =\frac{1728C_2^2d^2\log m} {\kappa^8\varepsilon^2\Delta^4}, \qquad s_{\mathrm{FLR}}=\lfloor T_{\mathrm{FLR}}\rfloor+1.\)
Provided \(s_{\mathrm{FLR}}\le N\), sufficient budgets are
\(\displaystyle s=s_{\mathrm{FLR}},\)
\(\displaystyle K\ge \max\left\{1, \left\lceil \frac{96s\ell^2\log m} {m^2\Delta^2\varepsilon} \right\rceil \right\}.\)
The stated failure probability is at most \(3/m^3\), so these budgets meet the requested confidence whenever \(\delta\ge3/m^3\). This is the feature-based guarantee of [Niranjan and Rajkumar](https://arxiv.org/pdf/1702.02661).
Its observation-law hypothesis holds here: a fresh type draw produces a Bernoulli outcome with mean \(P_{ij}\), and the prescribed independence of type draws gives independence of observations. The finite support size \(\tau\) introduces no additional statistical condition.
The strict pair threshold must remain feasible: when \(s_{\mathrm{FLR}}>N\), replacing it by \(N\) does not satisfy that theorem’s hypothesis. For either infeasible feature budgets or confidence \(\delta<3/m^3\), Section 4 supplies a proved polynomial-time alternative with the requested guarantee.
⟨structured verdict parsed — rendered above⟩
The output resolves the task. The deterministic algorithm correctly establishes polynomial-time solvability for the explicit-support input, and the separate sampling argument establishes the stated sufficient budgets for every requested accuracy and confidence. I found no major or minor mathematical issues.
Strict complete rankings give \(P_{ij}+P_{ji}=1\). The assumptions \(p_{\min}>0\) and complementarity also ensure that every off-diagonal probability lies in the domain \((0,1)\) of \(\psi\).
Since \(\Delta>0\), no off-diagonal entry satisfies \(\psi(P_{ij})=\psi(1/2)\). Strict monotonicity therefore excludes \(P_{ij}=1/2\). Consequently, precisely one direction is majority-preferred for each unordered pair.
The promised implication supplies transitivity. Completeness, asymmetry, and transitivity establish the claimed strict total order and its unique ranking \(\sigma^\star\). The assertion \(D(\sigma^\star,P)=0\) follows directly from the definition of \(D\).
The formula for \(P_{ij}\) correctly sums the masses of the supported rankings preferring \(i\) to \(j\).
The product denominator \(Q\) has bit length bounded by the sum of the input denominator bit lengths. Each \(W_t=Qw_t\) is an integer, and normalization gives \(\sum_tW_t=Q\). Thus the displayed integer comparison with \(Q\) decides each majority direction exactly.
The denominator construction, integer arithmetic, and pairwise accumulation have polynomial bit complexity. The conservative bound \(O(\tau m^2L^2)\) accommodates these operations and the ranking-position preprocessing.
In a strict total order, the alternative at position \(k\) has exactly \(m-k\) wins. These counts are distinct, so decreasing win-count sorting recovers \(\sigma^\star\) without a tie-handling gap.
Accordingly, the explicit-support algorithm is deterministic, polynomial in the stated input parameters, and independent of inverse margin, accuracy, and conditioning parameters. Ignoring sampled observations is legitimate for this input model. The output also addresses the intended observation-only interpretation separately.
Complementarity gives \(P_{ij}\in[p_{\min},1-p_{\min}]\), and \(p_{\min}\le1/2\). Thus both \(P_{ij}\) and \(1/2\) lie in the stipulated Lipschitz interval.
Applying the Lipschitz bound yields
\(\Delta\le\ell|P_{ij}-1/2|\) for every distinct pair. Taking the minimum proves \(g\ge\Delta/\ell>0\).
Using an upper bound for \(\ell\) and a positive lower bound for \(\Delta\) only increases the required sample budget, so the proposed certified-bound substitution is valid.
Conditional on the selected pair set, each pair receives \(K\) independent Bernoulli observations with its specified mean. This satisfies the hypotheses of the stated one-sided Hoeffding inequality.
A wrong orientation requires a deviation toward or across \(1/2\) of magnitude at least \(|P_{ij}-1/2|\). Including equality correctly covers an unfavorably resolved empirical tie.
Therefore the per-pair failure probability is bounded by
\(e^{-2K\Delta^2/\ell^2}\). The proposed ceiling in \(K\) makes this at most \(\delta/(2s)\), and the union bound gives total orientation failure probability at most \(\delta/2\).
Correctly oriented sampled edges form a subgraph of \(\sigma^\star\), so acyclicity follows.
For a fixed ranking with error greater than \(\varepsilon\), its inversion set has size \(t>\varepsilon N\).
If \(s>N-t\), avoidance is impossible. Otherwise, the displayed hypergeometric probability and product formula are correct. Every factor is nonnegative and bounded above by \(1-t/N\), giving the claimed bound \(e^{-\varepsilon s}\).
Union-bounding over all \(m!\) rankings is legitimate; no independence between rankings is required. The inequality \(\log(m!)\le m\log m\) verifies the stated sufficient threshold.
The truncation at \(N\) is handled correctly: when all pairs are selected, every nonempty inversion set is intersected. Thus this case does not require the untruncated threshold to hold.
A union bound gives simultaneous occurrence of correct sampled orientations and exclusion of every ranking with error greater than \(\varepsilon\), with probability at least \(1-\delta\).
On that event, the graph is acyclic. Every topological ordering respects all sampled edges and therefore cannot be one of the excluded inaccurate rankings.
This reasoning applies even though the output ranking depends on the sampled data: the exclusion event was established simultaneously for all rankings. No conditional-independence assumption is missing.
The total number of type draws is exactly \(sK\). The stated asymptotic bound follows from the ceiling and the lower bound \(K\ge1\).
Empirical counting, graph construction, and topological sorting have the claimed polynomial cost. Uniform pair selection can be implemented within the stated \(m^2\log(m+1)\) allowance.
The support-based simulation is also valid: uniform integer sampling followed by cumulative-mass lookup produces type \(t\) with probability \(W_t/Q=w_t\). Exact rejection sampling has bounded expected repetitions, and binary search gives the claimed expected polynomial per-draw cost. The output explicitly labels these runtime bounds as expected.
The distinction between polynomial dependence on \(\ell/\Delta\) and polynomial dependence on input bit length is correctly stated. An exponentially small probability margin can make this observation-only budget exponential in \(L\), while the exact-support algorithm remains polynomial in \(L\).
Substituting \(\gamma=5\) gives \(48(1+\gamma)^2=1728\) and \(16(1+\gamma)=96\). The choice \(\lfloor T_{\mathrm{FLR}}\rfloor+1\) correctly enforces the strict pair threshold, including when the threshold is an integer.
The representation, transitivity, margin, Lipschitz, and conditioning hypotheses are supplied by the task promises. Fresh independent type draws satisfy the required binary-observation law. The cited theorem’s displayed thresholds and failure probability agree with those used in the output. [Niranjan and Rajkumar, Theorem 1](https://arxiv.org/pdf/1702.02661)
The restriction \(\delta\ge3/m^3\) is necessary for obtaining the requested confidence directly from that guarantee. The output correctly preserves this restriction and correctly refuses to infer the theorem’s conclusion by truncating an infeasible strict threshold to \(N\).
The independent argument in Section 4 supplies the requested guarantee outside those regimes. No further theorem, amplification argument, or feature-recovery analysis is needed to establish the output’s overall claim.
No repair or additional clarification is needed to verify the argument.
⟨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.