Source-linked AI summary
How to Run a Campaign: Optimal Control of SIS and SIR Information Epidemics
Kundan Kandhway, Joy Kuri
TL;DR
Campaigners seek to maximize message spread by a deadline despite limited resources. The paper formulates optimal control for SIS and SIR information epidemics, including time-varying spreading rates and distinct recruitment and incentive controls. It establishes existence and deadline-conditional uniqueness, and examines strategy costs and sensitivity to spreading-rate profiles.
Problem
Campaigners need to allocate limited resources over time to spread a message by a deadline, while audience interest and information spreading rates can change during the campaign.
Source: §1 · pp. 1–3Method
Results
Solutions exist for both models and are unique for sufficiently small deadlines; the paper compares optimal-control costs with alternative strategies at constant rates and studies sensitivity to varying rate profiles.
Source: §1 · p. 3Takeaways & Limitations
The models represent campaign interest changes through time-varying spreading rates and distinguish direct recruitment from incentives that raise word-of-mouth spread.
Source: §1 · p. 3, §3 · p. 5Estimating spreading and recovery rates is nontrivial, and sensitivity of control strategies to estimation errors is left for future research.
Source: §7 · p. 15
Abstract
from arXiv · showhide
Information spreading in a population can be modeled as an epidemic. Campaigners (e.g. election campaign managers, companies marketing products or movies) are interested in spreading a message by a given deadline, using limited resources. In this paper, we formulate the above situation as an optimal control problem and the solution (using Pontryagin's Maximum Principle) prescribes an optimal resource allocation over the time of the campaign. We consider two different scenarios --- in the first, the campaigner can adjust a direct control (over time) which allows her to recruit individuals from the population (at some cost) to act as spreaders for the Susceptible-Infected-Susceptible (SIS) epidemic model. In the second case, we allow the campaigner to adjust the effective spreading rate by incentivizing the infected in the Susceptible-Infected-Recovered (SIR) model, in addition to the direct recruitment. We consider time varying information spreading rate in our formulation to model the changing interest level of individuals in the campaign, as the deadline is reached. In both the cases, we show the existence of a solution and its uniqueness for sufficiently small campaign deadlines. For the fixed spreading rate, we show the effectiveness of the optimal control strategy against the constant control strategy, a heuristic control strategy and no control. We show the sensitivity of the optimal control to the spreading rate profile when it is time varying.
1. Introduction
The paper formulates resource-limited campaigns to spread information by a deadline as optimal control problems, using time-varying spreading rates to represent changing audience interest. It develops SIS and SIR campaign models, establishes solution properties, and examines control costs and sensitivity to spreading-rate profiles.
1. Introduction
- The campaign models assume a homogeneously mixed population, with individuals communicating and exchanging messages on their own.Source: §1 · p. 1
- Prior optimal-control work mainly sought to contain disease or computer-virus spread, whereas this paper seeks to maximize information spread; information epidemics had received less attention.The paper also distinguishes its objective and quadratic control cost from marketing work in.Source: §1 · pp. 2–3
- Push, Pull, and Push-pull studies bound communication rounds for fixed spreading strategies, rather than optimizing information-spreading strategies.Source: §1 · p. 2
- Rumor-spreading work uses different epidemic models and impulse control, while product advertising and pricing studies and do not model viral message propagation.Source: §1 · p. 2
- Unlike biological epidemics, information spreading rates can change as campaign deadlines approach, so the models represent changing audience interest over time.The paper says previous studies ignored this characteristic of information epidemics.Source: §1 · p. 3
- The SIS model uses direct recruitment, while the SIR model adds incentives for infected individuals to increase the effective spreading rate; both use quadratic costs and time-varying rates.The objective combines the fraction receiving the message by the deadline with control costs.Source: §1 · p. 3
- Solutions exist for both models, and are unique when campaign deadlines are sufficiently small.Source: §1 · p. 3
- With constant spreading rates, the paper compares optimal-control costs against constant control, a heuristic strategy, and no control; with varying rates, it studies sensitivity to the rate profile.Source: §1 · p. 3
2. System Model and Problem Formulation: SIS Epidemic
The SIS formulation models message uptake and recovery in a fixed population, with direct recruitment added as a control. Its objective weighs infection at the deadline against the campaign’s accumulated quadratic cost.
2. System Model and Problem Formulation: SIS Epidemic
- The SIS state tracks susceptible and infected fractions in a fixed population, with infected individuals able to recover and become susceptible again.Source: §2 · p. 3
- Without control, infected fraction grows through susceptible-infected contact at rate β(t)s(t)i(t) and declines through recovery at rate γi(t).The effective spreading rate β(t) is time-varying and bounded.Source: §2 · p. 4
- The objective trades off the final infected fraction against campaign costs accumulated over time, with quadratic control cost.The formulation emphasizes infection at deadline T rather than the trajectory i(t) before the deadline.Source: §2 · p. 4
- The campaigner’s bounded recruitment control u(t) moves susceptible individuals into the infected class at rate u(t)s(t).Source: §2 · p. 4
- The initial infected fraction i0 represents the epidemic’s seed population, and the susceptible fraction begins at 1 − i0.Source: §2 · p. 4
3. System Model and Problem Formulation: SIR Epidemics
The SIR model represents message spreading by susceptible, infected, and recovered fractions, with infected individuals eventually recovering. Campaigners can use direct recruitment and word-of-mouth incentives to maximize the population reached while minimizing campaign cost.
3. System Model and Problem Formulation: SIR Epidemics
- The SIR model tracks susceptible, infected, and recovered fractions, with their sum equal to one and initially r(0)=0.Recovered individuals have stopped disseminating the message.Source: §3 · pp. 4–5
- Direct recruitment adds spreaders, while word-of-mouth incentives raise the effective spreading rate from β(t) to β(t)+u2(t).The controls are bounded nonnegative signals.Source: §3 · p. 5
- The objective pairs a quadratic control cost over campaign horizon 0 ≤ t ≤ T with reward equal to the total population fraction ever reached, i(T) + r(T) = 1 − s(T).Source: §3 · p. 5
4. Analysis of the Controlled SIS Epidemic
For the controlled SIS model, an optimal control exists, and Pontryagin’s Maximum Principle supplies conditions for computing it. The optimal control and state and adjoint trajectories are unique when the campaign deadline is sufficiently small.
4. Analysis of the Controlled SIS Epidemic
- The model’s infected fraction i(t) is bounded by 0 ≤ i(t) ≤ 1, and its dynamics involve the time-varying rate β(t), recovery rate γ, and control signal u(t).Source: §4 · p. 5
4.1. Existence of a Solution
- An optimal control signal and corresponding state trajectory exist for the controlled SIS problem.The proof invokes the Cesari Theorem [20].Source: §4.1 · p. 5
4.2. Solution to the SIS Optimal Control Problem
- Pontryagin’s Maximum Principle yields state and adjoint equations with initial and boundary conditions that characterize the optimum.The resulting system is solved numerically as a boundary-value problem using a shooting method.Source: §4.2 · p. 6
4.3. Uniqueness of the Solution to the SIS Optimal Control Problem
- For a sufficiently small campaign deadline T, the optimal control and the state and adjoint trajectories are unique.The uniqueness result applies to problem (4).Source: §4.3 · p. 6
5. Analysis of the Controlled SIR Epidemic
The controlled SIR problem has an optimal pair of direct-recruitment and word-of-mouth controls. Pontryagin’s Maximum Principle provides a numerical route to the controls, and the state and adjoint trajectories and solution are unique for sufficiently small deadlines.
5. Analysis of the Controlled SIR Epidemic
- The SIR problem is rewritten using two state variables and two controls, with the initial state and bounds specified.The reformulation removes redundant information from the original problem.Source: §5 · p. 7
5.1. Existence of a Solution
- An optimal pair of controls and corresponding state trajectories exist for the controlled SIR problem.The existence proof applies the Cesari Theorem [20].Source: §5.1 · p. 7
5.2. Solution to the SIR Optimal Control Problem with Direct and Word-of-mouth Control
- Pontryagin’s Maximum Principle gives conditions for the two optimal controls, which are used with the state and adjoint equations to compute the solution numerically.The equations form a system of ordinary differential equations.Source: §5.2 · p. 7
5.3. Uniqueness of the Solution to the SIR Optimal Control Problem with Direct Recruitment and Word-of-mouth Control
- For a sufficiently small campaign deadline T, the state and adjoint trajectories at the optimum and the solution are unique.This result concerns the SIR problem with direct recruitment and word-of-mouth control.Source: §5.3 · p. 8
6. Results
The results compare optimal, constant, heuristic, and no-control campaigns under constant and time-varying spreading rates. Optimal control is consistently less costly than no control, while its timing and benefit depend on campaign virality and the spreading-rate profile.
6.1. Constant E
- For R0 > 1, direct recruitment is strongest early when susceptibles are abundant, while SIR word-of-mouth control begins when both susceptible and infected populations are substantial.For R0 < 1, SIS direct control increases over time, while the SIR optimum uses no word-of-mouth control throughout.Source: §6.1 · p. 9, Figure 3 · p. 9
- As R0 increases, optimal-control effort and its effect on system evolution decrease, so less-viral campaigns benefit more from control.For the SIS case, the comparison uses R0 = 10 and R0 = 20; similar observations are reported for both SIR controls.Source: Figure 2 · p. 8, §6.1 · p. 9
6.2. Variable E
- With time-varying spreading rates, optimal-control shapes can differ from the constant-rate case, and optimal control increases infected SIS nodes and infected and recovered SIR nodes versus no control.The tested profiles represent increasing, decreasing, and fluctuating interest; the framework can also be modified to include time-varying recovery rates.Source: §6.2 · pp. 10–11, Figure 5 · p. 10, Figure 6 · p. 11
6.3. Comparison Between Optimal, Constant and a Heuristic Control
- The heuristic controls scale direct recruitment by the uncontrolled susceptible fraction and SIR word-of-mouth incentives by the uncontrolled susceptible and infected fractions; both are fixed open-loop at campaign start.The constant strategy applies half the maximum signal strength; the compared strategies can have similar final infected fractions but substantially different control effort.Source: §6.3 · pp. 12–13, Figure 8 · p. 12
- Optimal control always yields lower J than no control, while constant and heuristic controls can cost more than no control for some parameter vectors.When uncontrolled spread already produces high campaign reach, optimal control reduces costs only modestly; otherwise it decreases J relative to no control.Source: Figure 9 · p. 12, Figure 10 · p. 13, Figure 11 · p. 13
- As either cost weight b or c increases, J rises, but optimal control is less sensitive to these weights than the constant and heuristic strategies.The comparison also reports that more viral campaigns are less costly to run than less viral campaigns.Source: Figure 10 · p. 13, §6.3 · p. 14, Figure 12 · p. 14
7. Conclusion
The paper studies optimal campaign controls for SIS and SIR information epidemics with time-varying spreading rates. It establishes existence and, for sufficiently small deadlines, uniqueness, and reports control effectiveness for fixed spreading rates.
7. Conclusion
- For fixed spreading rates, optimal control outperforms constant control, a heuristic strategy, and no control in both models.The study also reports that the control strategy is sensitive to the time-varying spreading-rate profile.Source: §7 · p. 14
- Both models have solutions, and those solutions are unique for sufficiently small campaign deadlines.The models assume a homogeneously mixed population.Source: §7 · p. 14
- The SIS model uses direct recruitment, while the SIR model adds incentives for infected individuals alongside direct recruitment.The time-varying spreading rate represents changes in the population’s interest in the campaign topic.Source: §7 · p. 14
- Estimating spreading and recovery rates in real campaigns is nontrivial, and sensitivity to estimation errors is identified as future work.Source: §7 · p. 15
Appendix A. Proof for Theorem 4.2 (Uniqueness of the Solution to the SIS Model)
The appendix establishes uniqueness for the SIS and SIR optimal-control solutions when the campaign deadline is sufficiently small. Its proof compares candidate solutions through state and costate estimates, with the SIR argument following the same technique.
Appendix A. Proof for Theorem 4.2 (Uniqueness of the Solution to the SIS Model)
- For sufficiently small deadlines, the appendix concludes that the SIS solution is unique.The proof compares two candidate solutions, transforms the state and costate variables, and combines estimates to show their equality.Source: Appendix A · pp. 15–16
- For the SIR model with direct recruitment and word-of-mouth control, the same estimation technique establishes uniqueness for sufficiently small deadlines.The appendix presents estimates from the state and costate equations before concluding that the solutions coincide.Source: Appendix A · pp. 16–17