Answer: —
Theorem 10 — class: algorithmic
Given \(K\) options, an unknown society \(\mu\) over complete weak rankings, and an oracle that answers a queried pair by sampling a fresh member of the society, design an adaptive algorithm that returns a ranking \(\tau\) with \(d_M(\tau,\prec^{CO_\epsilon}_\mu)<\rho\) with probability at least \(1-\delta\), while bounding or minimizing its expected number of pair queries.
Let \(m=K\ge 2\). A society is specified by the list of its \(\tau\) complete weak ranking types with positive binary rational masses summing to \(1\); \(\tau\) is the support size, not the number of possible types, and \(L\) is the encoding bit length.
To preserve unknown-society elicitation, this list describes the oracle's instance and is hidden from the algorithm. Each query chooses distinct options and independently draws a fresh type, revealing only their comparison; its numerical outcome is \(1\) for preference for the first option, \(0\) for the second, and \(1/2\) for indifference.
Write \(y_{ij}\) for the expected outcome. Given binary rational \(\epsilon>0\), define \(d_i^*=|\{j\ne i:y_{ij}>1/2+\epsilon\}|\) and \(s_i^*=|\{j\ne i:|y_{ij}-1/2|\le\epsilon\}|\).
The target strict partial order is \(o_i\prec^{CO_\epsilon}_\mu o_j\) exactly when \(d_i^*+s_i^*<d_j^*\); equal or overlapping score intervals impose no comparison.
For a permutation \(r\), with rank \(1\) best, define \(d_M(r,\prec)=\min_{r'\in\mathcal L(\prec)}\max_i|r_i-r'_i|\), where linear extensions satisfy \(o_i\prec o_j\Rightarrow r'_j<r'_i\).
Given \(\rho\in\mathbb Z_{>0}\) and binary rational \(0<\delta<1\), require \(\Pr[d_M(r,\prec^{CO_\epsilon}_\mu)<\rho]\ge1-\delta\). Count oracle queries separately from computation, expressing bounds in \(m,\tau,L,\rho,\epsilon^{-1},\log(1/\delta)\).
Is this PAC rank elicitation problem solvable in polynomial expected time and polynomial expected queries in these parameters, or is it NP-hard?
Known: finite societies are covered by an adaptive PAC algorithm with an instance-dependent expected-query bound. Its guarantee is formulated for stochastic pairwise observations and also covers exactly the distribution-sampling oracle above, rather than only finite-agent inputs. [Verified source](https://ojs.aaai.org/index.php/AAAI/article/download/8978/8837).
A uniform polynomial query bound is available: with probability at least $1-\delta$, the algorithm below returns an exact linear extension of the target partial order.
The computation issue identified in the verifier report cannot simply be absorbed into the society’s encoding length $L$. In fact, under the usual sequential encoding of a rational as a binary numerator followed by a binary denominator, a polynomial expected computation bound in exactly the listed parameters is impossible. This is an input-access obstruction, not an NP-hardness proof.
I prove both statements below. Throughout, $L$ retains its stated meaning: the hidden society’s encoding length.
Write
$$
a_i=d_i^*,\qquad b_i=d_i^*+s_i^*.
$$
Thus $a_i\le b_i$, and the target comparison is
$$
o_i\prec^{CO_\epsilon}_\mu o_j
\quad\Longleftrightarrow\quad
b_i<a_j.
$$
This relation is irreflexive because $b_i\ge a_i$. It is transitive: if $b_i<a_j$ and $b_j<a_k$, then
$$
b_i<a_j\le b_j<a_k.
$$
It is therefore a strict partial order.
Lemma. Suppose that numbers $c_i$ satisfy
$$
a_i\le c_i\le b_i
$$
for every $i$. Sorting the options by decreasing $c_i$, with arbitrary tie breaking, produces a linear extension of the target order.
Proof. Every required comparison satisfies
$$
c_i\le b_i<a_j\le c_j.
$$
Consequently, $j$ appears before $i$, as the definition of a linear extension requires. Thus the resulting permutation $r$ belongs to $\mathcal L(\prec^{CO_\epsilon}_\mu)$, and
$$
d_M(r,\prec^{CO_\epsilon}_\mu)=0.
$$
This proves the lemma.
The algorithm therefore needs to find one score inside each interval; it need not identify the interval endpoints.
If $\epsilon\ge 1/2$, all pairwise means belong to the insensitive region. Every interval is $[0,m-1]$, so any permutation succeeds without queries.
Assume henceforth that $0<\epsilon<1/2$. Define
$$
B=\binom m2,\qquad
k=\left\lceil\log_2\frac{2B}{\delta}\right\rceil,\qquad
n=\left\lceil k\epsilon^{-2}\right\rceil.
$$
For each pair $i<j$, query $(i,j)$ exactly $n$ times and let $\widehat y_{ij}$ be the sample mean. Define
$$
\widehat y_{ji}=1-\widehat y_{ij}.
$$
This is justified because, for every complete weak ranking type, reversing a comparison replaces its outcome $Y_{ij}$ by $1-Y_{ij}$, including indifference. Hence
$$
y_{ji}=1-y_{ij},
\qquad
|\widehat y_{ji}-y_{ji}|=|\widehat y_{ij}-y_{ij}|.
$$
Compute
$$
\widehat d_i
=
\left|\left\{j\ne i:\widehat y_{ij}>\frac12\right\}\right|,
$$
and output the permutation obtained by sorting these integers in decreasing order.
For each sampled pair, the observations are independent, have the same distribution, and belong to $[0,1]$: each query draws a fresh type from the fixed society. Hoeffding’s inequality therefore gives
$$
\Pr\!\left[|\widehat y_{ij}-y_{ij}|\ge\epsilon\right]
\le 2\exp(-2n\epsilon^2).
$$
A union bound yields
$$
\Pr\!\left[\exists i<j:
|\widehat y_{ij}-y_{ij}|\ge\epsilon\right]
\le
2B\exp(-2k)
\le
2B\,2^{-k}
\le\delta.
$$
Let $E$ denote the complementary event, including the inferred reverse estimates. On $E$, fix an option $i$.
If $y_{ij}>1/2+\epsilon$, then
$$
\widehat y_{ij}>y_{ij}-\epsilon>\frac12,
$$
so this strong win contributes to $\widehat d_i$.
If $y_{ij}<1/2-\epsilon$, then
$$
\widehat y_{ij}<y_{ij}+\epsilon<\frac12,
$$
so this strong loss does not contribute.
Every remaining comparison satisfies $|y_{ij}-1/2|\le\epsilon$ and can contribute at most one. Consequently,
$$
d_i^*\le\widehat d_i\le d_i^*+s_i^*.
$$
The interval lemma applies. Thus, on $E$, the output is an exact linear extension. Since $\rho$ is a positive integer,
$$
\Pr\!\left[d_M(r,\prec^{CO_\epsilon}_\mu)<\rho\right]
\ge\Pr(E)\ge1-\delta.
$$
Means exactly at $1/2\pm\epsilon$ belong to the insensitive set, so the proof requires no separation from either boundary.
The deterministic query count is
$$
Q=Bn
=
O\!\left(
m^2\epsilon^{-2}
\left(\log m+\log(1/\delta)\right)
\right).
$$
It also bounds the expected query count. Neither $\tau$ nor the hidden society encoding is used.
The observations can be processed exactly. For each pair, maintain
$$
T_{ij}=\sum_{\ell=1}^{n}2Y_{ij}^{(\ell)}.
$$
Each summand belongs to $\{0,1,2\}$, and
$$
\widehat y_{ij}>\frac12
\quad\Longleftrightarrow\quad
T_{ij}>n.
$$
The counters require $O(\log(n+1))$ bits. Once $k$ and $n$ have been computed, response processing, score computation, and sorting require
$$
O\!\left((Q+m^2)\log(m(n+1))\right)
$$
bit operations.
If $D$ denotes the total encoding length of the visible numerical parameters, computing $k$ and $n$ adds polynomial time in $D$. Thus the complete algorithm is polynomial in the requested parameters together with $D$. This statement does not redefine $L$.
The supplied paper uses the same stochastic comparison outcomes $0,1/2,1$ and unknown-distribution sampling model. The proof above is independent of its adaptive algorithm. [PAC Rank Elicitation through Adaptive Sampling of Stochastic Pairwise Preferences](https://ojs.aaai.org/index.php/AAAI/article/download/8978/8837)
The following result strengthens the verifier’s observation that numerical values do not bound their rational encoding lengths.
Proposition. Suppose visible inputs are supplied on a sequential input tape, with each rational encoded as its binary numerator, a delimiter, and its binary denominator, without leading zeros. Reading or traversing an input symbol costs a computation step. Then no uniform algorithm can satisfy the PAC requirement on all instances while having both expected computation and expected queries bounded by polynomials in exactly
$$
m,\tau,L,\rho,\epsilon^{-1},\log(1/\delta).
$$
This proposition concerns a specified, conventional input model. It does not assert the same obstruction for every possible input-access convention.
Fix
$$
m=2,\qquad \rho=1,\qquad \epsilon=\frac18.
$$
Consider two societies, each supported on the two strict rankings:
Both have fixed support size $\tau=2$ and fixed society encoding length $L$. Their pairwise means are
$$
y_{12}^{(+)}=\frac34,
\qquad
y_{12}^{(-)}=\frac14.
$$
Because $\epsilon=1/8$, each target is a total order. The successful permutation places $o_1$ first under $\mu_+$ and $o_2$ first under $\mu_-$. Since $\rho=1$, the required distance must be zero.
Suppose an algorithm with the asserted polynomial bounds exists. Let $W$ be its computation cost plus its number of oracle queries.
For every integer $N\ge1$, consider
$$
\delta_N^{\mathrm e}
=
\frac{2^N}{2^{N+2}+1}.
$$
These fractions are reduced, and
$$
\frac15<\delta_N^{\mathrm e}<\frac14.
$$
All listed parameters therefore remain bounded independently of $N$. The assumed polynomial bounds imply the existence of a constant $C\ge1$ such that
$$
\mathbb E_{\mu_+,\delta_N^{\mathrm e}}[W]\le C
$$
for every $N$.
Set $H=\lceil4C\rceil$ and choose $N>H$. Markov’s inequality gives
$$
\Pr_{\mu_+,\delta_N^{\mathrm e}}[W>H]\le\frac14.
$$
The PAC guarantee gives probability greater than $3/4$ of outputting the permutation with $o_1$ first. Hence the event
$$
A=
\{\text{halt by cost }H\text{ and output }o_1\text{ first}\}
$$
has probability at least $1/2$.
Now replace the visible failure parameter by
$$
\delta_N^{\mathrm h}
=
\frac{2^N}{2^{N+M}+1},
$$
where $M$ will be chosen below. This fraction is also reduced. Its encoded numerator is identical to that of $\delta_N^{\mathrm e}$ and contains $N+1$ bits.
Because $N>H$, a computation of cost at most $H$ cannot reach the delimiter following that numerator. The two visible inputs are therefore indistinguishable throughout every execution counted by $A$. Under the same society $\mu_+$, their early-execution distributions coincide. Thus
$$
\Pr_{\mu_+,\delta_N^{\mathrm h}}(A)\ge\frac12.
$$
Next compare the two societies on the common hard input. For either orientation of the queried pair, every possible observation has positive probability under both societies, and the ratio
$$
\frac{\Pr_{\mu_-}(\text{observation})}
{\Pr_{\mu_+}(\text{observation})}
$$
is either $3$ or $1/3$.
Fix the algorithm’s internal randomness. Along any transcript containing $q$ queries, its likelihood under $\mu_-$ is therefore at least $3^{-q}$ times its likelihood under $\mu_+$. Adaptive query choices cause no additional factor: identical previous observations and internal randomness determine identical next queries.
Every transcript in $A$ has $q\le H$. Summing over such transcripts and averaging over internal randomness gives
$$
\Pr_{\mu_-,\delta_N^{\mathrm h}}(A)
\ge
3^{-H}\Pr_{\mu_+,\delta_N^{\mathrm h}}(A)
\ge
\frac{1}{2\cdot3^H}.
$$
On $\mu_-$, every output in $A$ is incorrect. Choose an integer $M$ such that
$$
2^{-M}<\frac{1}{2\cdot3^H}.
$$
Then
$$
\delta_N^{\mathrm h}
<
2^{-M}
<
\frac{1}{2\cdot3^H}.
$$
The algorithm’s error probability on this valid hard input exceeds its requested failure probability, contradicting the PAC guarantee. This proves the proposition.
The substantive elicitation result is proved: polynomially many oracle queries suffice, and the computation after numerical preprocessing is polynomial. Including visible numerical encoding lengths gives a complete polynomial-time algorithm.
For the society-only interpretation of $L$, the full requested computation bound is impossible in the sequential input model just specified. This obstruction already occurs for two options and two ranking types; it does not arise from combinatorial optimization.
An unqualified choice between “polynomial-time solvable in exactly the listed parameters” and “NP-hard” still requires an input-access convention. No NP-hardness claim is established here.
⟨structured verdict parsed — rendered above⟩
The output establishes substantial, correct results, but does not give an unconditional classification of the problem as stated. Its own assessment as partial is justified.
The uniform query algorithm is rigorous and returns an exact linear extension with the required probability. The computation bounds are also valid when the visible numerical input length is included. The sequential input-access obstruction is sound under its stated model.
The remaining issue is scope: the negative computation result depends on an input-access convention that USER_TASK does not expressly specify. No NP-hardness result is established.
The definitions
$$
a_i=d_i^*,\qquad b_i=d_i^*+s_i^*
$$
give $a_i\le b_i$. Consequently, the target relation is irreflexive.
The transitivity calculation is correct:
$$
b_i<a_j,\quad b_j<a_k
\quad\Longrightarrow\quad
b_i<a_j\le b_j<a_k.
$$
Thus the target is indeed a strict partial order.
If $c_i\in[a_i,b_i]$, every required comparison satisfies
$$
c_i\le b_i<a_j\le c_j.
$$
Sorting by decreasing $c_i$ therefore places $j$ before $i$. Arbitrary tie breaking is harmless because a required comparison forces a strict inequality between the corresponding scores.
The resulting permutation is a linear extension, so its distance $d_M$ is zero. This lemma is fully proved.
For $\epsilon\ge 1/2$, every mean in $[0,1]$ satisfies
$$
|y_{ij}-1/2|\le\epsilon.
$$
Hence $d_i^*=0$, $s_i^*=m-1$, and there are no required comparisons. The stated zero-query treatment is correct, including $\epsilon=1/2$.
For $0<\epsilon<1/2$, the sampling parameters are well defined: $m\ge2$ implies $B\ge1$, and $0<\delta<1$ implies $k>0$.
The identity
$$
y_{ji}=1-y_{ij}
$$
holds for every complete weak ranking type, including indifference. Inferring reverse estimates therefore preserves their absolute estimation errors.
Each sampled observation is independent, has the pair’s fixed distribution, and belongs to $[0,1]$. These are the hypotheses needed for the stated Hoeffding bound. No independence between different pairs is needed for the subsequent union bound.
The constants check correctly:
$$
n\epsilon^2\ge k,\qquad
e^{-2k}\le2^{-k},\qquad
2B\,2^{-k}\le\delta.
$$
Thus the event $E$ of simultaneous strict estimation errors below $\epsilon$ has probability at least $1-\delta$.
On $E$:
These three categories exhaust all comparisons, giving
$$
d_i^*\le\widehat d_i\le d_i^*+s_i^*.
$$
The interval lemma applies directly.
Means exactly at either boundary belong to the insensitive category, as required by the task. The proof does not assume a positive separation from those boundaries.
Finally, $\rho>0$ gives
$$
d_M=0<\rho
$$
whenever $E$ occurs. The PAC guarantee is fully proved, with the stronger conclusion of an exact linear extension on the success event.
The deterministic query count
$$
Q=O\!\left(m^2\epsilon^{-2}\bigl(\log m+\log(1/\delta)\bigr)\right)
$$
follows from the definitions of $B$, $k$, and $n$. It also bounds the expected query count. The algorithm does not require the hidden society list, its support size, or its masses.
The exact counter implementation is correct:
$$
\widehat y_{ij}>\frac12
\quad\Longleftrightarrow\quad
T_{ij}>n.
$$
Since $0\le T_{ij}\le2n$, the counter bit-length bound is valid. The stated processing and sorting bound is a valid upper bound.
Computing $k$ and $n$ from binary rationals can be performed using exact integer arithmetic in time polynomial in the visible encoding length $D$. This is a routine computational detail, rather than an unproved mathematical ingredient.
The complete computation bound is established with $D$ included. It does not, by itself, establish the requested bound using only the listed parameters, because those parameters need not bound $D$.
The two societies satisfy all relevant task assumptions: fixed $m=2$, fixed support size, positive rational masses, and fixed hidden encoding length.
Their target orders are opposite total orders. With $\rho=1$, success requires the corresponding exact permutation.
For the easy failure parameters,
$$
\delta_N^{\mathrm e}=\frac{2^N}{2^{N+2}+1},
$$
the fractions are reduced because their denominators are odd, and
$$
\frac15<\delta_N^{\mathrm e}<\frac14
$$
holds for every $N\ge1$. Thus all listed complexity parameters remain bounded independently of $N$, justifying a uniform constant $C$ for the expected combined cost.
With $H=\lceil4C\rceil$, Markov’s inequality gives the claimed probability bound. Combining it with success probability greater than $3/4$ gives
$$
\Pr(A)\ge\frac12.
$$
The easy and hard visible inputs have identical numerator prefixes of length $N+1$. Under the specified sequential tape model, $N>H$ prevents executions of cost at most $H$ from reaching the differing denominator. The transfer of the event probability between these inputs, under the same society, is therefore valid.
Under the two societies, every observation that can actually occur has likelihood ratio either $3$ or $1/3$. Indifference has probability zero under both and creates no relevant transcript. Adaptivity does not invalidate the likelihood comparison: conditioned on identical internal randomness and previous observations, the next query is identical.
Consequently, every transcript in $A$ has likelihood ratio at least $3^{-H}$, yielding
$$
\Pr_{\mu_-,\delta_N^{\mathrm h}}(A)
\ge\frac{1}{2\cdot3^H}.
$$
Every such output is incorrect under $\mu_-$. The choice of $M$ makes this lower bound exceed $\delta_N^{\mathrm h}$, contradicting the PAC requirement.
The proposition is correct under its expressly stated sequential input model. It establishes an input-access obstruction, not NP-hardness.
The paper’s problem-setting section specifies stochastic pairwise observations with numerical values $0$, $1/2$, and $1$, and sampling from an unknown underlying distribution. The prover’s description of that model is supported by the [supplied paper](https://ojs.aaai.org/index.php/AAAI/article/download/8978/8837).
The new sampling proof does not rely on importing the paper’s adaptive algorithm or its query theorem, so no missing application of that theorem affects the argument.
Major issue — incomplete classification relative to USER_TASK. The output proves a polynomial algorithm with an additional visible encoding-length parameter and a negative result under a particular sequential access convention. These are rigorous conditional results, but they do not select an unconditional answer to the task’s stated complexity question.
The minimum clarification is to specify whether visible rational inputs must be accessed sequentially, whether their encoding lengths count toward computation bounds, or whether another access model is intended. The conclusion must then be stated for that convention. No repair to the mathematical arguments in Sections 1–3 is needed.
There is no identified central false step, and no NP-hardness claim to accept or refute.
⟨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.