Answer: —
Theorem 4.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThere are absolute constants ǫ, γ > 0 such that there is no (1 −ǫ)-approximately maximal- in-distributional-range mechanism for the flexible submodular CPP problem with 1 player in the value oracle model, max{f(S) : |S| ≤k}, achieving a better than 1/mγ-approximation in expectation in the objective function, where m is the size of the ground set. This holds even for non-uniform mechanisms of arbitrary computational complexity, as long as the number of value queries is bounded by poly(m). In the following, we present a sketch of the proof of this theorem. The full proof appears in Appendix B.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m,k\), rational type masses \(\mu\in\Delta(T)\), and value-oracle access to monotone submodular types \(v_t:2^{[m]}\to\mathbb R_+\), with \(\bar v_\mu(S)=\sum_t\mu_t v_t(S)\), determine the best polynomial-query guarantee for selecting \(D_\mu\) from a fixed distributional range over integral sets \(S\subseteq[m]\), \(|S|\le k\), subject to \(\mathbb E_{S\sim D_\mu}[\bar v_\mu(S)]\ge(1-\epsilon)\max_{D\in\mathcal R_m}\mathbb E_{S\sim D}[\bar v_\mu(S)]\), while approximating \(\max_{|S|\le k}\bar v_\mu(S)\); in particular, decide whether the \(m^{-\gamma}\) lower bound persists.
A society is given by its support: a list \(T\) of \(\tau\) types with positive binary rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible types, and \(L\) is the bit length of the explicit input.
Let \(m\ge1\), \(0\le k\le m\) be integers and \(0<\epsilon<1\). Each type has a normalized monotone submodular valuation \(v_t:2^{[m]}\to\mathbb R_+\), accessed through exact value queries; define \(\bar v_\mu(S)=\sum_{t\in T}\mu_t v_t(S)\).
Write \(\Omega_{m,k}=\{S\subseteq[m]:|S|\le k\}\). An algorithm chooses a nonempty compact range \(\mathcal R_{m,k,\epsilon}\subseteq\Delta(\Omega_{m,k})\) independently of the society and valuations, and returns an outcome sampled from \(D_\mu\in\mathcal R_{m,k,\epsilon}\).
For every input it must satisfy \(\mathbb E_{S\sim D_\mu}[\bar v_\mu(S)]\ge(1-\epsilon)\max_{D\in\mathcal R_{m,k,\epsilon}}\mathbb E_{S\sim D}[\bar v_\mu(S)]\). Any qualifying distribution may be selected; feasibility holds for every sampled set.
The approximation guarantee \(\alpha\) means \(\mathbb E_{S\sim D_\mu}[\bar v_\mu(S)]\ge\alpha\max_{S\in\Omega_{m,k}}\bar v_\mu(S)\) on every input. Count queries to individual type oracles; allow nonuniform algorithms and unrestricted computation between queries. State query bounds, and any running-time bounds claimed, in \(m,\tau,L,1/\epsilon\).
What is the optimal worst-case approximation guarantee achievable by such algorithms using \(\operatorname{poly}(m,\tau,L,1/\epsilon)\) value queries? In particular, do there exist absolute constants \(\epsilon_0,\gamma>0\) ruling out guarantees better than \(m^{-\gamma}\) when \(\epsilon=\epsilon_0\)?
Known results: For one discrete player, absolute constants \(\epsilon_0,\gamma>0\) rule out approximation better than \(m^{-\gamma}\) for approximately maximal-in-distributional-range algorithms using polynomially many value queries, even with nonuniform unrestricted computation. [Dughmi–Vondrák](https://arxiv.org/pdf/1109.1055)
The stated distributional-input class includes that same one-type problem, so its lower-bound persistence subquestion is already covered; the cited result does not identify the optimal approximation guarantee.
I do not determine the optimal guarantee for unrestricted compact distributional ranges. I prove the following partial results:
The gap between the construction and the impossibility bound remains unresolved here.
Put
$$
f(S)=\bar v_\mu(S)=\sum_{t\in T}\mu_t v_t(S).
$$
Because the coefficients are positive, $f$ is normalized, nonnegative, monotone, and submodular. For example, for all $A,B\subseteq[m]$,
$$
f(A)+f(B)-f(A\cup B)-f(A\cap B)
=
\sum_{t\in T}\mu_t
\bigl(v_t(A)+v_t(B)-v_t(A\cup B)-v_t(A\cap B)\bigr)
\ge 0.
$$
An exact query to $f(S)$ can be implemented using exactly $\tau$ individual-type queries, followed by the weighted sum. Consequently, a one-type algorithm making $Q$ queries can be run on $f$ using $\tau Q$ individual-type queries. Its fixed range, approximate range-maximization property, and approximation guarantee are preserved.
Conversely, restrict a society algorithm to $\tau=1$ and $\mu_1=1$. This gives a one-type algorithm with exactly the same guarantee and range condition.
Thus polynomial-query attainability is equivalent in the two models. In particular, a dependence on the number of possible types plays no role: only the explicitly listed support incurs query overhead.
For $k=0$, the sole feasible outcome is $\varnothing$, and the optimum is zero. Below, assume $k\ge 1$. The bounds concern the worst case over admissible $k$; some individual values, such as $k=1$ and $k=m$, admit exact optimization with few queries.
We will repeatedly use the following elementary lemma.
Lemma. Let $f$ be normalized, monotone, and submodular, and let $A\subseteq[m]$. There are nonnegative weights $w_i$, supported on $A$, such that
$$
\sum_{i\in A}w_i=f(A),
\qquad
f(S)\ge \sum_{i\in S\cap A}w_i
\quad\text{for every }S\subseteq[m].
$$
Proof. Order $A=\{a_1,\ldots,a_s\}$, define
$$
A_j=\{a_1,\ldots,a_j\},
\qquad
w_{a_j}=f(A_j)-f(A_{j-1}),
$$
and set all other weights to zero. Monotonicity gives nonnegativity, and telescoping gives their sum.
For $B\subseteq A$, insert its elements in the specified order. Immediately before inserting $a_j\in B$, the previously inserted set is contained in $A_{j-1}$. Submodularity therefore makes its marginal contribution at least $w_{a_j}$. Telescoping these contributions gives
$$
f(B)\ge \sum_{i\in B}w_i.
$$
Finally, monotonicity gives $f(S)\ge f(S\cap A)$. This proves the lemma. $\square$
Write
$$
\operatorname{OPT}_k(f)=\max_{|S|\le k}f(S).
$$
Identify $[m]$ with a cyclic order, and let $W_1,\ldots,W_m$ be the cyclic windows of length $k$. Consider the range consisting of point masses on all singletons and all these windows. Query their values and select a maximizing set.
First, submodularity and normalization imply
$$
f(O)\le \sum_{i\in O}f(\{i\})
\le k\max_i f(\{i\})
$$
for every feasible $O$. Hence the best singleton has value at least $\operatorname{OPT}_k(f)/k$.
Second, apply the lemma with $A=[m]$. Each item belongs to exactly $k$ cyclic windows, so
$$
\sum_{j=1}^m f(W_j)
\ge
\sum_{j=1}^m\sum_{i\in W_j}w_i
=
k f([m])
\ge k\operatorname{OPT}_k(f).
$$
Thus the best window has value at least $(k/m)\operatorname{OPT}_k(f)$.
The construction therefore achieves
$$
\max\left\{\frac1k,\frac{k}{m}\right\}
\ge \frac1{\sqrt m}
$$
using at most $2m\tau$ individual-type queries.
We next strengthen this guarantee.
Assume $m\ge256$, and put $\ell=\ln m$. It remains to address the middle regime
$$
\sqrt{\frac m\ell}\le k\le\sqrt{m\ell},
$$
since outside this regime the preceding construction already achieves at least $\sqrt{\ell/m}$.
Define
$$
r=\left\lceil k\sqrt{\frac{\ell}{m}}\right\rceil.
$$
We will prove that there is a fixed list $S_1,\ldots,S_N$ of $k$-element sets, where
$$
N=64m^9,
$$
with the following property. For every $k$-element set $O$, write
$$
J_O=\{j:|S_j\cap O|=r\}.
$$
Then $J_O$ is nonempty and, for every $i\in O$,
$$
\frac{|\{j\in J_O:i\in S_j\}|}{|J_O|}
\ge \frac{r}{4k}.
$$
This property depends only on $m,k$.
Probability of an intersection of size $r$. Let $S$ be a uniformly random $k$-element set. For a fixed $O$ of size $k$, let
$$
p=\Pr(|S\cap O|=r),
\qquad
\lambda=\frac{k^2}{m}.
$$
The probability $p$ is independent of the particular $O$.
Set $a=k\sqrt{\ell/m}$. The middle-regime assumptions give
$$
1\le a\le\ell,
\qquad
r\le2a,
\qquad
\frac{r^2}{4\ell}\le\lambda\le\ell.
$$
Also, $m\ge256$ implies $m\ge16\ell$. Consequently,
$$
k\le\frac m4,
\qquad
r\le\frac k2.
$$
Using falling factorials, the hypergeometric probability is
$$
p=
\binom{k}{r}
\frac{(k)_r(m-k)_{k-r}}{(m)_k}.
$$
The bounds
$$
\binom{k}{r}\ge\left(\frac kr\right)^r,
\qquad
(k)_r\ge\left(\frac k2\right)^r,
\qquad
(m-k)_{k-r}\ge(m-2k)^{k-r},
\qquad
(m)_k\le m^k
$$
therefore imply
$$
p\ge
\left(\frac{\lambda}{2r}\right)^r
\left(1-\frac{2k}{m}\right)^{k-r}.
$$
For $0\le x\le1/2$, $\ln(1-x)\ge-2x$. Applying this with $x=2k/m$ gives
$$
p\ge
\left(\frac{\lambda}{2r}\right)^r e^{-4\lambda}
\ge
\left(\frac{r}{8\ell}\right)^r e^{-4\ell}.
$$
The inequality $x\ln(A/x)\le A/e$ for positive $x,A$ now yields
$$
p\ge e^{-(4+8/e)\ell}\ge m^{-7}.
$$
Simultaneous coverage. Draw $S_1,\ldots,S_N$ independently and uniformly from the $k$-element sets. For fixed $O$ and $i\in O$, define
$$
A_O=|J_O|,
\qquad
B_{O,i}=|\{j\in J_O:i\in S_j\}|.
$$
Then
$$
A_O\sim\operatorname{Bin}(N,p),
\qquad
B_{O,i}\sim\operatorname{Bin}\left(N,\frac{pr}{k}\right).
$$
The second assertion follows because, conditional on intersection size $r$, the intersection is a uniform $r$-element subset of $O$.
For a binomial variable $X$ of mean $\nu$, the multiplicative Chernoff bounds give
$$
\Pr(X>2\nu)\le e^{-\nu/3},
\qquad
\Pr(X<\nu/2)\le e^{-\nu/8}.
$$
Their hypotheses hold because the sampled sets are independent.
Since $p\ge m^{-7}$ and $r/k\ge1/m$,
$$
Np\ge64m^2,
\qquad
\frac{Npr}{k}\ge64m.
$$
Thus each of the events
$$
A_O>2Np,
\qquad
B_{O,i}<\frac{Npr}{2k}
$$
has probability at most $e^{-8m}$.
There are at most $(m+1)2^m$ events under consideration. The union bound gives total failure probability at most
$$
(m+1)2^m e^{-8m}<1.
$$
Therefore a fixed list exists for which all the desired inequalities hold. In particular, $B_{O,i}>0$, so $A_O>0$, and
$$
\frac{B_{O,i}}{A_O}
\ge
\frac{Npr/(2k)}{2Np}
=
\frac{r}{4k}.
$$
Fix a list satisfying the preceding property, independently of the society and valuations. Let $O$ be an optimal $k$-element set. Such an optimum exists: any smaller optimal set can be padded without decreasing its value.
Apply the modular lemma to $O$. Averaging over $J_O$ gives
$$
\begin{aligned}
\frac1{|J_O|}\sum_{j\in J_O}f(S_j)
&\ge
\frac1{|J_O|}\sum_{j\in J_O}\sum_{i\in S_j\cap O}w_i\\
&=
\sum_{i\in O}w_i\frac{B_{O,i}}{A_O}\\
&\ge
\frac{r}{4k}f(O).
\end{aligned}
$$
Hence some set in the list has value at least
$$
\frac{r}{4k}\operatorname{OPT}_k(f)
\ge
\frac14\sqrt{\frac{\ln m}{m}}\operatorname{OPT}_k(f).
$$
Use the range of point masses on the list, the singletons, and the cyclic windows. In the middle regime, the list gives the displayed guarantee; outside it, the singletons or windows give the stronger bound $\sqrt{\ln m/m}$.
For $m<256$, use the basic construction. Together these constructions achieve, uniformly in $k$,
$$
\Omega\left(\sqrt{\frac{\log(m+1)}m}\right).
$$
The range is finite, nonempty, compact, feasible, and independent of the society, valuations, and $\epsilon$. Exact maximization over it satisfies the required inequality for every $0<\epsilon<1$. The individual-type query count is at most
$$
\tau(64m^9+2m).
$$
This is polynomial in $m,\tau,L,1/\epsilon$.
The fixed family can be supplied as nonuniform advice, as permitted in the question. We claim query complexity only; no polynomial bit-time bound is claimed for arbitrary real-valued oracle answers.
The preceding order is optimal under an additional restriction on the range.
Proposition. Fix $d\ge0$. Suppose, for each $m,k$, the range is contained in the convex hull of at most $m^d$ fixed feasible lotteries. For some admissible $k$, its worst-case approximation guarantee is
$$
O_d\left(\sqrt{\frac{\log m}{m}}\right).
$$
This holds even with unlimited queries and computation.
Proof. For sufficiently large $m$, choose
$$
k=\left\lfloor\sqrt{m\ln m}\right\rfloor,
\qquad
q=\frac{k}{2m}.
$$
Let the generating lotteries be $D_1,\ldots,D_n$, with $n\le m^d$. Define their marginal inclusion probabilities
$$
x_{j,i}=\Pr_{S\sim D_j}(i\in S).
$$
Feasibility implies
$$
0\le x_{j,i}\le1,
\qquad
\sum_i x_{j,i}\le k.
$$
Independently include each item in a random set $O$ with probability $q$. Put
$$
X_j=\sum_{i\in O}x_{j,i}.
$$
Independence, the inequality $1+u\le e^u$, and convexity of the exponential give
$$
\begin{aligned}
\mathbb E[e^{X_j}]
&=\prod_i(1-q+qe^{x_{j,i}})\\
&\le\exp\left(q\sum_i(e^{x_{j,i}}-1)\right)\\
&\le\exp\left(q(e-1)\sum_i x_{j,i}\right)\\
&\le\exp\left(\frac{(e-1)k^2}{2m}\right)
\le m.
\end{aligned}
$$
Here $e^x-1\le(e-1)x$ for $0\le x\le1$, and $(e-1)/2<1$.
Set $C=d+3$. Markov's inequality yields
$$
\Pr(X_j\ge C\ln m)\le m^{1-C}.
$$
A union bound over all generators bounds the probability of any such event by $m^{-2}$.
Meanwhile, $|O|$ is binomial with mean $k/2$. The same Chernoff bounds give
$$
\Pr(|O|<k/4)\le e^{-k/16},
\qquad
\Pr(|O|>k)\le e^{-k/6}.
$$
For sufficiently large $m$,
$$
m^{-2}+e^{-k/16}+e^{-k/6}<1.
$$
Thus there exists a set $O$ satisfying
$$
\frac k4\le |O|\le k,
\qquad
X_j<C\ln m\quad\text{for every }j.
$$
Consider the additive valuation
$$
f_O(S)=|S\cap O|.
$$
It is normalized, nonnegative, monotone, and submodular. Its feasible optimum is $|O|\ge k/4$. For each generating lottery,
$$
\mathbb E_{S\sim D_j}[f_O(S)]
=
\sum_{i\in O}x_{j,i}
<
C\ln m.
$$
Linearity preserves this upper bound throughout their convex hull. Therefore every distribution in the range has approximation ratio at most
$$
\frac{4C\ln m}{k}
=
O_d\left(\sqrt{\frac{\ln m}{m}}\right).
$$
$\square$
This proposition establishes the optimal order for polynomially generated ranges. It does not establish the optimal order in the question: polynomial query complexity does not require a range to have polynomially many generators.
The supplied result, stated as Theorem 4.2 of [Dughmi–Vondrák](https://arxiv.org/pdf/1109.1055), gives absolute constants $\epsilon_0,\gamma>0$ ruling out guarantees better than $m^{-\gamma}$ for one-player, $(1-\epsilon_0)$-approximately maximal-in-distributional-range algorithms with polynomially many value queries. It allows nonuniformity and arbitrary computation between queries.
To apply it, restrict the present model to one type with mass $1$. Then:
An algorithm contradicting the stated impossibility threshold in the society model would therefore contradict the one-type theorem. This proves the requested persistence subquestion.
The construction achieves $\Omega(\sqrt{\log m/m})$ and is optimal for polynomially generated ranges. The general impossibility theorem supplies the threshold $m^{-\gamma}$ at a fixed $\epsilon_0$.
These results do not match for unrestricted compact ranges. Determining whether larger ranges, still searchable with polynomially many queries, improve the achievable order is the remaining obstacle to identifying the optimum.
⟨structured verdict parsed — rendered above⟩
Assessment: partial, with sound proved bounds. The output does not determine the optimal approximation guarantee requested by USER_TASK, and explicitly acknowledges this limitation. Its aggregation reduction, fixed-range construction, restricted-range upper bound, and persistence argument are correct. I found no false mathematical step or substantive gap in those partial results.
The sole major issue is the unresolved main target: optimality for unrestricted compact distributional ranges using polynomially many value queries.
The reduction is valid.
Thus polynomial-query attainability is equivalent between the models, with the stated factor of $\tau$ for aggregate-query simulation. This establishes equivalence of attainable guarantees; it does not determine those guarantees.
The treatment of $k=0$ is correct: normalization makes the only feasible outcome have value zero. The subsequent assumption $k\ge1$ is explicit. The distinction between a worst case over $k$ and easy individual values of $k$ is also appropriate.
The lemma and proof are correct.
The weights are nonnegative by monotonicity, and their sum is $f(A)$ by telescoping and normalization. For each element of $B\subseteq A$, its predecessors within $B$ form a subset of its predecessors within $A$. Diminishing marginal returns therefore gives the claimed comparison with its assigned weight.
Summing these marginal contributions establishes the bound for $B$. Applying monotonicity to $S\cap A\subseteq S$ extends it to every $S\subseteq[m]$.
The empty-set case is covered by the same definitions and normalization. No additional hypothesis is needed.
Both bounds are valid.
Normalized submodularity gives
$$
f(O)\le\sum_{i\in O}f(\{i\}),
$$
so the best singleton achieves at least $\operatorname{OPT}_k(f)/k$.
Each item occurs in exactly $k$ cyclic windows, including when $k=m$. The modular lemma therefore justifies the window sum and the guarantee $k/m$.
The numerical comparison
$$
\max\left\{\frac1k,\frac{k}{m}\right\}\ge\frac1{\sqrt m}
$$
is correct. The count of at most $2m\tau$ individual-type queries is also correct; duplicated sets can only reduce the number needed.
The parameter bounds and probability calculation are correct.
In the middle regime,
$$
a=k\sqrt{\frac{\ell}{m}}\in[1,\ell].
$$
Consequently, $r=\lceil a\rceil\le2a$ and
$$
\lambda=\frac{a^2}{\ell}\ge\frac{r^2}{4\ell}.
$$
The inequality $m\ge16\ln m$ holds throughout the stated domain $m\ge256$. It implies $k\le m/4$ and, together with $r\le2a$, implies $r\le k/2$.
The hypergeometric formula
$$
p=\binom{k}{r}\frac{(k)_r(m-k)_{k-r}}{(m)_k}
$$
is correct. All four subsequent bounds apply within these parameter restrictions. In particular, the logarithmic estimate is applied with
$$
0\le\frac{2k}{m}\le\frac12.
$$
The resulting estimate
$$
p\ge\left(\frac{r}{8\ell}\right)^r e^{-4\ell}
$$
has the correct direction. The inequality $x\ln(A/x)\le A/e$ then yields
$$
p\ge e^{-(4+8/e)\ell}\ge m^{-7},
$$
since $4+8/e<7$.
For each fixed pair $(O,i)$, the indicator variables across sampled sets are independent. Thus both binomial distributions asserted in the output are correct. Conditional uniformity of the intersection supplies the probability $pr/k$ for the second one.
The stated Chernoff bounds apply. The mean bounds
$$
Np\ge64m^2,\qquad \frac{Npr}{k}\ge64m
$$
justify the common failure bound $e^{-8m}$. The number of events is at most $(m+1)2^m$, and the displayed union bound is strictly below one.
Finally, the successful lower bound on $B_{O,i}$ ensures that $J_O$ is nonempty. Combining the successful upper and lower bounds gives exactly the required coverage fraction $r/(4k)$.
This step is valid.
Monotonicity permits padding an optimal feasible set to size $k$. The modular lemma supplies nonnegative weights on that optimum; their nonnegativity is essential and was established earlier. The coverage inequalities can therefore be multiplied by those weights and summed.
The averaging argument proves that one listed set has value at least
$$
\frac{r}{4k}\operatorname{OPT}_k(f)
\ge
\frac14\sqrt{\frac{\ln m}{m}}\operatorname{OPT}_k(f).
$$
Outside the middle regime, the basic construction gives the stated stronger bound. For the finitely many smaller values of $m$, its guarantee supports the uniform formulation
$$
\Omega\left(\sqrt{\frac{\log(m+1)}m}\right).
$$
The range satisfies every stated requirement: it is finite, nonempty, compact, feasible, and independent of valuations and society. Selecting a maximizing point mass gives exact range maximization, so every permitted $\epsilon$ is covered.
The bound
$$
\tau(64m^9+2m)
$$
is polynomial in the required parameters. Nonuniform advice is explicitly permitted. The output appropriately claims no polynomial running-time bound for arbitrary real oracle answers.
The proposition is correct under its explicitly stated additional restriction.
Feasibility gives the required marginal constraints. The exponential-moment calculation uses independent inclusion indicators and applies the convexity inequality only to $x_{j,i}\in[0,1]$. The last bound follows from
$$
k^2\le m\ln m,\qquad \frac{e-1}{2}<1.
$$
With $C=d+3$, Markov's inequality and the generator count give total failure probability at most $m^{-2}$. The cardinality variable has mean $k/2$, and both stated Chernoff estimates have the correct constants.
Their combined failure probability tends to zero, proving existence of the required nonempty feasible $O$ for sufficiently large $m$.
The additive valuation $f_O$ satisfies all valuation assumptions. Its optimum is $|O|$, and expected value under each generator equals the corresponding marginal sum. Linearity extends the upper bound to their convex hull, yielding the claimed order
$$
O_d\left(\sqrt{\frac{\ln m}{m}}\right).
$$
Together with the construction, this establishes the order for the restricted class. The output correctly warns that polynomial query complexity does not imply polynomially many generators.
The theorem reference and application are valid. Theorem 4.2 states the required single-player flexible-cardinality oracle lower bound and expressly includes nonuniform mechanisms with unrestricted computational complexity. The paper's definition of approximate maximality matches the expected-welfare condition used here. [Dughmi–Vondrák](https://arxiv.org/pdf/1109.1055)
All necessary hypotheses are satisfied:
Accordingly, the affirmative answer to the persistence subquestion is established. This does not establish the optimal approximation order.
Major — unresolved main target, Sections 6 and the opening status statement. The lower bound for unrestricted ranges and the achievable construction do not match. The matching proposition covers only ranges contained in the convex hull of polynomially many fixed lotteries. Therefore the optimal guarantee in USER_TASK, including its dependence on $\epsilon$, remains undetermined.
Minimum needed to complete the task: provide a matching result for the unrestricted compact-range model, with the relevant quantifiers over $\epsilon$ and polynomial query bounds stated explicitly. Further clarification of the existing calculations cannot close this gap; an additional mathematical result is required.
This is an acknowledged incompleteness, not an invalid inference or a false claim of having solved the main question. The proved partial results remain useful.
⟨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.