Go Viral, or Not: Rate-Optimal Control for Resource-Constrained Branching Processes

Shie Mannor, Kuang XuarXiv 2012 · DOI · arXiv

Abstract: We propose and analyze a new class of controlled multi-type branching processes with a per-step linear resource constraint, motivated by potential applications in viral marketing and cancer treatment. We show that the optimal exponential growth rate of the population can be achieved by maintaining a fixed proportion among the species, for both deterministic and stochastic branching processes. In the special case of a two-type population and with a symmetric reward structure, the optimal proportion is obtained in closed-form. In addition to revealing structural properties of controlled branching processes, our results are intended to provide the practitioners with an easy-to-interpret benchmark for best practices, if not exact policies. As a proof of concept, the methodology is applied to the linkage structure of the 2004 US Presidential Election blogosphere, where the optimal growth rate demonstrates sizable gains over a uniform selection strategy, and to a two-compartment cell-cycle kinetics model for cancer growth, with realistic parameters, where the robust estimate for minimal treatment intensity under a worst-case growth rate is noticeably more conservative compared to that obtained using more optimistic assumptions.

Introduction

Whether managing a digital marketing campaign or designing an oncological treatment plan, practitioners often face the challenge of controlling a heterogeneous population that grows through branching processes. In these scenarios, the population consists of multiple "types" (e.g., different political affiliations or cell states) with distinct reproductive rates.

While classical branching process theory is well-developed, real-world applications are often governed by strict resource constraints. For instance, a marketer may only have a limited budget for coupons, or a clinician may be restricted by chemotherapy toxicity levels. This paper addresses the problem of controlling multi-type branching processes under a per-step linear resource constraint: in each round, only a sub-population can be selected to reproduce, and the cost of this selection must not exceed a fixed fraction of the current total population size.

Methodology

The authors frame the control problem as an average-cost Markov Decision Process (MDP). To solve this, they utilize several key mathematical techniques:

  1. Simplex Scaling: Instead of tracking absolute population counts, the state is projected onto a unit simplex. This allows the analysis to focus on the mixture (the ratio of types) rather than the scale.
  2. Fixed-Point Analysis: By applying Kakutani’s Fixed-Point Theorem, the authors prove that an optimal stationary policy exists. This policy converges to a single, optimal population mixture that maximizes (or minimizes) the long-term growth rate.
  3. Deterministic-Stochastic Equivalence: The optimal growth rate for a continuous, deterministic model is shown to be identical to that of a realistic stochastic, integer-valued model in the large-population limit.
Geometric representation of the reachable set of population mixtures under a linear resource constraint.

For two-dimensional cases, the optimal strategy is characterized as "greedy," prioritizing the most productive type up to the resource limit. The paper provides explicit quadratic equations to calculate these optimal mixtures, offering a practical tool for decision-makers.

Empirical Validation

The methodology was tested on two distinct real-world datasets:

  • 2004 US Presidential Election Blogosphere: Using linkage data between 1,222 liberal and conservative blogs, the authors simulated political marketing spread. The optimal strategy achieved a growth factor gain of approximately 5x over a naive uniform strategy when the budget allowed targeting 80% of the population.
  • Cell-Cycle Kinetics Model: A two-compartment model (active vs. quiescent cells) was used to simulate cancer growth. While a uniform assumption suggested that an extermination rate of 37% per round would shrink the tumor, the robust model—accounting for unfavorable shifts in tumor composition—revealed that a 45% rate is actually required for guaranteed decline.

Key Insights and Conclusion

A central finding of this research is the power of consistency: an optimal growth rate can be achieved by simply maintaining a fixed ratio of types rather than employing complex, fluctuating strategies. Furthermore, the study demonstrates that uniform targeting is almost always suboptimal compared to a mixture that favors high-impact types.

While the 2D case is solved in closed-form, future work is needed to improve the scalability of numerical searches for populations with many types ($K > 2$). Additionally, addressing parameter sensitivity—particularly the difficulty of measuring reproduction matrices in clinical settings—remains a critical step for practical implementation in oncology.

Summary updated

Abstract

We propose and analyze a new class of controlled multi-type branching processes with a per-step linear resource constraint, motivated by potential applications in viral marketing and cancer treatment. We show that the optimal exponential growth rate of the population can be achieved by maintaining a fixed proportion among the species, for both deterministic and stochastic branching processes. In the special case of a two-type population and with a symmetric reward structure, the optimal proportion is obtained in closed-form. In addition to revealing structural properties of controlled branching processes, our results are intended to provide the practitioners with an easy-to-interpret benchmark for best practices, if not exact policies. As a proof of concept, the methodology is applied to the linkage structure of the 2004 US Presidential Election blogosphere, where the optimal growth rate demonstrates sizable gains over a uniform selection strategy, and to a two-compartment cell-cycle kinetics model for cancer growth, with realistic parameters, where the robust estimate for minimal treatment intensity under a worst-case growth rate is noticeably more conservative compared to that obtained using more optimistic assumptions.
BibTeX
@misc{mannor2012go,
  author = {Shie Mannor and Kuang Xu},
  title = {{Go Viral, or Not: Rate-Optimal Control for Resource-Constrained Branching Processes}},
  year = {2012},
  eprint = {1203.1072},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1203.1072},
}

Loading related content...

Figure