Answer: For fixed \(m\ge\nu\ge3\), an unconditional randomized polynomial-time \(\Omega(1/\log n)\) multiplicative approximation is achievable with an explicit dyadic distribution and success probability at least \(2/3\). Thus some nonnegative non-increasing \(g(n)=o(1)\) admits an \(n^{-g(n)}\) approximation, and every fixed \(\epsilon>0\) admits an \(n^{-\epsilon}\) approximation. Both stated universal pooled-budget barriers are overcome.
Theorem 2 — class: hardness
Given a finite directed network template \(G=(V,E)\), its campaign cascade distributions and initial seed sets, a threshold \(\nu\), and an average seed budget \(K\), consider a continuum of copies of \(G\). Each copy receives an integral seed plan \(\sigma\), with cost \(c(\sigma)\) and expected balanced-exposure value \(b(\sigma)\). Choose a distribution \(\pi\) over plans maximizing \(\sum_\sigma \pi_\sigma b(\sigma)/|V|\), subject to \(\sum_\sigma\pi_\sigma=1\), \(\sum_\sigma\pi_\sigma c(\sigma)\le K\), and \(\pi_\sigma\ge0\). Determine its approximation complexity, including whether the conditional inapproximability of Theorem 2 persists under this pooled budget.
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Here the society consists of copies of one network template, with \(\tau=1\) and total mass \(1\).
Fix integers \(m\ge\nu\ge3\). Input: a directed graph \(G=(V,E)\), with \(n=|V|\ge m\), initial seed sets \(I_i\subseteq V\), binary rational probabilities \(p_i(e)\in[0,1]\) for \(i\in[m]\), and a binary rational average budget \(\nu\le K\le\nu n\). Campaigns follow the independent cascade model, independently across campaigns, with no competition between campaigns.
An integral plan is any \(\sigma=(S_1,\ldots,S_m)\), with \(S_i\subseteq V\), including the empty plan. Its cost is \(c(\sigma)=\sum_i|S_i|\); initial seeds are free, and seeding the same vertex for different campaigns incurs separate costs.
Let \(R_i(\sigma)\) be the final reached set from \(I_i\cup S_i\), and define \(b(\sigma)=\mathbb E[|\{v\in V:|\{i:v\in R_i(\sigma)\}|=0\text{ or }|\{i:v\in R_i(\sigma)\}|\ge\nu\}|]\).
Choose a distribution \(\pi\) over all integral plans, independently of cascade outcomes, maximizing \(F(\pi)=\sum_\sigma\pi_\sigma b(\sigma)/n\), subject to \(\sum_\sigma\pi_\sigma=1\), \(\sum_\sigma\pi_\sigma c(\sigma)\le K\), and \(\pi_\sigma\ge0\). Individual plans may cost more than \(K\); plans and their values are not supplied as an explicit table.
Computational solutions are finite lists of plans with binary rational probabilities. Approximation ratios are multiplicative relative to the optimal pooled value; randomized guarantees have probability at least \(2/3\). State running times in \(n,|E|,m,\tau,L\) and any accuracy parameters, where \(L\) is the total input bit length.
For a fixed \(d\ge3\), let \(H_d\) assert that some sensitive Boolean predicate \(Q:\{0,1\}^d\to\{0,1\}\) yields a one-way collection of random local functions with \(N\) input bits and \(N^8\) outputs: each output applies \(Q\) to an independently uniform ordered tuple of distinct input coordinates. Sensitive means flipping one designated coordinate always flips the output; the coordinate tuples are public.
What polynomial-time multiplicative approximation ratios are achievable for this pooled-budget problem?
Does Gap-ETH still exclude \(n^{-g(n)}\)-approximation for every nonnegative non-increasing \(g(n)=o(1)\), or can such a ratio be attained?
For \(3\le d\le\nu-1\), does \(H_d\) still exclude \(n^{-\epsilon(d)}\)-approximation for some constant \(\epsilon(d)>0\), or can the pooled problem overcome that barrier?
With an integral per-copy budget, an approximation-preserving reduction from Densest-\(k\)-Sub-\(d\)-Hypergraph establishes these conditional barriers, already for deterministic cascades; the heterogeneous discrete problem also has an \(\Omega(n^{-1/2})\) approximation when \(\nu=3\). [Discrete results](https://arxiv.org/pdf/1906.00074); [local-function hardness premise](https://eccc.weizmann.ac.il/report/2011/007/revision/3/download/).
Randomized seeding has a \(1-1/e\) multiplicative guarantee with arbitrarily small additive error for a different, maximin influence objective. [Related randomization result](https://ojs.aaai.org/index.php/AAAI/article/view/17725). No result settling this exact pooled balanced-exposure problem was identified.
For fixed \(m\ge \nu\ge3\), the pooled-budget problem admits an unconditional randomized polynomial-time \(\Omega(1/\log n)\) multiplicative approximation. The algorithm outputs a polynomial-size list of plans with dyadic probabilities, always satisfies the average budget, and achieves its guarantee with probability at least \(2/3\).
Consequently:
These conclusions concern the universal exclusions in the question. They do not assert that every \(n^{-g(n)}\) ratio is attainable; that would include exact optimization when \(g=0\).
The proof below establishes an explicit ratio. It does not establish the best possible approximation ratio.
Write \(\varnothing\) for the empty plan. Define the normalized quantities
\(h(\sigma)=\frac1n\mathbb E[|\{v:v\text{ is reached by at least }\nu\text{ campaigns under }\sigma\}|]\)
and
\(z(\sigma)=\frac1n\mathbb E[|\{v:v\text{ is reached by no campaign under }\sigma\}|].\)
Thus \(b(\sigma)/n=h(\sigma)+z(\sigma)\). Extend both functions linearly to distributions over plans.
Let \(H^*\) be the maximum of \(h(\pi)\) over average-budget-feasible distributions, and put \(z_0=z(\varnothing)\). Adding seeds cannot make a reached vertex unreached: pre-sample the successful edges for each campaign, and additional seeds only enlarge the set reachable through those edges. Therefore \(z(\sigma)\le z_0\), and hence
\(F^*\le z_0+H^*.\)
Set \(q=K/(\nu n)\). Our hypotheses give \(1/n\le q\le1\). Seeding every vertex in any fixed \(\nu\) campaigns costs \(\nu n\) and makes every vertex sufficiently exposed. Mixing this plan with the empty plan, with respective probabilities \(q\) and \(1-q\), proves
\(H^*\ge q.\)
This positive lower bound will let us turn sampling errors into multiplicative guarantees.
A live-edge outcome \(X\) specifies, independently for each campaign and edge, whether that edge succeeds. Its distribution is equivalent to independent cascade: pre-sampling the attempted transmissions gives exactly the vertices reachable from the seeds through successful edges.
For a fixed outcome, define
\(h_X(\sigma)=\frac1n|\{v:v\text{ is reached by at least }\nu\text{ campaigns in }X\text{ under }\sigma\}|.\)
Take \(T\) independent outcomes \(X^1,\ldots,X^T\), and write
\(\widehat h(\sigma)=\frac1T\sum_{t=1}^T h_{X^t}(\sigma).\)
Let \(\eta=q/128\). There are \(2^{mn}\) integral plans. Hoeffding’s inequality and a union bound give
\(\Pr[\exists\sigma:\ |\widehat h(\sigma)-h(\sigma)|>\eta]\le 2^{mn+1}\exp(-2T\eta^2).\)
Thus choosing
\(T=\left\lceil\frac{mn\ln2+\ln24}{2\eta^2}\right\rceil\)
ensures, with probability at least \(11/12\), that
\(|\widehat h(\sigma)-h(\sigma)|\le\eta\quad\text{for every integral plan }\sigma.\)
On this event, the same inequality holds for every distribution over plans, by taking weighted averages.
For outcome \(t\), campaign \(i\), and vertex \(v\), let \(A_{tiv}\) be the set of vertices from which \(v\) is reachable in that campaign’s live-edge graph. Let \(a_{tiv}=1\) if its initial seeds already reach \(v\), and \(a_{tiv}=0\) otherwise.
Consider the following LP. Its variables are \(x_{iu}\), \(y_{tv}\), and \(z_{tiv}\):
\[ \text{Maximize }A=\frac1{Tn}\sum_{t,v}y_{tv}. \]
Its constraints are
\[ 0\le x_{iu}\le1,\qquad \sum_{i,u}x_{iu}\le K; \]
\[ 0\le y_{tv}\le1,\qquad 0\le z_{tiv}\le y_{tv}; \]
\[ z_{tiv}\le a_{tiv}+\sum_{u\in A_{tiv}}x_{iu}, \qquad \sum_{i=1}^m z_{tiv}\ge\nu y_{tv}. \]
Here and below, the displayed equations use the same mathematical notation as the inline formulas.
Why this is a relaxation of the pooled problem. Given any feasible distribution \(\pi\), set
\(x_{iu}=\Pr_{\sigma\sim\pi}[u\in S_i]\),
\(y_{tv}=\Pr_{\sigma\sim\pi}[v\text{ is sufficiently exposed in outcome }t]\),
and let \(z_{tiv}\) be the probability that both this event occurs and campaign \(i\) reaches \(v\).
Then \(z_{tiv}\le y_{tv}\). If the initial seeds do not reach \(v\), campaign \(i\) can reach it only if some additional seed belongs to \(A_{tiv}\); the union bound proves the corresponding reachability constraint. Finally, whenever \(v\) is sufficiently exposed, at least \(\nu\) campaigns reach it, proving \(\sum_i z_{tiv}\ge\nu y_{tv}\).
The LP objective of this feasible solution equals \(\widehat h(\pi)\). Consequently, its optimum satisfies
\(A\ge\widehat h(\pi)\quad\text{for every feasible }\pi.\)
The full-seeding mixture from Section 1 also proves \(A\ge q\), for every sample. On the simultaneous sampling event,
\(A\ge H^*-\eta.\)
Define
\(r=m-\nu+1,\qquad a=\lceil\log_2(2\nu)\rceil,\qquad J=\lceil\log_2(4/q)\rceil,\)
and
\(B=1+ar(J+1).\)
For \(j=0,\ldots,J\), put \(t_j=2^{-j}\).
One random rounded plan is generated as follows:
\(p_{iu}^{(j)}=\min\{1,arx_{iu}/t_j\}\).
To implement this with a bounded number of fair random bits, round each seed probability up to the nearest multiple of \(2^{-s}\), where \(s=\lceil\log_2(mn)\rceil\). Denote these implemented probabilities by \(\widetilde p_{iu}^{(j)}\). Rounding upward preserves all exposure lower bounds.
Fix a row \((t,v)\) with \(y=y_{tv}\ge t_J\). Order its \(z_{tiv}\) values decreasingly, and let \(z_{(\nu)}\) be the \(\nu\)-th largest.
Because every \(z_{tiv}\le y\),
\(\nu y\le\sum_i z_{tiv}\le(\nu-1)y+(m-\nu+1)z_{(\nu)}.\)
Therefore at least \(\nu\) distinct campaigns satisfy \(z_{tiv}\ge y/r\).
Choose \(j\) with \(t_j\le y<2t_j\), allowing \(j=0\) when \(y=1\). For each of those \(\nu\) campaigns, either its initial seeds already reach \(v\), or
\(\sum_{u\in A_{tiv}}x_{iu}\ge z_{tiv}\ge y/r\ge t_j/r.\)
In the latter case, the probability that no rounded seed reaches \(v\) is at most
\[ \prod_{u\in A_{tiv}} \left(1-\min\{1,arx_{iu}/t_j\}\right) \le \exp\left(-\frac{ar}{t_j}\sum_{u\in A_{tiv}}x_{iu}\right) \le e^{-a}. \]
If any factor has seed probability \(1\), the failure probability is zero; otherwise the first inequality follows from \(1-u\le e^{-u}\).
Since \(a\ge\ln(2\nu)\), a union bound over the \(\nu\) campaigns shows that, conditional on this scale, \(v\) is sufficiently exposed with probability at least \(1-\nu e^{-a}\ge1/2\).
This scale is selected with probability \(t_j/2\). Thus the unconditional exposure probability is at least \(t_j/4\ge y/8\).
Rows with \(y_{tv}<t_J\) contribute at most \(t_J\) to the normalized LP objective. Therefore a random rounded plan \(P\) satisfies
\[ \mathbb E[\widehat h(P)] \ge\frac{A-t_J}{8} \ge\frac{A-q/4}{8} \ge\frac{3A}{32}, \]
where the last two inequalities use \(t_J\le q/4\) and \(A\ge q\).
Before rounding probabilities upward, conditional expected cost at scale \(j\) is at most \(arK/t_j\). Averaging over scales gives expected cost at most \(ar(J+1)K/2\).
Upward rounding adds at most \(mn2^{-s}\le1\) to conditional expected cost. Since \(K\ge1\), the implemented rounded plan therefore satisfies
\(\mathbb E[c(P)]\le BK.\)
Generate \(R\) independent rounded plans \(P_1,\ldots,P_R\), where \(R\) is a power of two satisfying
\(R\ge\frac{\ln12}{2(3q/64)^2}.\)
Let \(Q_R\) be their uniform distribution and let \(\overline c=R^{-1}\sum_\ell c(P_\ell)\).
Conditional on the sampled LP, Hoeffding’s inequality and the exposure bound give, with probability at least \(11/12\),
\[ \widehat h(Q_R)\ge\frac{3A}{32}-\frac{3q}{64}\ge\frac{3A}{64}. \]
Markov’s inequality gives, with probability at least \(11/12\),
\(\overline c\le12BK.\)
Choose \(\lambda\) as the largest inverse power of two no greater than \(\min\{1/2,K/\overline c\}\); take \(\lambda=1/2\) if \(\overline c=0\). Output
\(\pi=(1-\lambda)\delta_{\varnothing}+\lambda Q_R.\)
This is an explicit list of at most \(R+1\) plans. Its probabilities are dyadic because both \(R\) and \(1/\lambda\) are powers of two. For every realization of the algorithm,
\(\mathbb E_{\sigma\sim\pi}[c(\sigma)]=\lambda\overline c\le K.\)
On the cost event, \(\lambda\ge1/(24B)\): the largest inverse power of two below a positive number is at least half that number.
On the simultaneous sampling and rounding-value events,
\[ h(Q_R)\ge\widehat h(Q_R)-\eta \ge\frac{3A}{64}-\frac q{128} \ge\frac A{32}. \]
Using \(A\ge H^*-\eta\) and \(H^*\ge q\), this implies
\(h(Q_R)\ge(127/4096)H^*.\)
The empty plan contributes at least \(z_0\), and every rounded plan contributes at least its sufficiently exposed fraction. Therefore
\[ F(\pi)\ge(1-\lambda)z_0+\lambda h(Q_R) \ge\frac{z_0}{2}+\frac{127H^*}{98304B} \ge\frac{z_0+H^*}{800B} \ge\frac{F^*}{800B}. \]
Thus an explicit achievable ratio is
\[ \boxed{ \frac{1}{ 800\left[ 1+\lceil\log_2(2\nu)\rceil(m-\nu+1) \left(\lceil\log_2(4\nu n/K)\rceil+1\right) \right] }. } \]
The three probabilistic estimates above each have failure probability at most \(1/12\).
Binary-encoded rational edge probabilities can be sampled exactly using rejection sampling. For a denominator \(D\), sample an integer using \(\lceil\log_2D\rceil\) fair bits and reject values outside \(\{0,\ldots,D-1\}\). Acceptance probability is at least \(1/2\).
Cap the attempts for every edge sample so that the probability of any cap being exceeded is at most \(1/12\). On that event, return the feasible full-seeding/empty mixture instead. Coupling with the uncapped exact sampler justifies applying the preceding estimates to the successful execution. A union bound over these four failure events leaves success probability at least \(2/3\).
There is no external accuracy parameter. The internal quantities satisfy
\(T=O((mn+1)q^{-2}),\qquad R=O(q^{-2}),\qquad q^{-1}=\nu n/K\le n.\)
For the sampled LP:
The total worst-case bit running time is consequently polynomial in \(n,|E|,m,L\). Here \(\tau=1\), so it is also polynomial in the requested parameter list \(n,|E|,m,\tau,L\). The output contains \(O(n^2)\) plans.
The output distribution is sampled independently of the subsequent cascades: the live-edge outcomes used by the algorithm are training samples, not the eventual cascade outcomes.
For fixed \(m,\nu\), the explicit ratio is
\(\Omega\!\left(1/(1+\log(\nu n/K))\right),\)
and hence \(\Omega(1/\log n)\) uniformly over the permitted budgets.
Choose a sufficiently large constant \(C\), depending only on \(m,\nu\), such that the guarantee is at least \(1/(C\ln n)\) for every admissible \(n\). Define, for \(n\ge3\),
\(g(n)=\ln(C\ln n)/\ln n.\)
Then \(n^{-g(n)}=1/(C\ln n)\) and \(g(n)=o(1)\). Taking \(C\ge e\) makes \(g\) nonnegative and decreasing on this domain: its derivative has the sign of \(1-\ln(C\ln n)\). Extend it constantly below \(3\), if needed.
Thus an \(n^{-g(n)}\) approximation exists for a nonnegative non-increasing \(g=o(1)\). This disproves the proposed universal Gap-ETH exclusion for the pooled problem.
Also, for every fixed \(\epsilon>0\),
\(1/(C\ln n)\ge n^{-\epsilon}\)
for all sufficiently large \(n\). The finitely many smaller sizes can be handled exactly by enumerating all plans and live-edge outcomes, then solving the resulting finite distribution LP. With those sizes bounded, this takes polynomial time in \(L\). Therefore an \(n^{-\epsilon}\) approximation is available for every fixed \(\epsilon>0\), including any proposed \(\epsilon(d)>0\).
The cited [discrete balance results](https://arxiv.org/pdf/1906.00074) concern a budget imposed separately on each integral plan. Our rounding instead uses plans of larger cost and dilutes them with the empty plan. The proof above shows constructively why those approximation exclusions cannot carry over unchanged to an average budget. It does not rely on the \(1-1/e\) guarantee for the different [maximin randomization objective](https://ojs.aaai.org/index.php/AAAI/article/view/17725).
A constant-factor approximation, or a matching limitation on the logarithmic guarantee, is not established here.
⟨structured verdict parsed — rendered above⟩
The central approximation argument is correct. It establishes an unconditional randomized polynomial-time approximation with the displayed ratio, and therefore \(\Omega(1/\log n)\) for fixed \(m,\nu\). Its conclusions about overcoming the two proposed universal hardness barriers follow.
There are two minor presentation issues: the fallback distribution need not have dyadic probabilities, and the choice of \(R\) needs an explicit polynomial upper bound. Neither requires new mathematics or invalidates the approximation result under the task’s binary-rational output requirement.
I interpret \(m,\nu\) as fixed integers, consistently with the task and the prover’s stated conclusions. When tracking them as parameters, the displayed approximation ratio retains its dependence on \(m,\nu\).
The decomposition \(b(\sigma)/n=h(\sigma)+z(\sigma)\) is correct: the two counted exposure conditions are disjoint.
Under a common live-edge realization, adding seeds only enlarges each campaign’s reached set. Consequently \(z(\sigma)\le z_0\), and averaging over any feasible distribution gives \(F^*\le z_0+H^*\).
The full-seeding plan has cost \(\nu n\) and sufficiently exposes every vertex. Its mixture with the empty plan at weight \(q=K/(\nu n)\) is feasible and proves \(H^*\ge q\). The permitted budget range gives \(1/n\le q\le1\).
These claims cover the endpoint \(q=1\) and allow arbitrary initial seed sets.
For each fixed plan, the sampled quantities lie in \([0,1]\) and are independent across the \(T\) outcomes. The stated Hoeffding bound, followed by a union bound over \(2^{mn}\) plans, is valid.
With the specified \(T\), the failure probability is at most
\[
2^{mn+1}\exp\bigl(-(mn\ln2+\ln24)\bigr)=1/12.
\]
Here and throughout this report, displayed mathematics is understood with the requested rendering delimiters.
The uniform event extends to every distribution by linearity, including distributions chosen after observing the samples. Thus adaptive selection of the output distribution introduces no additional sampling gap.
The proposed LP variables correctly encode a feasible relaxation:
Its objective equals \(\widehat h(\pi)\) for the constructed feasible point. Therefore \(A\ge q\) for every sample and \(A\ge H^*-\eta\) on the uniform sampling event.
The order-statistic inequality is correct:
\[
\nu y\le \sum_i z_{tiv}\le(\nu-1)y+(m-\nu+1)z_{(\nu)}.
\]
It implies that at least \(\nu\) campaigns have \(z_{tiv}\ge y/r\).
For every \(y\ge t_J\), a permitted scale satisfies \(t_j\le y<2t_j\), with the explicitly handled endpoint \(y=1\).
For each selected campaign without initial reachability, the LP provides enough seed mass to obtain failure probability at most \(e^{-a}\). The product estimate is valid in both cases identified by the prover: a seed probability equals \(1\), or all probabilities remain below \(1\).
Since \(a=\lceil\log_2(2\nu)\rceil\ge\ln(2\nu)\), the union bound gives conditional exposure probability at least \(1/2\). Independence between those campaign-success events is unnecessary.
Multiplying by the scale probability yields exposure probability at least \(y/8\). Upward rounding of seed probabilities preserves this lower bound.
Discarded rows contribute at most \(t_J\), and \(t_J\le q/4\). Consequently
\[
\mathbb E[\widehat h(P)]\ge(A-t_J)/8\ge3A/32.
\]
All constants and inequalities in this calculation are correct.
At scale \(j\), the unrounded expected cost is at most \(arK/t_j\). Weighting by \(t_j/2\) and summing yields \(ar(J+1)K/2\).
Upward probability rounding increases conditional expected cost by at most \(mn2^{-s}\le1\). Since \(K\ge\nu\ge3\), the claimed bound \(\mathbb E[c(P)]\le BK\) follows.
For every realized list of plans, the dilution factor satisfies \(\lambda\overline c\le K\). Thus feasibility is unconditional, including when the favorable concentration events fail.
On \(\overline c\le12BK\), rounding the dilution factor down to an inverse power of two gives \(\lambda\ge1/(24B)\), as claimed.
Conditional on the sampled LP, the rounded plans are independent and their sampled values lie in \([0,1]\). The stated choice of \(R\) makes the lower-tail failure probability at most \(1/12\).
Using \(A\ge q\), the empirical lower bound gives \(\widehat h(Q_R)\ge3A/64\). On the uniform sampling event,
\[
h(Q_R)\ge3A/64-q/128\ge A/32.
\]
Together with \(A\ge H^*-\eta\) and \(q\le H^*\), this implies \(h(Q_R)\ge127H^*/4096\).
The final estimate is valid. In particular, the coefficient comparison needed for \(1/(800B)\) is
\[
127/98304>1/800,
\]
and \(1/2\ge1/(800B)\). Thus the displayed explicit approximation ratio follows.
The sampling, rounding-value, and cost events each fail with probability at most \(1/12\). The capped exact sampler contributes another failure event of probability at most \(1/12\).
The coupling justification is sound: the analysis can be performed on the ideal uncapped execution, and the actual execution agrees whenever no cap is exceeded. A union bound therefore gives success probability at least \(2/3\).
The successful main branch outputs dyadic probabilities. The fallback remains feasible and binary-rational, but need not be dyadic; this is Issue 1 below.
The training samples are independent of the eventual cascades, as required.
The reachability construction and stated LP dimensions are polynomial. The LP is rational, feasible, and bounded, so the invoked polynomial-time rational LP result applies. Its coefficients have polynomial encoding length.
Since \(q^{-1}\le n\), the sample count \(T\) is polynomial. The claimed bounds for \(R\) and output size hold with a suitably bounded choice of \(R\); Issue 2 concerns making that choice explicit.
For fixed \(m,\nu\), the approximation is \(\Omega(1/\log n)\). The proposed function \(g\) has the claimed identity, limit, and monotonicity for \(C\ge e\). Hence it supplies an attainable ratio within the class covered by the proposed universal Gap-ETH exclusion.
For each fixed \(\epsilon>0\), logarithmic decay eventually dominates \(n^{-\epsilon}\). Exact enumeration for the finitely many smaller sizes is polynomial in \(L\): with fixed \(m\) and bounded \(n\), the numbers of plans and live-edge outcomes are bounded constants, while rational arithmetic retains polynomial bit complexity.
Thus both claimed barrier conclusions follow. The argument does not establish an optimal approximation ratio or exact polynomial-time optimization.
There are no major issues or blocking gaps.
⟨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.