Answer: —
Theorem 2 — class: algorithmic
Given finite \(T\) and \(J\), rational type masses \(\mu_t\) and item supplies \(q_j\) with \(\sum_t\mu_t=\sum_jq_j=1\), known rankings \(\succ_t\), and oracle access to each type's common valuation vector \(v_t\), design a deterministic algorithm that makes at most \(1+\lambda+\lambda\lceil\log_2|J|\rceil\) queries per positive-mass type and returns \(x=(x_{tj})\) satisfying \(x_{tj}\ge0\), \(\sum_jx_{tj}=\mu_t\), and \(\sum_tx_{tj}=q_j\); determine its worst-case distortion \(\sup_v \frac{\max_{x'\in\mathcal X(\mu,q)}W(x';v)}{W(x;v)}\), where \(W(x;v)=\sum_{t,j}x_{tj}v_t(j)\), and whether \(2\eta^{-1/(\lambda+1)}\) is achievable for \(\eta=\min(\{\mu_t:\mu_t>0\}\cup\{q_j:q_j>0\})\).
Let \(T\) and \(J\) be finite, with rational masses \(\mu_t\ge 0\) and supplies \(q_j\ge 0\), each summing to \(1\). Each type \(t\) has a known ranking \(\succ_t\) consistent with an unknown, unrestricted nonnegative valuation \(v_t:J\to\mathbb R_{\ge0}\); a value query for \((t,j)\) returns \(v_t(j)\).
A feasible mass allocation \(x\) satisfies \(x_{tj}\ge0\), \(\sum_jx_{tj}=\mu_t\), and \(\sum_tx_{tj}=q_j\). Write \(\mathcal X(\mu,q)\) for these allocations and \(W(x;v)=\sum_{t,j}x_{tj}v_t(j)\). Distortion is the worst-case ratio \(\max_{x'\in\mathcal X(\mu,q)}W(x';v)/W(x;v)\) over valuations consistent with the rankings.
For an integer \(\lambda\ge0\), let \(\eta=\min(\{\mu_t:\mu_t>0\}\cup\{q_j:q_j>0\})\).
Target. Is there a polynomial-time deterministic algorithm using at most \(1+\lambda+\lambda\lceil\log_2|J|\rceil\) queries per positive-mass type and achieving distortion at most \(2\eta^{-1/(\lambda+1)}\), or is achieving this guarantee NP-hard? What is the optimal worst-case distortion under this query budget?
Nearest known results. With \(n\) individual agents and \(n\) indivisible items, a polynomial-time deterministic algorithm uses \(1+\lambda+\lambda\log_2 n\) queries per agent and achieves distortion at most \(2n^{1/(\lambda+1)}\). No result for the exact mass-allocation model was verified.
The requested guarantee is achievable in polynomial time. In fact, the algorithm below uses at most \(1+\lambda\lceil\log_2|J|\rceil\) queries per positive-mass type. This settles the algorithmic existence question. I do not establish the optimal worst-case distortion under the query budget.
The computational model is exact arithmetic and comparisons on query answers. For rational answers, the algorithm also has polynomial bit complexity in the input and answer lengths.
Proven claim. There is a deterministic algorithm producing an allocation \(x\) such that, for every consistent valuation profile \(v\),
\[
\max_{y\in\mathcal X(\mu,q)}W(y;v)
\le
\min\!\left\{\eta^{-1},\,2\eta^{-1/(\lambda+1)}\right\}W(x;v).
\]
This inequality also covers profiles whose optimal welfare is zero.
Delete zero-mass types and zero-supply items. These rows and columns must be zero in every feasible allocation, so deletion preserves all attainable welfare values. Let \(m\) be the remaining number of items. Each remaining supply is at least \(\eta\).
If the allowed query budget is at least \(m\), query every remaining value and compute an optimal transportation allocation. This gives distortion \(1\). Otherwise use the construction below. In particular, we may assume \(\lambda<m\), which bounds the exponents used in the computations.
For each type, list the remaining items in ranking order as \(j_{t,1},\ldots,j_{t,m}\). Consistency implies
\[
v_t(j_{t,1})\ge\cdots\ge v_t(j_{t,m}).
\]
The argument permits ties and therefore also applies when consistency requires strict inequalities.
Set
\[
\rho=\eta^{-1/(\lambda+1)}\ge1.
\]
Query \(M_t=v_t(j_{t,1})\). If \(M_t=0\), every remaining value of this type is zero; no further queries are needed.
For each \(k\in\{1,\ldots,\lambda\}\), find the last position
\[
b_{t,k}=\max\{i:v_t(j_{t,i})\ge M_t\rho^{-k}\}
\]
by binary search.
Here position \(1\) is a known true position, and position \(m+1\) is an artificial false sentinel. The initial interval has length \(m\), so at most \(\lceil\log_2m\rceil\) queries identify the boundary. Moreover, the boundary's value is known: every true endpoint is either position \(1\) or a position that was queried.
Let \(Q_t\) be the set of queried positions, including position \(1\). Define
\[
\widehat v_t(j_{t,i})
=
\max\bigl(\{v_t(j_{t,h}):h\in Q_t,\ h\ge i\}\cup\{0\}\bigr).
\]
Ranking consistency gives
\[
0\le\widehat v_t(j)\le v_t(j),
\qquad
\widehat v_t(j_{t,1})=M_t.
\]
This uses at most
\[
1+\lambda\lceil\log_2m\rceil
\le1+\lambda\lceil\log_2|J|\rceil
\]
queries per positive-mass type.
I claim that, for every remaining type and item,
\[
v_t(j)\le \rho\,\widehat v_t(j)+M_t\rho^{-\lambda}.
\tag{1}
\]
When \(\lambda=0\), this follows from \(v_t(j)\le M_t\). When \(M_t=0\), it is immediate.
Otherwise, if \(v_t(j)<M_t\rho^{-\lambda}\), the additive term alone proves (1). For the remaining case, let \(k\) be the smallest integer in \(\{1,\ldots,\lambda\}\) satisfying
\[
v_t(j)\ge M_t\rho^{-k}.
\]
The position of \(j\) is at most \(b_{t,k}\). Because this boundary was queried,
\[
\widehat v_t(j)\ge v_t(j_{t,b_{t,k}})\ge M_t\rho^{-k}.
\]
If \(k=1\), then \(v_t(j)\le M_t=\rho M_t\rho^{-1}\). If \(k>1\), minimality gives
\[
v_t(j)<M_t\rho^{-(k-1)}=\rho M_t\rho^{-k}.
\]
Thus in either case \(v_t(j)\le\rho\widehat v_t(j)\), proving (1).
Return a deterministically chosen maximizer
\[
x\in\operatorname*{arg\,max}_{y\in\mathcal X(\mu,q)}
\sum_{t,j}y_{tj}\widehat v_t(j).
\]
Write its surrogate welfare as \(\widehat W\), and set
\[
S=\sum_t\mu_tM_t.
\]
Since the surrogate values are lower estimates,
\[
W(x;v)\ge\widehat W.
\tag{2}
\]
The essential capacity bound is
\[
\widehat W\ge\eta S.
\tag{3}
\]
To prove it, initially assign mass \(\eta\mu_t\) of each type to its first-ranked remaining item. The load on any item \(j\) is
\[
\ell_j=\eta\sum_{t:j_{t,1}=j}\mu_t\le\eta\le q_j.
\]
Each row also stays within its required mass.
If \(\eta<1\), complete this partial allocation by assigning residual mass
\[
r_{tj}=\frac{(1-\eta)\mu_t(q_j-\ell_j)}{1-\eta}.
\]
Indeed, the residual row requirements are \((1-\eta)\mu_t\), the residual column requirements are \(q_j-\ell_j\), and both sum to \(1-\eta\). The displayed product construction has exactly these marginals. If \(\eta=1\), the initial allocation is already complete.
Its surrogate welfare is at least \(\eta S\), because all remaining contributions are nonnegative. Optimality of \(x\) proves (3).
Let \(x^\star\) maximize true welfare. Summing (1) against \(x^\star\), using its row sums and then surrogate optimality, gives
\[
\begin{aligned}
W(x^\star;v)
&\le \rho W(x^\star;\widehat v)+\rho^{-\lambda}S\\
&\le \rho\widehat W+\rho^{-\lambda}S\\
&\le\left(\rho+\eta^{-1}\rho^{-\lambda}\right)\widehat W.
\end{aligned}
\]
By the definition of \(\rho\),
\[
\eta^{-1}\rho^{-\lambda}=\rho.
\]
Applying (2) therefore yields
\[
W(x^\star;v)\le2\eta^{-1/(\lambda+1)}W(x;v).
\]
Also, \(W(x^\star;v)\le S\), since every value of type \(t\) is at most \(M_t\). Equations (2) and (3) consequently give
\[
W(x^\star;v)\le\eta^{-1}W(x;v),
\]
proving the claimed minimum of the two bounds.
The optimization step is a minimum-cost transportation problem: use type supplies \(\mu_t\), item demands \(q_j\), and arc costs \(-\widehat v_t(j)\). It is feasible, since \(y_{tj}=\mu_tq_j\) is feasible, and bounded, since total transported mass is \(1\). Strongly polynomial minimum-cost-flow algorithms apply. [Orlin, *A Faster Strongly Polynomial Minimum Cost Flow Algorithm*](https://pubsonline.informs.org/doi/pdf/10.1287/opre.41.2.338).
No irrational coefficients are needed in this optimization: every surrogate value is either zero or a query answer. Threshold comparisons can also avoid extracting roots, because for nonnegative values
\[
v_t(j)\ge M_t\rho^{-k}
\quad\Longleftrightarrow\quad
v_t(j)^{\lambda+1}\ge M_t^{\lambda+1}\eta^k.
\]
For rational answers these are exact rational comparisons of polynomial bit length, using \(\lambda<m\).
What remains open in this argument. The construction proves an upper bound, not a matching lower bound for arbitrary adaptive deterministic query algorithms. The optimal distortion is exactly \(1\) when the budget permits querying all positive-supply items. Outside that regime, neither the exact optimum nor a matching asymptotic lower bound is established here.
⟨structured verdict parsed — rendered above⟩
The output is partial relative to the full USER_TASK. The welfare argument establishes the requested upper bound, and the transportation formulation supports polynomial-time computation in the stated arithmetic model. The optimal worst-case distortion remains unresolved, as the prover explicitly acknowledges.
There is also an incorrect stronger query-count claim concerning the full-revelation branch. This does not invalidate compliance with the user’s actual query budget.
Since both sets of nonnegative masses sum to \(1\), each has a positive entry, so \(\eta\) is defined and satisfies \(0<\eta\le1\). Removing zero-mass rows and zero-supply columns preserves feasible welfare values. At least one item remains.
Restricting each ranking to the remaining items preserves the monotonicity needed throughout the proof. Every remaining supply satisfies \(q_j\ge\eta\).
In the branch where the allowed budget is less than \(m\), the assertion \(\lambda<m\) is valid: the prescribed budget is at least \(1+\lambda\).
Querying all \(m\) remaining values is permitted whenever the prescribed budget is at least \(m\). Optimizing those values gives welfare equal to the true optimum.
Minor issue: This branch need not satisfy the opening claim of at most \(1+\lambda\lceil\log_2|J|\rceil\) queries.
A concrete failure occurs with \(|J|=m=5\) and \(\lambda=1\). The prescribed budget is \(5\), so the algorithm queries all five values. The advertised stronger bound is \(4\).
Minimum clarification: Specify which budget controls this branch and make the global query-count assertion consistent with it. The current branch respects the USER_TASK budget.
For \(M_t>0\), each threshold is positive and no larger than \(M_t\). Thus position \(1\) is a valid true endpoint. The artificial sentinel need not correspond to an actual value.
Balanced binary search reduces an initial endpoint distance of \(m\) to \(1\) in at most \(\lceil\log_2m\rceil\) queries. Its final true endpoint is either position \(1\) or a queried position. Consequently, the boundary value used subsequently is indeed known.
For every queried position \(h\ge i\), ranking consistency gives \(v_t(j_{t,h})\le v_t(j_{t,i})\). The stated lower-estimate inequalities follow, including equality with \(M_t\) at position \(1\).
The case \(M_t=0\) is handled correctly by nonnegativity and monotonicity. The stated query bound is valid for the threshold-search branch.
The cases \(\lambda=0\) and \(M_t=0\) are valid.
In the remaining case, an item below the final threshold satisfies the additive bound directly. Otherwise, the set defining the smallest \(k\) is nonempty. Its position precedes the queried boundary, so the surrogate value is at least the corresponding threshold.
For \(k=1\), the upper bound by \(M_t\) gives the claimed multiplicative comparison. For \(k>1\), minimality gives the strict upper bound by the preceding threshold. Equality at a threshold causes no problem.
Hence inequality (1) is established for every remaining type and item.
The initial allocation respects row requirements because \(\eta\le1\). Its column loads satisfy the displayed bound because the masses of types selecting any one item sum to at most \(1\).
The residual formula is correct despite its canceling factors. Its marginals are
\(\sum_j r_{tj}=(1-\eta)\mu_t\)
and
\(\sum_t r_{tj}=q_j-\ell_j\).
Here the proof uses \(\sum_j\ell_j=\eta\) and \(\sum_t\mu_t=1\), both valid. All residual entries are nonnegative. The separate treatment of \(\eta=1\) avoids division by zero.
The initial allocation contributes exactly \(\eta S\) in surrogate welfare. Nonnegative residual contributions and surrogate optimality therefore establish (3).
Summation of (1) against a true optimum gives the additive contribution \(\rho^{-\lambda}S\) using its row sums. Surrogate optimality justifies replacing its surrogate welfare by \(\widehat W\). Inequality (3) then supplies the bound on \(S\).
The identity \(\eta^{-1}\rho^{-\lambda}=\rho\) is correct. Together with (2), it yields the requested factor.
The independent estimate \(W(x^\star;v)\le S\) is also valid, so the minimum of the two stated factors follows. Neither argument divides by a possibly zero welfare.
The transportation formulation has the correct supplies, demands, and objective sign. The displayed product allocation proves feasibility. Every entry is bounded by its row mass, so the feasible region is compact and an optimum exists.
The cited paper establishes strongly polynomial minimum-cost-flow algorithms and explicitly discusses their usefulness with irrational data. Thus arbitrary real query answers are compatible with the stated exact-arithmetic interpretation. [Orlin’s paper](https://www.math.ubc.ca/~anstee/math523/StronglyPolynomialNetworkFlow.pdf)
Minor issue: The prover does not state the precise theorem version being applied. The paper’s initial formulation uses integral balances and additional simplifying network assumptions; the write-up does not explain how its invocation accommodates rational balances and this transportation network.
Minimum clarification: State the applicable general minimum-cost-flow theorem, including its numeric assumptions, and identify any routine scaling or preprocessing required. Also specify a fixed deterministic implementation or tie-breaking convention. This is a standard application, not an identified mathematical obstruction.
The root-free threshold comparison is correct because raising nonnegative quantities to the positive integer power \(\lambda+1\) preserves order. With \(\lambda<m\), the rational powers have polynomial bit length. The optimization coefficients are indeed queried values or zero.
The proved inequality remains meaningful when optimal welfare is zero.
Minor issue: The original ratio is undefined when both numerator and denominator are zero. The inequality does not itself define that ratio.
Minimum clarification: State the convention for zero-optimum profiles, or formulate the guarantee throughout as the welfare inequality. This does not affect positive-optimum profiles.
Full revelation establishes distortion \(1\) in that regime, subject to the zero-welfare convention. Outside it, the output provides an upper bound only.
Major issue relative to the full assignment: There is no matching lower bound or other characterization establishing optimal worst-case distortion under the prescribed budget. The prover correctly acknowledges this omission; it is not an overclaim.
Required further work: Establish optimality against all permitted adaptive deterministic query algorithms, or determine a different optimal guarantee with matching bounds. This requires additional mathematics, not clarification of the existing proof.
The direction is promising: the central welfare proof survives verification. The overall classification remains partial because an explicitly requested component is unanswered. Under the supplied reporting rules, that requires the JSON complexity field to be "unresolved", despite the valid algorithmic upper-bound result.
⟨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.