Optimizing Message-Driven Recruitment on Networks

We study adaptive message-driven recruitment on social networks, motivated by digital public-health deployments in which growth relies on non-monetary behavioral nudges rather than paid referral incentives. We introduce a sequential influence model in which a decision maker repeatedly broadcasts one of several message types (or no message) to the currently active population; each broadcast has instantaneous, label-dependent effects that temporarily boost recruitment probabilities along social ties whose relationship contexts match the message. Policies are evaluated using a discounted active-mass objective that rewards both scale and timeliness, capturing the value of early engagement and equity-weighted reach. We show that optimizing such policies is computationally intractable even under strong structural simplifications, and that the problem is hard to approximate along two natural dimensions: maximizing recruitment within a fixed time horizon, and minimizing time to reach a target recruitment level. On the positive side, we analyze a natural adaptive policy that greedily maximizes expected one-step gain, and establish a parameterized approximation guarantee in terms of an instance-dependent amplification parameter that quantifies how strongly recruitment can compound over time. Finally, we illustrate our theoretical findings through experiments on synthetic networks and recruitment scenarios derived from real-world data.