Answer: All three guarantees hold. The explicit PTAS sampling bound uses \(e=\min\{\epsilon,1\}\), agreeing with the stated inverse-square bound for \(0<\epsilon\le1\); larger fixed accuracies use \(e=1\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIt is possible to compute a ranking that pro- vides a (1 + ϵ)-approximation to the optimal ranking with probability at least 1 −δ in two ways: 1. Asking O(m4 log(m/δ)/ϵ2) random voters for each pair- wise comparison, and running a PTAS for FAST on the tournament with estimated weights, which guarantees polynomial running time. 2. Asking O(log(m/δ)/ϵ2) random voters for each pairwise comparison, and running an exact solver for FAST on the tournament with estimated weights (assuming ϵ < 1/3), which does not guarantee polynomial running time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given alternatives \(A\) and a finite support of uncertainty types \(t\), with rational masses \(\mu_t\) and pairwise probabilities \(q_t(a,b)=\Pr_{D_t}[a\succ b]\) realizable by distributions over rankings, find a ranking \(\hat\sigma\) minimizing \(H_\mu(\sigma)=\sum_t\mu_t\mathbb{E}_{\rho\sim D_t}[d_{\mathrm{KT}}(\sigma,\rho)] = \sum_{a\succ_\sigma b}\sum_t\mu_t q_t(b,a)\), or return one satisfying \(H_\mu(\hat\sigma)\le(1+\epsilon)\min_\sigma H_\mu(\sigma)\). In the sample-access variant, each draw samples \(t\sim\mu\) and returns \(q_t(a,b)\) for a queried pair; determine whether the paper’s two guarantees hold: \(O(m^4\log(m/\delta)/\epsilon^2)\) draws per pair followed by the FAST PTAS, or \(O(\log(m/\delta)/\epsilon^2)\) followed by an exact FAST solver when \(\epsilon<1/3\), with success probability at least \(1-\delta\).
Let \(A\) contain \(m\ge2\) alternatives; all input and output rankings are strict total orders. A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type supplies binary-rational probabilities \(q_t(a,b)\in[0,1]\), promised jointly realizable by some distribution \(D_t\) over rankings; thus \(q_t(a,b)+q_t(b,a)=1\). The distributions themselves need not be supplied.
For a ranking \(\sigma\), define \(H_\mu(\sigma)=\sum_t\mu_t\mathbb E_{\rho\sim D_t}[d_{\mathrm{KT}}(\sigma,\rho)]=\sum_{a\succ_\sigma b}\sum_t\mu_tq_t(b,a)\), using Kendall tau distance. Any minimizing ranking is acceptable when there are ties.
In the sample-access variant, the probability tables are hidden: each query names a distinct pair and independently draws \(t\sim\mu\), returning the exact value \(q_t(a,b)\). Estimated weights are empirical means, with reverse weights their complements.
Here weighted FAST minimizes \(\sum_{a\succ_\sigma b}w_{ba}\) for nonnegative directed weights satisfying \(w_{ab}+w_{ba}=1\). Let \(L\) denote the total binary description length, including the underlying probability tables and rational accuracy parameters; state running times in \(m,\tau,L,\epsilon,\delta\).
Does minimizing \(H_\mu\) admit a \((1+\epsilon)\)-approximation in polynomial time in \(m,\tau,L,\log(1/\delta)\) for each fixed \(\epsilon>0\), with success probability at least \(1-\delta\), where \(0<\delta<1\)?
Do \(O(m^4\log(m/\delta)/\epsilon^2)\) draws per unordered pair followed by a weighted FAST PTAS retain this guarantee?
Do \(O(\log(m/\delta)/\epsilon^2)\) draws per unordered pair followed by an exact weighted FAST solver retain it for \(0<\epsilon<1/3\), without requiring polynomial solver time?
For finite equally weighted uncertain voters, both sampling and approximation guarantees above are established by [Procaccia–Shah](https://procaccia.info/wp-content/uploads/2020/03/uncertainty.pdf).
[Kenyon-Mathieu–Schudy](https://cs.brown.edu/~claire/Publis/kenyonschudy.pdf) establish a PTAS for nonnegative weighted FAST with complementary pair weights; this includes the numerical weight domain specified here.
Yes to all three questions. The proofs below work directly with the supplied support and rational masses.
Write \(e=\min\{\epsilon,1\}\). The first two algorithms attain a \((1+e)\)-approximation, hence a \((1+\epsilon)\)-approximation. Their explicit inverse-square sampling bound is \(O(m^4\log(m/\delta)/e^2)\), which is the stated bound in the usual accuracy range \(0<\epsilon\le1\). Larger fixed accuracies are handled by running with accuracy \(1\). The third question already assumes \(0<\epsilon<1/3\).
Define \(w_{ab}=\sum_{t=1}^{\tau}\mu_tq_t(a,b)\) for distinct alternatives \(a,b\). Nonnegativity, normalization, and complementary probabilities imply
\(w_{ab}\ge0,\qquad w_{ab}+w_{ba}=\sum_t\mu_t=1.\)
For any ranking \(\sigma\), linearity of expectation gives
\(H_\mu(\sigma)=\sum_{t=1}^{\tau}\mu_t\sum_{a\succ_\sigma b}\Pr_{\rho\sim D_t}[b\succ_\rho a]=\sum_{a\succ_\sigma b}w_{ba}.\)
Thus the objectives agree exactly, including their minimizing rankings. Computing these weights requires only the pairwise tables, rather than distributions realizing them.
The weighted FAST PTAS of [Kenyon-Mathieu–Schudy, Theorem 1](https://cs.brown.edu/~claire/Publis/kenyonschudy.pdf) applies to nonnegative weights with complementary pair weights. Both the exact weights above and the empirical weights below satisfy these hypotheses.
We use the following consequence of that theorem. For accuracy \(\alpha>0\), a rational weighted FAST instance of description length \(B\) can be approximated within \(1+\alpha\), with failure probability at most \(\zeta\), in time
\(m^{g(1/\alpha)}\operatorname{poly}(B)\log(2/\zeta),\)
for some function \(g\) depending only on the PTAS. The logarithmic confidence dependence can also be obtained by independently repeating a constant-success version and retaining the ranking with smallest exactly evaluated cost.
The aggregate weights have polynomial description length: a common denominator can be formed from the input denominators, whose total binary length is bounded by \(L\). Consequently, constructing the aggregate instance and applying the PTAS with accuracy \(e\) gives running time
\(O(\tau m^2)\operatorname{poly}(L)+m^{g(1/e)}\operatorname{poly}(m,L)\log(2/\delta).\)
For every fixed \(\epsilon>0\), this is polynomial in \(m,\tau,L,\log(1/\delta)\), and the success probability is at least \(1-\delta\). This proves the first guarantee.
Let \(F\) and \(\widehat F\) denote ranking costs under true and estimated complementary weights. Suppose
\(\max_{a\ne b}|w_{ab}-\widehat w_{ab}|\le r.\)
Write \(N=\binom m2\).
If two rankings \(\pi,\sigma\) disagree on \(k\) unordered pairs, then
\(F(\pi)+F(\sigma)\ge k.\)
Indeed, on every disagreement pair their two costs sum to \(w_{ab}+w_{ba}=1\); all remaining contributions are nonnegative.
In particular, distinct rankings have costs whose sum is at least \(1\).
Let \(\sigma^\star\) minimize \(F\), and write \(C=F(\sigma^\star)\). Suppose an algorithm returns \(\widehat\sigma\) satisfying
\(\widehat F(\widehat\sigma)\le(1+\beta)\min_\sigma\widehat F(\sigma).\)
Every ranking uses exactly one weight from each unordered pair, so
\(|F(\sigma)-\widehat F(\sigma)|\le Nr.\)
It follows that
\(F(\widehat\sigma)\le(1+\beta)C+(2+\beta)Nr.\)
Take \(\beta=e/2\) and \(r=e/(32N)\). Since \(e\le1\),
\(F(\widehat\sigma)\le(1+e/2)C+5e/64.\)
There are two cases.
Thus the transfer guarantee holds even when the optimum is zero or arbitrarily small.
Now suppose \(\widehat\sigma\) minimizes \(\widehat F\) exactly. Let \(k\) be its number of disagreement pairs with \(\sigma^\star\), and write \(Y=F(\widehat\sigma)\).
The contributions of agreement pairs cancel when comparing the two rankings. Estimated optimality and the error bound therefore imply
\(Y-C\le2rk.\)
The disagreement bound gives \(k\le Y+C\). For \(r<1/2\), combining these inequalities yields
\((1-2r)Y\le(1+2r)C,\qquad Y\le\frac{1+2r}{1-2r}C.\)
This is the complementary-weight specialization of the perturbation argument in [Procaccia–Shah, Lemma 1](https://procaccia.info/wp-content/uploads/2020/03/uncertainty.pdf). Choosing
\(r=\frac{\epsilon}{4+2\epsilon}\)
makes the last ratio exactly \(1+\epsilon\). This argument also covers \(C=0\), and every possible tie choice by the exact solver.
Fix one orientation for each unordered pair. For that orientation, each query returns a random variable \(X=q_T(a,b)\), where \(T\sim\mu\). Thus
\(0\le X\le1,\qquad \mathbb E[X]=\sum_t\mu_tq_t(a,b)=w_{ab}.\)
With \(s\) independent draws, let \(\widehat w_{ab}\) be their empirical mean and set \(\widehat w_{ba}=1-\widehat w_{ab}\). Hoeffding’s inequality gives
\(\Pr[|\widehat w_{ab}-w_{ab}|>r]\le2\exp(-2sr^2).\)
Reverse weights have the same error. A union bound over the \(N\) unordered pairs consequently gives
\(\Pr[\max_{a\ne b}|\widehat w_{ab}-w_{ab}|>r]\le2N\exp(-2sr^2).\)
Take \(r=e/(32N)\) and
\(s_{\mathrm P}=\left\lceil\frac{512N^2}{e^2}\log\frac{4N}{\delta}\right\rceil.\)
With probability at least \(1-\delta/2\), all weight errors meet the perturbation bound. Apply the weighted FAST PTAS to the empirical instance with accuracy \(e/2\) and failure probability at most \(\delta/2\). Conditional on any empirical instance, its stated guarantee applies because the weights are nonnegative and complementary.
The approximate-optimizer transfer proved above then gives
\(H_\mu(\widehat\sigma)\le(1+e)\min_\sigma H_\mu(\sigma).\)
The total failure probability is at most \(\delta\). Moreover,
\(s_{\mathrm P}=O(m^4\log(m/\delta)/e^2)\)
draws suffice per unordered pair.
Independent sampling across pairs need not produce jointly realizable empirical marginals. This causes no difficulty: the weighted FAST theorem and both perturbation arguments require only nonnegative complementary weights.
Take \(r=\epsilon/(4+2\epsilon)\) and
\(s_{\mathrm E}=\left\lceil\frac{(4+2\epsilon)^2}{2\epsilon^2}\log\frac{2N}{\delta}\right\rceil.\)
The same concentration calculation shows that every weight error is at most \(r\), with probability at least \(1-\delta\). On that event, an exact empirical optimizer satisfies
\(H_\mu(\widehat\sigma)\le(1+\epsilon)\min_\sigma H_\mu(\sigma).\)
For \(0<\epsilon<1/3\),
\(s_{\mathrm E}=O(\log(m/\delta)/\epsilon^2)\)
draws suffice per unordered pair. No polynomial-time assumption on the solver is used.
For completeness, an exact solver can use subset dynamic programming. Let \(f(S)\) be the minimum empirical cost of a ranking of \(S\subseteq A\). Then
\(f(\varnothing)=0,\qquad f(S)=\min_{v\in S}\left[f(S\setminus\{v\})+\sum_{u\in S\setminus\{v\}}\widehat w_{vu}\right].\)
To verify the recurrence, place \(v\) last. The preceding alternatives contribute their optimal internal cost, and each pair involving \(v\) contributes \(\widehat w_{vu}\). Conversely, every ranking has some last alternative. Recording minimizing choices reconstructs a strict total order.
The recurrence requires \(O(m^2 2^m)\) rational arithmetic operations.
Let \(Q_{\mathrm P}=Ns_{\mathrm P}\) and \(Q_{\mathrm E}=Ns_{\mathrm E}\). The total query counts are
\(Q_{\mathrm P}=O(m^6\log(m/\delta)/e^2),\qquad Q_{\mathrm E}=O(m^2\log(m/\delta)/\epsilon^2).\)
Each empirical weight has binary length \(O(L+\log s)\): its denominator divides \(s\) times a common denominator of the underlying probability tables. Ranking costs require only an additional \(O(\log m)\) bits.
Counting each promised sampling-oracle draw as one call, valid bit-time bounds are
\(T_{\mathrm P}=O(Q_{\mathrm P})\operatorname{poly}(L+\log s_{\mathrm P})+m^{g(2/e)}\operatorname{poly}(m,L+\log s_{\mathrm P})\log(2/\delta),\)
and, using the exact dynamic program,
\(T_{\mathrm E}=O(Q_{\mathrm E}+m^2 2^m)\operatorname{poly}(L+\log s_{\mathrm E}+\log m).\)
These algorithms work directly with the \(\tau\) supplied types. Rational masses require no expansion into an equally weighted voter population.
⟨structured verdict parsed — rendered above⟩
The argument is mathematically sound and establishes all three approximation guarantees in the conventional accuracy range. The reduction, perturbation bounds, concentration constants, and running-time estimates check out, including when the optimum is zero.
There is one minor scope issue: the second question states an inverse-square sampling bound without restricting \(\epsilon\), whereas the prover explicitly establishes that bound uniformly for \(0<\epsilon\le1\). For larger accuracies, its algorithm uses \(\min\{\epsilon,1\}\). This affects the stated parameter dependence, not the approximation guarantee.
The definition
\(w_{ab}=\sum_{t=1}^{\tau}\mu_tq_t(a,b)\)
is valid. Positivity of the masses, nonnegativity of the probabilities, normalization, and complementary probabilities give nonnegative weights satisfying \(w_{ab}+w_{ba}=1\).
The objective identity is correct: each unordered pair contributes one Kendall disagreement indicator, whose expectation is the probability of the orientation opposite to the output ranking. Finite sums justify exchanging expectation and summation. Consequently, the weighted FAST objective and \(H_\mu\) agree exactly.
The cited PTAS applies. Kenyon-Mathieu–Schudy define their weighted problem using nonnegative weights with pair sums bounded between a positive constant \(b\) and \(1\); here \(b=1\). Their Theorem 1 supplies a randomized PTAS, so the prover’s stated consequence for prescribed approximation accuracy is legitimate. Joint realizability of the weights is not a theorem hypothesis. [Kenyon-Mathieu–Schudy, Problem 2 and Theorem 1](https://cs.brown.edu/~claire/Publis/kenyonschudy.pdf).
Confidence amplification is correctly described. Independent repetitions have a constant probability of producing a successful ranking; retaining the ranking of smallest exactly evaluated cost preserves success whenever any repetition succeeds. A logarithmic number of repetitions therefore suffices.
The aggregate rational weights have polynomial description length. Products of the input denominators have binary length bounded by the sum of their binary lengths, which is controlled by \(L\). Rational arithmetic therefore supports the claimed polynomial bit complexity.
Assessment: The first guarantee is established for every fixed positive \(\epsilon\).
If two rankings disagree on \(k\) unordered pairs, their costs on each such pair sum to \(1\). Contributions from other pairs are nonnegative. Thus
\(F(\pi)+F(\sigma)\ge k\)
is correct.
Distinct strict total orders disagree on at least one pair, so their costs sum to at least \(1\). This implication uses the strict-total-order assumption correctly.
Every ranking selects exactly \(N=\binom m2\) weights. Therefore the uniform weight-error assumption implies
\(\lvert F(\sigma)-\widehat F(\sigma)\rvert\le Nr\).
Combining this bound with empirical approximate optimality correctly yields
\(F(\widehat\sigma)\le(1+\beta)C+(2+\beta)Nr\).
The constants check out. For \(\beta=e/2\), \(r=e/(32N)\), and \(e\le1\), the additive term is at most \(5e/64\).
Both cases are valid:
The second case correctly handles an optimum of zero and arbitrarily small positive optima. It also implies uniqueness of the true optimum in that range; no tie assumption is missing.
Assessment: The deterministic transfer argument is rigorous.
Agreement-pair contributions cancel in the comparison of the two rankings. Each disagreement pair contributes at most \(2r\) to the error in their cost difference. Empirical optimality therefore gives
\(Y-C\le2rk\).
The disagreement bound gives \(k\le Y+C\). Since \(r<1/2\), the rearrangement
\(Y\le\frac{1+2r}{1-2r}C\)
is valid.
For \(r=\epsilon/(4+2\epsilon)\), the ratio is exactly \(1+\epsilon\), and \(r<1/2\) holds throughout the requested range. No division by \(C\) occurs, so the argument remains valid when \(C=0\).
The attribution to the Procaccia–Shah perturbation argument is accurate: their proof uses cancellation on agreement pairs and bounds disagreement count through the sum of the two true costs. The prover provides the needed argument directly rather than relying on an unstated lemma. [Procaccia–Shah, Lemma 1 and its proof](https://procaccia.info/wp-content/uploads/2020/03/uncertainty.pdf).
Assessment: The transfer holds for every exact empirical minimizer, including arbitrary tie choices.
For each fixed queried orientation, the samples are independent, bounded in \([0,1]\), and have mean \(w_{ab}\). These satisfy the stated Hoeffding bound’s hypotheses.
Setting reverse estimates to complements gives the same absolute error in both orientations. The union bound correctly uses \(N\) unordered pairs.
For the PTAS procedure,
\(2s_{\mathrm P}r^2\ge\log(4N/\delta)\),
so the probability of any excessive weight error is at most \(\delta/2\). Conditional on any empirical instance, the PTAS failure probability is at most \(\delta/2\). Combining these events gives total failure probability at most \(\delta\).
For the exact procedure,
\(2s_{\mathrm E}r^2\ge\log(2N/\delta)\),
so the corresponding total failure probability is at most \(\delta\).
Since \(m\ge2\), replacing the logarithms involving \(N\) by \(O(\log(m/\delta))\) is valid. The claimed per-pair and total query counts follow.
Empirical joint realizability is unnecessary: all subsequent arguments require only nonnegative complementary weights.
Assessment: Both sampling guarantees and their constants are correct, subject to the accuracy-range clarification below.
The dynamic-programming recurrence has the correct orientation. Placing \(v\) last makes each preceding alternative \(u\) contribute \(\widehat w_{vu}\). Every nonempty ranking has a last alternative, so the recurrence covers all rankings. The empty-set base case and reconstruction of a strict total order are sufficient.
The stated \(O(m^2 2^m)\) rational-operation bound is valid.
A common denominator of the underlying probability tables, multiplied by the common sample count, is a common denominator for all empirical weights. Its binary length is \(O(L+\log s)\). Summing at most \(N\) such weights adds only \(O(\log m)\) bits. The reported bit-time bounds consequently follow.
The oracle-call accounting is explicit and consistent with the sample-access model. No expansion of rational masses into an equally weighted population is required.
Minor — parameter convention for the second sampling bound. The written algorithm establishes the uniform bound
\(O(m^4\log(m/\delta)/\min\{\epsilon,1\}^2)\).
It agrees with the question’s inverse-square expression for \(0<\epsilon\le1\). For unrestricted variable \(\epsilon>1\), the clamped algorithm’s bound does not have uniform inverse-square dependence on \(\epsilon\).
The minimum clarification is to specify whether the second question’s sampling bound is understood in the conventional range \(0<\epsilon\le1\), or with constants permitted to depend on each fixed \(\epsilon\). The prover already identifies the convention and proves the approximation guarantee for larger \(\epsilon\); no mathematical repair to the argument 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.