Answer: —
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor any ε > 0, there exists a submodular (2 −ε)-stable valuations profile ⃗v such that for any integer k ≥1, approximating the optimal allocation in ⃗v within any factor larger than 1−1 2k requires at least m k value queries.
statement extracted from the paper’s text layer; consult the paper for the exact wording
For \(\epsilon>0\), admissible \(m,k\) with \(k\mid m\), and \(\rho>1-\frac{1}{2k}\), consider societies with \(\tau=m/k\) complete submodular valuation types, each of mass \(\mu_t=1/\tau\), and per-capita supply \(b_j=1/\tau\) for each of \(m\) item categories. Each unit of mass must receive an integral bundle \(S\subseteq M\), while the allocation variables \(x_{t,S}\) may be fractional and satisfy \(\sum_S x_{t,S}=\mu_t\) and \(\sum_{t,S:\,j\in S}x_{t,S}\le b_j\). Given value-oracle access to each \(v_t\), and restricting to instances with a unique optimum unchanged after any submass \(\delta\) of a type is split off and its value for one item is inflated by the paper’s \((2-\epsilon)\)-perturbation, must every algorithm use at least \(\binom{m}{k}\) queries in the worst case to return a feasible allocation with welfare at least \(\rho\) times optimal?
Let \(M\) have \(m\) item categories, with integers \(k\geq1\), \(k\mid m\), and \(\tau=m/k\geq2\); fix rational \(0<\epsilon\leq1\) and \(1-1/(2k)<\rho\leq1\).
A society is given by its support: the list of its \(\tau\) positive-mass types and their binary rational masses. Here \(\mu_t=1/\tau\), so total mass is \(1\); \(\tau\) counts supported types, not all possible valuations.
Each type has a normalized, monotone submodular valuation \(v_t:2^M\to\mathbb{Q}_{\geq0}\), defined on every bundle and accessible only through exact value queries \((t,S)\mapsto v_t(S)\).
An allocation consists of real masses \(x_{t,S}\geq0\) satisfying \(\sum_{S\subseteq M}x_{t,S}=\mu_t\) and \(\sum_t\sum_{S\ni j}x_{t,S}\leq1/\tau\) for every \(j\in M\). Each recipient receives an integral bundle; empty bundles are allowed.
Welfare is \(W(x)=\sum_t\sum_{S\subseteq M}x_{t,S}v_t(S)\), and \(\mathrm{OPT}=\max_x W(x)\).
Promise that the maximizing vector \(x^*\) is unique. For every type \(t\), item \(j\), and rational \(0<\delta\leq\mu_t\), split \(t\) into masses \(\mu_t-\delta\) and \(\delta\), retaining \(v_t\) on the former and replacing it on the latter by \(v'_{t,j}(S)=v_t(S)+(1-\epsilon)v_t(S\cap\{j\})\); supplies stay fixed and zero-mass rows are omitted.
The proportional lift of \(x^*\), assigning \((1-\delta/\mu_t)x^*_{t,S}\) and \((\delta/\mu_t)x^*_{t,S}\) to these rows, must remain the unique welfare optimum after every such perturbation.
Use deterministic algorithms; let \(L\) bound the binary lengths of the explicit input and oracle replies, and state query bounds and running times in \(m,\tau,L,k,\epsilon,\rho\).
Must every deterministic value-oracle algorithm guaranteeing a feasible allocation with \(W(x)\geq\rho\,\mathrm{OPT}\) on this promised class use at least \(\binom{m}{k}\) queries in the worst case, or can this guarantee be achieved with fewer queries?
For discrete auctions with \(m/k\) bidders, a stated oracle inapproximability result requires at least \(\binom{m}{k}\) value queries for approximation above \(1-1/(2k)\) under \((2-\epsilon)\)-stability ([source](https://arxiv.org/pdf/2006.09889v2)).
The later published version also states that these discrete stable submodular auctions admit no polynomial-time approximation scheme ([source](https://link.springer.com/article/10.1007/s00224-022-10078-9)). No result settling the specified continuous promise was located.
Write
$$
N=\binom{m}{k},
\qquad
\alpha=2k\rho-(2k-1).
$$
The assumptions imply $0<\alpha\leq1$.
I prove the following new full-class lower bounds:
$$
\binom{m}{\lfloor m/2\rfloor}\geq N
$$
queries.
For all admissible parameters, I also prove
$$
Q\geq
\max\left\{
\tau,\,
0,\,
\left\lceil N-\frac1\alpha\right\rceil
\right\},
$$
where $Q$ denotes worst-case query complexity.
These results do not settle the question for every admissible parameter choice. In particular, the case $\tau=2$, $\epsilon<1$, $\rho=1$ remains unresolved here.
All constructions and arguments below are self-contained.
Every promised instance has a partition
$$
(O_1,\ldots,O_\tau)
$$
of $M$, possibly containing empty parts, such that
$$
x^*_{t,O_t}=\frac1\tau
$$
and all other coordinates vanish.
Proof. Suppose one row $t$ has positive mass on distinct bundles $A$ and $B$. Split that row with $\delta=\mu_t/2$, using any item $j$.
In the proportional lift, both split rows have positive mass on both bundles. For sufficiently small $h>0$, make the following exchange: in the perturbed row, add $h$ on $A$ and subtract $h$ on $B$; in the unperturbed row, do the reverse.
Both this exchange and its negative are feasible. They preserve row masses and aggregate masses on every bundle, hence preserve item usages. Because welfare is linear, either one direction improves welfare, or the exchange produces a distinct optimum. Both conclusions contradict the split promise.
Thus each original row uses exactly one bundle. Its mass is $1/\tau$, so the supply constraints force these bundles to be disjoint.
If an item were unassigned, adding it to any row’s bundle would preserve feasibility. Monotonicity would either increase welfare, contradicting optimality, or preserve welfare, contradicting uniqueness. Thus the bundles cover $M$. ∎
Suppose an instance has a unique optimum that is a partition allocation. Then its complete split promise holds if and only if every allowed full-type perturbation, corresponding to $\delta=\mu_t$, preserves that allocation as the unique continuous optimum.
Proof. Necessity follows by taking $\delta=\mu_t$.
For sufficiency, fix a split of type $t$ and an item $j$. Normalization gives the perturbation bonus
$$
c=(1-\epsilon)v_t(\{j\})\geq0
$$
on bundles containing $j$. Aggregate the two split rows of a feasible split allocation $z$ into an original row, obtaining a feasible original allocation $y$.
If $j\in O_t$, then
$$
W_{\mathrm{split}}(z)
=
W(y)+c\sum_{S\ni j}z^{\mathrm{pert}}_S
\leq
\mathrm{OPT}+c\delta.
$$
The proportional lift attains this bound. Equality forces $W(y)=\mathrm{OPT}$, hence $y=x^*$ by original uniqueness.
If $j\notin O_t$, nonnegativity gives
$$
W_{\mathrm{split}}(z)
\leq
W(y)+c\sum_{S\ni j}y_{t,S}
=
W_{\mathrm{full}}(y)
\leq
\mathrm{OPT}.
$$
The last inequality uses the full perturbation’s unique optimum, which receives no bonus. Again, the proportional lift attains the bound, and equality forces $y=x^*$.
In either case, aggregation to a row supported only on $O_t$ forces both split rows to use only $O_t$. Their prescribed masses determine the proportional lift uniquely. The argument also covers the omission of a zero-mass row. ∎
In particular, when $\epsilon=1$, every unique partition optimum automatically satisfies the split promise.
This argument uses additive valuations, so it applies throughout the promised class.
For every admissible $\epsilon$ and $\rho$, every deterministic guaranteeing algorithm requires at least $\tau$ queries in the worst case.
Proof. Since $\rho>1-1/(2k)\geq1/2$, put
$$
g=2\rho-1>0.
$$
Choose positive dyadic rationals $b$ and $C$ satisfying
$$
b\leq\frac g8,
\qquad
C\geq\frac4g.
$$
Suppose an algorithm uses fewer than $\tau$ queries on every promised instance. Let $a$ be the type in its first query. If it makes no queries, choose any type $a$.
Define a baseline instance by
$$
v_t(S)=\lambda_t|S|,
\qquad
\lambda_a=1,
\qquad
\lambda_t=\frac{bt}{\tau+1}\quad(t\ne a).
$$
Thus all nonowner coefficients are positive, distinct, and at most $b$.
The unique optimum gives all of $M$ to type $a$ and empty bundles to all other types. To verify the full perturbation promise, note that an item’s additive coefficient in any competing type can increase to at most
$$
(2-\epsilon)b\leq2b<1.
$$
Type $a$ therefore remains the unique highest-valued recipient of every item. The continuous optimum is unique: equality in the itemwise welfare bound forces every item’s entire supply to type $a$, which forces that row to use $M$ and every other row to use the empty bundle. Proposition 2 establishes the split promise.
Run the algorithm on this baseline. There is a type $h\ne a$ that it never queries: when queries occur, $a$ is queried first; when none occur, any other type suffices.
Define a second instance by replacing only $\lambda_h$ by $C$. The transcript is unchanged. This second instance is also promised, because
$$
C\geq4>2\geq(2-\epsilon)\max_{t\ne h}\lambda_t.
$$
Its unique optimum gives all items to type $h$.
For the common output, normalize
$$
y_{t,S}=\tau x_{t,S}.
$$
Each row sums to one, and feasibility implies
$$
\sum_{t,S}|S|y_{t,S}\leq m.
$$
Let
$$
A=\sum_S|S|y_{a,S},
\qquad
H=\sum_S|S|y_{h,S}.
$$
On the baseline,
$$
\tau W(x)\leq A+b(m-A),
\qquad
\mathrm{OPT}=\frac m\tau.
$$
Consequently, a successful baseline output must satisfy
$$
\frac Am\geq r:=\frac{\rho-b}{1-b}.
$$
Because $b\leq1/8$,
$$
r
=
\rho-\frac{b(1-\rho)}{1-b}
\geq\rho-2b
\geq\rho-\frac g4.
$$
On the second instance, all coefficients other than $C$ are at most one. Hence
$$
\frac{W'(x)}{\mathrm{OPT}'}
\leq
\frac Hm+\frac1C
\leq
1-\frac Am+\frac1C
\leq
1-r+\frac g4
\leq
1-\rho+\frac g2
=
\frac12
<
\rho.
$$
Here $A+H\leq m$ follows from feasibility.
Thus the same output cannot satisfy the approximation guarantee on both promised instances, a contradiction. ∎
When $k=1$, we have $\tau=m=N$. Therefore this proves the requested literal lower bound for the entire allowed range of $\epsilon$ and $\rho$ in that case.
These instances have explicit-input and oracle-reply binary lengths
$$
O\left(\log(m+1)+\log(\tau+1)+\log\frac1{2\rho-1}\right).
$$
I use the hidden-partition valuations appearing in the proof of Theorem 2 of [Fikioris and Fotakis](https://arxiv.org/pdf/2006.09889v2), but verify their continuous properties directly.
Choose an ordered partition $(O_1,\ldots,O_\tau)$ with $|O_t|=k$. Define
$$
v_t(S)=
\begin{cases}
|S|,& |S|\leq k-1,\\
k-\frac12,& |S|=k,\ S\ne O_t,\\
k,& S=O_t\text{ or }|S|\geq k+1.
\end{cases}
$$
Normalization and monotonicity follow directly from the definition. The possible marginal values when adding an item to a bundle of cardinality $s$ are
$$
\begin{array}{c|c}
s&\text{possible marginals}\\ \hline
s\leq k-2&1\\
s=k-1&\frac12,\ 1\\
s=k&0,\ \frac12\\
s\geq k+1&0.
\end{array}
$$
For strictly nested bundles, cardinality increases, and every possible earlier marginal is at least every possible later marginal. This proves diminishing returns, hence submodularity. For $k=1$, the first row is absent and the same reasoning applies.
Giving each type $O_t$ yields welfare $k$. Every bundle has value at most $k$, and total recipient mass is one, so
$$
\mathrm{OPT}=k.
$$
First recall a direct price argument. Suppose nonnegative prices $p_j$ make each $O_i$ the unique maximizer of
$$
u_i(S)=v_i(S)-\sum_{j\in S}p_j.
$$
For every feasible allocation,
$$
W(x)
\leq
\frac1\tau\sum_i u_i(O_i)
+
\frac1\tau\sum_jp_j.
$$
The partition allocation attains equality. Positive mass on any other bundle makes the utility inequality strict, proving uniqueness.
For the original valuations, uniform prices $p_j=1/2$ give this certificate.
Now perturb an entire type $t$ on item $j$. Set
$$
d=\frac{1-\epsilon}{2},
\qquad
p_j=\frac12+d,
\qquad
p_\ell=\frac12\quad(\ell\ne j).
$$
For an unperturbed type $i$ and a bundle $S\ne O_i$, write $r=|S|$. Its utility gap below $O_i$ is
$$
u_i(O_i)-u_i(S)
=
\frac{a_r}{2}
+
d\bigl(\mathbf1[j\in S]-\mathbf1[j\in O_i]\bigr),
$$
where
$$
a_r=
\begin{cases}
k-r,&r\leq k-1,\\
1,&r=k,\\
r-k,&r\geq k+1.
\end{cases}
$$
Since $a_r\geq1$, this gap is at least
$$
\frac12-d=\frac\epsilon2>0.
$$
For the perturbed type, the bonus is
$$
c=(1-\epsilon)v_t(\{j\})\leq1-\epsilon.
$$
If $j\in O_t$, the bonus increases each gap by
$$
c(1-\mathbf1[j\in S])\geq0.
$$
If $j\notin O_t$, alternatives excluding $j$ have unchanged gaps. Alternatives containing $j$ have an original gap at least $1/2+d$, so their perturbed gap is at least
$$
\frac12+d-c
\geq
\frac12+\frac{1-\epsilon}{2}-(1-\epsilon)
=
\frac\epsilon2.
$$
Thus every type uniquely demands its designated bundle at these prices after every full perturbation. The price argument and Proposition 2 prove the complete continuous promise.
Oracle replies and masses have binary length $O(\log(m+1)+\log(\tau+1))$.
For every bundle,
$$
v_t(S)
\leq
\frac{|S|+k-1}{2}
+
\frac12\mathbf1[S=O_t].
$$
For cardinality below $k$, this follows from $|S|\leq k-1$; above $k$, it follows from $|S|\geq k+1$. At cardinality $k$, equality holds.
For a feasible output, put
$$
y_{t,S}=\tau x_{t,S},
\qquad
H(O)=\sum_t y_{t,O_t}.
$$
Each row of $y$ sums to one. Summing item constraints gives
$$
\sum_{t,S}|S|y_{t,S}\leq m=\tau k.
$$
Therefore
$$
W(x)\leq k-\frac12+\frac{H(O)}{2\tau}.
$$
Since $\mathrm{OPT}=k$, the requested guarantee requires
$$
H(O)\geq\tau\alpha.
$$
Answer queries using the common baseline: value $|S|$ below cardinality $k$, value $k-1/2$ at cardinality $k$, and value $k$ above it.
Let an algorithm have worst-case query bound $q<N$. A uniformly random ordered balanced partition has each $O_t$ uniform among the $N$ subsets of cardinality $k$. Every fixed query excludes at most a $1/N$ fraction of partitions. Thus the event $A$ that a partition agrees with all baseline replies satisfies
$$
\Pr(A)\geq1-\frac qN>0.
$$
The baseline execution must terminate within $q$ queries. Otherwise a compatible promised instance after the first $q$ replies would force the same deterministic execution to exceed its query bound.
Its output is fixed across all compatible partitions. For that output,
$$
\mathbb E[H(O)]
=
\frac1N\sum_t\sum_{|S|=k}y_{t,S}
\leq\frac\tau N.
$$
As $H(O)\geq0$,
$$
\mathbb E[H(O)\mid A]
\leq
\frac{\tau}{N-q}.
$$
Some compatible instance therefore satisfies
$$
\frac{W(x)}{\mathrm{OPT}}
\leq
1-\frac1{2k}
+
\frac1{2k(N-q)}.
$$
This is strictly smaller than $\rho$ whenever $q<N-1/\alpha$. Consequently,
$$
Q\geq
\max\left\{0,\left\lceil N-\frac1\alpha\right\rceil\right\}.
$$
The following argument strengthens the preceding expectation bound.
If $\tau\geq3$ and
$$
\rho>1-\frac1{2m},
$$
every deterministic guaranteeing algorithm requires at least $N$ queries.
Proof. Suppose its worst-case bound is $q\leq N-1$, and use the same baseline transcript.
The number of ordered balanced partitions is
$$
P=\frac{m!}{(k!)^\tau}.
$$
Each query excludes at most $P/N$ partitions. Hence at least
$$
P-\frac{qP}{N}
\geq
\frac PN
=
\frac{(m-k)!}{(k!)^{\tau-1}}
$$
partitions remain compatible.
When $\tau\geq3$, this last number is at least two: after fixing $O_1$, there are at least two ways to partition the remainder, obtained, for example, by exchanging an item between two remaining nonempty parts.
Choose distinct compatible partitions $O$ and $\widetilde O$. They differ in at least two rows, because if all but one part agreed, the final parts would also agree.
For a row where they differ, the row-sum constraint gives
$$
y_{t,O_t}+y_{t,\widetilde O_t}\leq1.
$$
For a row where they agree, the corresponding contribution to
$H(O)+H(\widetilde O)$ is at most two. Therefore
$$
H(O)+H(\widetilde O)\leq2\tau-2.
$$
At least one of these two compatible instances has $H\leq\tau-1$. On that instance,
$$
W(x)
\leq
k-\frac12+\frac{\tau-1}{2\tau}
=
k-\frac1{2\tau},
$$
and hence
$$
\frac{W(x)}{\mathrm{OPT}}
\leq
1-\frac1{2k\tau}
=
1-\frac1{2m}
<
\rho.
$$
This contradicts the guarantee. ∎
This establishes the literal lower bound, including for exact optimization, whenever $\tau\geq3$.
The previous family leaves an elimination loophole when $\tau=2$: all but one candidate bundle can identify the last candidate. The construction below removes that loophole by allowing both upward and downward changes.
For $\epsilon=1$ and $\rho=1$, every deterministic algorithm requires at least
$$
R=\binom{m}{\lfloor m/2\rfloor}
$$
queries on the full promised class.
Proof. Put
$$
r=\lfloor m/2\rfloor,
\qquad
s=m-r.
$$
Since $m\geq2$, both are positive. Define the cardinality valuation
$$
f_n(S)=
\begin{cases}
|S|,&|S|\leq n-1,\\
n-\frac14,&|S|=n,\\
n,&|S|\geq n+1.
\end{cases}
$$
Its marginal sequence is
$$
1,\quad\frac34,\quad\frac14,\quad0,
$$
with absent ranges omitted. Thus it is normalized, monotone, and submodular.
Index items by $1,\ldots,m$ and set
$$
a_j=\frac{2^{j-1}}{100\cdot2^m},
\qquad
a(S)=\sum_{j\in S}a_j.
$$
Distinct subsets have distinct $a(S)$, and
$$
0\leq a(S)<\frac1{100}.
$$
The baseline valuations of the first two types are
$$
v_1(S)=f_r(S)+a(S),
\qquad
v_2(S)=f_s(S).
$$
If $\tau>2$, give every other type the additive valuation
$$
v_t(S)=\frac{t}{10\tau}|S|.
$$
Let $B$ be the unique subset of cardinality $r$ maximizing $a(S)$. For every subset $D$ of cardinality $r$, define a variant changing only the first type:
$$
v_1^D(S)
=
f_r(S)+a(S)+\sigma_D\frac1{16}\mathbf1[S=D],
$$
where
$$
\sigma_D=
\begin{cases}
-1,&D=B,\\
1,&D\ne B.
\end{cases}
$$
Before adding the modular term, the possible marginals have ranges
$$
\begin{array}{c|c}
\text{current cardinality}&\text{marginal range}\\ \hline
\text{at most }r-2&\{1\}\\
r-1&[11/16,13/16]\\
r&[3/16,5/16]\\
\text{at least }r+1&\{0\}.
\end{array}
$$
These ranges are nonnegative and decrease with cardinality. Thus every signed variant is monotone and submodular by diminishing returns. Adding a nonnegative modular function preserves both properties. Normalization holds because $D$ is nonempty.
Use uniform prices $p_j=1/2$.
For $f_n$, utility is maximized exactly at cardinality $n$, with value
$$
\frac n2-\frac14.
$$
Every other cardinality has utility at most
$$
\frac n2-\frac12.
$$
The modular term is smaller than $1/100$, and the signed change is confined to cardinality $r$. Consequently, type $1$ always has its utility maximum at cardinality $r$.
In the baseline, its unique utility maximizer is $B$. If $D\ne B$, the positive change makes $D$ the unique maximizer, because
$$
\frac1{16}>\frac1{100}.
$$
If $D=B$, the negative change makes the unique second-largest subset under $a(S)$ the maximizer. In all variants, denote the resulting unique maximizer by $C$; then $C\ne B$.
Type $2$ maximizes utility exactly on all subsets of cardinality $s$. Every remaining type uniquely maximizes utility at the empty bundle, because its additive coefficient is smaller than $1/2$.
The partition assigning $C$ to type $1$, $M\setminus C$ to type $2$, and empty bundles to the remaining types attains the price upper bound.
Equality forces type $1$ to receive only $C$ and every remaining type after type $2$ to receive only the empty bundle. Type $1$ exhausts the supply of each item in $C$. Thus type $2$ can use only subsets of $M\setminus C$; its utility-maximizing bundles have cardinality $s=|M\setminus C|$, so it must receive exactly $M\setminus C$.
This proves uniqueness of the continuous optimum. The baseline has the corresponding unique partition with first bundle $B$. Since $\epsilon=1$, Proposition 2 establishes every required split promise.
Run an exact algorithm on the baseline. If it makes fewer than $R$ queries, there is a subset $D$ of cardinality $r$ whose value it never queries for type $1$.
The variant indexed by $D$ changes exactly that oracle coordinate. Determinism therefore gives the same transcript and output on the baseline and variant. But their unique optima differ, so that output cannot be optimal on both.
This proves the lower bound. ∎
Because $k=m/\tau\leq m/2$ and binomial coefficients increase up to the middle,
$$
R\geq\binom{m}{k}.
$$
The construction has binary reply length
$$
O(m+\log(m+1)+\log(\tau+1)).
$$
As a supplementary check, all signed variants were exhaustively checked for submodularity and uniqueness of type $1$’s utility maximizer for $2\leq m\leq6$. The proof above does not depend on this check.
The hidden-partition family alone cannot establish the full lower bound throughout the requested approximation range.
Indeed, give each type equal mass on all subsets of cardinality $k$:
$$
x_{t,S}=\frac1{\tau N}\quad(|S|=k).
$$
A uniformly chosen such subset contains each item with probability $k/m=1/\tau$. Thus this allocation is feasible. Its welfare on every hidden-partition instance is
$$
W(x)=k-\frac12+\frac1{2N},
$$
so its ratio is
$$
1-\frac1{2k}+\frac1{2kN}.
$$
It uses zero queries. This is only a restricted-family guarantee.
For $\tau=2$, the same family also admits exact identification using $N-1$ queries: query type $1$ on all but one candidate bundle, infer the remaining candidate if necessary, and give the complement to type $2$. This also is only a restricted-family algorithm.
The signed construction in Section 5 handles exact optimization at $\epsilon=1$. It does not establish stability for $\epsilon<1$, and I make no such claim.
For completeness, exact optimization on the entire promised class is achievable by:
Proposition 1 ensures that a continuous optimum occurs among the enumerated partitions. Normalization supplies empty-bundle values without queries.
The query count is
$$
\tau(2^m-1).
$$
Using ordinary exact rational arithmetic, a valid bit-time bound, excluding the oracle’s internal computation, is
$$
O\left(
(\tau2^m+\tau^{m+1})
(m+\tau L+\log(\tau+1))^2
\right).
$$
This returns the exact optimum for every allowed $\epsilon$ and $\rho$, with no additional dependence on those parameters.
Every query lower bound above also gives the same order of running-time lower bound in a model charging at least one unit per oracle call. The constructions’ reply lengths were stated explicitly; the lower bounds are witnessed at those input sizes.
Thus the full $\binom{m}{k}$ lower bound is now proved in the parameter ranges stated at the beginning, but the complete dichotomy remains open.
⟨structured verdict parsed — rendered above⟩
The output establishes genuine partial results. The mathematical arguments for the stated parameter ranges are sound. It does not resolve the full dichotomy in USER_TASK, and its explicit-input size claim in Section 2 needs correction.
Step-by-step verification
From
$$
1-\frac1{2k}<\rho\leq1,
$$
the stated conclusion
$$
0<\alpha=2k\rho-(2k-1)\leq1
$$
is correct.
The exchange argument is valid. If an original row gives positive mass to distinct bundles, its proportional half-split gives both bundles positive mass in both split rows. A sufficiently small exchange in either direction preserves nonnegativity, row masses, and every item’s aggregate usage.
The two welfare changes are negatives of one another. A nonzero change contradicts optimality in one direction; a zero change contradicts uniqueness. This argument also works when $\epsilon=1$.
Once every row uses one bundle, equal row masses and item supplies force pairwise disjointness. Adding an unassigned item to one designated bundle gives a distinct feasible allocation whose welfare cannot decrease. Optimality and uniqueness therefore force coverage of every item.
Finding: correct, including empty parts and the endpoint $\epsilon=1$.
Normalization correctly makes the perturbation bonus equal to
$$
c\mathbf1[j\in S],
\qquad
c=(1-\epsilon)v_t(\{j\})\geq0.
$$
Aggregating the split rows preserves feasibility. Both cases in the proof are valid:
Nonnegativity then forces both split rows to be supported only on $O_t$, and their row masses uniquely determine the lift. The argument includes $\delta=\mu_t$, where the zero-mass row is omitted.
Finding: correct.
The baseline and modified additive instances satisfy the promise. The inequalities separating the owner’s coefficient from all perturbed competing coefficients are strict.
With fewer than $\tau$ queries, some type other than the initially queried owner remains unqueried. Changing that type’s coefficient preserves the deterministic transcript.
The welfare estimates correctly use
$$
A+H\leq m,
$$
and the numerical calculation is valid:
$$
r\geq\rho-\frac g4,
\qquad
\frac{W'(x)}{\mathrm{OPT}'}
\leq1-r+\frac g4
\leq\frac12<\rho.
$$
The no-query case is handled explicitly.
Thus the query lower bound is established. For $k=1$, the identities $\tau=m=N$ give the claimed full lower bound.
Finding: the mathematical argument is correct; the accompanying encoding-size claims have minor issues described below.
The definition matches the construction in the cited [Theorem 2 proof](https://arxiv.org/pdf/2006.09889v2). The output independently verifies the continuous properties, so it does not rely on transferring the discrete lower bound.
The marginal ranges establish diminishing returns for strictly nested bundles. Equal nested bundles cause no issue because they are identical. The omitted cardinality ranges when $k=1$ are handled correctly.
The optimum welfare is $k$: the partition attains it, and every bundle’s value is at most $k$.
The price certificate is valid. Row-mass equalities bound the utility contribution, and nonnegative prices together with item supplies bound the price contribution. The designated partition attains both bounds.
For the perturbed prices,
$$
d=\frac{1-\epsilon}{2},
$$
all claimed utility gaps are strictly positive. In particular, both relevant lower bounds equal
$$
\frac{\epsilon}{2}>0.
$$
The estimate $v_t(\{j\})\leq1$ remains valid when $k=1$, where singleton values need not all equal one.
Finding: normalization, monotonicity, submodularity, continuous uniqueness, and the complete split promise are established.
The bundlewise inequality is valid in each cardinality range. Summing it uses precisely the normalized row masses and aggregate item constraint, yielding
$$
W(x)\leq k-\frac12+\frac{H(O)}{2\tau}.
$$
Consequently, the approximation guarantee requires
$$
H(O)\geq\tau\alpha.
$$
Finding: correct for arbitrary feasible fractional allocations.
On the deterministic baseline transcript, each informative query excludes a fraction $1/N$ of ordered balanced partitions; other queries exclude none. The union bound therefore applies despite adaptivity.
The termination argument is valid: a compatible promised instance exists after any prefix of at most $q<N$ baseline queries. Continued execution beyond the claimed bound would contradict the bound on that instance.
The fixed output is feasible because some compatible promised instance exists and feasibility is independent of the hidden partition. Its unconditional expectation satisfies
$$
\mathbb E[H(O)]\leq\frac{\tau}{N}.
$$
Nonnegativity and the compatibility probability give the stated conditional bound.
The strict failure condition and integer rounding correctly yield
$$
Q\geq\max\left\{0,\left\lceil N-\frac1\alpha\right\rceil\right\}.
$$
Finding: correct. No stronger bound follows from this argument as written.
The partition count and the exclusion count are correct. For $\tau\geq3$, at least two compatible partitions remain after at most $N-1$ queries.
Distinct partitions must differ in at least two rows. The row-mass constraints therefore imply
$$
H(O)+H(\widetilde O)\leq2\tau-2.
$$
Substitution into the fractional welfare bound gives the claimed ratio
$$
1-\frac1{2m}.
$$
The hypothesis on $\rho$ makes the contradiction strict.
Finding: correct. The proof does not cover equality at that accuracy threshold.
The signed variants’ marginal ranges are correctly computed and establish monotonicity and submodularity. Adding the nonnegative modular term preserves these properties.
Distinct subset sums under $a(S)$ are unique, and their total range is less than $1/100$. Thus the change of magnitude $1/16$ produces the claimed unique maximizer in both sign cases.
The uniform-price argument correctly excludes other cardinalities. Although type $2$ has several utility maximizers, equality and the supply constraints force its bundle to be exactly the complement of type $1$’s bundle. This establishes uniqueness of the entire continuous allocation, rather than merely uniqueness for type $1$.
Since $\epsilon=1$, Proposition 2 applies. The indistinguishability argument changes exactly one unqueried oracle coordinate and separates two unique optima.
Finally, $k\leq\lfloor m/2\rfloor$ justifies
$$
\binom{m}{\lfloor m/2\rfloor}\geq\binom{m}{k}.
$$
Finding: correct, including the smallest allowed case $m=2$.
The uniform fractional allocation is feasible and has the stated welfare on the hidden-partition family. The restricted-family exact algorithm for $\tau=2$ also correctly uses at most $N-1$ queries. Neither is presented as a full-class algorithm.
The exhaustive upper bound is valid: Proposition 1 ensures that an optimum appears among the enumerated partitions. The query count
$$
\tau(2^m-1)
$$
is correct, and the displayed bit-time bound is a valid conservative bound for enumeration and ordinary exact rational arithmetic.
Finding: these statements correctly describe the established upper bound and the limitations of the constructions.
Issues and minimum required follow-up
USER_TASK. Further work must establish the full-class lower bound or a full-class algorithm with fewer queries there. Restricted-family algorithms do not suffice.The supplementary exhaustive check is unnecessary to the proof and supplies no independently auditable evidence without its implementation. Since none of the conclusions depends on it, this does not block verification.
⟨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.