Answer: Yes. The rational cap \(h=\min\{1,\alpha b\}\) gives a finite exact mass-flow implementation satisfying \(F(\pi)\geq\alpha(1-e^{-1/\alpha})\operatorname{OPT}\), hence also the requested bound with \(-\varepsilon\). An achievable exact running time is \(2^{O(m^2)}\operatorname{poly}(m,\tau,L,1/h)\), where \(m=\tau=q\).
Theorem 2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThe expected cascade of πu is bounded by f(πu) ≥α(1 −e−1 α )f(π∗).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite directed template \(H=(U,E)\) with \(q=|U|\), rational IC edge probabilities, and a rational budget \(b\), consider a continuum of independent copies indexed by \(x\in[0,1]\). Each role \(u\in U\) has normalized mass \(1/q\) per copy, and \(H\) specifies the ties within each copy. A policy chooses role seeds in copies based on the paper's partial edge feedback, with \(\int_0^1 |S_x|\,dx\le b\) on every realization, and maximizes \(F(\pi)=\frac1q\mathbb{E}[\int_0^1\sum_{u\in U}\mathbf{1}\{u\text{ is eventually active in copy }x\}\,dx]\). Does a mass version of the paper's α-greedy policy attain \(F(\pi)\ge\alpha(1-e^{-1/\alpha})\operatorname{OPT}-\varepsilon\), and can such a policy be represented and computed from finite module and feedback-history data?
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 types are the roles of a directed template \(H=(U,E)\), with \(m=q=|U|\ge1\), \(\tau=q\), and mass \(1/q\) per role; total society mass is one.
Copies of \(H\) are indexed by \(x\in[0,1]\), with no edges between copies. Each copy follows independent cascade (IC), with independent edge states and binary-rational probabilities \(p_e\in[0,1]\). Interpret the continuum by exact mass flows: copies sharing an observed history split into feedback outcomes according to their conditional IC probabilities; selecting a submass cannot depend on unobserved edge states.
Initially no role is active. A policy may seed previously unseeded roles in measurable submasses of copies, or wait one global diffusion slot; multiple seeding moves may occur within a slot. After a seed has aged \(d\ge1\) slots, feedback reveals all outgoing edges of vertices reachable from that seed by live paths of at most \(d-1\) edges; observations from all seeds are retained. Histories include seed identities, seeding times, and revealed edge states.
Seeding one role in copy mass \(a\) costs \(a\). For rational \(0<b\le q\), require \(\int_0^1|S_x|\,dx\le b\) on every policy realization. Define \(F(\pi)=q^{-1}\mathbb E[\int_0^1\sum_{u\in U}\mathbf1\{u\text{ eventually active in copy }x\}\,dx]\), and let \(\operatorname{OPT}\) be its supremum over all measurable policies using only the specified feedback and obeying this budget; waiting has no cost or deadline.
For rational \(0<\alpha\le1\), define mass \(\alpha\)-greedy by a rational batch cap \(h>0\). At each seeding move, choose a positive-mass history and an unseeded role maximizing the conditional expected increase in eventual active-role count in that copy; break ties by a fixed ordering. Seed copy mass equal to the minimum of \(h\), the available history mass, and the remaining budget.
Let \(p_{x,u}\) be the conditional probability that role \(u\) eventually activates from the seeds already chosen, without further seeding. Except for the first move, seed only when \(\frac{\int_0^1\sum_u p_{x,u}\,dx}{\int_0^1\sum_u\mathbf1\{p_{x,u}>0\}\,dx}\ge\alpha\); otherwise wait one slot. Stop when the budget is exhausted or every role has been seeded.
For every rational \(0<\varepsilon<1\), does mass \(\alpha\)-greedy admit a computable batch cap \(h\) and a finite description using module histories and mass allocations such that \(F(\pi)\ge\alpha(1-e^{-1/\alpha})\operatorname{OPT}-\varepsilon\)? What running time is achievable in \(m,\tau,L,1/\varepsilon\), and \(1/h\), where \(L\) is the total binary input length?
For finite societies with unit seed costs and a positive integer cardinality budget, exact conditional-marginal \(\alpha\)-greedy has the approximation guarantee \(f(\pi)\ge\alpha(1-e^{-1/\alpha})f(\pi^*)\). [Yuan and Tang](https://www.ijcai.org/proceedings/2017/0546.pdf)
No result settling this precise continuum mass-flow approximation question was located.
The answer is yes, with an exact guarantee stronger than the requested one. Choose the rational cap \(\displaystyle h=\min\{1,\alpha b\}\). Then mass \(\alpha\)-greedy has a finite rational mass-flow description and satisfies
\(\displaystyle F(\pi)\geq \alpha(1-e^{-1/\alpha})\operatorname{OPT}.\)
Writing \(\displaystyle e=|E|\), an achievable exact running time is
\(\displaystyle 2^{O(e)}\operatorname{poly}(q,L,1/h).\)
Since \(\displaystyle e\leq q^2\) and \(\displaystyle m=\tau=q\), this is also \(\displaystyle 2^{O(m^2)}\operatorname{poly}(m,\tau,L,1/h,1/\varepsilon)\). The algorithm does not need to use \(\displaystyle \varepsilon\).
The finite guarantee cited in the question is [Yuan and Tang, Theorem 2](https://www.ijcai.org/proceedings/2017/0546.pdf). The proof below establishes the mass-flow statement directly.
For an edge realization \(\displaystyle \omega\), let \(\displaystyle R_\omega(S)\) denote the roles reachable from seed set \(\displaystyle S\) by live paths, including the seeds themselves. Eventual activation under IC equals this reachability set.
Fix a positive-mass module history \(\displaystyle \eta\), with current seeds \(\displaystyle S\). Conditional on this history, unrevealed edge states remain independent with their original probabilities.
To justify this posterior assertion, expose feedback slot by slot. The outgoing edges exposed next have tails whose reachability is already certified by previously exposed live paths. Consequently, the choice of the next edges to reveal depends only on previously revealed states. A specified history therefore imposes only the states of its revealed edges. Seed choices and mass cuts impose no additional restrictions on unrevealed edges, because such cuts cannot depend on those states.
Define the support graph at \(\displaystyle \eta\) by retaining:
Let \(\displaystyle A_\eta\) be the roles reachable from \(\displaystyle S\) in this support graph, and put \(\displaystyle O_\eta=U\setminus A_\eta\).
A role has positive conditional activation probability exactly when it belongs to \(\displaystyle A_\eta\). Indeed, a support path has positive conditional probability of being entirely live, whereas a live path must be a support path. Thus every role in \(\displaystyle O_\eta\) has conditional activation probability zero.
Two structural properties will be used:
In particular, the edge states inside the induced graph on \(\displaystyle O_\eta\) are still independent with their original probabilities.
For an unseeded role \(\displaystyle z\), write its current conditional marginal as
\(\displaystyle \Delta_\eta(z)= \mathbb E_\eta\!\left[|R_\omega(S\cup\{z\})|-|R_\omega(S)|\right].\)
Lemma. Fix an initial history \(\displaystyle \eta\). At any later positive-probability history obtained by additional legal seeding and feedback, the conditional marginal gain in the fixed target set \(\displaystyle O_\eta\), from adding any role \(\displaystyle z\), is at most \(\displaystyle \Delta_\eta(z)\). For a role already seeded initially, this marginal is zero.
Proof. Let \(\displaystyle S'\supseteq S\) be the later seed set. Let \(\displaystyle K\) be the roles reachable from \(\displaystyle S'\) by paths consisting entirely of revealed live edges. Every role in \(\displaystyle K\) is certainly eventually active. Every revealed edge tail belongs to \(\displaystyle K\).
First suppose \(\displaystyle z\in A_\eta\). No completion consistent with \(\displaystyle \eta\) has a live path from \(\displaystyle A_\eta\) into \(\displaystyle O_\eta\). Adding \(\displaystyle z\) therefore has zero marginal gain in \(\displaystyle O_\eta\).
Now suppose \(\displaystyle z\in O_\eta\). In a completion \(\displaystyle \omega\), consider a role in
\(\displaystyle \bigl(R_\omega(S'\cup\{z\})\setminus R_\omega(S')\bigr)\cap O_\eta.\)
Choose a live path to this role starting at \(\displaystyle z\). This path cannot enter \(\displaystyle A_\eta\), because it could not subsequently return to \(\displaystyle O_\eta\). It also cannot meet \(\displaystyle R_\omega(S')\): otherwise its endpoint would already be reachable from \(\displaystyle S'\). Consequently, the entire path lies in \(\displaystyle O_\eta\setminus K\).
All edges with tails in \(\displaystyle O_\eta\setminus K\) are unrevealed at the later history. Their conditional states remain independent with the original probabilities. The later expected marginal in \(\displaystyle O_\eta\) is therefore at most the expected number of roles reachable from \(\displaystyle z\) in the induced graph on \(\displaystyle O_\eta\setminus K\), with value zero if \(\displaystyle z\in K\).
Deleting vertices cannot increase reachability in any edge realization. Hence this upper bound is at most the original expected reachability from \(\displaystyle z\) in the induced graph on \(\displaystyle O_\eta\). Initially, no role of \(\displaystyle O_\eta\) is reachable from \(\displaystyle S\), so this last quantity equals the initial marginal restricted to \(\displaystyle O_\eta\). It is at most \(\displaystyle \Delta_\eta(z)\). This proves the lemma. \(\displaystyle \square\)
Use unnormalized active-role mass. At a current greedy state, define
\(\displaystyle C=\int_0^1\sum_{u\in U}p_{x,u}\,dx,\qquad A=\int_0^1\sum_{u\in U}\mathbf 1\{p_{x,u}>0\}\,dx.\)
Let \(\displaystyle D\) be the largest conditional marginal over all positive-mass histories and their unseeded roles.
For any feasible comparison policy \(\displaystyle \rho\), let \(\displaystyle V_\rho=qF(\rho)\). We claim that
\[\displaystyle V_\rho\leq A+bD. \tag{1}\]
To prove this, couple the current greedy prefix and \(\displaystyle \rho\) using the same edge states. After the prefix, simulate \(\displaystyle \rho\), ignoring observations supplied only by the prefix.
This simulation is legal as an auxiliary comparison procedure. There is no deadline, so it may wait until every feedback observation requested by the simulated policy is available. A role already seeded by the prefix need not be seeded again. The final union of seed sets activates every role activated by \(\displaystyle \rho\). The auxiliary procedure uses at most \(\displaystyle b\) additional seed mass; its combined cost need not obey the original budget, since it is used only for comparison.
Retain each copy’s initial history as a tag, and use its fixed target set \(\displaystyle O_\eta\). Initially, activation in this set has probability zero. By the lemma, each subsequent unit of seed mass has conditional expected marginal at most \(\displaystyle D\) in this target set. Summing these gains bounds its final expected active-role mass by \(\displaystyle bD\).
Outside the tagged target sets, active-role mass is at most \(\displaystyle A\), their total complementary role mass. Since the union activates everything activated by \(\displaystyle \rho\), inequality \(\displaystyle (1)\) follows.
The same argument covers policies with infinitely many moves: apply it to finite prefixes, then use monotone convergence. Eventual activation is the increasing union of the reachability sets generated by those prefixes. Nonnegative marginal gains permit the corresponding sum and integral to pass to the limit.
Taking the supremum over feasible comparison policies, and writing \(\displaystyle V^*=q\operatorname{OPT}\), gives
\[\displaystyle V^*\leq A+bD. \tag{2}\]
Whenever the greedy gate permits seeding, \(\displaystyle C\geq\alpha A\). Thus
\[\displaystyle D\geq\frac{V^*-C/\alpha}{b}. \tag{3}\]
Before the first move, \(\displaystyle C=A=0\), so \(\displaystyle (3)\) also holds there by \(\displaystyle (2)\).
Suppose a permitted greedy move seeds mass \(\displaystyle a\). It chooses a history-role pair attaining \(\displaystyle D\), and its mass selection does not depend on unrevealed edges. Therefore its increase in \(\displaystyle C\) is exactly
\[\displaystyle C_{\mathrm{new}}-C=aD. \tag{4}\]
Waiting does not change \(\displaystyle C\). The seeds remain fixed, and the exact feedback split preserves their expected eventual active-role count by the law of total expectation.
Moreover, the gate becomes satisfied within at most \(\displaystyle q\) consecutive waiting slots. Once all current seeds have age at least \(\displaystyle q\), feedback reveals outgoing edges of every reachable role: every reachable role admits a simple live path of length at most \(\displaystyle q-1\). The eventual active set is then determined in every resulting history. All activation probabilities are zero or one, so the gate ratio is one.
Let \(\displaystyle a_1,\ldots,a_M\) be the greedy batch masses, and let \(\displaystyle C_i\) be the value after the first \(\displaystyle i\) batches, including any intervening waits. Define
\(\displaystyle \delta_i=V^*-C_i/\alpha.\)
Combining \(\displaystyle (3)\) and \(\displaystyle (4)\) yields
\[\displaystyle \delta_i \leq \left(1-\frac{a_i}{\alpha b}\right)\delta_{i-1}. \tag{5}\]
Our cap satisfies \(\displaystyle a_i\leq h\leq\alpha b\), so all factors in \(\displaystyle (5)\) are nonnegative. Consequently, once termination and full budget expenditure are established,
\[\displaystyle \delta_M \leq V^*\prod_{i=1}^{M}\left(1-\frac{a_i}{\alpha b}\right) \leq V^*\exp\!\left(-\frac{\sum_i a_i}{\alpha b}\right). \tag{6}\]
The next section establishes both required facts.
The issue is that a move can cost less than \(\displaystyle h\) by exhausting a small history. A lower bound on batch size is therefore unavailable.
Maintain auxiliary positive-mass fragments. Fragments with identical observed histories may be grouped when computing available history mass, but their genealogies remain separate.
For a seeding allocation, take whole fragments in a fixed order, followed by at most one partial fragment. Thus each move cuts at most one fragment into two positive pieces. A nonterminal move costing less than \(\displaystyle h\) exhausts its selected history and cuts no fragment.
Set
\(\displaystyle K_0=\lfloor b/h\rfloor+1,\qquad P=2^e(K_0+1). \)
There are at most \(\displaystyle K_0\) moves consisting of a full-cap move or a terminal move. Hence there are at most \(\displaystyle K_0\) proper fragment cuts.
For a current fragment, let \(\displaystyle r\) be the number of edge states revealed along its genealogy. Give it weight \(\displaystyle 2^{e-r}\).
Initially there is one fragment of weight \(\displaystyle 2^e\). Therefore total fragment weight is always at most \(\displaystyle P\). Every fragment has weight at least one, so there are at most \(\displaystyle P\) current fragments.
Now fix any finite execution prefix. Every nonterminal move costing less than \(\displaystyle h\) seeds all fragments of its selected history. Charge that move to one descendant fragment present at the end of the prefix. All moves charged to a given descendant lie on its genealogy, and each adds a previously unseeded role. At most \(\displaystyle q\) moves can therefore be charged to it.
It follows that every finite execution prefix has at most
\[\displaystyle M\leq K_0+qP \tag{7}\]
seeding moves. An infinite execution would violate this uniform bound. Since there are at most \(\displaystyle q\) waiting slots between successive seeding moves, the entire execution is finite.
If it stops before exhausting the budget, every role must have been seeded almost everywhere, which costs \(\displaystyle q\). Because \(\displaystyle b\leq q\), this can occur only when the budget has also been exhausted. Hence
\(\displaystyle \sum_{i=1}^{M}a_i=b.\)
Substituting into \(\displaystyle (6)\) gives
\(\displaystyle V^*-C_M/\alpha\leq e^{-1/\alpha}V^*, \)
and therefore
\(\displaystyle F(\pi)=C_M/q \geq\alpha(1-e^{-1/\alpha})\operatorname{OPT}. \)
The algorithm stores positive-mass fragments, groups them by their exact module histories, and records every mass allocation rationally. A history records seed identities, seed times, and revealed edge states. These records suffice to determine the feedback available after a wait.
For each history:
All quantities are rational. Choose a fixed lexicographic ordering of encoded history-role pairs for ties. Fragment cuts use only observed histories and the fixed fragment order, so they never depend on unrevealed edge states. Under the stipulated exact-flow interpretation, these rational cuts specify legal measurable submass selections.
For completeness, arithmetic bit lengths are also bounded. Let \(\displaystyle D_{\mathrm{den}}\) be the product of the denominators of the edge probabilities. Its binary length is \(\displaystyle O(L)\). Because the posterior on unrevealed edges is a product distribution, every conditional feedback probability has denominator dividing \(\displaystyle D_{\mathrm{den}}\).
Let \(\displaystyle Q\) be a common denominator of \(\displaystyle b\) and \(\displaystyle h\). After \(\displaystyle T\) global waits, every fragment mass has denominator dividing
\(\displaystyle QD_{\mathrm{den}}^T.\)
This follows inductively: seeding cuts use a stored history mass, the remaining budget, or \(\displaystyle h\); a feedback split multiplies by a probability whose denominator divides \(\displaystyle D_{\mathrm{den}}\). Thus mass bit lengths are
\(\displaystyle O(L+\ell_h+TL),\)
where \(\displaystyle \ell_h\) is the binary length of \(\displaystyle h\). For our chosen cap, \(\displaystyle \ell_h=O(L)\).
By \(\displaystyle (7)\),
\(\displaystyle P=O\!\left(2^e(1+b/h)\right),\qquad M=O\!\left(q\,2^e(1+b/h)\right),\qquad T\leq qM. \)
There are at most \(\displaystyle P\) current fragments. Each history calculation enumerates at most \(\displaystyle 2^e\) worlds and uses polynomial-time graph computations and exact arithmetic. Combining these bounds gives
\(\displaystyle 2^{O(e)}\operatorname{poly}(q,L,1/h) \)
bit operations, using \(\displaystyle b\leq q\). The finite execution log itself provides the requested description by module histories and rational mass allocations.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The argument establishes the requested continuum approximation guarantee, with no additive loss, and supplies a finite rational implementation with the claimed exponential running time. I found no major or minor issue requiring repair.
This conclusion uses the stipulated exact mass-flow interpretation. In particular, selecting a submass according to observed histories preserves the conditional distribution of unrevealed edges.
The chosen cap \(h=\min\{1,\alpha b\}\) is positive, rational, and computable from the input. It satisfies the bound \(h\leq\alpha b\) needed later.
The claimed exact guarantee implies the requested guarantee for every permitted \(\varepsilon\). The implementation therefore need not depend on \(\varepsilon\).
The identification \(m=\tau=q\) respects the task’s definition of supported types. The bound \(e\leq q^2\) is valid for the directed graph \(E\subseteq U\times U\), including possible loops.
The posterior assertion is justified under the specified feedback rule:
Consequently, conditioning on an attainable history fixes revealed states without further restricting unrevealed states.
The characterization of \(A_\eta\) is correct. Every finite support path has positive conditional probability of being live, and every possible live path lies in the support graph. Probabilities equal to zero or one cause no exception.
Both stated structural properties follow:
Thus the assertion concerning untouched edge states within \(O_\eta\) is valid.
The lemma is correctly restricted to the fixed initial target set \(O_\eta\). It does not assert diminishing conditional marginals for all roles.
The proof checks out step by step:
The case \(z\in K\) correctly has zero marginal. The statement about roles seeded initially also follows immediately from their membership in the seed set.
No unjustified adaptive-submodularity assumption is used.
The auxiliary concatenation argument is valid.
The simulation retains the comparison policy’s own observations and can ignore information supplied only by the greedy prefix. Waiting without a deadline permits the required observations to become available. Omitting a repeated physical seed does not remove the original seed from the union.
The comparison procedure need not satisfy the original budget after concatenation: only its additional seed mass must be bounded by \(b\). The write-up explicitly distinguishes these two requirements.
Retaining initial histories as tags makes the target sets in the lemma fixed throughout the comparison. The lemma then bounds every additional seeding gain in those sets by the current global maximum \(D\). Their complementary role mass is exactly \(A\). Hence the claimed inequality
\[
V_\rho\leq A+bD
\]
is justified.
The extension to infinitely many sequential moves is also valid: seed sets and their eventual reachability sets increase along finite prefixes, gains are nonnegative, and the total added seed mass remains bounded by \(b\). The stated monotone-convergence passage is appropriate.
Taking a supremum does not require an optimal policy to exist. Thus the bound involving \(V^*=q\operatorname{OPT}\) follows.
When the gate permits seeding, \(C\geq\alpha A\) yields the asserted lower bound on \(D\). Before the first move, \(C=A=0\), so the separate first-move treatment is correct.
The gain identity \(C_{\mathrm{new}}-C=aD\) follows from selecting mass within one conditional history without selecting on hidden states. Waiting preserves aggregate expected eventual activation through exact feedback splitting.
The waiting bound is correct: after every current seed has aged \(q\) slots, all reachable roles have outgoing edges exposed, since simple reachable paths have length at most \(q-1\). The eventual active set is then determined, making the gate ratio one.
There is no division-by-zero problem after the first move: positive seeded mass gives positive \(C\) and \(A\).
The recurrence is algebraically correct. Crucially, \(a_i\leq\alpha b\) ensures nonnegative multiplication factors. This remains sufficient even if an intermediate \(\delta_i\) becomes negative.
The product-to-exponential bound is valid over the full stated range, including a zero factor. Once total expenditure is \(b\), the resulting approximation factor is exactly the claimed one.
The fragment argument addresses the potentially arbitrarily small batch sizes.
Its bounds are valid:
Thus the uniform bound \(P\) on current fragments is justified.
The charging argument is also sound. Each nonterminal move smaller than \(h\) seeds all fragments in its selected history. A final descendant can therefore be charged only for distinct roles seeded along its genealogy, giving at most \(q\) charges.
The uniform bound on every finite prefix excludes an infinite sequence of seeding moves. The bounded waiting intervals exclude an infinite execution consisting of waits.
Stopping because every role has been seeded requires cost \(q\). Since \(b\leq q\), this cannot leave unspent budget. Full expenditure is therefore established before it is used in the recurrence.
Enumerating edge completions suffices for all stated computations: conditional activation probabilities, conditional marginals, and feedback outcomes. Reachability computations are finite and polynomial per completion.
The fragment allocations are rational and use only permitted information. Histories retain the seed times needed to determine subsequent feedback.
The arithmetic bounds are consistent:
The bounds on fragment count, move count, waiting count, and arithmetic length combine into
\[
2^{O(e)}\operatorname{poly}(q,L,1/h).
\]
Additional exponential factors from enumerating worlds or processing exponentially many fragments remain within \(2^{O(e)}\).
The cases \(q=1\), \(e=0\), \(\alpha=1\), and \(b=q\) do not invalidate these arguments.
The attribution to [Yuan and Tang, Theorem 2](https://www.ijcai.org/proceedings/2017/0546.pdf) is accurate: it states the displayed approximation factor for their finite uniform-cost setting. The continuum proof is independent of applying that theorem, so no unsupported transfer between models occurs.
The output establishes an approximation guarantee and an exponential-time implementation. It establishes neither polynomial-time computation of the optimum nor hardness. Accordingly, the appropriate continuous-status category is other.
No repair feedback is necessary.
⟨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.