d4-conf-atal-2017-0235 (d4-conf-atal-2017-0235)

For a population with rational type masses \(\mu_r\), specify a directed sparse random network by giving each ordered pair of type-\(r\) and type-\(s\) agents an edge independently with probability \(\lambda_{rs}/N\), where \(N\) is population size and the rational contact rates \(\lambda_{rs}\) are bounded. Assign edges to a fixed finite set of tie categories, each with an uncertain propagation parameter \(\theta_j\in[a_j,b_j]\). Given a seeding budget \(\kappa\), a feasible action is a type-wise seed-mass profile \(z\) with \(0\le z_r\le\mu_r\) and \(\sum_r z_r\le\kappa\). Let \(g_\mu(z,\theta)\) be the limiting expected influenced mass after a fixed finite cascade horizon, and let \(g^G_\mu(\theta)\) be the corresponding type-wise greedy benchmark. Can one compute a finitely represented randomized strategy over feasible profiles with the \((1-1/e,\epsilon)\)-minimax guarantee of Theorem 1, in time polynomial in the number of types, input bit length, horizon, and \(1/\epsilon\), independently of \(N\)?

A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_r\), with \(\sum_r\mu_r=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length.
Input also specifies rational rates \(0\le\lambda_{rs}\le C\), for a fixed constant \(C\), a category map \(c(r,s)\in\{1,\ldots,m\}\), rational intervals \(0\le a_j\le b_j\le1\), rational \(0<\kappa\le1\), an integer horizon \(T\ge1\), and rational \(0<\epsilon<1\). The number \(m\) of tie categories is fixed; write \(P=\prod_j[a_j,b_j]\).
For population sizes \(N\) with integral \(N\mu_r\), each ordered pair of distinct agents of types \(r,s\) has an edge independently with probability \(\lambda_{rs}/N\); its category is \(c(r,s)\). The graph is sampled once and is not observed before seeding.
All seeds are activated at time zero and attend certainly. In each of \(T\) synchronous rounds, every already active agent independently attempts to activate each inactive out-neighbor with probability \(\theta_{c(r,s)}\); failed attempts may be repeated next round, and activation is permanent. There are no observations, later interventions, or additional random propagation parameters.
Let \(F_N(k,\theta)\) be the expected final active fraction, averaging over the graph and propagation, when \(k_r\) agents of each type are seeded. Define \(Z=\{z\in\mathbb R^\tau:0\le z_r\le\mu_r,\ \sum_rz_r\le\kappa\}\) and \(g_\mu(z,\theta)=\lim_{N\to\infty}F_N(\lfloor Nz\rfloor,\theta)\), along these population sizes.
Define the type-wise greedy benchmark by starting with no seeds and adding one seed at a time to maximize the marginal increase in \(F_N\), until \(\lfloor N\kappa\rfloor\) seeds are chosen; exclude exhausted types and break ties by smallest type index. If its allocation is \(k_N^G(\theta)\), set \(g_\mu^G(\theta)=\limsup_{N\to\infty}F_N(k_N^G(\theta),\theta)\).
For any Borel probability distribution \(Q\) on \(Z\), put \(V(Q)=\inf_{\theta\in P}\mathbb E_{z\sim Q}[g_\mu(z,\theta)/g_\mu^G(\theta)]\) and \(V^*=\sup_Q V(Q)\). A finitely represented strategy is an explicit finite list of feasible rational profiles and rational probabilities summing to one.
Does this problem admit an algorithm computing a finitely represented strategy \(Q\) with \(V(Q)\ge(1-1/e)V^*-\epsilon\) in time polynomial in \(m,\tau,L,T,1/\epsilon\) for each fixed \(m\), independently of \(N\), or is achieving this approximation guarantee NP-hard?
For discrete directed networks with a fixed number of tie categories, a polynomial-time \((1-1/e,\epsilon)\)-minimax approximation relative to the greedy benchmark is established by [Wilder et al.](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p1305.pdf).
No result settling this precise limiting mass problem was located in the literature search.

Partial progress: polynomial parameter discretization and a weaker approximation

Put
$$ \alpha=1-\frac1e. $$

I do not settle whether the requested guarantee is polynomial-time achievable or NP-hard. I prove two additional results:

• There is an unconditional polynomial-time algorithm producing a finitely represented strategy satisfying

$$ V(Q)\ge \alpha^3V^*-\epsilon. $$

• The requested $\alpha$ guarantee follows from a precisely specified oracle: approximate, from above, the supremum of the limiting greedy benchmark over each of polynomially many rational parameter cells.

The discretization uses multiplicative sensitivity of the diffusion numerator. It accommodates zero propagation parameters and does not assume continuity of the greedy benchmark.

Everything needed from the earlier notes is proved below, including a valid branching-process domination and an accumulated numerical-error bound.

1. The limiting objective and its basic properties

Write
$$ p_{rs}(d;\theta) = \theta_{c(r,s)}(1-\theta_{c(r,s)})^{d-1}, \qquad d\ge 1. $$

At propagation probability zero, the waiting time is infinite. At probability one, its distribution puts probability one on waiting time one; thus the formula means $p_{rs}(1;\theta)=1$ and $p_{rs}(d;\theta)=0$ for $d>1$.

Define
$$ x_s(0)=z_s, $$
and, for $1\le t\le T$,
$$ H_s(t) = \sum_{r=1}^{\tau}\lambda_{rs} \sum_{d=1}^{t}p_{rs}(d;\theta)x_r(t-d), $$
$$ x_s(t) = \mu_s-(\mu_s-z_s)e^{-H_s(t)}. $$

Proposition 1: existence and uniform convergence

The limit defining $g_\mu$ exists, and
$$ g_\mu(z,\theta)=\sum_{s=1}^{\tau}x_s(T). $$

For each fixed input society and horizon,
$$ \sup_{\theta\in[0,1]^m} \sup_k \left| F_N(k,\theta)-g_\mu(k/N,\theta) \right| \longrightarrow 0, $$
where $k$ ranges over all allocations respecting type capacities.

Proof

Presample an independent geometric waiting time on every existing directed edge. Its clock starts when its source becomes active. This reproduces the repeated-attempt process. A vertex is active by time $T$ exactly when a seed reaches it along a directed path whose waiting times sum to at most $T$. Such a path has at most $T$ edges.

For a uniformly selected type-$s$ vertex, the incoming graph neighborhood through depth $T$ converges to a multitype branching tree. A type-$s$ vertex has independent Poisson numbers of type-$r$ incoming children, with means
$$ \mu_r\lambda_{rs}. $$
A type-$r$ vertex is independently marked as seeded with probability $z_r/\mu_r$.

Here is a valid uniform truncation bound. Fix an integer
$$ D\ge \max\{1,2C\}, \qquad R=1+D. $$
For sufficiently large $N$, every edge probability is at most $1/2$. A Bernoulli variable of parameter $p$ is stochastically dominated by a Poisson variable of mean $-\log(1-p)$: the latter is positive with probability exactly $p$. Consequently, a fresh incoming exploration count is dominated by a Poisson variable of mean at most
$$ \sum_{\text{candidate agents}} -\log(1-\lambda_{rs}/N) \le 2\sum_{\text{candidate agents}}\lambda_{rs}/N \le 2C. $$
It is therefore dominated by a Poisson variable of mean $D$. The limiting offspring count is also dominated by this law.

Thus both neighborhood sizes can be bounded by a Poisson-$D$ branching process through depth $T$. If $Z_d$ denotes its generation size, then
$$ \mathbb E Z_{d+1}^2 = D^2\mathbb E Z_d^2+D\mathbb E Z_d \le R^2\mathbb E Z_d^2. $$
For its total size $M=\sum_{d=0}^T Z_d$, this gives
$$ \mathbb E M\le (T+1)R^T, \qquad \mathbb E M^2\le (T+1)^2R^{2T}. $$

Truncate explorations after $K$ vertices. For fixed $K$, binomial-to-Poisson approximation and the probability of repeated vertex labels give convergence of the truncated neighborhoods. Conditional on types, seed indicators are sampled without replacement within each type. Coupling this sampling to sampling with replacement gives an error bounded by a constant times
$$ \frac{K^2}{N\mu_{\min}}, \qquad \mu_{\min}=\min_r\mu_r, $$
uniformly over the seed allocation. Propagation marks can be coupled using common uniforms, uniformly over $\theta$.

The probability that truncation changes the activation event is at most $\mathbb E M/K$. Taking first $N$ and then $K$ to infinity proves the asserted uniform convergence.

To evaluate the tree, let $q_s(t)$ be its type-$s$ root activation probability. A type-$r$ child activates its parent by time $t$ with probability
$$ \sum_{d=1}^t p_{rs}(d;\theta)q_r(t-d). $$
Independent Poisson thinning gives
$$ 1-q_s(t) = \left(1-\frac{z_s}{\mu_s}\right) \exp\left( -\sum_r\mu_r\lambda_{rs} \sum_{d=1}^t p_{rs}(d;\theta)q_r(t-d) \right). $$
Substituting $x_s(t)=\mu_sq_s(t)$ yields the stated recursion. Its continuity in $z$ also establishes the limit for $\lfloor Nz\rfloor$. $\square$

For brevity, write
$$ g(z,\theta)=g_\mu(z,\theta), \qquad b(\theta)=g_\mu^G(\theta), \qquad O(\theta)=\max_{z\in Z}g(z,\theta). $$

Proposition 2: derivatives and benchmark bounds

Define
$$ U=\frac{(T+1)R^T}{\mu_{\min}}, \qquad H=\frac{(T+1)^2R^{2T}}{\mu_{\min}^2}. $$
On the seed-capacity box,
$$ e^{-C}\le \partial_r g(z,\theta)\le U, $$
and
$$ -H\le \partial_r\partial_s g(z,\theta)\le 0. $$

Moreover,
$$ \alpha O(\theta)\le b(\theta)\le O(\theta), \qquad b(\theta)\ge\kappa. $$
In particular,
$$ 0\le V^*\le \frac1\alpha<2. $$

Proof

Choose the branching-tree root type according to the mass vector $\mu$. Let $n_r$ count type-$r$ vertices whose weighted distance to the root is at most $T$, including the root when applicable. Conditional on the tree and waiting times, inactivity has probability
$$ \prod_r\left(1-\frac{z_r}{\mu_r}\right)^{n_r}. $$
Therefore
$$ g(z,\theta) = 1-\mathbb E\left[ \prod_r\left(1-\frac{z_r}{\mu_r}\right)^{n_r} \right]. $$

The conditional activation polynomial has nonnegative first derivatives and nonpositive second derivatives, including pure second derivatives. Their absolute values are bounded by $M/\mu_{\min}$ and $M^2/\mu_{\min}^2$. The preceding moment bounds justify differentiation under the expectation and continuity up to the boundary.

The lower derivative bound follows from the recursion. All activation derivatives are nonnegative, so
$$ \partial_r x_r(T)\ge e^{-H_r(T)}. $$
Also,
$$ H_r(T) \le C\sum_u\mu_u\sum_{d=1}^T p_{ur}(d;\theta) \le C. $$

For the benchmark bounds, fix the graph and edge waiting times. Each target is activated precisely when its reverse reachable set intersects the seed set. Final activation is consequently a coverage function, hence monotone and submodular. Expectation preserves both properties.

Exchangeability within each type makes the prescribed type-wise greedy algorithm an individual-agent greedy algorithm. With $K_N=\lfloor N\kappa\rfloor$, the usual greedy recurrence gives
$$ F_N(k_N^G(\theta),\theta) \ge \left[1-\left(1-\frac1{K_N}\right)^{K_N}\right] \operatorname{OPT}_N(\theta) \ge \alpha\operatorname{OPT}_N(\theta). $$
Indeed, submodularity bounds the remaining optimal gain by the sum of at most $K_N$ current marginals; greedy chooses at least their average.

Uniform convergence from Proposition 1 implies
$$ \operatorname{OPT}_N(\theta)\longrightarrow O(\theta). $$
For one direction, every finite allocation divided by $N$ belongs to $Z$. For the other, floor a maximizing profile in $Z$. Taking a limsup proves the benchmark approximation bounds.

Finally, all $K_N$ seeds are certainly active, giving $b(\theta)\ge\kappa$. The payoff bound follows from $g(z,\theta)\le O(\theta)\le b(\theta)/\alpha$.

Each finite greedy value is Borel in $\theta$, because its allocation is determined by finitely many comparisons of continuous functions with a specified tie rule. Its limsup $b$ is Borel. Thus all expectations used below are well-defined. $\square$

2. A polynomial weighted optimization oracle

The following algorithm concerns numerator optimization only. It does not evaluate $b$.

Proposition 3

Let $\theta^1,\ldots,\theta^J\in[0,1]^m$ be rational, and let $w_i$ be nonnegative rational weights summing to one. For rational $0<\eta<1/4$, a feasible rational profile can be computed satisfying
$$ f(z)\ge(\alpha-\eta)\max_{y\in Z}f(y), \qquad f(z)=\sum_{i=1}^Jw_i g(z,\theta^i). $$
The profile has total seed mass $\kappa$. The running time and output bit length are polynomial in the supplied bit length, $J,\tau,T,1/\eta$.

Proof

The function $f$ inherits the derivative bounds of Proposition 2. Choose a fixed positive rational
$$ \ell\le e^{-C}. $$
For example, $\ell=2^{-2D}$ suffices.

Put $\delta=\eta/2$ and
$$ a=\frac{\delta\ell}{32}. $$
Start at $z=0$. At each step, compute every eligible derivative to absolute error at most $a$ and select the coordinate with largest computed derivative.

Let $d$ be its true derivative and $d_{\max}$ the largest eligible true derivative. Then
$$ d\ge d_{\max}-2a \ge \left(1-\frac{\delta}{16}\right)d_{\max}. $$

Let $\widetilde d$ be its computed derivative and set
$$ h=\left(1-\frac{\delta}{2}\right)\widetilde d. $$
The largest allowed coordinate increment ends at capacity or at the remaining budget. Accept that endpoint if its computed derivative is at least $h$. Otherwise, bisect, maintaining an accepted lower endpoint and a rejected upper endpoint, until their distance is at most $a/H$, then take the lower endpoint.

At every accepted endpoint, the true derivative is at least
$$ h-a \ge \left(1-\frac{\delta}{2}\right)d-2a \ge (1-\delta)d. $$
Since the derivative is nonincreasing along the coordinate, the same lower bound holds throughout the step.

For a bisection-ending step, the Hessian bound and the rejected upper endpoint give
$$ d_{\mathrm{end}} \le h+2a \le \left(1-\frac{\delta}{2}\right)d+3a \le \left(1-\frac{\delta}{4}\right)d. $$
Such a step is positive. If its lower endpoint were zero, the rejected upper endpoint would be within $a/H$ of the start, so its true derivative would be at least $d-a$. Rejection instead implies
$$ d_{\mathrm{upper}}<h+a\le d-\frac{\delta d}{2}+2a<d-a, $$
a contradiction.

All coordinate derivatives decrease as the profile increases. Hence each coordinate can undergo at most
$$ 1+\frac4\delta\log\frac U\ell $$
bisection-ending steps. Capacity-ending steps exhaust a coordinate; there is at most one budget-ending step. The total number of steps is polynomial.

Parametrize the path by seeded mass $s\in[0,\kappa]$. Throughout each step, the chosen derivative is at least $(1-2\delta)$ times the largest currently eligible derivative.

Let $f^*=\max_{y\in Z}f(y)$ and choose a maximizer $y$. Monotonicity and diminishing returns on the full capacity box imply
$$ f^*-f(z) \le f(z\vee y)-f(z) \le \sum_r(y_r-z_r)_+\partial_r f(z). $$
Exhausted coordinates contribute zero, and
$$ \sum_r(y_r-z_r)_+\le\kappa. $$
Thus, almost everywhere along the path,
$$ \frac{d}{ds}f(z(s)) \ge \frac{1-2\delta}{\kappa}\bigl(f^*-f(z(s))\bigr). $$
The budget is filled because all eligible derivatives are positive and the total capacity is one. Since $f(0)=0$, integration yields
$$ f(z(\kappa)) \ge \left[1-e^{-(1-2\delta)}\right]f^* \ge (\alpha-2\delta)f^*. $$

It remains to justify numerical complexity. The recursion and all first derivatives form an arithmetic-and-exponential circuit with
$$ S=O(J\tau^3T^2) $$
gates. Exact exponential arguments lie in $[-C,0]$. Exact intermediate magnitudes are bounded by a quantity $A$ satisfying
$$ \log A=O\bigl(\log(J\tau T)+\log U+1\bigr). $$
For instance, a sufficiently large fixed multiple of
$$ 2+(1+C)J\tau T(1+U) $$
works.

As long as intermediate errors are at most one, additions, multiplications, and exponentials increase the maximum preceding error by a factor at most
$$ K=4A+8, $$
plus their local rounding error. For exponentials this uses that the perturbed arguments remain in $[-C-1,1]$.

If every local operation has absolute error at most
$$ \nu=\frac{a}{2(S+1)K^S}, $$
induction gives a final error at most
$$ \nu(S+1)K^S\le a/2. $$
The required precision is therefore
$$ O\bigl(\log(1/a)+S\log K+\log(S+1)\bigr), $$
which is polynomial. On this fixed bounded argument interval, Taylor expansion computes the exponential to that precision in polynomial time: the remainder is bounded by a constant times a fixed constant raised to the truncation order, divided by its factorial.

Each bisection needs $O(\log(H/a)+1)$ iterations. Its endpoints are rational, and the cumulative number of midpoint operations is polynomial, so profile bit lengths are polynomial as well. This proves the claimed implementation. $\square$

The same oracle applies to any nonzero nonnegative rational linear combination of scenarios, by normalizing its coefficients.

3. New sensitivity bounds

The next bounds concern fixed seed profiles. They do not assert regularity of the greedy benchmark.

Proposition 4: multiplicative sensitivity

If
$$ \theta\le\theta'\le\rho\theta $$
coordinatewise, where $\rho\ge1$ and both vectors belong to $[0,1]^m$, then
$$ g(z,\theta)\le g(z,\theta')\le\rho^Tg(z,\theta). $$

In particular, the hypothesis forces a zero coordinate of $\theta$ to remain zero.

Proof

First work at finite $N$ with a fixed seed set and graph. Presample, for each existing edge and each absolute round, an independent Bernoulli attempt bit. This is another valid representation of the specified process.

Activation of a target is a monotone Boolean function of these bits. Whenever activation occurs, it has a certificate consisting of a time-respecting path from a seed, using at most $T$ successful bits.

A successful pivotal bit must belong to every successful certificate: turning off a bit outside one certificate preserves that certificate. Consequently, on an activation outcome, there are at most $T$ successful pivotal bits.

For a Bernoulli bit of parameter $p$, the probability that it is both successful and pivotal equals $p$ times the derivative of the activation probability with respect to that bit’s parameter. Summing over bits and averaging over targets and graphs gives
$$ \sum_{j=1}^m \theta_j\partial_jF_N(k,\theta) \le T F_N(k,\theta). $$
The identity and inequality also hold at endpoints by their polynomial expressions.

Interpolate positive coordinates logarithmically:
$$ \theta_j(u) = \theta_j\exp\left( u\log\frac{\theta'_j}{\theta_j} \right), \qquad 0\le u\le1, $$
and leave zero coordinates fixed. Monotonicity of the derivatives gives
$$ \frac{d}{du}F_N(k,\theta(u)) \le T\log(\rho)\,F_N(k,\theta(u)). $$
Integration yields
$$ F_N(k,\theta')\le\rho^TF_N(k,\theta). $$
Taking the population limit proves the result. $\square$

Proposition 5: absolute sensitivity proportional to seed mass

Let $s=\sum_rz_r$, and define the rational bound
$$ B=TD(1+D)^{T-1}. $$
Then
$$ |g(z,\theta)-g(z,\theta')| \le sB\|\theta-\theta'\|_\infty. $$

Proof

It suffices to compare coordinatewise ordered vectors, by replacing arbitrary vectors with their coordinatewise minimum and maximum. Let their maximum coordinate difference be $h$, and couple attempt bits by common uniforms.

If a target activates under the larger vector but not the smaller one, some successful path under the larger vector contains a differing attempt bit. An activation path can be chosen with distinct vertices and strictly increasing attempt rounds.

For a specified path of length $\ell$, the probability its graph edges exist is at most $(C/N)^\ell$. Conditional on their existence, the probability of at least one differing bit is at most $\ell h$.

If the seed set has size $k$, there are at most $kN^\ell$ ordered paths of length $\ell$, summed over targets, and $\binom T\ell$ possible increasing round sequences. A union bound therefore gives
$$ |F_N(k,\theta)-F_N(k,\theta')| \le \frac{k}{N}h \sum_{\ell=1}^T \ell\binom T\ell C^\ell. $$
The sum equals
$$ TC(1+C)^{T-1}\le B. $$
Passing to the limit proves the assertion. $\square$

The factor $s$ is useful: after normalization by a denominator at least $\kappa$, it removes dependence on $1/\kappa$ from this discretization.

4. Polynomially many parameter cells

Fix rational $0<t<1$, and set
$$ h_0=\frac{t}{2B}, \qquad \delta=\frac{t}{4T}. $$

In each coordinate, use knots
$$ 0,\quad h_0,\quad h_0(1+\delta),\quad h_0(1+\delta)^2,\quad\ldots,\quad1, $$
replacing the first knot exceeding one by one. Intersect the resulting intervals with $[a_j,b_j]$. Their products form finitely many closed rational cells covering $P$.

For every coordinate interval $[\ell_j,u_j]$, either
$$ u_j\le h_0 $$
or
$$ u_j\le(1+\delta)\ell_j. $$

Let $\ell_i,u_i$ be the lower and upper corners of cell $i$, and put
$$ A=(1+\delta)^T\le e^{t/4}\le1+\frac t2. $$
Apply multiplicative sensitivity to the coordinates above the cutoff, and then absolute sensitivity to the coordinates below it. For every feasible profile,
$$ g(z,\ell_i) \le g(z,\theta) \le g(z,u_i) \le A g(z,\ell_i)+\frac{\kappa t}{2}, \qquad \theta\text{ in cell }i. $$
Taking maxima over profiles gives
$$ O(\theta)\le A O(\ell_i)+\frac{\kappa t}{2}. $$

The number of knots per coordinate is
$$ O\left( 1+\frac{T}{t} \left(T+\log(T+1)+\log(1/t)\right) \right). $$
Indeed, $\log B=O(T+\log(T+1))$ and $\log(1+\delta)\ge\delta/2$.

Thus the number $J$ of cells is polynomial in $T,1/t$ for each fixed $m$. Repeated multiplication constructs rational knots with polynomial bit length. Interval clipping adds only the input endpoints.

Proposition 6: a finite envelope game approximates the original game

Define
$$ \beta_i=\sup_{\theta\text{ in cell }i}b(\theta) $$
and
$$ W(Q)= \min_{1\le i\le J} \frac{\mathbb E_Q g(z,\ell_i)}{\beta_i}. $$
Then, for every Borel strategy $Q$,
$$ W(Q)\le V(Q)\le W(Q)+2t. $$

Proof

For any $\theta$ in cell $i$, monotonicity and $b(\theta)\le\beta_i$ give
$$ \frac{\mathbb E_Q g(z,\theta)}{b(\theta)} \ge \frac{\mathbb E_Q g(z,\ell_i)}{\beta_i} \ge W(Q). $$
Taking the infimum proves the first inequality.

Choose a cell attaining the finite minimum in $W(Q)$, and choose a sequence $\theta_n$ in that cell satisfying
$$ b(\theta_n)\longrightarrow\beta_i. $$
No attainment or continuity assumption is needed. The numerator bound gives
$$ V(Q) \le A\frac{\mathbb E_Q g(z,\ell_i)}{\beta_i} +\frac{\kappa t}{2\beta_i} \le AW(Q)+\frac t2. $$
Also,
$$ \beta_i\ge b(\ell_i)\ge\alpha O(\ell_i), $$
so $W(Q)\le1/\alpha<2$. Therefore
$$ V(Q)-W(Q) \le \frac{t}{2\alpha}+\frac t2 <2t. $$
$\square$

This is a polynomial-size reduction, but its coefficients $\beta_i$ are not yet supplied by a polynomial-time algorithm.

5. Computing strategies for finite scenario games

We will use a finite-game procedure whose benchmark coefficients are rational and given explicitly.

Proposition 7

Suppose rational $\theta^i\in[0,1]^m$ and positive rational $d_i$ are supplied, and the payoffs
$$ h_i(z)=\frac{g(z,\theta^i)}{d_i} $$
belong to $[0,2]$. Define
$$ W_d^*=\sup_Q\min_i\mathbb E_Qh_i(z). $$
For rational $0<t<1/64$, a polynomial-time algorithm outputs a rational empirical strategy satisfying
$$ \min_i\mathbb E_Qh_i(z) \ge (\alpha-t)W_d^*-t. $$
Its profiles have total mass $\kappa$.

Proof

Use unnormalized adversarial weights initialized to one. At iteration $n$, normalize them to rational weights $w_{n,i}$ and apply Proposition 3 to
$$ \sum_i w_{n,i}h_i(z) $$
with approximation tolerance $t$.

For every choice of adversarial weights,
$$ \max_z\sum_iw_{n,i}h_i(z)\ge W_d^*. $$
This follows because, for any distribution $Q$,
$$ \min_i\mathbb E_Qh_i \le \sum_iw_{n,i}\mathbb E_Qh_i \le \max_z\sum_iw_{n,i}h_i(z). $$
Hence the returned profile $z^n$ satisfies
$$ \sum_iw_{n,i}h_i(z^n)\ge(\alpha-t)W_d^*. $$

Round each payoff to a fixed dyadic mesh, obtaining $\widetilde h_i(z^n)\in[0,2]$ with absolute error at most
$$ \sigma=\frac t8. $$
With $\rho=t/8$, update unnormalized weights by
$$ v_{n+1,i} = v_{n,i} \left(1-\frac{\rho}{2}\widetilde h_i(z^n)\right). $$

For $0\le u\le1$ and $\rho\le1/2$,
$$ \log(1-\rho u)\ge-\rho u-\rho^2, \qquad \log(1-\rho u)\le-\rho u. $$
Comparing the total weight with each individual weight after $K$ iterations yields
$$ \min_i\frac1K\sum_{n=1}^K\widetilde h_i(z^n) \ge \frac1K\sum_{n=1}^K \sum_iw_{n,i}\widetilde h_i(z^n) - \frac{2\log J}{\rho K} -2\rho. $$
Replacing rounded payoffs by true payoffs costs at most $2\sigma$.

Choose
$$ K\ge \frac{64J}{t^2}. $$
Since $\log J\le J$, the total regret is at most
$$ \frac t4+\frac t4+\frac t4<t. $$
The empirical distribution on $z^1,\ldots,z^K$, with probabilities $1/K$, has the stated guarantee.

All updates are rational. Because rounded payoffs use a fixed dyadic mesh, every multiplicative factor has a fixed polynomial bit bound. Each unnormalized weight is a product of at most $K$ such factors, so its bit length is polynomial. This avoids recursive growth of payoff precision with weight precision.

The circuit evaluation argument in Proposition 3 computes the required payoff approximations in polynomial time. $\square$

6. An unconditional polynomial-time weaker guarantee

Theorem 8

For every fixed $m$, there is an algorithm, independent of $N$, running in time polynomial in $m,\tau,L,T,1/\epsilon$ and outputting a finitely represented strategy such that
$$ V(Q)\ge\alpha^3V^*-\epsilon. $$

Proof

Set
$$ t=\frac{\epsilon}{64} $$
and construct the cells from Section 4. Write $O_i=O(\ell_i)$.

For each lower corner $\ell_i$, apply Proposition 3 with tolerance $t/2$. Its full-budget profile has value $v_i$ satisfying
$$ \kappa\le v_i\le O_i, \qquad v_i\ge(\alpha-t/2)O_i. $$
Compute a rational approximation $\widetilde v_i$ with error at most $t\kappa/4$, and define
$$ d_i= \max\left\{ \kappa,\, \widetilde v_i-\frac{t\kappa}{4} \right\}. $$
Then
$$ \kappa\le d_i\le O_i, \qquad d_i\ge(\alpha-t)O_i. $$
For the lower bound, the downward estimate loses at most $t\kappa/2$, and $O_i\ge\kappa$.

Put $q=\alpha-t$. The finite payoffs $g(z,\ell_i)/d_i$ are bounded by $1/q<2$, so Proposition 7 applies.

For every $Q$, the benchmark bound gives
$$ d_i\le O_i\le\frac{b(\ell_i)}{\alpha}, $$
and hence
$$ \min_i\frac{\mathbb E_Qg(z,\ell_i)}{d_i} \ge \alpha \min_i\frac{\mathbb E_Qg(z,\ell_i)}{b(\ell_i)} \ge \alpha V(Q). $$
Consequently,
$$ W_d^*\ge\alpha V^*. $$
The finite-game output satisfies
$$ \min_i\frac{\mathbb E_Qg(z,\ell_i)}{d_i} \ge q\alpha V^*-t. $$

Now take arbitrary $\theta$ in cell $i$. Section 4 gives
$$ b(\theta) \le O(\theta) \le A O_i+\frac{\kappa t}{2} \le \left(\frac A q+\frac t2\right)d_i. $$
Monotonicity gives $\mathbb E_Qg(z,\theta)\ge\mathbb E_Qg(z,\ell_i)$. Therefore
$$ V(Q) \ge \frac{q}{A+qt/2} \min_i\frac{\mathbb E_Qg(z,\ell_i)}{d_i} \ge \frac{\alpha q^2}{A+qt/2}V^*-t. $$
Here the coefficient multiplying the final error is at most one.

Because $A\le1+t/2$ and $q<1$,
$$ A+qt/2\le1+t. $$
Furthermore,
$$ \frac{\alpha(\alpha-t)^2}{1+t} \ge \alpha^3-3t. $$
Indeed, the difference from $\alpha^3$ is at most
$$ (\alpha^3+2\alpha^2)t\le3t. $$
Using $V^*<2$, we conclude
$$ V(Q) \ge \alpha^3V^*-7t \ge \alpha^3V^*-\epsilon. $$

The grid has polynomially many cells for fixed $m$. Every subsequent step uses polynomial-time numerator oracles and rational arithmetic. The output is an explicit polynomial-length list of feasible rational profiles with rational probabilities. No population size is used by the algorithm. $\square$

7. A sufficient missing oracle for the requested factor

The following is a conditional result, not an assertion that its oracle exists.

Theorem 9

Suppose that, for the rational cells constructed in Section 4, an algorithm can compute rational numbers $\widehat\beta_i$ satisfying
$$ \beta_i\le\widehat\beta_i\le(1+t)\beta_i, \qquad \beta_i=\sup_{\theta\text{ in cell }i}b(\theta), $$
in time polynomial in the input length and $1/t$.

Then the requested guarantee
$$ V(Q)\ge\alpha V^*-\epsilon $$
is polynomial-time achievable for fixed $m$.

Proof

Again take $t=\epsilon/64$. Define the rational finite game
$$ \widehat W(Q) = \min_i \frac{\mathbb E_Qg(z,\ell_i)}{\widehat\beta_i}. $$
Its payoffs are bounded by $1/\alpha<2$, since
$$ \widehat\beta_i\ge\beta_i\ge b(\ell_i)\ge\alpha O(\ell_i). $$

For every $Q$, Proposition 6 and the oracle bounds give
$$ \frac{W(Q)}{1+t} \le \widehat W(Q) \le W(Q) \le V(Q). $$
Thus
$$ \widehat W^* \ge \frac{V^*-2t}{1+t}. $$

Applying Proposition 7,
$$ V(Q) \ge \widehat W(Q) \ge \frac{\alpha-t}{1+t}(V^*-2t)-t. $$
Since
$$ \frac{\alpha-t}{1+t}\ge\alpha-2t, \qquad \frac{\alpha-t}{1+t}\le1, \qquad V^*<2, $$
the right-hand side is at least
$$ \alpha V^*-7t \ge \alpha V^*-\epsilon. $$
$\square$

This isolates a specific sufficient computational step. Approximating $b$ at the cell corners is not the oracle hypothesis: the required numbers approximate its supremum throughout each cell.

For comparison, the finite-network result in [Wilder et al., Section 5](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p1305.pdf) obtains the requested greedy-normalized factor through parameter discretization. The argument here supplies a polynomial discretization for the limiting mass model, but leaves the cellwise greedy coefficients uncomputed.

As a fully resolved special case, if $P$ is a singleton, then
$$ V^*=\frac{O(\theta)}{b(\theta)}. $$
Proposition 3 directly produces a single rational profile with the requested guarantee, without evaluating $b$.

8. What remains open

The unconditional theorem has factor $\alpha^3$, rather than the requested $\alpha$. It therefore does not settle the task.

The new discretization removes two potential obstacles: an exponentially large additive parameter grid and dependence on inverse seed or type masses. For the requested factor, a sufficient remaining step is polynomial-time approximation of the cellwise greedy suprema. No such algorithm is established here.

No hardness reduction is established either. In particular, neither the need for this oracle nor possible irregularity of the benchmark proves NP-hardness.

⟨structured verdict parsed — rendered above⟩

Verification report

Result: partial, with sound substantive progress and minor expositional gaps. The output establishes a weaker polynomial-time approximation and a conditional route to the requested approximation. It does not resolve the polynomial-time versus NP-hardness question in USER_TASK, and explicitly acknowledges this.

Write $\alpha=1-1/e$. I found no central false step in the arguments for the unconditional $\alpha^3$ guarantee or the conditional $\alpha$ guarantee.

1. Limiting diffusion formula

Proposition 1 is sound in substance.

The geometric waiting-time representation matches the specified repeated-attempt process: an edge’s waiting time starts after its source becomes active. Activation by round $T$ is determined by paths with total waiting time at most $T$, so only graph neighborhoods through depth $T$ matter.

The incoming branching-tree means $\mu_r\lambda_{rs}$ have the correct orientation. The displayed recursion correctly includes:

• certain activation of seeds at time zero;
• independent incoming subtrees;
• activation delays of at least one round;
• infinite waiting time when the propagation probability is zero;
• deterministic waiting time one when it is one.

The branching-process domination is valid. In particular, the inequality
$$ -\log(1-p)\le 2p $$
is used only after requiring $p\le 1/2$. Summing incoming edge probabilities gives the claimed bound $2C$.

The generation-moment calculation and the resulting total-size bounds are correct. Their exponential dependence on $T$ is acceptable here: this proposition proves convergence for each fixed input, rather than supplying a polynomial population-size threshold.

The seed-coupling estimate is uniform over allocations because sampling is without replacement within each type, and every type has positive mass. Common propagation uniforms make the coupling uniform over $\theta$.

Minor issue: the graph-coupling step invokes “binomial-to-Poisson approximation” without stating the approximation theorem or an explicit bound for a truncated exploration. The hypotheses are present and the missing detail is routine for fixed truncation size, but the theorem invocation should be made precise.

The final passage from $k/N$ to $\lfloor Nz\rfloor/N$ is justified by continuity of the displayed finite-time recursion.

2. Derivatives, greedy benchmark, and measurability

Proposition 2 is correct, subject to one finite-population edge-case qualification.

The conditional inactivity product gives nonnegative first derivatives and nonpositive mixed and pure second derivatives. The moment bounds control their absolute values, including at capacity boundaries, and justify taking expectations of the derivatives.

The lower derivative estimate is valid: differentiating the recursion gives the direct contribution
$$ \partial_r x_r(T)\ge e^{-H_r(T)}, $$
and the waiting-time probabilities have total mass at most one, giving $H_r(T)\le C$.

The finite-population coverage representation is appropriate for this propagation model. For fixed graph and waiting times, every target contributes an indicator that its reverse reachable set intersects the seed set. Thus monotonicity and submodularity hold, and expectation preserves them.

Exchangeability within types makes the prescribed type-wise greedy rule an individual-agent greedy rule. The stated greedy recurrence consequently establishes
$$ \alpha O(\theta)\le b(\theta)\le O(\theta). $$
Uniform convergence and flooring a continuous maximizer justify the passage from finite-population optima to $O(\theta)$.

Minor issue: the finite greedy inequality contains $1/K_N$, although $K_N=\lfloor N\kappa\rfloor$ can equal zero for small admissible populations. The displayed inequality must be restricted to sufficiently large $N$ with $K_N\ge1$. This does not affect any limiting conclusion.

The bounds $b(\theta)\ge\kappa$ and $V^*\le1/\alpha$ are correct. The Borel measurability argument also works: finite greedy allocations are selected by finitely many comparisons of continuous functions, and the population limsup is countable.

3. Weighted numerator optimization

Proposition 3 is correct.

The coordinate-selection error is controlled by the positive derivative lower bound. The estimates for accepted endpoints and rejected bisection endpoints have sufficient slack; the constants do not require exact derivative evaluation.

The argument that a bisection-ending step has positive length is valid. The derivative drop on such a step, combined with coordinatewise decrease of all derivatives as the profile increases, bounds the number of steps by a polynomial in
$$ \tau,\quad 1/\eta,\quad \log U,\quad \log(1/\ell). $$
Since $\log U$ is polynomial in $L$ and $T$, exponentially large numerical values of $U$ do not cause exponentially many steps.

The diminishing-returns inequality on the full capacity box is valid even when $z\vee y$ exceeds the seed budget. The proof uses that point only to bound the objective gap; it does not claim that point is feasible for optimization.

Exhausted coordinates contribute nothing to that gap bound. The resulting differential inequality and integration give the claimed approximation factor.

The numerical implementation is also adequately controlled:

• the circuit has polynomially many gates;
• exponential arguments remain in a fixed bounded interval;
• intermediate magnitudes have polynomial logarithmic size;
• the accumulated-error estimate requires only polynomial precision;
• the bisection count and rational endpoint bit lengths remain polynomial.

The extension to nonzero nonnegative rational linear combinations is valid through normalization.

4. Sensitivity bounds

Propositions 4 and 5 are correct.

For Proposition 4, absolute-round attempt bits give a valid monotone representation. A successful activation has a certificate containing at most $T$ successful bits. Every successful pivotal bit must belong to every successful certificate, so the pivotal-bit count is at most $T$. The derivative identity therefore supports the displayed logarithmic sensitivity bound.

Zero coordinates are handled correctly by keeping them fixed during interpolation. Endpoints cause no difficulty because finite-population activation probabilities are polynomials in the attempt probabilities.

Minor wording issue: “Monotonicity of the derivatives” should specify nonnegativity of the first parameter derivatives. The interpolation requires nonnegative derivatives, not an additional assertion that those derivatives increase with the parameters.

For Proposition 5, activation paths can have distinct vertices and strictly increasing attempt rounds. The path count, graph-edge probability bound, and union bound over differing attempt bits are consistent. The identity
$$ \sum_{\ell=1}^T \ell\binom T\ell C^\ell = TC(1+C)^{T-1} $$
is correct, as is its upper bound by $B$.

The factor equal to total seed mass survives the population limit and is used correctly later.

5. Parameter cells and envelope game

Section 4 and Proposition 6 are correct.

The clipped intervals preserve the stated alternatives: a coordinate interval either lies below the cutoff or has multiplicatively close endpoints.

The combined sensitivity estimate correctly increases the coordinates above the cutoff multiplicatively and handles the remaining coordinates additively. Its additive error is proportional to $\kappa$, which cancels against denominators bounded below by $\kappa$.

The estimate
$$ (1+\delta)^T\le e^{t/4}\le1+t/2 $$
holds for the stated range $0<t<1$.

The number of cells is polynomial for each fixed $m$. The rational knot construction has polynomial bit length because both the number of multiplications and the bit length of each factor are polynomial.

Proposition 6 correctly avoids assuming continuity or attainment of the greedy benchmark. A sequence approaching the cell supremum is enough because the numerator bound holds uniformly throughout the cell. The estimate
$$ W(Q)\le V(Q)\le W(Q)+2t $$
has the correct inequality directions and constants.

However, these cell coefficients are mathematical definitions, not algorithmically supplied data. Proposition 6 alone does not provide the requested algorithm.

6. Finite scenario optimization

Proposition 7 is correct.

The weighted numerator oracle applies after normalizing the rational coefficients involving $1/d_i$.

The best-response comparison with $W_d^*$ does not require an unproved minimax theorem or existence of an optimal distribution. The displayed inequality holds for every distribution, and hence for the supremum.

The multiplicative weight update stays positive. The logarithmic estimates give the stated regret bound, and the two payoff-rounding errors are properly included. With the chosen iteration count, the total additive loss is less than $t$.

Using a fixed dyadic payoff mesh prevents uncontrolled recursive growth of weight precision. The empirical strategy has rational probabilities and feasible rational profiles.

7. Unconditional weaker guarantee

Theorem 8 is established by the preceding arguments.

The downward-rounded denominator satisfies
$$ \kappa\le d_i\le O_i, \qquad d_i\ge(\alpha-t)O_i. $$
The rounding loss is accounted for correctly.

The comparison
$$ W_d^*\ge\alpha V^* $$
has the correct direction: restricting the adversary to lower corners can only increase the relevant infimum, while replacing the benchmark by $d_i$ incurs the stated factor.

The transfer back to all parameters uses the upper bound on $O(\theta)$, rather than any unstated regularity of $b(\theta)$. The resulting coefficient is
$$ \frac{\alpha(\alpha-t)^2}{A+(\alpha-t)t/2}. $$
The subsequent estimates justify the claimed final bound
$$ V(Q)\ge\alpha^3V^*-\epsilon. $$

This is genuine polynomial-time progress independent of $N$. It does not establish the requested guarantee: the difference between $\alpha$ and $\alpha^3$ does not disappear as $\epsilon$ tends to zero.

8. Conditional requested guarantee and singleton case

Theorem 9 is correct as a conditional theorem.

Its hypothesis concerns upper approximations to the benchmark supremum throughout each cell. It does not follow from evaluating the benchmark at the corners.

The comparisons between $\widehat W$, $W$, and $V$ are valid. The finite-game approximation and the bound $V^*<2$ yield the stated additive loss and hence the requested guarantee under the oracle hypothesis.

No implementation or hardness result for that oracle is established. Its assumed availability cannot be counted as an unconditional solution.

The singleton identity
$$ V^*=\frac{O(\theta)}{b(\theta)} $$
is correct.

Minor issue: the singleton paragraph omits the choice of optimization tolerance needed to turn Proposition 3’s multiplicative loss into additive error at most $\epsilon$. It should explicitly require a tolerance satisfying $\eta V^*\le\epsilon$, using the already established uniform bound on $V^*$.

The comparison with the finite-network result is accurately presented as context, rather than as a theorem applied to the limiting model. Section 5 of the cited paper states the corresponding finite-network approximation result. [Wilder et al.](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p1305.pdf)

9. Actionable feedback

The write-up needs only minor clarification to make its partial results fully explicit:

• State the precise binomial-to-Poisson approximation used for truncated graph explorations and explain its uniform applicability.
• Restrict the displayed finite greedy recurrence to $K_N\ge1$.
• Replace the ambiguous derivative-monotonicity wording with the exact nonnegativity property used.
• Specify the tolerance needed for the singleton guarantee.

Resolving USER_TASK requires additional mathematics: either an unconditional algorithm achieving the requested factor, including all benchmark computations it needs, or a hardness proof for that guarantee. The output supplies neither. The missing cellwise oracle is a sufficient route, not a proved necessary obstacle.

⟨structured verdict parsed — rendered above⟩