Answer: —
Theorem 7 — class: algorithmic
Given item classes \(J=[d]\) with rational per-capita supplies \(q_j\ge 0\), a finite set of additive valuation types \(T\) with rational masses \(\mu_t\) summing to one, and comparison-oracle access to each type’s valuation \(v_t\), compute a finite-support rational assignment \(x_{t,b}\ge 0\) over integral bundles \(b\in\mathbb{Z}_{\ge 0}^d\). Require \(\sum_b x_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_j=q_j\) for every class \(j\); every bundle with positive assigned mass must satisfy \(v_t\cdot(b+e_j)\ge v_t\cdot q\) for some class with positive supply, and \(v_t\cdot b\ge\frac12\mathrm{MMS}_t(q)\). Here \(\mathrm{MMS}_t(q)\) is the maximum \(z\) for which a distribution over integral bundles has expectation \(q\) and every bundle in its support has value at least \(z\) under \(v_t\). Determine the comparison-query and running-time complexity in \(d\), \(|T|\), and the input bit length.
There are \(m=d\ge 1\) item classes with binary-rational per-capita supplies \(q_j\ge 0\), with \(\sum_j q_j>0\).
A society is given by its support: the list of \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\), summing to one; \(\tau\) counts supported types, not possible types.
Each type has a hidden additive valuation vector \(v_t\in\mathbb R_{\ge0}^d\). A comparison query presents two binary-encoded integral bundles \(a,b\in\mathbb Z_{\ge0}^d\) and returns one of greater value, choosing arbitrarily on equality; no numerical values or fractional-bundle queries are available.
Let \(L\) be the total bit length of the explicit rational input. Count oracle calls separately from bit operations, including the encoding of queries and output.
Define \(\mathrm{MMS}_t(q)=\sup\{z\ge0:\exists\text{ a probability distribution }p\text{ on }\mathbb Z_{\ge0}^d,\ \mathbb E_p[b]=q,\ p(b)>0\Rightarrow v_t\cdot b\ge z\}\).
The required assignment is a finite list of binary-encoded bundles and nonnegative rational masses \(x_{t,b}\), satisfying \(\sum_bx_{t,b}=\mu_t\) and \(\sum_{t,b}x_{t,b}b_j=q_j\) for every \(j\).
Every \(x_{t,b}>0\) must satisfy \(v_t\cdot b\ge\tfrac12\mathrm{MMS}_t(q)\) and \(v_t\cdot(b+e_j)\ge v_t\cdot q\) for some \(j\) with \(q_j>0\), where \(e_j\) is the unit vector; the added copy is hypothetical.
Is computing such an assignment deterministically possible with polynomially many comparison queries and polynomial bit running time in \(m,\tau,L\), or is it NP-hard? What is its worst-case comparison-query complexity in these parameters?
For finite societies with \(n\) agents and \(m\) indivisible goods, simultaneous PROP1 and \(\tfrac12\)-MMS allocation has a deterministic algorithm using \(O(n^4\log m)\) comparisons and the same stated running time; \(\Omega(\log m)\) comparisons are necessary even for constant-sized societies with identical valuations. [Source](https://arxiv.org/html/2404.18133v2)
These discrete results do not settle the mass-society problem defined above.
The assignment is computable deterministically in polynomial bit time, with
$$
O\!\left(\tau m\log(m+1)\right)
$$
comparison queries.
The optimal query complexity remains unresolved. The lower bounds can, however, be strengthened substantially beyond those in the notes: for $m\ge2$, the worst case requires
$$
\Omega\!\left(m+\tau\log(m+1)\right)
$$
comparisons. These bounds hold even when queries may use arbitrarily large integral coefficients.
The exceptional cases are completely settled: $m=1$ requires no comparisons, and $m=2$ has worst-case complexity $\Theta(\tau)$.
All arguments below concern the mass-society model directly; they do not apply the [cited finite-society theorem](https://arxiv.org/html/2404.18133v2).
Write
$$
J=\{j:q_j>0\}.
$$
This set is nonempty by hypothesis.
Suppose that, for each type $t$, we construct a finite rational probability distribution $p_t$ on integral bundles with mean $q$, satisfying both required inequalities. Setting
$$
x_{t,b}=\mu_t p_t(b)
$$
then gives
$$
\sum_b x_{t,b}=\mu_t,
\qquad
\sum_{t,b}x_{t,b}b_j
=\sum_t\mu_t q_j=q_j.
$$
Thus the types may be handled independently.
For the single-type construction, fix a valuation $v\in\mathbb R_{\ge0}^m$, and define
$$
V=v\cdot q,
\qquad
M=\max_{j\in J}v_j.
$$
The PROP1 requirement is equivalent to
$$
v\cdot b+M\ge V.
$$
Indeed, a class attaining $M$ belongs to $J$ and supplies the required hypothetical copy.
We will sometimes describe comparisons between nonnegative rational vectors. These are legal abbreviations: multiplying both vectors by a common positive denominator gives integral query bundles with the same comparison outcome. Each returned side certifies a weak inequality, including under arbitrary equality responses.
For nonnegative rational supplies $s$ and positive rational population mass $r$, define
$$
U(s,r)=\frac{v\cdot s}{r}
$$
and
$$
\mathcal T(s,r)=
\max\left\{
z\ge0:
\sum_j s_j\min(v_j,z)\ge rz
\right\}.
$$
The maximum exists. The feasible set contains zero and is closed, and every feasible threshold satisfies
$$
rz\le\sum_j s_j\min(v_j,z)\le v\cdot s.
$$
It is therefore contained in the compact interval $[0,U(s,r)]$.
Set
$$
\Theta=\mathcal T(q,1).
$$
For every valuation $v$,
$$
\mathrm{MMS}_v(q)\le\Theta.
$$
Proof. Suppose a distribution with mean $q$ guarantees value at least $z$ on its support. Every supported integral bundle satisfies
$$
\sum_j b_j\min(v_j,z)\ge z.
$$
If the bundle contains a copy worth at least $z$, that copy contributes $z$ to the truncated sum. Otherwise truncation leaves its value unchanged.
Taking expectations gives
$$
\sum_j q_j\min(v_j,z)\ge z.
$$
The expectations are legitimate because there are finitely many coordinates, each with finite prescribed mean. Hence $z\le\Theta$. Taking the supremum over feasible $z$ proves the claim. $\square$
Sort the active classes by nonincreasing unit value, using comparisons of unit bundles. Start with $s=q$ and $r=1$.
While supplies remain, let $h$ be a maximum-valued remaining class.
Every removal leaves $r>0$. There are at most $m$ removals.
Every removal preserves $\mathcal T(s,r)$.
Proof. At a removal,
$$
s_h<r,
\qquad
v_h\ge U(s,r).
$$
For the new supplies $s'$ and mass $r'=r-s_h$,
$$
U(s',r')
=
\frac{rU(s,r)-s_hv_h}{r-s_h}
\le U(s,r).
$$
For every $z\in[0,U(s,r)]$, we have $\min(v_h,z)=z$, so
$$
\sum_j s_j\min(v_j,z)\ge rz
\quad\Longleftrightarrow\quad
\sum_j s'_j\min(v_j,z)\ge r'z.
$$
Both feasible sets lie in this interval: the old one by its average bound, and the new one because its average does not increase. Thus the feasible sets coincide. $\square$
At termination, every remaining class satisfies
$$
v_j\le U(s,r).
$$
If a comparison caused termination, this follows because $h$ was maximum-valued. If $s_h\ge r$, nonnegativity gives
$$
U(s,r)\ge\frac{s_hv_h}{r}\ge v_h.
$$
If no supplies remain, the assertion is vacuous.
Consequently, truncation changes nothing at $z=U(s,r)$, and Lemma 2 yields
$$
\Theta=U(s,r),
\qquad
v\cdot s=r\Theta,
\qquad
v_j\le\Theta\quad\text{whenever }s_j>0.
$$
Every removed singleton has value at least $\Theta$, since its value was at least the current average, which bounds the preserved threshold.
Finally, if any removal occurred, its first removed class satisfied $v_h\ge V$. Therefore
$$
M\ge V.
$$
In that situation every nonnegative bundle automatically satisfies PROP1.
Let $a\in\mathbb Q_{\ge0}^k$, with corresponding values
$$
w_1\ge\cdots\ge w_k\ge0.
$$
One can construct, without further valuation queries, a rational distribution on at most $k+1$ integral bundles with mean $a$, every supported bundle having value at least
$$
\sum_{j=1}^k a_jw_j-w_1.
$$
Proof. Put
$$
C_0=0,
\qquad
C_j=\sum_{\ell=1}^j a_\ell.
$$
Let $g$ equal $w_j$ on $[C_{j-1},C_j)$ and zero on $[C_k,\infty)$. It is nonincreasing.
For $u\in[0,1)$, place one copy in the bundle for each point $u+\ell$, with $\ell$ a nonnegative integer, lying in a class interval. The resulting counts are
$$
b_j(u)=
\left\lceil C_j-u\right\rceil
-
\left\lceil C_{j-1}-u\right\rceil.
$$
These counts are nonnegative integers and can be computed directly.
Averaging over $u$ gives
$$
\int_0^1 b_j(u)\,du=C_j-C_{j-1}=a_j.
$$
For example, this follows by integrating the indicators of the points $u+\ell$ lying in $[C_{j-1},C_j)$; together, their integration domains cover that interval.
By monotonicity,
$$
\sum_{\ell\ge0}g(u+\ell)
\ge\int_u^\infty g(x)\,dx
\ge\int_0^\infty g(x)\,dx-w_1.
$$
This is the claimed value bound.
The bundle changes only at fractional parts of the prefix sums $C_j$. Partitioning $[0,1)$ at these rational breakpoints gives at most $k+1$ intervals. On each interval, evaluate the bundle at a rational midpoint and assign probability equal to the interval length. This produces the required finite rational distribution. $\square$
For $k=0$, the analogous construction is the empty bundle with probability one.
Consider the residual supplies $s$ and population mass $r$ after singleton removal.
For each remaining class, compare $2e_j$ with $s/r$. Let $A$ contain those classes for which the oracle returns $2e_j$. Then
$$
j\in A\Longrightarrow v_j\ge\frac{\Theta}{2},
\qquad
j\notin A\Longrightarrow v_j\le\frac{\Theta}{2}.
$$
Either classification is valid on equality. Put
$$
B=\sum_{j\in A}s_j.
$$
Choose rational quantities $c_j$, supported on $A$, with
$$
0\le c_j\le s_j,
\qquad
\sum_jc_j=r.
$$
A greedy choice suffices. Assign singleton $e_j$ to population mass $c_j$. Every recipient thereby gets value at least $\Theta/2$.
Distribute the leftover supplies $s-c$ to these same recipients as follows. Parametrize them by $u\in[0,1)$, with population mass $r\,du$. Give singleton labels on intervals of lengths $c_j/r$. Write
$$
\frac{s_j-c_j}{r}=k_j+f_j,
\qquad
k_j\in\mathbb Z_{\ge0},
\quad
0\le f_j<1.
$$
Give everyone $k_j$ additional copies of class $j$, and one more when $u<f_j$.
The singleton-label boundaries and the thresholds $f_j$ give only $O(m)$ intervals. Their bundles and rational masses consume exactly $s$. Nonnegative valuations preserve the singleton value guarantee.
Assign singleton $e_j$ to mass $s_j$ for every $j\in A$. The remaining mass is
$$
R=r-B>0,
$$
with supplies consisting of the classes outside $A$.
Its average value is
$$
U_{\mathrm{small}}
=
\frac{\sum_{j\notin A}s_jv_j}{R}
=
\frac{r\Theta-\sum_{j\in A}s_jv_j}{r-B}
\ge\Theta,
$$
because $v_j\le\Theta$ for every residual class.
Apply Lemma 3 to the small-class supplies divided by $R$, in their known value order. Their maximum value $w$ satisfies $w\le\Theta/2$. Hence every resulting bundle has value at least
$$
U_{\mathrm{small}}-w\ge\frac{\Theta}{2}.
$$
If no small classes remain, the preceding inequality forces $\Theta=0$, and the empty bundle is valid.
If singleton removal occurred, then $M\ge V$, so every constructed bundle satisfies PROP1.
Otherwise $\Theta=V$. A bundle containing an assigned singleton from $A$ satisfies
$$
v\cdot b+M
\ge v_j+M
\ge2v_j
\ge\Theta=V.
$$
A rounded small-class bundle satisfies
$$
v\cdot b+M
\ge U_{\mathrm{small}}-w+M
\ge U_{\mathrm{small}}
\ge\Theta=V,
$$
since $M\ge w$.
Every bundle also has value at least $\Theta/2$, including the initially removed singletons. Lemma 1 therefore gives
$$
v\cdot b\ge\frac{\Theta}{2}
\ge\frac12\mathrm{MMS}_v(q).
$$
The assigned masses sum to one, and their consumption is exactly $q$. Applying this construction independently to every type completes the assignment.
For each type, the algorithm uses:
Sorting remains valid under arbitrary equality responses: every comparison agrees with the weak numerical ordering of the actual values.
There are $O(m)$ output bundles per type. To check their encoding lengths, let $D$ be the product of the input supply denominators. Its bit length is $O(L)$. Every positive residual population mass $r$ or $R$ is an integer multiple of $1/D$, and thus is at least $1/D$. All supplies divided by these masses have polynomial encoding length.
The remaining operations—prefix sums, ceilings, fractional parts, interval lengths, and multiplication by $\mu_t$—preserve polynomial encoding length. Integral query bundles are obtained by denominator clearing. Bundle multiplicities are computed in binary without enumerating copies.
Thus the total query count is
$$
O\!\left(\tau m\log(m+1)\right),
$$
and all bit operations, query encoding, and output encoding take polynomial time in $m,\tau,L$.
Fix an integer $k$ with $2\le k\le m$, and take
$$
q_j=\frac1k\quad\text{for every }j,
\qquad
\mu_t=\frac1\tau\quad\text{for every }t.
$$
Each hidden valuation will be the indicator of a $k$-element set $H_t$:
$$
v_{t,j}=
\begin{cases}
1,&j\in H_t,\\
0,&j\notin H_t.
\end{cases}
$$
For every such valuation,
$$
\mathrm{MMS}_t(q)=1.
$$
The expected value is exactly $k/k=1$, giving the upper bound.
For attainability, choose one class uniformly from $H_t$, and independently include each class outside $H_t$ with probability $1/k$. This finite distribution has mean $q$ and value exactly one on every bundle.
Consequently, every qualifying bundle must satisfy
$$
\sum_{j\in H_t}b_j\ge1,
$$
because its value is integral and must be at least $1/2$.
For each type maintain a set $S_t$, initially all $m$ indices, such that every $k$-element subset of $S_t$ remains a possible valued set.
For a query to type $t$, let $c=a-b$.
If $|S_t|\ge2k$, retain whichever of
$$
\{j\in S_t:c_j\ge0\},
\qquad
\{j\in S_t:c_j<0\}
$$
is larger. Answer in favor of $a$ for the first set, and $b$ for the second. Every $k$-element subset of the retained set is consistent with this answer.
If $|S_t|<2k$, fix any $k$-element subset of $S_t$ and answer this and subsequent queries truthfully for that fixed valuation.
Each query reduces the maintained set size by at most a factor of two. If $K_t$ queries have been directed to type $t$, then
$$
|S_t|\ge m\,2^{-K_t}.
$$
The possible valuations for different types remain independent.
At termination, every positive-mass bundle assigned to type $t$ must intersect every $k$-element subset of $S_t$. Otherwise a possible hidden valuation would give it value zero.
Thus the bundle has at most $k-1$ zero coordinates within $S_t$, and integrality implies
$$
\sum_j b_j\ge |S_t|-k+1.
$$
The total supply is $m/k$. Therefore
$$
\frac{m}{k}
\ge
\frac1\tau\sum_t\bigl(|S_t|-k+1\bigr),
$$
or
$$
\frac1\tau\sum_t|S_t|
\le\frac{m}{k}+k-1.
$$
Let $N=\sum_tK_t$ be the total number of queries. Convexity of the exponential gives
$$
\frac1\tau\sum_t|S_t|
\ge
\frac{m}{\tau}\sum_t2^{-K_t}
\ge m\,2^{-N/\tau}.
$$
Combining the inequalities yields the explicit lower bound
$$
N\ge
\tau\log_2\left(
\frac{m}{m/k+k-1}
\right).
$$
Choose $k=\lceil\sqrt m\rceil$. Then
$$
\frac{m}{k}+k-1<2\sqrt m,
$$
so
$$
N>
\tau\left(\frac12\log_2m-1\right).
$$
In particular, for $m\ge16$,
$$
N\ge\frac{\tau}{4}\log_2m.
$$
This proves $\Omega(\tau\log m)$.
The proof places no restriction on query coefficient sizes.
This bound uses the same supplies $q_j=1/k$, but all types have the same unknown valued set $H$, of size $k$.
For a fixed output, aggregate its positive masses into a probability distribution $p$ on bundles. It has mean $q$.
If the output is valid for $H$, every supported bundle contains at least one valued copy. Its expected number of valued copies is
$$
\sum_{j\in H}q_j=1.
$$
Hence every positive-mass bundle must contain exactly one valued copy:
$$
\sum_{j\in H}b_j=1.
$$
We next bound how many valued sets can be compatible with one output.
A finite distribution with mean $(1/k,\ldots,1/k)$ can satisfy
$$
\sum_{j\in H}b_j=1
$$
on every supported bundle for at most
$$
\left(\frac{m}{k}\right)^k
$$
different $k$-element sets $H$.
Proof. Let $\mathcal F$ be the family of compatible sets. If it is empty, there is nothing to prove.
Let $E$ consist of those coordinates satisfying $b_j\le1$ on every supported bundle. Every $H\in\mathcal F$ is contained in $E$, since a valued coordinate with multiplicity at least two would violate the displayed equality.
For each supported bundle define
$$
A_b=\{j\in E:b_j=1\}.
$$
Every compatible set intersects $A_b$ in exactly one coordinate. Moreover, for each $j\in E$,
$$
\sum_b p(b)\mathbf 1_{\{j\in A_b\}}
=\mathbb E_p[b_j]=\frac1k.
$$
Choose $H$ uniformly from $\mathcal F$, and let $X_j$ be its membership indicators on $E$. Write $\mathsf H$ for Shannon entropy in bits.
We use three elementary entropy facts: the chain rule, reduction of conditional entropy under additional conditioning, and the bound $\mathsf H(Y)\le\log_2 r$ for a variable with at most $r$ possible outcomes. The chain rule follows by factoring joint probabilities. Conditioning reduction follows from concavity of entropy; the outcome bound follows from concavity of the logarithm.
Order the coordinates of $E$. For every subset $A\subseteq E$, the chain rule and conditioning reduction give
$$
\mathsf H(X_A)
\ge
\sum_{j\in A}\mathsf H(X_j\mid X_{<j}),
$$
where $X_{<j}$ includes all earlier coordinates of $E$.
Multiply this inequality for $A=A_b$ by $kp(b)$ and sum over bundles. The covering identity above gives
$$
\begin{aligned}
k\sum_b p(b)\mathsf H(X_{A_b})
&\ge
\sum_{j\in E}
\left(k\sum_b p(b)\mathbf 1_{\{j\in A_b\}}\right)
\mathsf H(X_j\mid X_{<j})\\
&=
\sum_{j\in E}\mathsf H(X_j\mid X_{<j})\\
&=\mathsf H(X_E).
\end{aligned}
$$
Since $X_{A_b}$ has exactly one nonzero coordinate,
$$
\mathsf H(X_{A_b})\le\log_2|A_b|.
$$
Every $A_b$ is nonempty because $\mathcal F$ is nonempty. Concavity of the logarithm now gives
$$
\begin{aligned}
\log_2|\mathcal F|
=\mathsf H(X_E)
&\le k\sum_b p(b)\log_2|A_b|\\
&\le k\log_2\left(\sum_b p(b)|A_b|\right)\\
&=k\log_2\left(\frac{|E|}{k}\right)\\
&\le k\log_2\left(\frac{m}{k}\right).
\end{aligned}
$$
Exponentiation proves the lemma. $\square$
Fix a permissible deterministic tie rule, such as returning the first bundle on equality. There are
$$
\binom{m}{k}
$$
possible identical valuations. An algorithm using at most $Q$ binary comparisons has at most $2^Q$ leaves.
By Lemma 4, each leaf’s output can be valid for at most $(m/k)^k$ of these valuations. Therefore
$$
Q\ge
\log_2\binom{m}{k}
-
k\log_2\left(\frac{m}{k}\right).
$$
For $m=2k$, this becomes
$$
Q\ge\log_2\binom{2k}{k}-k.
$$
The central binomial coefficient is the largest of the $2k+1$ binomial coefficients whose sum is $2^{2k}$, so
$$
Q\ge k-\log_2(2k+1)=\Omega(m).
$$
For odd $m$, use $m-1$ active classes and give the remaining class zero supply. This proves the same asymptotic bound.
Thus $\Omega(m)$ comparisons are necessary even with identical valuations and any number of supported types.
For $m=1$, let $q>0$ and $v\ge0$. Then
$$
\mathrm{MMS}_v(q)=v\lfloor q\rfloor.
$$
The floor-and-ceiling lottery attains this value. If $v>0$, any strictly larger guaranteed threshold would require every bundle to contain at least $\lfloor q\rfloor+1$ copies, contradicting its mean. For $v=0$, the identity is immediate.
Give every type this lottery. Each bundle has at least $\lfloor q\rfloor$ copies and satisfies
$$
b+1\ge q.
$$
Both fairness requirements follow without any comparison queries.
The upper bound already gives $O(\tau)$ comparisons.
For a matching lower bound, take equal type masses and
$$
q=\left(\frac9{10},\frac9{10}\right).
$$
Consider the two possible valuations
$$
v^{(1)}=(1,9),
\qquad
v^{(2)}=(9,1).
$$
Both have MMS equal to $9$. For $v^{(1)}$, a lottery assigning $e_2$ with probability $9/10$ and $9e_1$ with probability $1/10$ has mean $q$ and constant value $9$. The expected-value upper bound is also $9$. The other valuation is symmetric.
Answer every query consistently with $v^{(1)}$. An unqueried type could have either valuation. Every bundle assigned to it must therefore satisfy both half-MMS inequalities. A bundle with fewer than two copies cannot do so: a singleton has value one under one of the valuations.
Every queried type must receive a nonempty bundle. If $U$ types remain unqueried, total consumption is therefore at least
$$
\frac{2U+(\tau-U)}{\tau}
=1+\frac U\tau.
$$
The actual total supply is $9/5$, forcing
$$
U\le\frac45\tau.
$$
At least $\tau/5$ types must be queried. Hence the worst-case complexity for $m=2$ is $\Theta(\tau)$.
For $m\ge2$, combining the linear lower bound with the product lower bound gives
$$
\boxed{
\Omega\!\left(m+\tau\log(m+1)\right)
\ \le\
\text{optimal worst-case query complexity}
\ \le\
O\!\left(\tau m\log(m+1)\right).
}
$$
For bounded $m$, the two-class construction supplies the needed $\Omega(\tau)$ lower bound by adding zero-supply classes.
The upper bound holds for every explicit input length $L$. The lower bounds use input families of length
$$
O\!\left(m\log(m+1)+\tau\log(\tau+1)\right).
$$
Thus they establish hardness already for polynomial-size rational inputs, without relying on large query encodings.
The positive polynomial-time classification is fully proved. The optimal dependence of query complexity on jointly growing $m$ and $\tau$ remains open.
⟨structured verdict parsed — rendered above⟩
The polynomial-time construction is sound. The output therefore resolves the polynomial-time-versus-hardness question in favor of polynomial time. It does not determine the optimal worst-case comparison-query complexity, which it explicitly leaves open. One lower-bound argument also needs a minor clarification about its maintained state.
This reduction is correct. If each $p_t$ has mean $q$, then $x_{t,b}=\mu_t p_t(b)$ satisfies both the type-mass constraints and aggregate supply constraints. Finiteness and rationality are preserved.
The PROP1 reformulation is also correct:
$$
v\cdot b+M\ge V,
\qquad
M=\max_{j:q_j>0}v_j,
\qquad
V=v\cdot q.
$$
The maximum is attained because the active set is finite and nonempty.
Clearing a common positive denominator makes the proposed rational-vector comparisons legal integral-bundle queries. Arbitrary equality responses certify the weak inequalities used subsequently.
The existence argument for $\mathcal T(s,r)$ is valid. Its feasible set is nonempty, closed, and contained in the finite interval $[0,U(s,r)]$.
Lemma 1 is correct. For every supported integral bundle, either some copy has value at least $z$, or truncation leaves every included copy’s value unchanged. In either case,
$$
\sum_j b_j\min(v_j,z)\ge z.
$$
Taking expectations is justified by the finite number of coordinates and their finite prescribed means. Taking the supremum over attainable guarantees proves the stated MMS upper bound; attainment of MMS is unnecessary.
Every removal has $s_h<r$, so the remaining population mass is positive. The oracle response used for removal implies $v_h\ge U(s,r)$.
Lemma 2’s algebra and feasible-set equivalence are correct. The new average does not increase, and both feasible sets lie in the interval on which $\min(v_h,z)=z$.
At termination, the stated bound on every residual unit value follows from either stopping condition. If supplies are exhausted, the residual average and threshold are both zero. Thus this edge case causes no division by zero or omitted positive-value population.
Removed singletons meet the threshold guarantee. Moreover, the first removal implies $M\ge V$, which indeed makes PROP1 automatic for every nonnegative bundle.
Lemma 3 is correct.
The ceiling formula counts the nonnegative integral lattice points belonging to each class interval. Its integral over $u\in[0,1)$ gives the prescribed mean.
The monotonicity estimate
$$
\sum_{\ell\ge0}g(u+\ell)
\ge \int_u^\infty g(x)\,dx
\ge \int_0^\infty g(x)\,dx-w_1
$$
is valid because $g$ is nonnegative, nonincreasing, and bounded above by $w_1$.
The rational breakpoints yield at most $k+1$ positive-length intervals. Midpoint representatives preserve the means because breakpoint values have measure zero. The empty-coordinate case is explicitly covered.
Both cases are correct.
When $B\ge r$, the singleton masses total $r$. The additional-copy construction consumes exactly the remaining supplies and preserves each singleton’s value guarantee.
When $B<r$, the calculation $U_{\mathrm{small}}\ge\Theta$ correctly uses the residual bound $v_j\le\Theta$. Lemma 3 then gives the required half-threshold guarantee. The case of no small classes is handled correctly: it forces $\Theta=0$.
The PROP1 verification covers removed singletons, residual singleton recipients, and rounded bundles. When no removal occurred, $\Theta=V$; the displayed inequalities establish PROP1 in each residual case.
Consequently, every positive-mass output bundle satisfies both requirements of the task.
The upper bound
$$
O\!\left(\tau m\log(m+1)\right)
$$
is justified. Sorting, singleton removal, and residual classification use the stated numbers of comparisons. A conventional comparison sort remains valid under arbitrary tie responses because every response respects the actual weak numerical order.
The bit-complexity accounting is sound. The product $D$ of supply denominators has bit length $O(L)$. Positive residual masses are integer multiples of $1/D$, so their reciprocals have polynomial encoding length. The subsequent rational operations, denominator clearing, and binary bundle counts also have polynomial encoding length.
The construction produces $O(m)$ bundles per type and never needs to enumerate individual copies. Thus query encoding and output encoding are included in the polynomial-time conclusion.
The indicator valuations have MMS exactly one, and the initial sign-based adversary responses are consistent with every $k$-element subset of the retained set.
Minor issue: the freezing branch does not explicitly update $S_t$. The proof first describes $S_t$ as representing every still-possible $k$-element valued set. When $|S_t|<2k$, it fixes one subset and answers truthfully for that valuation, but does not state what happens to $S_t$. The later resource argument still requires every $k$-element subset of $S_t$ to remain possible.
Under a literal interpretation that leaves $S_t$ unchanged, this invariant is false. For example, take $m=5$, $k=3$, and fix $H=\{1,2,3\}$. The query comparing $e_1$ with $e_4$ returns $e_1$, excluding the alternative set $\{2,4,5\}$, although that set remains a subset of the unchanged $S_t$.
Minimum clarification: explicitly specify the maintained set after fixing a valuation and confirm that both the possible-subset invariant and the displayed size bound apply to that same set. This is a routine state-definition clarification rather than a gap requiring new mathematics.
Subject to that clarification, the resource-conservation calculation, convexity inequality, and choice $k=\lceil\sqrt m\rceil$ check out. The claimed coefficient for $m\ge16$ is correct.
This argument is correct.
For identical indicator valuations, every positive-mass bundle must contain exactly one valued copy: it contains at least one, and the aggregate expected number is exactly one.
Lemma 4’s entropy argument is valid. All variables have finite ranges. The coordinate coverage identity justifies the weighted chain-rule inequality, and the exactly-one condition gives the stated entropy bound for each $A_b$. The logarithmic concavity step then yields the claimed bound on compatible valued sets.
The decision-tree leaf count is applicable after fixing a permissible tie rule. The central-binomial calculation proves the asymptotic linear bound. Adding a zero-supply coordinate handles odd dimensions without allowing that coordinate to appear in any positive-mass bundle.
The one-class MMS formula and zero-query lottery are correct, including zero valuations and integral supplies.
The two-class lower bound is also correct. Both example valuations have MMS nine. An unqueried type needs at least two copies in every assigned bundle, while every queried type needs at least one. Aggregate supply therefore forces at least $\tau/5$ queried types, establishing the claimed $\Theta(\tau)$ complexity.
Major coverage gap: the jointly growing query-complexity parameters remain unresolved. The displayed upper and lower bounds do not match, and the output explicitly acknowledges this. This is incomplete coverage of the requested optimal worst-case complexity, not a defect in the polynomial-time algorithm.
The work establishes substantial progress: a valid deterministic polynomial-time construction, a valid linear query lower bound, and the exact stated edge cases. The optimal general query complexity still requires another round.
⟨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.