Answer: —
Theorem 3.1 — class: algorithmic
Given a finite set of types \(T\) with rational shares \(\mu_t\), a block-structured cascade model with a finite shared environment \(\Omega\) and rational prior, a seeding budget \(\beta\), and \(q\) rounds, determine the infimum ratio of expected adopted mass under adaptive greedy to that under non-adaptive greedy. In each round, each policy chooses a type-mass vector \(\Delta x\geq 0\) with \(\sum_t\Delta x_t\leq\beta/q\) and \(x+\Delta x\leq\mu\), maximizing expected marginal adoption; adaptive greedy conditions on the observed type-level adoption profile under full feedback, or the type-level exposure profile under myopic feedback, while non-adaptive greedy uses the prior.
A society is given by its support: the list of \(\tau\) types \(T\) with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Define a block cascade by a simple directed graph \(G=(T,E)\) and an explicitly listed finite environment \(\Omega\) with positive rational prior \(p\). Each \(\omega\) specifies live edges \(E_\omega\subseteq E\); incoming live-edge sets at distinct types are independent under \(p\). Sample \(\omega\) once for the entire seeding process.
A type block has coordinates \(z\in[0,1]\) with mass measure \(\mu_t\,dz\). Seeding mass \(x_t\) seeds its prefix \(z\leq x_t/\mu_t\); a live edge transmits adoption between equal coordinates. Thus final adopted mass at type \(v\) is \(a_v(x,\omega)=\mu_v\max_{t:\,t\leadsto_\omega v}x_t/\mu_t\), allowing paths of length zero, and total adoption is \(A(x,\omega)=\sum_v a_v(x,\omega)\).
Full feedback reveals the vector \(a(x,\omega)\) after diffusion finishes. Myopic feedback reveals \(e(x,\omega)\), defined by the same formula using only paths of length at most one. Policies retain the complete history of actions and feedback; neither feedback directly reveals \(\omega\).
Let \(q\geq1\) be an integer and \(0<\beta\leq1\) a rational budget. Starting at \(x=0\), each greedy policy performs \(q\) rounds, choosing a real vector \(\Delta x\geq0\) with \(\sum_t\Delta x_t\leq\beta/q\) and \(x+\Delta x\leq\mu\) that maximizes the expected marginal \(A(x+\Delta x,\omega)-A(x,\omega)\). Adaptive greedy uses the posterior given its history; non-adaptive greedy always uses the prior. Both break ties by the lexicographically greatest increment in a fixed type order.
Write \(X_b^g(\omega)\) for adaptive greedy's final vector under feedback \(b\in\{\mathrm{full},\mathrm{myopic}\}\), and \(x^g\) for non-adaptive greedy's final vector. Any running times are measured in \(m=|E|\), \(\tau\), \(|\Omega|\), \(q\), and total input bit length \(L\).
What is the sharp universal lower bound \(\gamma_b=\inf_{\mathcal I}\mathbb E_\omega[A(X_b^g(\omega),\omega)]/\mathbb E_\omega[A(x^g,\omega)]\) for each feedback model \(b\), where \(\mathcal I\) ranges over all admissible instances, including all budgets and round counts?
For finite-agent triggering cascades, the corresponding infimum is exactly \(1-1/e\) under both feedback models, including the independent cascade and linear threshold subclasses; adaptive greedy also guarantees \(1-1/e\) of the optimal non-adaptive influence. [Chen–Peng–Schoenebeck–Tao](https://arxiv.org/pdf/1911.08164).
No result settling this specific mass-cascade ratio was located in the literature search.
The sharp infima for unrestricted instances remain unresolved. The following results are proved here for both feedback models.
$$
1-\left(1-\frac{2}{q}\right)\left(1-\frac1q\right)^{q-2}
$$
for $q\geq2$.
The upper-bound construction for the second result also establishes
$$
0\leq\gamma_{\mathrm{full}}\leq1-\frac1e,
\qquad
0\leq\gamma_{\mathrm{myopic}}\leq1-\frac1e
$$
for the unrestricted problem. The lower bounds proved below have additional hypotheses.
Set
$$
c=\frac{\beta}{q},
\qquad
F(x)=\mathbb E_\omega[A(x,\omega)].
$$
For an environment $\omega$, write $R_\omega(t)$ for the types reachable from $t$, including $t$.
For each destination $v$, adoption is its mass multiplied by a maximum of linear functions:
$$
a_v(x,\omega)
=
\mu_v\max_{t:\,v\in R_\omega(t)}\frac{x_t}{\mu_t}.
$$
Consequently, $A(x,\omega)$ is continuous, coordinatewise nondecreasing, and convex in $x$. These properties also hold for every posterior expectation of $A$.
Every round has a compact feasible increment polytope. Its continuous objective therefore attains a maximum. Successively maximizing coordinates within the compact set of objective maximizers produces the unique prescribed lexicographically greatest maximizer.
The lexicographically greatest maximizer of a convex function over a polytope is a vertex.
Proof. Let $d$ be that maximizer, and express it as a convex combination of vertices:
$$
d=\sum_j\lambda_jv_j,
\qquad
\lambda_j>0,
\qquad
\sum_j\lambda_j=1.
$$
Convexity gives
$$
f(d)\leq\sum_j\lambda_jf(v_j)\leq f(d).
$$
Thus every $v_j$ in this combination is also an objective maximizer and is lexicographically at most $d$.
If some $v_j$ differs from $d$, let $\ell$ be the earliest coordinate at which any of these vertices differs from $d$. All preceding coordinates agree with $d$. At coordinate $\ell$, every differing vertex must have a smaller coordinate, by lexicographic maximality. Their weighted average cannot equal $d_\ell$, a contradiction. Hence every $v_j=d$, so $d$ is a vertex. $\square$
Both greedy policies spend exactly $c$ in every round. Before round $i$, remaining capacity is at least
$$
1-(i-1)c\geq c.
$$
If an optimal increment spent less than $c$, one could increase a coordinate while remaining feasible. Monotonicity would preserve objective optimality, while the increment would become lexicographically greater. This contradicts the tie rule.
A vertex of
$$
\left\{d:0\leq d_t\leq u_t,\ \sum_t d_t\leq c\right\}
$$
has at most one coordinate strictly between $0$ and $u_t$. Indeed, two such coordinates could be perturbed in opposite directions by a sufficiently small amount, expressing the point as the midpoint of two distinct feasible points.
Thus a greedy round fills some remaining type capacities and has at most one additional partial coordinate. The same vertex statement applies to the global non-adaptive optimization polytope
$$
P_\beta=\left\{y:0\leq y\leq\mu,\ \sum_t y_t\leq\beta\right\}.
$$
Finally, every feasible adoption value is at most $1$, and paths of length zero give
$$
A(x,\omega)\geq\sum_t x_t.
$$
Both final greedy vectors therefore have adoption at least $\beta>0$, so their ratio is well-defined.
For a subset $B\subseteq T$, define its full seeding vector by
$$
s^B_t=
\begin{cases}
\mu_t,&t\in B,\\
0,&t\notin B.
\end{cases}
$$
Write $x\vee s^B$ for coordinatewise maximum.
Let $y$ be a fixed feasible non-adaptive vector. Suppose there is a set $S\subseteq T$ such that
$$
y\leq s^S,
$$
and a partition
$$
S=B_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}B_r
$$
satisfying
$$
\sum_{t\in B_j}\mu_t\leq c
\qquad
\text{for every }j.
$$
Then adaptive greedy, under either feedback model, satisfies
$$
\mathbb E[A(X_b^g,\omega)]
\geq
\left[1-\left(1-\frac1r\right)^q\right]F(y).
$$
Proof. Fix a feasible $x$ and an environment $\omega$. Let
$$
\rho_v=\frac{a_v(x,\omega)}{\mu_v}.
$$
For each block $B_j$, define $C_{jv}$ to be $1$ if some type in $B_j$ reaches $v$, and $0$ otherwise. Fully seeding $B_j$ raises adoption at a reached destination to its full mass. Therefore
$$
A(x\vee s^{B_j},\omega)-A(x,\omega)
=
\sum_v\mu_v(1-\rho_v)C_{jv}.
$$
Since $y\leq s^S$, a destination adopted under $y$ must be reachable from some type in $S$. If $\sum_jC_{jv}\geq1$, then
$$
\rho_v+(1-\rho_v)\sum_jC_{jv}\geq1.
$$
If $\sum_jC_{jv}=0$, its adoption under $y$ is zero. Summing these destination-wise inequalities proves
$$
A(y,\omega)
\leq
A(x,\omega)
+
\sum_{j=1}^r
\left[A(x\vee s^{B_j},\omega)-A(x,\omega)\right].
$$
After any adaptive history, each operation $x\mapsto x\vee s^{B_j}$ is an available comparison action: its increment is nonnegative, respects capacities, and costs at most
$$
\sum_{t\in B_j}\mu_t\leq c.
$$
Conditional greedy optimality and the preceding inequality consequently imply
$$
\mathbb E[A(X_{i+1},\omega)-A(X_i,\omega)\mid H_i]
\geq
\frac{
\mathbb E[A(y,\omega)-A(X_i,\omega)\mid H_i]
}{r}.
$$
Here $H_i$ denotes the complete history after $i$ rounds. The argument does not require $A(X_i,\omega)$ to be observed.
Put
$$
a_i=\mathbb E[A(X_i,\omega)].
$$
Taking expectations gives
$$
a_{i+1}\geq
\left(1-\frac1r\right)a_i+\frac{F(y)}r.
$$
Starting from $a_0=0$ and iterating proves the claim. $\square$
This lemma uses no independence assumption beyond the existence of the given probability distribution. In particular, it applies to every admissible instance in the task.
Suppose
$$
\max_t\mu_t\leq c=\frac{\beta}{q}.
$$
Let
$$
F^*=\max_{y\in P_\beta}F(y)
$$
be the optimal non-adaptive value. Then, for either feedback model,
$$
\mathbb E[A(X_b^g,\omega)]
\geq
\left[1-\left(1-\frac1{2q}\right)^q\right]F^*
\geq
(1-e^{-1/2})F^*.
$$
The same lower bounds therefore hold for the ratio against non-adaptive greedy.
Proof. Choose the lexicographically greatest maximizer $y^*$ of $F$ over $P_\beta$. Lemma 1 makes it a vertex, so it fully seeds a set $S$ and has at most one additional partially seeded type $t$.
The fully seeded types have total mass at most $\beta=qc$. We partition them into groups of mass at most $c$ by the following procedure: process them in any order, adding types to the current group until the next type would exceed $c$, then start a new group. Each type fits because $\mu_t\leq c$.
Let $W_j$ denote the mass of group $j$. Consecutive groups satisfy
$$
W_j+W_{j+1}>c:
$$
the first type in group $j+1$ did not fit in group $j$.
There cannot be $2q$ or more groups. Otherwise, pairing the first $2q$ consecutive groups would give
$$
\sum_jW_j
\geq
\sum_{\ell=1}^q(W_{2\ell-1}+W_{2\ell})
>
qc,
$$
contrary to the mass bound on $S$. Hence $S$ requires at most $2q-1$ groups.
If $y^*$ has a partial type, add that type as one further singleton group. Its full mass is at most $c$. We have thus found a full seeding vector dominating $y^*$, partitioned into at most $2q$ round-feasible blocks.
Lemma 2, with empty blocks added if necessary, yields
$$
\mathbb E[A(X_b^g,\omega)]
\geq
\left[1-\left(1-\frac1{2q}\right)^q\right]F^*.
$$
Finally, $1-u\leq e^{-u}$ gives
$$
\left(1-\frac1{2q}\right)^q\leq e^{-1/2}.
$$
Since $F(x^g)\leq F^*$, the ratio assertion follows. $\square$
This covers a regime where capacities can bind repeatedly and masses need not be equal. Its hypothesis does not cover types whose mass exceeds a round’s allowance.
Assume now that all masses equal
$$
\mu_t=\frac1\tau,
$$
and that, for an integer $K\geq1$,
$$
c=\frac K\tau,
\qquad
\beta=\frac{qK}{\tau}\leq1.
$$
For either feedback model,
$$
\mathbb E[A(X_b^g,\omega)]
\geq
\left[1-\left(1-\frac1q\right)^q\right]F^*.
$$
Against non-adaptive greedy, for $q\geq2$,
$$
\frac{\mathbb E[A(X_b^g,\omega)]}{F(x^g)}
\geq
1-\left(1-\frac2q\right)\left(1-\frac1q\right)^{q-2}.
$$
For $q=1$, the ratio is $1$.
Proof. We first establish that each round fully seeds exactly $K$ previously unseeded types.
Inductively, suppose the current vector has coordinates either $0$ or $1/\tau$. By Lemma 1, the chosen increment is a vertex and has at most one partial coordinate. It spends exactly $K/\tau$. All full increment coordinates contribute integer multiples of $1/\tau$, so a single strictly partial coordinate cannot complete that total. Thus there is no partial coordinate, proving the induction.
Likewise, a lexicographically greatest global optimizer over $P_\beta$ spends exactly $qK/\tau$ and is a vertex. It therefore fully seeds a set of exactly $qK$ types. Partitioning that set into $q$ sets of $K$ types and applying Lemma 2 proves the first bound.
For the stronger comparison, define the realized whole-block coverage function
$$
f_\omega(S)=A(s^S,\omega).
$$
It is monotone and submodular: a destination contributes its mass precisely when at least one member of $S$ reaches it. In particular, adding a fixed set of seeds has no larger marginal at a larger base set.
Let $N_i$ be the non-adaptive seed set after $i$ rounds, and set
$$
g_i=\mathbb E[f_\omega(N_i)-f_\omega(N_{i-1})].
$$
These gains are nonincreasing. To verify this, let $C_{i+1}=N_{i+1}\setminus N_i$. Submodularity and prior greedy optimality give
$$
\begin{aligned}
g_{i+1}
&\leq
\mathbb E[f_\omega(N_{i-1}\cup C_{i+1})-f_\omega(N_{i-1})]\\
&\leq g_i.
\end{aligned}
$$
The comparison batch $C_{i+1}$ is feasible at round $i$, since it consists of $K$ types not yet seeded there. Consequently, for $q\geq2$,
$$
F(s^{N_2})=g_1+g_2
\geq
\frac2q\sum_{i=1}^qg_i
=
\frac2qF(x^g).
$$
Both policies take the same first action. After any first-round history, adaptive greedy can choose the fixed second non-adaptive batch. Conditional optimality and averaging therefore give
$$
a_2\geq F(s^{N_2})\geq\frac2qF(x^g),
$$
where $a_i$ denotes adaptive expected adoption after $i$ rounds.
Partition the fixed final set $N_q$ into its $q$ non-adaptive batches. The proof of Lemma 2 gives, at every subsequent round,
$$
a_{i+1}\geq
\left(1-\frac1q\right)a_i+\frac{F(x^g)}q.
$$
Iterating from the displayed bound on $a_2$ yields
$$
a_q\geq
\left[
1-\left(1-\frac2q\right)\left(1-\frac1q\right)^{q-2}
\right]F(x^g).
$$
For one round, both policies use the same prior and tie rule and hence coincide. $\square$
We now construct admissible aligned equal-mass instances whose ratios converge to $1-1/e$. This proves sharpness within the class of Section 4 and supplies the unrestricted upper bound.
Let $k$ tend to infinity through integers, and put
$$
M=k^4,\qquad H=k^3,\qquad \varepsilon=\frac1k.
$$
Define
$$
Q_1=M-H+1,
$$
and, for $i=2,\ldots,k$,
$$
h_i=\left\lfloor\frac{Q_{i-1}}k\right\rfloor+1,
\qquad
Q_i=Q_{i-1}-h_i.
$$
There are $k$ columns of leaves. In the first row, column $1$ has $H-1$ leaves, while every other column has $H$ leaves. In row $i\geq2$, every column has $h_i$ leaves. Finally, the residual part of column $1$ has $Q_k$ leaves, and every other residual column part has $Q_k-1$ leaves.
Each column has exactly $M$ leaves. Indeed,
$$
\sum_{i=2}^kh_i=Q_1-Q_k,
$$
so the total for column $1$ is
$$
H-1+(Q_1-Q_k)+Q_k=M,
$$
and for another column it is
$$
H+(Q_1-Q_k)+(Q_k-1)=M.
$$
Let $a=1-1/k$. Write
$$
h_i=\frac{Q_{i-1}}k+\theta_i,
\qquad 0<\theta_i\leq1.
$$
Solving the recurrence gives
$$
Q_k
=
a^kM+a^{k-1}
-
\sum_{i=2}^ka^{k-i}\theta_i.
$$
Hence
$$
\left|\frac{Q_k}{M}-a^k\right|
\leq\frac{k+1}{M},
\qquad
\frac{Q_k}{M}\longrightarrow e^{-1}.
$$
The analogous formula for each $Q_i$, with $i\leq k$, shows that all $Q_i>1$ for sufficiently large $k$. Thus all listed leaf counts are positive.
Also,
$$
h_2\leq H-\frac Hk+\frac1k+1<H
$$
for sufficiently large $k$. Since the positive $h_i$ make the $Q_i$ decrease, the sequence $h_i$ is nonincreasing. In particular,
$$
kh_i<M
\qquad(i\geq2).
$$
Introduce sources
$$
s,u_1,\ldots,u_k,v_1,\ldots,v_k,
$$
the column leaves just described, $2M$ private leaves, and one gate leaf $t$.
The number of these types is
$$
N_0=(k+2)M+2k+2.
$$
Choose a power of two $N\geq N_0$, and add $N-N_0$ isolated types. Give every type mass $1/N$. These masses are positive dyadic rationals and sum to $1$.
Set
$$
q=k+1,\qquad c=\frac1N,\qquad\beta=\frac{k+1}{N}.
$$
Thus each round fully seeds exactly one type.
The deterministically live edges are:
The gate has two incoming edges, $s\to t$ and $v_1\to t$. There are two environments:
Only the gate’s incoming live-edge set is random. All other incoming sets are deterministic, so independence across distinct target types holds. Both environment probabilities are positive rational numbers.
Every edge runs from a source to a leaf. Therefore all paths of positive length have length one, and full and myopic feedback coincide.
Choose the type order with
$$
v_1,v_2,\ldots,v_k
$$
preceding all the $u_j$, and with the $v_i$ in their displayed order. Other positions can be arbitrary.
We compare gains in units of the common mass $1/N$. An unseeded source contributes its own unit in addition to its newly adopted leaves. Directly seeding a leaf or isolated type has gain at most one unit.
Initially, the leaf gains are
$$
\begin{aligned}
s &: 2M+\varepsilon,\\
u_j &: M,\\
v_1 &: M-1+(1-\varepsilon)=M-\varepsilon,\\
v_i &: kh_i<M\qquad(i\geq2).
\end{aligned}
$$
Thus both policies first seed $s$.
After any number of column sources have been seeded, every remaining column source still has leaf gain $M$. The prior marginal gate contribution to $v_1$ is $1-\varepsilon$, and its remaining row contains at most $M-1$ leaves. Every other row source has fewer than $M$ leaves. Non-adaptive greedy therefore seeds all $k$ column sources.
Its expected adopted mass is
$$
F(x^g)
=
\frac{2M+kM+\varepsilon+(k+1)}N.
$$
The feedback after seeding $s$ identifies the environment.
If the gate adopts, its incoming edge from $v_1$ is absent. All row sources have leaf gain less than $M$, so adaptive greedy seeds all column sources.
If the gate does not adopt, $v_1\to t$ is known to be live. The leaf gain of $v_1$ is then
$$
M-1+1=M.
$$
It ties with the column sources and wins by the specified type order.
Suppose subsequently that $v_1,\ldots,v_{i-1}$ have been seeded, with $i\geq2$. Column $1$ has $Q_{i-1}$ unadopted leaves, and every other column has $Q_{i-1}-1$. The best column-source leaf gain is therefore $Q_{i-1}$. However,
$$
kh_i
=
k\left(\left\lfloor\frac{Q_{i-1}}k\right\rfloor+1\right)
>
Q_{i-1}.
$$
Thus a row source wins. The row sizes are nonincreasing, and the tie order selects $v_i$. Inductively, adaptive greedy seeds every row source in this branch.
The total number of row leaves is
$$
B_k
=
kM-\left[Q_k+(k-1)(Q_k-1)\right]
=
kM-kQ_k+k-1.
$$
The gate is adopted in both adaptive branches. Consequently,
$$
\mathbb E[A(X_b^g,\omega)]
=
\frac{2M+1+(1-\varepsilon)B_k+\varepsilon kM+(k+1)}N
$$
for both feedback models.
The ratio is
$$
\rho_k
=
\frac{2M+1+(1-\varepsilon)(kM-kQ_k+k-1)+\varepsilon kM+(k+1)}
{2M+kM+\varepsilon+(k+1)}.
$$
Divide numerator and denominator by $kM$. Using
$$
\varepsilon\longrightarrow0,
\qquad
\frac{Q_k}{M}\longrightarrow e^{-1},
\qquad
\frac{2M}{kM}\longrightarrow0,
$$
we obtain
$$
\rho_k\longrightarrow1-e^{-1}.
$$
These instances belong to the aligned equal-mass class with $K=1$. Theorem 4 gives a lower bound of at least $1-1/e$ throughout that class, because
$$
\left(1-\frac1q\right)^q\leq e^{-1}.
$$
The construction proves the matching upper bound. Therefore the infimum within the aligned equal-mass class is exactly $1-1/e$ under each feedback model.
For unrestricted instances, the construction proves
$$
\gamma_b\leq1-\frac1e.
$$
Nonnegativity proves $\gamma_b\geq0$. The stronger lower bounds above apply to specified subclasses.
The principal unresolved case has types larger than $c=\beta/q$, which may be seeded partially over several rounds. Lemma 2 cannot directly compare against a fully seeded such type: that operation is infeasible in one round. Dividing it into smaller increments does not preserve the comparison inequality, because adoption is convex along a single type’s seeding coordinate.
Thus neither unrestricted sharp infimum is determined by this argument.
⟨structured verdict parsed — rendered above⟩
The output establishes correct partial results, but does not determine either unrestricted sharp infimum requested in USER_TASK. Its admission that the unrestricted problem remains unresolved is accurate.
The lower bounds under additional mass hypotheses, the sharper finite-round comparison, and the construction approaching $1-1/e$ are sound. I found no false central step. There is one minor domain omission in Lemma 2.
Adoption is continuous, monotone, and convex: correct. For fixed $\omega$ and destination $v$, the reachability set is fixed and nonempty because it includes $v$. Thus
$$
a_v(x,\omega)=\mu_v\max_{t:\,v\in R_\omega(t)}\frac{x_t}{\mu_t}
$$
is a positive multiple of a maximum of finitely many linear functions. Summation and expectation preserve the stated properties. This also applies to a fixed posterior.
Existence and uniqueness under the tie rule: correct. Each feasible increment set is compact and nonempty. The objective is continuous, so its maximizer set is compact and nonempty. Successive coordinate maximization over that set defines a unique lexicographically greatest point.
Lemma 1: correct. The convexity inequalities force every vertex with positive weight in the representation of $d$ to attain the same maximum objective value. At the earliest coordinate where any such vertex differs from $d$, all preceding coordinates agree with $d$, and every differing coordinate must be smaller by lexicographic maximality. Their weighted average cannot equal the corresponding coordinate of $d$. This establishes that $d$ is a vertex.
Exact spending in each round: correct. Before round $i$, total remaining capacity is at least
$$
1-(i-1)c\geq c,
$$
using $qc=\beta\leq1$. An increment spending less than $c$ therefore leaves some coordinate that can be increased. Monotonicity, together with objective maximality, makes the increased increment another objective maximizer; its lexicographic improvement contradicts the tie rule.
At most one partial coordinate: correct. Two coordinates strictly between their respective bounds permit opposite perturbations preserving their sum and feasibility. Such a point cannot be a vertex. This argument applies to both the round polytope and the global optimization polytope.
Positive denominator: correct. Feasibility gives $A(x,\omega)\leq1$, while length-zero paths give
$$
A(x,\omega)\geq\sum_t x_t.
$$
Both policies spend total mass $\beta>0$, so the ratio is well-defined.
The whole-block marginal formula is correct. For feasible $x$, one has $0\leq\rho_v\leq1$. If a member of $B_j$ reaches $v$, fully seeding that member makes adoption at $v$ equal to $\mu_v$. Otherwise, the operation does not change adoption there. Hence
$$
A(x\vee s^{B_j},\omega)-A(x,\omega)
=
\sum_v\mu_v(1-\rho_v)C_{jv}.
$$
The comparison inequality is correct. If no member of $S$ reaches $v$, then $y\leq s^S$ implies adoption under $y$ at $v$ is zero. Otherwise,
$$
\rho_v+(1-\rho_v)\sum_j C_{jv}\geq1,
$$
which bounds the adoption fraction under $y$. Summing over destinations yields the displayed comparison.
Conditional greedy comparison is correct. Each operation $x\mapsto x\vee s^{B_j}$ costs at most the full mass of $B_j$, hence at most $c$. It is an admissible comparison action after every history. Conditional optimality therefore bounds the greedy marginal by the average of these comparison marginals.
The proof does not require the current total adoption to be observed. It uses conditional expectations given the complete history, which are valid under either feedback model.
The recurrence and its solution are correct, provided $r\geq1$. Since $y$ is fixed, the law of total expectation gives
$$
a_{i+1}\geq
\left(1-\frac1r\right)a_i+\frac{F(y)}r.
$$
Starting from $a_0=0$ gives the claimed bound.
Minor issue: Lemma 2 does not explicitly require $r\geq1$. Its hypotheses allow $y=0$ and $S=\varnothing$, for which an empty partition can have $r=0$, making the displayed expressions undefined. The minimum clarification is to state that the partition has a positive number of blocks, with empty blocks permitted. All subsequent applications already use positive block counts.
The statement that this lemma does not require independence is correct.
The optimizer structure is correct. Compactness gives a global maximizer, and Lemma 1 gives a vertex with fully seeded coordinates and at most one partial coordinate.
The grouping argument is correct. Under $\mu_t\leq c$, every processed type fits in an individual group. When a new group starts, its first type failed to fit in the preceding group, so
$$
W_j+W_{j+1}>c.
$$
If there were at least $2q$ groups, pairing the first $2q$ would force their total mass to exceed $qc=\beta$, contradicting feasibility.
Adding the possible partially seeded type as a singleton produces a full-block vector dominating the optimizer, with at most $2q$ feasible blocks. Padding with empty blocks permits application of Lemma 2 with exactly $2q$ blocks.
Both resulting bounds are correct:
$$
\mathbb E[A(X_b^g,\omega)]
\geq
\left[1-\left(1-\frac1{2q}\right)^q\right]F^*
\geq
(1-e^{-1/2})F^*.
$$
The exponential inequality is used within its valid range. Since $F(x^g)\leq F^*$, the comparison against non-adaptive greedy follows.
This theorem does not apply to arbitrary instances: its hypothesis excludes every type whose mass exceeds $c$.
Whole-type actions: correct. Assuming the current coordinates are either zero or $1/\tau$, each remaining positive capacity is $1/\tau$. A vertex has at most one partial increment coordinate, and exact spending is $K/\tau$. Full coordinates contribute integer multiples of $1/\tau$, so a single strictly partial coordinate cannot complete the required total.
The induction begins at zero and establishes that every round seeds exactly $K$ previously unseeded types.
The same reasoning applies to the global optimizer, with exact budget spending justified by the earlier monotonicity and lexicographic argument. It seeds exactly $qK$ types. Partitioning these into $q$ batches establishes the first bound.
Submodularity and decreasing non-adaptive gains: correct. For fixed $\omega$, each destination contributes its mass when the seed set intersects its set of reaching types. This is a coverage function, so adding a fixed batch has no greater marginal at a larger seed set.
The next non-adaptive batch consists of $K$ types still unseeded at the preceding round, so it is a feasible comparison there. Consequently,
$$
g_{i+1}\leq g_i.
$$
For a nonincreasing sequence of $q$ gains, the first two gains have sum at least $2/q$ of the total, giving
$$
F(s^{N_2})\geq\frac2qF(x^g).
$$
The adaptive second-round comparison is correct. Both policies have the same first action. The fixed second non-adaptive batch remains feasible after every first-round feedback history. Conditional greedy optimality and averaging therefore give
$$
a_2\geq F(s^{N_2}).
$$
The finite-round bound is correct. Applying the whole-block recurrence to the fixed final non-adaptive seed set and iterating from $a_2$ gives
$$
a_q\geq
\left[
1-\left(1-\frac2q\right)
\left(1-\frac1q\right)^{q-2}
\right]F(x^g).
$$
At $q=2$, the expression equals $1$ and the argument applies directly. At $q=1$, both policies use the same prior and tie rule, so the ratio is exactly $1$.
The column totals are correct. The recurrence telescopes as stated, giving exactly $M$ leaves in every column.
The recurrence solution is correct. With $a=1-1/k$ and
$$
h_i=\frac{Q_{i-1}}k+\theta_i,
\qquad 0<\theta_i\leq1,
$$
the displayed formula
$$
Q_k=a^kM+a^{k-1}
-\sum_{i=2}^k a^{k-i}\theta_i
$$
follows from the recurrence. Its stated error bound is valid, and therefore
$$
\frac{Q_k}{M}\longrightarrow e^{-1}.
$$
The analogous recurrence formula supports positivity of the residual counts for sufficiently large $k$: its leading term remains of order $M$, while the rounding correction is at most of order $k$.
The bound on $h_2$ is correct. Since $Q_i$ decreases, the floor expression defining $h_i$ is nonincreasing. Thus $h_i<H$ and $kh_i<M$ for all relevant rows once $k$ is sufficiently large.
The type count is correct:
$$
N_0=(k+2)M+2k+2.
$$
Padding to a power of two produces positive dyadic masses summing to one. The parameters satisfy
$$
q=k+1,\qquad c=\frac1N,\qquad
\beta=\frac{k+1}{N}\leq1.
$$
The graph is simple. The two environments have positive rational probabilities for sufficiently large $k$. Only the incoming set at the gate is random; every other incoming set is deterministic. Hence incoming sets at distinct types are independent.
Every edge goes from a source to a leaf, so no positive-length path exceeds length one. Full and myopic feedback coincide throughout these instances.
The initial gains are correct. The first row has $kH-1=M-1$ column leaves. The gate contributes its appropriate expected marginal, producing the stated initial gains.
All unseeded sources contribute the same additional unit for their own adoption. This common contribution does not alter source comparisons. The source $s$ strictly wins the first round.
After seeding $s$, each remaining column source retains $M$ unadopted column leaves. The prior marginal gate contribution of $v_1$ is $1-\varepsilon$, so its total leaf gain is at most $M-\varepsilon<M$. Every other row source also has fewer than $M$ remaining leaves. Non-adaptive greedy therefore seeds all columns.
The denominator
$$
F(x^g)=
\frac{2M+kM+\varepsilon+(k+1)}N
$$
correctly counts private leaves, column leaves, expected gate adoption, and seeded sources.
The first feedback identifies the environment. After seeding $s$, the gate adopts exactly when its incoming edge from $s$ is live.
In that branch, the gate offers no further marginal gain, and columns strictly beat rows.
In the other branch, $v_1$ has $M-1$ row leaves plus the gate, tying the column sources at leaf gain $M$. The prescribed order selects $v_1$.
After rows through $i-1$ have been selected, the remaining column counts are exactly $Q_{i-1}$ and $Q_{i-1}-1$. The inequality
$$
kh_i>Q_{i-1}
$$
is strict by the definition of $h_i$. Remaining row sizes are nonincreasing, and the stated tie order selects $v_i$. Thus the induction establishing selection of every row is valid.
The final counts are correct:
$$
B_k=kM-kQ_k+k-1.
$$
The gate adopts in both adaptive branches, so the expected numerator is correctly stated.
Dividing the ratio by $kM$ gives the claimed limit $1-e^{-1}$. The private-leaf and source terms vanish at that scale, while the uncovered column fraction converges to $e^{-1}$.
Together with Theorem 4, this proves that the infimum in the aligned equal-mass subclass is exactly $1-1/e$ under both feedback models. Because these are admissible unrestricted instances, the construction also proves
$$
\gamma_b\leq1-\frac1e.
$$
Major completeness issue: neither unrestricted sharp infimum is determined.
The output proves only
$$
0\leq\gamma_b\leq1-\frac1e
$$
universally. Its positive lower bounds have additional hypotheses. In particular, no established comparison covers arbitrary types larger than a round allowance.
The discussion of this obstruction accurately identifies a limitation of Lemma 2. It does not constitute a universal lower bound or a matching construction below the established upper bound.
The minimum substantive completion needed is a proof determining the unrestricted infimum for each feedback model. Merely clarifying the existing exposition cannot supply this missing result. The prover correctly labels its current contribution as partial.
⟨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.