Answer: Attaining \(\frac{e-1}{(2e-1)\zeta}\) is \(\mathrm{NP}\)-hard for every prescribed constant \(\zeta\ge1\), even with one type and all capacities equal to one.
Theorem 2 — class: algorithmic
Given \(A\) arms, \(\tau\) types with rational masses \(\mu_x\), a finite-support reward-vector law \(P_x\) for each type, per-capita arm capacities \(q_a\), a probe budget \(I\), and overhead \(\alpha\), choose a probe set \(S\), \(|S|\le I\), and assignment probabilities \(p_a(x,r_S)\). Here the observed group mass is \(\nu_S(x,r_S)=\mu_xP_x(r_S)\), and the probabilities must satisfy \(\sum_a p_a(x,r_S)=1\) and \(\sum_{x,r_S}\nu_S(x,r_S)p_a(x,r_S)\le q_a\). With \(v(x,r_S,a)=r_a\) for \(a\in S\) and \(v(x,r_S,a)=\mathbb E_{P_x}[R_a]\) otherwise, maximize \((1-\alpha(|S|))\exp\!\left(\sum_{x,r_S}\nu_S(x,r_S)\log\!\left(\sum_a p_a(x,r_S)v(x,r_S,a)\right)\right)\).
A society is given by its support: a list of \(\tau\ge1\) types with positive binary-rational masses \(\mu_x\), summing to \(1\); \(\tau\) is the support size, not the number of possible types. There are \(m=A\ge1\) arms.
For each type, \(P_x\) is an explicitly listed finite-support probability law on rational reward vectors in \([0,1]^m\), with binary-rational probabilities. Let \(K\) be the total number of listed vectors and \(L\) the total input bit length.
Capacities are binary rationals \(q_a\in[0,1]\) with \(\sum_a q_a\ge1\). The integer budget satisfies \(1\le I\le m\); overhead is an explicitly given rational nondecreasing table \(\alpha:\{0,\ldots,I\}\to[0,1]\), with \(\alpha(0)=0\) and \(\alpha(I)=1\).
Choose a single probe set \(S\subseteq\{1,\ldots,m\}\), \(|S|\le I\), before observations. For each positive-mass observation group, define \(\nu_S(x,r_S)=\mu_xP_x(R_S=r_S)\) and choose \(p_a(x,r_S)\in[0,1]\).
Require \(\sum_a p_a(x,r_S)=1\) for every group and \(\sum_{x,r_S}\nu_S(x,r_S)p_a(x,r_S)\le q_a\) for every arm. Set \(v(x,r_S,a)=r_a\) when \(a\in S\), and \(v(x,r_S,a)=\mathbb E_{P_x}[R_a]\) otherwise.
Maximize \(F(S,p)=(1-\alpha(|S|))\exp\!\bigl(\sum_{x,r_S}\nu_S(x,r_S)\log(\sum_a p_a(x,r_S)v(x,r_S,a))\bigr)\). Its value is \(0\) if any positive-mass group has zero utility or the overhead factor is zero. Let \(\mathrm{OPT}\) be its maximum.
For a prescribed constant \(\zeta\ge1\), does this problem admit a polynomial-time multiplicative \(\frac{e-1}{(2e-1)\zeta}\)-approximation, or is attaining this ratio NP-hard? State running times in \(m,\tau,K,L,I\), and dependence on \(\zeta\).
For finite agents, greedy probing has a stated \(\frac{e-1}{(2e-1)\zeta}\) guarantee for overhead-adjusted expected product welfare, conditional on surrogate assumptions and an instance-dependent lower bound on \(\zeta\). [Verified source](https://arxiv.org/html/2506.14988v6).
No result settling this approximation question for the specified distributional objective and aggregate capacities was located.
Attaining the ratio \(\frac{e-1}{(2e-1)\zeta}\) is \(\mathrm{NP}\)-hard for every prescribed constant \(\zeta\ge1\). In fact, every fixed positive multiplicative approximation ratio is \(\mathrm{NP}\)-hard, even with one type, binary rewards, dyadic probabilities, and \(q_a=1\) for every arm.
Thus a deterministic algorithm with running time polynomial in \(m,\tau,K,L,I\), for fixed \(\zeta\), would imply \(\mathrm{P}=\mathrm{NP}\).
For completeness, assignment for a fixed probe set admits a polynomial-time multiplicative approximation. Enumerating probe sets gives a \((1-\varepsilon)\)-approximation in time
\(\left(\sum_{j=0}^{I-1}\binom mj\right)\operatorname{poly}(m,\tau,K,L,\varepsilon^{-1})\).
The hardness concerns selecting the probe set when \(I\) varies.
We use the following known gap theorem. Fix constants \(s_0>0\) and \(\delta>0\). Given a universe \(U\) of size \(n\) and explicitly listed sets \(C_1,\ldots,C_N\), all of size \(d\), with integer \(t=n/d\), it is \(\mathrm{NP}\)-hard to distinguish:
This is stated in [Proposition 4.2 of *PASS Approximation*](https://people.csail.mit.edu/mirrokni/pass_approximation_journal.pdf).
Apply the theorem with \(s_0=1\) and \(\delta=1/16\). For \(t\ge2\), every collection of at most \(t\) sets in a NO instance leaves at least \(3n/16\) elements uncovered. Indeed,
\((1-1/t)^t\ge1/4\).
To verify this inequality, the derivative of \(f(t)=t\log(1-1/t)\), for real \(t>1\), is
\[
\]
\(\displaystyle f'(t)=\frac1{t-1}-\log\!\left(1+\frac1{t-1}\right)>0,\)
because \(\log(1+y)<y\) for \(y>0\). The value at \(t=2\) therefore gives the claimed bound.
Consequently, the NO coverage bound is \(13n/16\).
Start with such a coverage instance. If \(N<t\), it cannot be a YES instance, so this case can be decided immediately. Hence assume \(N\ge t\).
Choose a power of two \(D\) satisfying \(4n\le D<8n\). Choose integers \(h_u\), for \(u\in U\), each equal to either \(\lfloor D/n\rfloor\) or \(\lceil D/n\rceil\), such that \(\sum_{u\in U}h_u=D\). Define \(w_u=h_u/D\).
These probabilities are positive dyadic rationals and satisfy
\(\displaystyle \frac{3}{4n}\le w_u\le\frac{5}{4n}.\)
Construct the following instance:
\(\displaystyle R_a(u)=\mathbf 1_{\{u\in C_a\}}\) for \(a\le N\), and \(R_{N+1}(u)=0\).
All requirements in the question hold, including \(I\le m\). Identical reward vectors may be merged by summing their probabilities; this preserves the law and dyadic encoding.
For every genuine arm,
\(\displaystyle \mathbb E[R_a]=\sum_{u\in C_a}w_u\le\frac{5d}{4n}=\frac{5}{4t}\le\frac2t.\)
The capacities impose no further restriction: an arm’s total assignment mass is always at most the society’s total mass, which is one.
Let \(S\) be a probe set with \(|S|\le t\), and define its covered outcomes by
\(\displaystyle B(S)=\bigcup_{\substack{a\in S\\a\le N}}C_a.\)
An outcome belongs to \(B(S)\) exactly when some genuine probed arm returns reward one. Thus coverage is determined by the observation group, as required by the policy’s information restriction.
Probe the \(t\) sets of a disjoint cover. Every positive-mass observation group then contains a probed arm with reward one. Assign that group entirely to such an arm.
Every group has utility one, the overhead factor is one, and the policy is feasible. Therefore \(F(S,p)=1\). Since all utilities and overhead factors are at most one, \(\mathrm{OPT}=1\).
Suppose \(|B(S)|\le13n/16\). The probability mass of uncovered outcomes satisfies
\(\displaystyle W=\sum_{u\notin B(S)}w_u\ge\frac{3n}{16}\frac{3}{4n}=\frac9{64}\ge\frac18.\)
On an uncovered outcome, every probed reward is zero and every unprobed arm has mean at most \(2/t\). Since group utility is a convex combination of these values, it is at most \(2/t\). On covered outcomes it is at most one.
If any group has zero utility, the objective is zero. Otherwise, for \(t>2\),
\(\displaystyle \log F(S,p)\le W\log(2/t)\le\frac18\log(2/t),\)
and hence
\(\displaystyle F(S,p)\le(2/t)^{1/8}.\)
This bound holds for every feasible policy, including fractional policies.
In a NO instance, every set of at most \(t\) probes satisfies the coverage hypothesis. Sets of \(t+1\) probes have overhead factor zero. Therefore
\(\displaystyle \mathrm{OPT}_{\mathrm{NO}}\le(2/t)^{1/8}.\)
Fix \(\zeta\ge1\), and write
\(\displaystyle \beta=\frac{e-1}{(2e-1)\zeta},\qquad Z=\lceil\zeta\rceil,\qquad T=2(6Z)^8.\)
Because \(e>2\),
\(\displaystyle \beta>\frac1{3\zeta}\ge\frac1{3Z}.\)
For \(t\ge T\), the preceding bound becomes
\(\displaystyle (2/t)^{1/8}\le\frac1{6Z}<\beta.\)
Assume a polynomial-time \(\beta\)-approximation algorithm exists. We could decide the coverage gap as follows.
For a YES instance, the returned solution must have value at least \(\beta\), since \(\mathrm{OPT}=1\). It cannot use \(t+1\) probes, whose value is zero. It also cannot cover at most \(13n/16\) elements, since then its value would be at most \(1/(6Z)<\beta\). Thus the test accepts.
For a NO instance, no collection of at most \(t\) sets passes the coverage test, and a returned set of size \(t+1\) can simply be rejected. Thus the test rejects.
The small-\(t\) enumeration takes
\(N^{O(T)}\operatorname{poly}(n)=N^{O(\zeta^8)}\operatorname{poly}(n)\)
time, which is polynomial for each prescribed constant \(\zeta\). The construction has \(\tau=1\), \(m=N+1\), \(K\le n\), \(I=t+1\), and input length
\(L=O(nm+n\log n+t\log t)\).
It is polynomial in the coverage input size.
This contradicts the coverage gap theorem unless \(\mathrm{P}=\mathrm{NP}\). The same argument works for any fixed positive ratio by choosing a sufficiently large constant \(T\).
The decision procedure only checks coverage. It needs no exact comparison of logarithms, exponentials, or irrational objective values.
Here is a justified upper bound for the general input model.
Fix \(S\), and index its positive-mass observation groups by \(g\). There are at most \(K\) groups. Write their masses as \(\nu_g\), their reward coefficients as \(v_{ga}\), and utilities as \(u_g=\sum_a p_{ga}v_{ga}\).
Let \(Q=\sum_aq_a\), so \(1\le Q\le m\). The constant policy \(p^0_{ga}=q_a/Q\) is feasible, because its aggregate assignment to arm \(a\) is \(q_a/Q\le q_a\).
If some group has \(v_{ga}=0\) for every arm with \(q_a>0\), its utility is zero under every feasible policy. Indeed, a zero-capacity arm receives zero assignment in every positive-mass group.
Otherwise, \(p^0\) gives every group positive utility. Under binary encoding, positive input rationals are at least \(2^{-L}\). Every positive coefficient \(v_{ga}\) is therefore at least \(2^{-2L}\), including an unprobed mean. Consequently,
\(\displaystyle u_g(p^0)\ge b_0:=2^{-3L}/m.\)
Fix rational \(0<\varepsilon<1\), and let \(\theta=\varepsilon/4\). Blending an optimal policy \(p^*\) with \(p^0\) gives
\(\displaystyle p^\theta=(1-\theta)p^*+\theta p^0.\)
It remains feasible, has every utility at least \(b=\theta b_0\), and has geometric welfare at least \((1-\theta)\) times the optimum for \(S\). Thus restricting utilities to \([b,1]\) loses at most \(-\log(1-\theta)\le2\theta\) in log welfare.
On \([b,1]\), interpolate \(\log u\) at rational breakpoints with consecutive ratios at most \(1+\theta\). The concave piecewise-linear interpolant \(\ell\) satisfies
\(\displaystyle \log u-\theta\le\ell(u)\le\log u.\)
Indeed, on each interval both functions lie between its endpoint logarithms, whose difference is at most \(\log(1+\theta)\le\theta\).
There are
\(J=O((L+\log m+\log\varepsilon^{-1})/\varepsilon)\)
segments. Concavity means that \(\ell\) is the minimum of the extended segment lines. Approximate each line’s coefficients by rationals and shift downward so that, throughout \([b,1]\), its error is between zero and \(\theta\). This requires polynomially many precision bits. The resulting function \(\widetilde\ell\) satisfies
\(\displaystyle \log u-2\theta\le\widetilde\ell(u)\le\log u.\)
Maximizing \(\sum_g\nu_g\widetilde\ell(u_g)\) is a rational linear program: introduce one variable per group bounded above by every segment line. It has \(O(Km+K)\) variables and \(O(Km+KJ+m)\) constraints, all with polynomial encoding length.
Its solution loses at most \(4\theta=\varepsilon\) in log welfare compared with the unrestricted optimum. Hence its welfare is at least \(e^{-\varepsilon}\ge1-\varepsilon\) times that optimum. The fixed overhead factor preserves this guarantee.
Thus fixed-set assignment takes
\(\operatorname{poly}(m,\tau,K,L,\varepsilon^{-1})\)
time. Enumerating all probe sets of size at most \(I-1\) gives the stated running time
\(\displaystyle \left(\sum_{j=0}^{I-1}\binom mj\right)\operatorname{poly}(m,\tau,K,L,\varepsilon^{-1}).\)
Choosing among the sets using their approximate log objectives and log overheads, to additional accuracy \(O(\varepsilon)\), preserves a \((1-\varepsilon)\)-guarantee after adjusting the internal accuracy by a constant factor. Sets with zero overhead are skipped. For fixed \(I\), this running time is polynomial; its dependence on \(I\) is exponential in general.
The cited paper uses overhead-adjusted expected product welfare with finite-agent assignment constraints. Those premises differ from the weighted geometric mean over observation groups and aggregate capacities here. Its conditional guarantee therefore does not supply an approximation theorem for this input model. [Source: problem formulation](https://arxiv.org/html/2506.14988v6).
The reduction above settles the specified distributional objective directly.
⟨structured verdict parsed — rendered above⟩
The hardness argument is sound in substance and resolves the intended approximation question. Its reduction, welfare bounds, and separation constants check out. Two minor boundary omissions should be clarified. I found no major issue requiring new mathematics.
The source supports the equal-size set-cover gap used in Section 1. Proposition 4.2 includes the qualification “for sufficiently large k,” where its set-size parameter corresponds to the prover’s \(d\). Its subsequent discussion also treats \(t\) as arbitrarily large. [PASS Approximation, Proposition 4.2 and following discussion](https://people.csail.mit.edu/mirrokni/pass_approximation_journal.pdf)
Omitting the sufficiently-large-set-size qualification does not invalidate the hardness implication: an algorithm for the broader class would also solve the restricted hard class. Nevertheless, preserving that qualification would make the citation more precise.
For \(t\ge2\), the numerical deduction is correct:
Minor issue — the literal promise at \(t=1\). The two displayed promise conditions overlap at this boundary. For example, take one listed set equal to the entire universe, with \(d=n\). This is a YES instance, but it also satisfies the displayed NO inequality: for \(s=1\), the permitted coverage fraction is \(1+\delta\).
Thus the small-\(t\) enumeration cannot distinguish the two literal labels at \(t=1\). This is an ambiguity in the stated source promise and its boundary handling, not a failure of the large-\(t\) hardness argument.
Minimum clarification: Explicitly restrict the source hard promise to \(t\ge2\), retaining the source’s qualifications, and limit the small-\(t\) decision claim to that promise.
The construction satisfies the task’s input requirements.
Merging identical reward vectors preserves both the law and the observations available to the policy.
The mean-reward calculation is correct: each genuine arm has mean at most \(5/(4t)\le2/t\). The stated construction length is a valid polynomial upper bound for the explicit encoding.
No issue arises here.
The proof respects the policy’s information restriction.
Whether an outcome is covered is determined by its probed reward vector: coverage holds exactly when at least one genuine probed coordinate equals one. Thus an observation group cannot mix covered and uncovered outcomes.
In a YES instance, probing a disjoint cover gives every group an observable arm with reward one. Assigning that group entirely to such an arm is feasible and gives utility one. Since the overhead is zero at \(t\) probes, the resulting objective is one.
All utilities and overhead factors are at most one, so the conclusion \(\mathrm{OPT}=1\) is justified.
No issue arises here.
Every critical inequality checks out.
If at most \(13n/16\) outcomes are covered, at least \(3n/16\) are uncovered. Their mass therefore satisfies \(W\ge9/64\ge1/8\).
On every uncovered group:
Covered groups have utility at most one. Zero-utility groups give objective zero, as required by the task’s convention.
For \(t>2\), \(\log(2/t)<0\), so the direction of the inequality using \(W\ge1/8\) is correct. This gives \(F(S,p)\le(2/t)^{1/8}\).
The bound applies to every feasible fractional policy. Probe sets of size \(t+1\) have objective zero. Hence the claimed NO optimum bound is valid in the range used by the hardness argument.
The separation constants are correct.
For \(e>2\), the claimed inequality \(\beta>1/(3\zeta)\ge1/(3Z)\) holds. With \(T=2(6Z)^8\), every \(t\ge T\) satisfies \((2/t)^{1/8}\le1/(6Z)<\beta\).
Accordingly:
The decision procedure uses only the returned probe set and exact coverage counts. It does not require computing or comparing irrational welfare values.
For fixed \(\zeta\), the small-\(t\) enumeration has polynomial running time, with exponent \(O(\zeta^8)\). This establishes hardness against deterministic algorithms polynomial in \(m,\tau,K,L,I\) for every prescribed constant \(\zeta\).
The extension to every fixed positive approximation ratio also follows from the stated argument. The proof does not establish a randomized-complexity consequence, and its explicit deterministic qualification is appropriate.
Apart from the \(t=1\) promise qualification identified above, no issue arises here.
The upper-bound argument is sound.
Feasibility and positivity. The constant policy \(p^0_{ga}=q_a/Q\) satisfies the group normalization and aggregate capacities. A zero-capacity arm must receive zero assignment in every positive-mass group.
Therefore, the stated coefficient test correctly detects whether positive geometric welfare is possible for the fixed set, apart from the separately handled zero-overhead case.
The lower bound \(u_g(p^0)\ge2^{-3L}/m\) is conservative and valid. A positive unprobed mean contains at least one positive probability–reward product, giving the claimed coefficient lower bound.
Blending. Convexity of the feasible region preserves feasibility. The utility lower bound and the multiplicative welfare loss both follow from the stated blend. Because the group masses sum to one, the resulting log-welfare loss is at most \(2\theta\).
Piecewise-linear approximation. The logarithm’s concavity gives a lower interpolant. The endpoint logarithm difference bounds its error by \(\theta\). The stated segment count is valid, and the representation as the minimum of extended segment lines is correct.
Rounding each line downward with uniform error at most \(\theta\) preserves the stated approximation bounds. The required coefficient magnitudes and precision have polynomial bit length.
Linear program and accuracy. The variable and constraint counts are correct. The LP is rational, feasible, and has bounded objective. Combining the restriction loss with the surrogate error gives the stated log-welfare loss of at most \(4\theta=\varepsilon\). Thus the returned policy achieves at least a \(1-\varepsilon\) fraction of the fixed-set optimum.
The numerical selection across probe sets is a routine finite-precision step; the stated constant-factor adjustment of internal accuracy is sufficient. No additional mathematical lemma is missing here.
Enumerating sizes through \(I-1\) is sufficient because every set of size \(I\) has zero overhead factor. The displayed enumeration running time is correct.
Minor issue — no explicit fallback when every candidate has value zero. Section 5 detects zero fixed-set optima and skips zero-overhead sets, but does not say what solution the overall algorithm returns if no positive candidate remains. This situation is permitted, for example when all listed rewards are zero.
Minimum clarification: Specify that the algorithm returns a feasible policy when all candidate values are zero. This is an output-completeness omission; it does not affect the approximation or hardness conclusions.
The stated distinction between objectives is supported by the cited paper: its guarantee concerns overhead-adjusted expected finite-agent product welfare and includes an instance-dependent condition on \(\zeta\). [Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits, Theorem 1](https://arxiv.org/html/2506.14988v6)
That guarantee does not directly establish an approximation result for the task’s weighted geometric mean over observation groups with aggregate capacities. The reduction addresses the specified objective directly.
The appropriate overall classification is proved with minor gaps: the substantive hardness conclusion stands, and the identified repairs concern promise boundaries and algorithm output completeness.
⟨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.