Answer: A correct policy achieving the stated additive guarantee can be constructed and executed in polynomial time.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateSuppose a rank- ing σ is drawn from D. Algorithm 1 correctly elicits σ, using at most H(D) + 2(m −1) queries in expectation. Since there are distributions D over A! with H(D) = Θ(m log m) (for example the uniform distribution), this addi- tive term is quite small, and we will see later that Algorithm 1 comes very close to the H(D) optimum for the distributions we care about here.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given alternatives \(C\), a support \(S\subseteq C!\), and rational ranking-type masses \(\mu_\sigma\) summing to \(1\), find an adaptive pairwise-comparison policy \(P\) that identifies each queried user’s ranking and satisfies \(Q_\mu(P)\leq \operatorname{OPT}(\mu)+2(m-1)\), where \(Q_\mu(P)=\sum_{\sigma\in S}\mu_\sigma d_P(\sigma)\) and \(\operatorname{OPT}(\mu)\) is the minimum per-capita query mass of any correct policy.
Let \(C\) contain \(m\geq 1\) alternatives; \(C!\) denotes their complete strict rankings. A society is given by its support: a nonempty list \(S\subseteq C!\) of \(\tau\) types with positive binary rational masses \(\mu_\sigma\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings, and \(L\) is the total input bit length.
A deterministic adaptive policy asks truthful pairwise comparisons, each costing one query, and terminates with the user's complete ranking. Require correctness for every ranking in \(C!\), including rankings outside \(S\); represent the policy by a finite algorithm rather than an explicitly expanded decision tree.
Let \(d_P(\sigma)\) be its query count, \(Q_\mu(P)=\sum_{\sigma\in S}\mu_\sigma d_P(\sigma)\), and \(\operatorname{OPT}(\mu)=\min_P Q_\mu(P)\) over correct policies.
Can a correct policy satisfying \(Q_\mu(P)\leq\operatorname{OPT}(\mu)+2(m-1)\) be constructed and executed in polynomial time in \(m,\tau,L\), or is achieving this additive guarantee NP-hard?
Known results: distribution-aware sorting achieves expected query count at most \(H(D)+2(m-1)\), while every correct binary-query policy has expected count at least the Shannon entropy \(H(D)\). [Peters and Procaccia](https://dominik-peters.de/publications/sort-elicit.pdf)
These results already concern arbitrary distributions over rankings, including the stated rational-mass societies; the supplied question therefore does not introduce a distinct continuous approximation problem. [Moran and Yehudayoff](https://eccc.weizmann.ac.il/report/2013/106/revision/1/download/)
The additive guarantee is achievable in polynomial time. More precisely, one can construct a deterministic policy, correct for every ranking, satisfying \(Q_\mu(P)\leq H(\mu)+2(m-1)\leq\operatorname{OPT}(\mu)+2(m-1)\).
The entropy bound for distribution-aware insertion sort is stated in [Peters and Procaccia, Theorem 1](https://dominik-peters.de/publications/sort-elicit.pdf). The computational issue here is implementing the conditional searches from the explicit support while retaining correctness at zero-probability insertion positions. We give that implementation below.
All logarithms have base \(2\), and entropy uses the convention \(0\log 0=0\). For \(m=1\), output the unique ranking without queries. Henceforth assume \(m\geq2\).
An ordered search tree on positions \(1,\ldots,n\) is a full binary tree whose leaves, from left to right, are those positions. Each internal node separates two consecutive intervals and asks a threshold question. It therefore identifies every position, regardless of its probability.
For a probability vector \(p=(p_1,\ldots,p_n)\), define
\(F(p)=\min_T\sum_{j=1}^n p_jd_T(j)\),
where the minimum ranges over these trees and \(d_T(j)\) is leaf depth.
We use the following established ordered-search result: for a positive probability distribution on a finite linearly ordered set, threshold queries identify the selected element with expected query count at most its entropy plus \(2\). This is [Moran and Yehudayoff, Lemma 2](https://eccc.weizmann.ac.il/report/2013/106/revision/1/download/). Removing branches with no possible position, and suppressing nodes with only one possible answer, turns such a search into an ordered search tree without increasing its cost. Consequently, \(F(p)\leq H(p)+2\) when every coordinate is positive.
We now justify the same bound when coordinates can vanish. Every full binary tree with \(n\) leaves has leaf depth at most \(n-1\): each ancestor on a root-to-leaf path has a sibling subtree containing a distinct additional leaf. Thus, for any probability vectors \(p,q\),
\(\left|F(p)-F(q)\right|\leq(n-1)\sum_j|p_j-q_j|\).
Indeed, each tree’s cost satisfies this inequality, and applying it to a minimizing tree for either vector proves both directions.
For \(0<\varepsilon<1\), put
\(p_j^{(\varepsilon)}=(1-\varepsilon)p_j+\varepsilon/n\).
This is a positive probability vector, so the established result applies. Therefore
\(F(p)\leq H(p^{(\varepsilon)})+2+(n-1)\sum_j|p_j-p_j^{(\varepsilon)}|\).
Letting \(\varepsilon\) tend to zero proves \(F(p)\leq H(p)+2\), because entropy is continuous on the finite probability simplex.
Crucially, the minimizing trees here retain all positions. The limiting argument is only a proof device; the algorithm below uses exact input weights.
Let \(w_1,\ldots,w_n\) be nonnegative integer weights, possibly all zero. For an interval \([a,b]\), let \(D[a,b]\) be the minimum weighted sum of leaf depths measured from that interval’s subtree root.
The recurrence is
\(D[a,a]=0\), and, for \(a<b\),
\(D[a,b]=\sum_{j=a}^b w_j+\min_{a\leq r<b}\bigl(D[a,r]+D[r+1,b]\bigr)\).
To justify it, any ordered tree’s root splits the interval after some \(r\). Every leaf incurs one comparison at that root, contributing \(\sum_{j=a}^b w_j\). The remaining contributions come from the two subtrees. Conversely, combining minimizing subtrees at any such split gives a valid tree. Induction on interval length proves the recurrence.
Prefix sums provide interval weights. The dynamic program uses \(O(n^3)\) arithmetic operations and \(O(n^2)\) table entries. Store a minimizing split, choosing the smallest in case of ties; reconstruction gives a deterministic tree.
If \(W=\sum_jw_j>0\), its expected depth under \(p_j=w_j/W\) is exactly \(F(p)\). If \(W=0\), the recurrence still constructs a correct tree identifying every position.
Fix an enumeration \(C=\{c_1,\ldots,c_m\}\). Begin with the sorted sequence \((c_1)\).
At stage \(k\), suppose the already elicited order is \(b_1\succ\cdots\succ b_{k-1}\). Maintain the subset \(A\subseteq S\) whose restrictions to \(\{c_1,\ldots,c_{k-1}\}\) equal this order.
There are \(k\) possible insertion positions for \(c_k\), numbered from top to bottom. For each position \(j\), sum the weights of rankings in \(A\) placing \(c_k\) there, and construct the ordered search tree from Section 2.
A node splitting positions after \(r\) asks whether \(c_k\succ b_r\). Since the existing sequence is correctly sorted, the answer is yes exactly when the true insertion position is at most \(r\). Thus every tree question is a permitted pairwise comparison.
Follow the answers to a leaf \(j\), insert \(c_k\) at that position, and retain in \(A\) exactly the types with that insertion position.
Correctness follows by induction. The initial one-element sequence is correct. At each subsequent stage, the ordered search tree identifies the true insertion position among every possible position, so insertion preserves correctness. After stage \(m\), the output is the complete ranking.
This proof also covers rankings outside \(S\). If \(A\) becomes empty, all weights are zero, but the dynamic program still produces a complete ordered search tree. The policy continues correctly.
Let \(\Sigma\) be a random ranking with distribution \(\mu\). Define \(J_k\) as the insertion position of \(c_k\) among \(\{c_1,\ldots,c_k\}\).
The tuple \((J_2,\ldots,J_m)\) determines \(\Sigma\): starting from \(c_1\), perform the specified insertions successively. Conversely, every ranking determines that tuple. Hence, by the entropy chain rule,
\(H(\mu)=H(J_2,\ldots,J_m)=\sum_{k=2}^m H(J_k\mid J_2,\ldots,J_{k-1})\).
Fix a preceding insertion history of positive probability. Its partial order determines exactly the compatible support subset \(A\). Therefore the normalized position weights computed by the policy are precisely the conditional distribution of \(J_k\) given that history.
By Section 1, the conditional expected number of stage-\(k\) queries is at most the entropy of this conditional distribution plus \(2\). Averaging over histories and summing over stages yields
\(Q_\mu(P)\leq\sum_{k=2}^m\bigl(H(J_k\mid J_2,\ldots,J_{k-1})+2\bigr)=H(\mu)+2(m-1)\).
For completeness, the entropy lower bound applies to every correct policy in the question. Its terminating answer strings for distinct supported rankings are distinct and prefix-free: after a terminating string, a deterministic policy cannot continue on another ranking having the same answer prefix. Thus Kraft’s inequality gives \(\sum_{\sigma\in S}2^{-d_P(\sigma)}\leq1\). Concavity of the logarithm then gives
\(H(\mu)-Q_\mu(P)=\sum_{\sigma\in S}\mu_\sigma\log\!\left(2^{-d_P(\sigma)}/\mu_\sigma\right)\leq\log\!\left(\sum_{\sigma\in S}2^{-d_P(\sigma)}\right)\leq0\).
Consequently, \(\operatorname{OPT}(\mu)\geq H(\mu)\), proving the requested guarantee.
Write each input mass as \(\mu_\sigma=a_\sigma/b_\sigma\), with positive integers \(a_\sigma,b_\sigma\). Set \(B=\prod_{\sigma\in S}b_\sigma\) and replace each mass by the integer weight \(u_\sigma=a_\sigma(B/b_\sigma)\).
The bit length of \(B\) is \(O(L)\), and \(\sum_\sigma u_\sigma=B\). Thus this exact conversion takes polynomial time.
Precompute each alternative’s position in each supported ranking. At stage \(k\), scanning the active types and determining their insertion positions takes \(O(\tau k)\) elementary operations. The search-tree dynamic program takes \(O(k^3)\) arithmetic operations. Over all stages, these bounds sum to \(O(\tau m^2+m^4)\), apart from polynomial-time preprocessing.
Every dynamic-programming value is at most \((k-1)B\): any relevant tree has depth at most \(k-1\), and its total weight is at most \(B\). Arithmetic therefore uses integers of \(O(L+\log m)\) bits. This establishes polynomial bit complexity, not merely polynomial arithmetic complexity.
Finally, every execution uses at most \(\sum_{k=2}^m(k-1)=m(m-1)/2\) comparisons, including executions outside the support. The policy is represented by this fixed algorithm and the preprocessed input; it builds only the current insertion tree, never an expanded sorting decision tree.
Thus both construction and execution are polynomial in \(m,\tau,L\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes the requested additive guarantee, correctness for every ranking, and polynomial construction and execution time under the stated explicit-support encoding. I found no major or minor mathematical issues requiring repair.
The output addresses the actual task: a deterministic algorithm representing a policy, rather than an explicitly expanded decision tree. It measures expected cost using the supplied rational masses and requires correctness outside the support.
The case \(m=1\) is correctly handled by returning the unique ranking with zero queries. Both entropy and optimal expected cost are then zero.
[Moran and Yehudayoff, Lemma 2](https://eccc.weizmann.ac.il/report/2013/106/revision/1/download/) supplies the claimed entropy-plus-two bound for threshold search on a finite linearly ordered set. The prover applies it first to strictly positive distributions, so its use does not depend on resolving any zero-probability behavior in the source’s search implementation.
Pruning branches containing no possible position and suppressing nodes with only one possible answer preserves identification and cannot increase query counts. Threshold answers restrict the remaining candidates to consecutive intervals, so the resulting tree has the required ordered leaves.
The introductory attribution to [Peters and Procaccia, Theorem 1](https://dominik-peters.de/publications/sort-elicit.pdf) is also accurate: that theorem states the expected sorting bound with additive term \(2(m-1)\). The output independently addresses the implementation and universal-correctness requirements.
The leaf-depth bound \(n-1\) is correct: each ancestor contributes a sibling subtree containing a distinct additional leaf.
Consequently, every fixed tree’s weighted cost changes by at most
\((n-1)\sum_j|p_j-q_j|\). Applying this bound to minimizers in both directions establishes the asserted bound for \(F\). Such minimizers exist because there are finitely many full ordered binary trees with the prescribed finite leaf set.
The perturbed vector \(p^{(\varepsilon)}\) is positive and normalized. Its distance from \(p\) tends to zero, and finite-dimensional Shannon entropy is continuous under the stated convention at zero. The limiting inequality therefore proves \(F(p)\leq H(p)+2\).
Crucially, the optimization always retains every position as a leaf. No zero-probability position is discarded by this argument.
The singleton base case correctly assigns zero depth within its subtree.
Every root split occurs between consecutive positions. The root contributes the total interval weight once, while the two subtree costs account for all remaining depths. Conversely, joining minimizing subtrees realizes each candidate split. Thus the recurrence is exact.
The operation and storage bounds, \(O(n^3)\) and \(O(n^2)\), respectively, are correct. Deterministic tie-breaking supplies a deterministic reconstructed tree.
For positive total weight, normalization converts the weighted objective exactly into expected depth. With all weights zero, the recurrence still reconstructs a full tree identifying every position.
At stage \(k\), a split after position \(r\) has \(1\leq r\leq k-1\), so the queried alternative \(b_r\) exists. Under the correctly sorted current sequence, \(c_k\succ b_r\) holds exactly when its insertion position is at most \(r\). The threshold query is therefore implemented correctly by one truthful pairwise comparison.
Filtering the active support by the identified insertion position preserves the stated compatibility invariant. The induction establishing correctness of the growing sequence is valid.
If the true ranking lies outside the support, either a zero-weight position is selected or the active set eventually becomes empty. Both situations are covered by complete ordered trees. The policy therefore terminates correctly for every ranking in \(C!\).
Successive insertion positions determine the complete ranking, and each complete ranking determines those positions. The entropy identity and chain-rule decomposition follow.
For every history having positive probability, the compatible support has positive total mass. Normalizing its position weights gives precisely the required conditional distribution. The ordered-search bound therefore applies at each such history.
Averaging and summing over the \(m-1\) insertion stages yields
\(Q_\mu(P)\leq H(\mu)+2(m-1)\). Zero-probability histories contribute nothing to this expectation while remaining covered by the correctness argument.
Distinct supported rankings must produce distinct terminating answer strings. Determinism makes those strings prefix-free: a policy terminating at a given answer prefix cannot continue on another execution with that prefix.
Kraft’s inequality consequently applies. The displayed logarithmic concavity calculation has the correct sign, and every denominator is positive because supported masses are positive. It establishes \(H(\mu)\leq Q_\mu(P)\) for every admissible policy.
Hence \(H(\mu)\leq\operatorname{OPT}(\mu)\), giving the requested additive guarantee.
The product of denominators has bit length \(O(L)\). The integer conversion is exact, and normalization gives \(\sum_\sigma u_\sigma=B\).
The stated support scans and dynamic programs total \(O(\tau m^2+m^4)\) elementary or arithmetic operations, apart from polynomial preprocessing. All relevant weighted-depth values are bounded by \((k-1)B\), so their bit lengths are \(O(L+\log m)\). This justifies polynomial bit complexity.
Every execution uses at most \(m(m-1)/2\) comparisons. Constructing only the current insertion tree avoids any need to enumerate all possible histories. The finite algorithm and preprocessed support therefore constitute the required polynomially constructible and executable policy.
No additional clarification is needed to make the argument verifiable.
⟨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.