Spread, then Target, and Advertise in Waves:
Optimal Capital Allocation Across Advertising Channels
Soheil Eshghi, Victor M. Preciado, Saswati Sarkar, Santosh S. Venkatesh,
Qing Zhao, Raissa D’Souza, and Ananthram Swami

arXiv:1702.03432v1 [math.OC] 11 Feb 2017

Abstract
We obtain optimal strategies for the allocation of influence budget across multiple channels and across time for an external
influencer, e.g., a political campaign, seeking to maximize its effect on an election given a network of agents with linear consensusseeking opinion dynamics. We show that for a general set of objective functions, the optimal influence strategy at every time
uses all channels at either their maximum rate or not at all. Furthermore, we prove that the number of switches between these
extremes is bounded above both by a term that is typically much smaller than the number of agents. This means that the optimal
influence strategy is to exert maximum effort in waves for every channel, and then cease effort and let the effects propagate. We
also show that at the beginning, the total cost-adjusted reach of a channel determines its relative value, while targeting matters
more closer to election time. We demonstrate that the optimal influence structures are easily computable in several practical cases.
We explicitly characterize the optimal controls for the case of linear objective functions via a closed form. Finally, we see that
in the canonical election example, identifying late-deciders approximately determines the optimal campaign resource allocation
strategy.

I. I NTRODUCTION
Opinions are important definers of real-world outcomes: they affect who is elected for political office [1], which policies
are successful [2], and which products are bought by customers [3]. The proliferation of online media has complicated [4],
sped up [5], and enhanced [6] opinion change processes. The opinion change process can be affected by interested parties
through advertising channels, which are media by which messages are distributed to a target audience. Political campaigns and
marketing departments apportion their advertising budgets between such channels (e.g., TV ads, website banner ads, billboards)
in order to maximize some ultimate goal (e.g., votes, sales) [7]. The importance of this decision has increased in conjunction
with the increasing resources devoted to these efforts: the 2016 US election campaigns, for example, were estimated to spend
$4.4 billion on TV advertising alone [8], while worldwide total marketing spend was estimated to be over $1.6 trillion [9].
Thus, studying the related multi-channel resource allocation problem is both timely and significant.
In particular, influence on opinions can be classified into two types based on its direct provenance: in the endogenous
influence mechanism (e.g., word-of-mouth), individuals process the expressed opinions of other individuals they meet, and
consider their credibility and the level of acquaintance and trust in synthesizing a new opinion based on the information.1
This leads to the notion of an endogenous influence weighted graph that captures these (consensus-seeking) processes. On
the other hand, in the exogenous influence mechanism, an external influencer seeks to convince an individual to change their
mind. This mechanism is facilitated by various advertising channels2 in the opinion formation model that have a channel reach
structure (which denotes the nodes that can be reached by a particular channel) that is not necessarily related to the endogenous
neighborhood. The actions of other influencers also affect each individual’s opinion change process, which can in general be
random (noisy) process. The influencer seeks to maximize a function of the global state (the vector of individual opinions) at
a specific time (corresponding, for example, to an election or a new product launch) by controlling how much of their budget
they will allocate to each costly advertising channel at their disposal at various times (see Fig. 1). In this paper, we study the
nature of these optimal allocations and provide structures and algorithms for their computation.
However, this apportioning decision is complicated by several factors: 1- The reach of each channel is limited, and there
are significant overlaps in the target audience of various channels [11]. 2- Different channels have differing costs, and attempts
to influence opinions by external sources can affect individuals in different, and sometimes opposite, ways [12]. 3- The
apportioning decision is dynamic (depends on time) and changes with the state of the network, and therefore constitutes an
optimization in the space of functions.
Soheil Eshghi is with the School of Electrical Engineering, and Yale Institute of Network Science (YINS), Yale University, New Haven, CT 06520

soheil.eshghi@yale.edu
Victor M. Preciado, Saswati Sarkar, and Santosh S. Venkatesh are with the School of Electrical and Systems Engineering, University of Pennsylvania,
Philadelphia, PA 19104 preciado, swati, venkates@seas.upenn.edu
Qing Zhao is with the School of Electrical and Computer Engineering, Cornell University, Ithaca, NY 15853 qz16@cornell.edu
Raissa D’Souza is with the Departments of Computer Science and Mechanical and Aerospace Engineering, University of California, Davis, Davis, CA
95616 raissa@cse.ucdavis.edu
Ananthram Swami is with the Army Research Laboratory, Adelphi, MD 20783 aswami@arl.army.mil
The work of Eshghi, Zhao, D’Souza, and Swami were supported in part by the Army Research Laboratory Network Science CTA under Cooperative
Agreement W911NF-09-2-0053.
1 These weights can, in general, be dynamic, even depending on the expressed opinion [10]. In this work, we consider static weights.
2 Throughout this work, we use the word channel to represent both the medium (e.g., TV advertising) and the reach of the medium (e.g., people who watch
TV) – the distinction is clear in context.

Fig. 1: Different advertising channels have differing, possibly overlapping, reaches and come at differing costs. Furthermore, the
effect of a channel may be different on various individuals. These external influences are modulated by internal conversations
within the network whereby agents integrate this information with that of their neighbors. The decision of the advertiser,
therefore, is to apportion resources between these channels factoring in these complexities so as to get an optimal return on
investment, which in the election example is votes cast in favor of the campaign.

Furthermore, the influencer faces several trade-offs: influencing a channel earlier allows the influenced individuals to spread
the effect to their neighbors (diffusion), while lessening the impact on the influenced individuals as they moderate the effects of
the external influence with the opinions of their neighbors (dilution). There is also a trade-off between utilizing cheap channels
versus utilizing expensive but effective ones. These competing forces make the a priori determination of optimal influence
allocation hard to determine.
There are also significant technical challenges to solving this problem, as characterizing the optimal allocation of budget to
channels requires characterizing the structure of an optimal constrained vector of controls over a graph. There does not exist
a general theory of the structure of vector optimal controls that would define the nature of these controls, much less so in the
presence of a general graph structure. Furthermore, the work also requires computing the optimal control of the well-studied
linear consensus dynamics [13], [14] in a novel setting, as the classical literature is concerned with reaching agreement among
agents, while our objectives may incentivize agreement in some circumstances and disagreement in others. Thus, finding the
new allocation requires a new synthesis of spectral graph theory and optimal control theory.
Contributions: In this work, we model the advertising influence problem as a constrained graphical consensus control process
(without requiring the homogeneity and independence assumptions of epidemiological models gfor the same process [15]) with
overlapping exogenous influence channels and the endogenous influence of agents upon each other [16]. Using Pontryagin’s
Maximum principle, spectral graph theory, and custom analytical arguments, we determine the structure of optimal the allocation
of capital to the various influence channels at various times during the time horizon.
We show that for a general class of objectives, the optimal control for each of the channels is bang-bang (only takes its
extreme values), with the number of switches being upper-bounded by a term3 which is itself upper-bounded by the number
of individuals. These structures mean that the search for optimal controls can be conducted on the space of vectors of a fixed
size rather than on the space of functions.
Furthermore, for the case of a linear objective (i.e., when individuals make a decision in proportion to their opinion), we
explicitly calculate the candidate optimal controls, providing an open-loop algorithm with respect to the dynamics that can
compute the vector of optimal controls in a logarithmic number of steps. This allocation also implicitly determines the relative
criticality of a particular channel to the global objective, and thus defines an explicitly computable metric for the influence
of a channel at any given time that allows the influencer to compare and contrast the effects of different channels, as well as
the effect of a channel at different times. We prove that reaching likely voters is useful for ranking the influence of channels
3 The

number of non-zero elements in the orthogonal projection of the channel influence vector on the eigenvectors of the consensus dynamics

only close to decision/election time, while the cost-effectiveness of a channel (defined as its total reach divided by its cost) is
more important at earlier times.
For the case where the objective is a sum of sigmoids (e.g., individuals make a decision whether they are convinced or not
by a specific party before deciding to vote), which is a relaxed version of voting between two alternatives, we show that the
optimal control can be approximated just by knowing the agents who change their minds at the terminal time in the optimal
allocation (late-deciders [17]).
In sum, the work represents a new confluence of the literature on consensus dynamics and optimal control theory, while
providing significant novel structures, computational algorithms, metrics, and insights to the optimal capital allocation for
advertising problem.
II. L ITERATURE R EVIEW
As this work draws upon the literature in multiple areas, we will discuss antecedents in each area in turn:
Consensus: Linear consensus-seeking dynamics are some of the oldest models used to model the spread of opinions [18]. In
these models, opinions (states) are taken to be continuous, and each node uses a (weighted) average opinion of its neighbors’
opinions in each time-step to update its opinion. Continuous-time variants of these dynamics, as well as the closely related
literature on flocking [19] have have been rigorously studied by control theorists [13], [14], [20]. Most of these results focus on
asymptotic properties of these dynamics and their convergence, and not on their finite-time behavior and the effect of influence
on such behavior.
Control of Opinion Propagation: The case of affecting the outcome of such opinion dynamics is a research question that
has only recently been studied. Yildiz et al. [21] consider the case of stubborn agents who refuse to change their opinions
in a two-opinion voter model. They show that the mean average opinion is only a function of the structure of the network
and the placement of the stubborn nodes. They then investigate the optimal placement of these stubborn nodes. Kempe et al.
[22] and Anshelevich et al. [23] also discuss how to contain the spread of an opinion through an optimal initial placement
of stubborn nodes holding opposing opinions for differing models of opinion propagation. However, the focus of all of these
papers has been on static optimization, i.e., actions that are taken at a specific point in time. On the other hand, social networks
are naturally dynamic, i.e., their states are time-varying, and it is natural to assume that actions prescribed to affect them can
also be dynamic. Such optimal actions (henceforth referred to as controls) can be derived using optimal control theory.
Linear Optimal Control: Optimal control theory has addressed issues of linear control in detail [24]–[26]. Results on the
bang-bang nature and the finite number of switches in linear optimal control in the case where actions are not costly and the
time horizon is not fixed are well known [24]. However these results do not apply directly in the case with costly actions and
where the goal is not to drive the system to a known state in minimum time. Therefore, the current work represents a step
beyond those results and provides a context-specific method of evaluating the relative value of influence on a channel at all
points within a time horizon, a question of practical importance that was not addressed by this strain of work.
Optimal Control of Epidemic Spread and Diffusion: This work bears a similarity with the literature on the optimal control
of information spread, in that both aim to optimize a terminal function subject to some spread dynamics. Most such work uses
compartmental epidemic models (e.g., SI [15], [27]) and is thus dissimilar in dynamics to the one we consider. Furthermore,
we show that when opinions can take continuous values (instead of the finite fixed values assumed in compartmental models),
the optimal controls for influence maximization are significantly different to the structures proposed for information spread
(which typically advocate some form of maximal spreading at the start of the time interval [27], [28]). The model also allows
an even more explicit incorporation of graph structure than metapopulation models, e.g., [29], as their approximation breaks
down when the population of each patch/type is small, and therefore provides a poor model for interactions at the scale of
individuals.
Adversarial Sensor Network Deception:Finally, the problem discussed in this paper has a direct analog in the optimal
deception of a sensor network by an adversary, as discussed in [30]. In this setting, a state-estimation sensor network [31]
can be misdirected through local noise injection at a fixed number of points, that will effect a subset of nodes in the vicinity.
The optimal locations and patterns for the noise to affect the conclusion of the network will depend also on the dynamic
information fusion model of the sensor network and its relationship with the reach of each of the noise injection points. This
problem, too, will require the same type of exogenous influence and endogenous processing model as the opinion influence
problem, as well as having the same objective structure. Thus, any structural results obtained will have direct implications for
the adversary’s optimal deception policy.
In summary, the work integrates elements of the rich literature in linear consensus protocols, spectral graph theory, and
optimal control, and applies the synthesis to the problem of resource allocation in advertising, achieving strong structural
guarantees and applied insights.
III. S YSTEM M ODEL D ESCRIPTION
In this section, after presenting our notation (§III-A), we outline our system model (§III-B) and its dynamics (§III-C). Then
we outline the bounds on the actions of the influencer (§III-D) and describe their objective (§III-E). We finish the section by
presenting a technical assumption (§III-F) and by stating the overall problem (§III-G).

Fig. 2: Each agent takes into account the options of its neighbors in updating its own opinion. The weight given by node i to
the opinion of its neighbor j is a measure of how much it trusts their appraisal. If agents i and j are not neighbors, we will
have aij = 0 by default. In our model, we assume that neighborhood is a symmetric relation and that aij = aji , i.e., trust is
a symmetric relation.

A. Notation
xi (t) = opinion of agent i at time t
uk (t) = influence on channel k at time t
aij = magnitude of effect agent j’s opinion on the opinion of agent i
Ni = neighbors of agent i in G
bik = relative magnitude of the effect of influence on channel k on agent i in channel k
ei (t) = sum effect of other influence on agent i at time t
T = terminal time
ck (·) = cost of influence on channel k
r = total resources of influencer over the time period
Ji (·) = Value of opinion of agent i at time T to influencer
J(·) = Value of opinion profile at time T to influencer

→, and the
For compactness, we use [n] to represent {1, 2, . . . , n}. For a matrix W, we denote the k-th column of W as −
w
k
−→
k-th row of the same as Wk . Furthermore, we use wij to denote the (i, j)-th element of the matrix W.
B. System Model
We assume that the system contains n agents, with the (continuous valued) state/opinion of agent i ∈ [n] at time t denoted
by xi (t) ∈ R. Each agent communicates with other agents based on an edge-weighted undirected connected communication
graph G = (V, E, A)4 . The (non-negative) weight on an edge between agents i, j ∈ [n], which determines the relative weight
agent i gives to agent j in its state update, is represented by aij , and the matrix of such weights is represented by A. An
agent j is said to be a neighbor of agent i (and vice versa) if aij > 0 (See Fig. 2).5
At each time t, each agent updates their state based on a weighted average of the difference of its current state and that of its
neighbors, as well as the influence that will be described below, and a known drift signal (which may be due to the influence
of other competing influencers), which we denote by ei (t) for i ∈ [n]. The linear averaging model of opinion updates has
a long history in opinion and social influence studies, both in continuous time (the celebrated model of Abelson [32], [33]
which serves as a building block for this model) as well as in discrete time [18], [34], as well as being a well-studied model
of consensus [13], [35]. Mathematically, it can be thought of as a gradient descent algorithm implemented by agents seeking
to minimize disagreement (measured by Laplacian potential) [35].
An influencer aims to shape the opinion profile (i.e., the opinion vector of all agents) at a fixed terminal time T according
to its objective function through the judicious use of its fixed, known influence channels. Each channel of influence (e.g.,
advertising medium) is limited in its reach.
We say that any channel only affects a specific subset of agents, hence called a channel. The structure of these channels is
pre-specified and captured in a hyper-graph G0 = (V, H) on the same node set. There are |H| = m hyper-edges (channels)
that can be influenced, with the assumption that influencing a channel only directly affects the members within that channel.
The influence exerted by the influencer on channel i ∈ [m] is denoted by the scalar ui .
In this model, the effect of influence on a channel can differ on all agents within the channel, potentially even having opposite
effects. These effects are captured by the influence gain: bik determines the linear relative gain of influence on channel i ∈ [m]
4 However,
5 While

the results can be generalized to weighted directed graphs in which the weighted Laplacian has a generalized Jordan form with real eigenvalues
negative weight updates are conceivable, they will not be considered in this paper.

on agent k ∈ hi within that channel. If agent k is not within channel i, we define bik to be zero. Without loss of generality,
we assume uk ≥ 0 for k ∈ [m], and encode the possible negative effects in the respective gains. Stacking these values into a
matrix Bn∗m captures the hypergraph structure of the channels. The linear approximation of the effect of external influence
on opinion dynamics is also a long-standing tradition [33], [36].
C. Dynamics
To understand the dynamics, we provide the following discrete-time intuition: an agent i ∈ [m] constructs its change in state
in the time interval (t, t + ∆) based on the weighted difference between its own state and that of its neighbors, as well as the
influence exerted on it in that time period and the drift signal:
X

X
xi (t + ∆) = xi (t) + ∆
aij (xj (t) − xi (t)) +
bik uk (t) + ei (t) .
j∈Ni

k:i∈hk

This simply states that agents attempt to align their state/opinion with that of their neighbors, and the influencer’s effort acts
as a hindrance to that process. Note that the above can be re-written to represent the classic discrete-time consensus model
[18] with influence:6
 X

X
X
∆aij xj (t) + ∆
bik uk (t) + ei (t) .
aij )xi (t) +
xi (t + ∆) =(1 − ∆
j∈Ni

j∈Ni

k:i∈hk

Subtracting xi (t) from both sides, dividing by ∆ and taking the limit as ∆ goes to zero, we arrive at the following continuous
time agent-level dynamics:
X
X
X
X
X
ẋi (t) =
aij (xj (t) − xi (t)) +
bik uk (t) + ei (t) = (−
aij )xi (t) +
aij xj (t) +
bik uk (t) + ei (t)
j∈Ni

j∈Ni

k:i∈hk

j∈Ni

k:i∈hk

We let L be the weighted Laplacian matrix, where for all i, j ∈ [n] such that i 6= j, lij = −aij , and lii =
i ∈ [n]. Stacking these equations, we arrive at the following system-level dynamics:
→
−̇
−
→
−
−
x
(t) = −L →
x
(t) + B
u
(t) + →
e
(t)

P

j∈Ni

aij for all

(1)
n∗m m∗1
n∗1
→
−
−
→
We assume that the states/opinions at time 0 are known ( x (0) = x0 ), however we will see that the value of the states at
time 0 has no direct bearing on our structural results.
n∗1

n∗n

n∗1

D. Admissible Control Strategies
The total expenditure on all channels is bounded by r > 0, the amount of capital available to the influencer. This is captured
through the following capital constraint:
Z TX
m
ck (uk (t)) dt. ≤ r (budget constraint)
(2)
0

k=1

Assumption 1. We assume that for all k ∈ [m], ck (·) is increasing, differentiable and concave. Furthermore, without loss of
generality, we assume that ck (0) = 0 for all k ∈ [m].
This models the high start-up cost of utilizing a channel relative to the diminishing cost of additional influence once a
channel is already being influenced. Nevertheless, the above assumption allows the case where ck is linear.
We assume that for all channels k ∈ [m], the influence that can be exerted on channel k at any time t is bounded above by
a time-varying value umax
(t).7 This can capture both physical limits on the influence (i.e., availability of media) and limits
k
on the susceptibility of agents to the influence. Note that we only require umax
(t) to be differentiable, which is not a strong
k
assumption. This includes the case where umax
is a constant.
k
∀k∈[m] 0 ≤ uk (t) ≤ umax
(t) (influence constraint)
k

(3)

−
We will restrict ourselves to →
u that are piecewise continuous (i.e., that only have a finite number of discontinuities)8 . We shall
use U to denote the set of such controls that fulfill (3):
−
U := {→
u : 0 ≤ u (t) ≤ umax (t), k ∈ [m], t ∈ [0, T ]}
k

k

In our model, employing channel k ∈ [m] at effort level u at time t ∈ [0, T ] incurs a cost of ck (u), where for all k ∈ [m],
ck (·) : [0, maxt∈[0,T ] umax
(t)] → [0, +∞). Note that we assume that for all k ∈ [m], ck (·) is time-invariant.
k
6 The results derived in this paper would also apply to the Friedkin and Johnsen model of opinion updates [36] given uniform susceptibility to change across
agents.
7 This rules out impulse controls.
8 Note that this means, in particular, that the integral in (2) is well-defined

E. Objective
The objective of the influencer is a function of the opinion profile at a fixed time T . The nature of the function will depend
on the information aggregation method employed by the set of individuals. We consider the most general case, where any
increase in the opinion of any particular individual at time T (keeping all other opinions the same) is not detrimental to the
influencer. This is obviously the case in both political and marketing campaigns.
While our reasoning applies to a general family of objective functions, we will give special consideration to functions that
model voting in an election between two options (relevant in the political campaign setting) and weighted averaging (relevant
in estimating total returns from marketing efforts and in the sensor network setting).
−
−
Assumption 2. The objective, J(→
x (T )), is an increasing9 , differentiable function of vector of terminal opinions (→
x (T )).
In particular, we will mention the application of our results to a particular family of objective functions that are separable
in the elements of the vector of opinions:
−
J(→
x (T )) =

n
X

Ji (xi (T )).

(4)

i=1

Two specific types of separable functions are of interest:
1) Linear functions:
Ji (xi (T )) = pi xi (T ),

pi > 0,

(5)

which model the simplest case, where the utility the influencer gains from an individual has a linear relationship with its state
at time T . In the marketing example, this can model the amount of sales as a simple function of an individual’s opinion of
a product. This is also a useful approximation in the intruder detection case where the utility for the influencer is a simple
function of a sensor’s report level. The mapping of the election example to this utility is not direct: this can model the case
where each agent votes with probability pi , and if it does, chooses among two options with a probability that is linearly related
to their opinion (i.e., they flip an appropriately weighted coin). However, finding the correct total weight of the coin to be
considered depends on the assumptions made by the modeler, and multiple normalizations may be defensible. This ambiguity
leads to the definition of a second type of utility for the specific case of the election example.
2) Sigmoid functions: Assume each individual i ∈ [n] has to vote for one of two options/candidates/products/policies (0
and 1) at time T , and that the influencer backs option 1 (without loss of generality). Each individual is assumed to vote with
probability pi > 0, and to choose who to vote for among two options based on whether their state at time T is above or below
a agent-specific threshold θi (which models the various biases for and against an option). Thus, the utility gained from each
individual can be modeled using a Heaviside function with a jump at θi (h(xi (T ) − θi ) (which is agent i’s vote):
Ji (xi (T )) = pi h(xi (T ) − θi ).
However, this utility is discontinuous at xi (T ) = θi , which complicates analysis. The sigmoid (see Fig. 3):
pi
,
(6)
Ji (xi (T )) =
−α
i
1 + e (xi (T )−θi )
is a smooth approximation to the Heaviside utility, with the closeness of the approximation being determined by the choice of
the parameter αi — the greater αi is, the faster the transition. In the extreme of taking αi to infinity, this function will indeed
converge to the aforementioned Heaviside function.
F. Technical Assumption
We now add some technical assumption that will be needed in our arguments:
−
∂J(→
x (T ))
Assumption 3. There exists a j ∈ [n] such that
> 0 for all x(T ) ∈ R.
∂xj (T )
Note that this is equivalent to saying there exists at least one individual such that the influencer always values a marginal
increase in its state. That is, holding all opinions the same, any increase in that agent’s opinion will be translated to a strict
increase in their likelihood of voting for the choice backed by the influencer.10 The purpose of this assumption is to rule out
a pathological case where the necessity conditions for the optimality of an allocation become so general that they apply for
all controls and are thus uninformative.
9 Note

that this encodes the non-negative benefit of an increase in opinions at time T to the influencer.
−
→
that this rules out J(·) functions with stationary points, i.e., those for which ∇x(T ) J(x(T )) = 0 for some x(T ) ∈ R.

10 Note

Fig. 3: The sigmoid function is a smooth approximation to a Heaviside step function. It maps the opinions of an agent into
their probability of voting for the option favored by the influencer. The parameter θi determines the convincing threshold for
individual i, where the probability the agent votes for the favored option increases significantly if they are convinced beyond
their threshold. The parameter αi determines the sharpness of this dependence on the bias - large αi model an abrupt transition
from not voting for the choice to voting for it given a small change of opinion, while smaller αi represent a more gradual
transition.
G. Problem Statement
−
We aim to find analytical and computational structures for the controls that maximize J(→
x (T )) under the dynamics outlined
in (1) and with constraints (3) and (2) on the controls:
max
s.t.

−
J(→
x (T ))
→
−̇
−
−
x = −L→
x + B→
u
0 ≤ um (t) ≤ umax
∀m
m ,
Z T X
M
cm (um (t)) dt ≤ r
0

m=1

→
−
u ∈U

In the most general case, this problem has a general-form, potentially non-convex objective function, as well as a potentially
non-convex budget constraint (when any of the ci (·)’s is strictly concave). Furthermore, the number of competing influence
channels, m, and therefore the number of optimization variables, can potentially be large. These factors complicate naive
approaches to solving the problem.
We reformulate the problem with auxiliary variables to aid the analysis. We define the auxiliary variables γ and q such that,
m
X
γ(0) = 0,
γ̇(t) = −
ck (uk (t)),
(7)
k=1

q(0) = 0,

q̇(t) = 1, (proxy for time).

(8)

As can be seen, γ(t) is the running cost of the influence up to time t, and q is a proxy for time. Thus, the capital constraint
becomes γ(T ) ≥ −r, and the integral constraint has been transformed to a terminal time one. So we can rewrite the optimization
as:
−
max
J(→
x (T ))
(9)
s.t.

→
−̇
−
−
−
x (t) = −L→
x (t) + B→
u (t) + →
e (t),
m
X
γ̇(t) = −
ck (uk (t)), q̇(t) = 1,
→
−
u ∈ U,

k=1

γ(T ) ≥ −r.

IV. R ESULTS
In this section, we outline the analytical structures of the optimal controls. To show the nature of the results, we first explain
some necessary priors §IV-A. Then we prove the existence of optimal controls §IV-B (under some conditions) and identify

their structure using our main theorem §IV-C (proved in §IV-D). A refinement is presented for the case of the linear objective
§IV-E that allows the direct computation of the control and shows that the optimal control is unique, while providing insight
into the logic of the allocation decision. Finally, the sigmoid approximation to voting is revisited §IV-F and an approximation
to the optimal control is presented.
A. Preliminaries
For an undirected, connected graph G, the weighted Laplacian matrix L will be real and symmetric (i.e., L will be
Hermitian), and therefore L will be positive semi-definite and will have real, non-negative eigenvalues [37, page 13]. Thus,
it will have an eigen-decomposition [38, Appendix A.5] (i.e., L = QΞQT , where Q is an orthogonal matrix where all
columns are eigenvectors of L and Ξ is a diagonal matrix where the diagonal elements are eigenvalues of L). 11 The smallest
eigenvalue will be zero and will have multiplicity 1 (as L is row-stochastic and G is connected) [37, page 13]. We will order
→
−
the eigenvalues of Ξ smallest to largest (ξ1 = 0 < ξ2 ≤ . . . ≤ ξn ) and therefore column i ∈ [m] of Q, Q i will be the i-th
→
−
→
−
→
−
eigenvector of L12 . Note that this means that Q 1 = √1n 1 n , where 1 n = (1, . . . , 1)T .
We now state and prove a lemma that shows optimal controls for the main problem exist. We then provide the claim of our
main result (Theorem 1) and then present a subcase where the bound can be significantly strengthened and the optimal control
can be calculated open-loop (Theorem 2). We provide proofs of these results in the subsequent subsection (§IV-D).
B. Existence of Optimal Solutions
We now prove that optimal controls for (9), and therefore our original problem, exist when ci (·)’s are linear.
Lemma 1. Optimal controls for problem (9) exist for linear ci (·)’s.
−
Proof. The solutions to the dynamics ODEs (1), (7), and (8) exist for all →
u ∈ U as the RHS terms are locally Lipschitz. We
→
−
also have that for every (t, x (t), γ(t), q(t)), the set:


m
X
−
−
−
−
ck (uk (t)), 1 →
P := (−L→
x (t) + B→
u (t) + →
e (t))T , −
u m∗1 (t) : 0 ≤ uk (t) ≤ umax
(t),
k
∈
[m]
k
k=1

is compact, as the domain is compact and the functions are continuous. P is also convex, as in the first n dimensions, it
is mapped linearly from a convex set, in the n + 1-th dimension it is also a linear mapping from a convex set (for linear
ci (·)), and it is constant in the n + 2-th dimension. Thus, according to Filippov’s theorem [25, page 119], the reachable set
→, 0, 0) := {(→
−
−
→, γ(0) = 0, q(0) = 0, u ∈ U} from (−
→, 0, 0) is compact and convex. The
R T (−
x
x (T ), γ(T ), q(T )) : →
x (0) = −
x
x
0
0
0
reachable set will still be compact and convex if we restrict it by only looking at controls that lead to γ(T ) ≥ −r (as it is
−
an intersection of two convex sets).13 By the Weierstrass theorem [25, page 7], the continuous function J(→
x (T )) will have
a global maximum on this closed, compact set. Thus, by the definition of the reachable set, there will exist an control that
steers the state to this global maximum, and all such controls will thus be optimal.
C. Structural Results for the Optimal Control
Theorem 1. For all i ∈ [m] and
for theE case where
D→
− →
−
• ci (·) is strictly concave,
B i , 1 n 6= 0, and umax
(t) is constant
i
−
→
• ci (·) is linear and the system (L, LBi ) is controllable [40, p. 144]
1) Optimal controls are bang-bang, taking on their maximum or minimum values at all times t (u∗i (t) ∈ {umax
, 0}).
i
2) The number of switches between these values is bounded above:
D→
− →
− E
a) In the general case, by one less than the number of non-zero elements in { Q j , B i }N
j=1 .
D→
Pj
− − ED→
− →
− E
→
−
→
−
→
−
N
p
Qj, B i .
b) For J( x (T )) = h p , x (T )i, by the number of of sign variations in { k=1 sk }j=1 , where sj := Q j , →
An example of an optimal control with these characteristics is provided in Fig. 4. The proof of this theorem is presented in
§IV-D. The actual number of switches of each optimal control can be significantly less than the fixed upper-bound of N − 1
(which can in general be very high). The conditions in the statement of the theorem rule out pathological cases where the
necessary conditions for optimality derived from the Maximum Principle [26, page 182] do not rule out singular arcs [25, page
113] within the optimal controls.14
Note that the theorem conditions can apply for some i ∈ [m] and not others, in which case the derived structure only applies
to those i that fulfill the conditions of the theorem.
11 However,
12 Notice

the reasoning below applies to any L that has a generalized Jordan form with real eigenvalues.
this is possible because L is Hermitian and therefore the geometric multiplicity of all eigenvalues is equal to their algebraic multiplicity [39, page

6-5].
−
→
→
13 This set is non-empty because −
u (t) = 0 for all t is a member.
14 Singular arcs are those for which control does not affect the Hamiltonian, and thus the Hamiltonian-maximizing condition of the maximum principle is
silent on the optimal value of the control over that arc.

~ i fulfilling the conditions of Theorem 1, the optimal control ui (t) will be bang-bang, only taking its
Fig. 4: For a ci (·) and B
minimum or maximum values and switching between them a bounded number of times. Note that the function can be fully
described by the set of switching times {τi }i , making them easier to compute, store, and implement.

D. Proof of Theorem 1
We define costate variables corresponding to each of the state variables in (9), as summarized in Table I. Now, for this new
state variable
costate variable

−
→
x
−
→
Λ

γ

q

β

z

TABLE I: Correspondence between the state variables and their respective co-state variables.
system of equations, we define the Hamiltonian as:
m

X
→
−
→
−
→
−
→
− −
−
−
−
−
H(→
x (t), γ, q, Λ , β, z, →
u (t)) = − Λ T L→
x + Λ T B→
u + ΛT→
e (q) − β
ck (uk ) + z,

(10)

k=1

where for the continuous costate functions we have (at points of continuity of the controls):
→
−
→
−̇
dH
dH
= LT Λ (t), β̇(t) = −
= 0,
Λ (t) = − →
−
dγ
dx
 →

−
dH
d−
e (q) →
ż(t) = −
=−
,Λ ,
dq
dq

(11)
(12)

with terminal state constraints:
−
−
→
−
λ0 ∂J(→
x (T ))
λ0 ∂J(→
x (T ))
Λ (T ) =
≥ 0, z(T ) =
= 0,
→
−
∂z(T )
∂ x (T )
β(T ) ≥ 0,
β(T )[γ(T ) + r] = 0,

(13)
(14)

with λ0 ∈ {0, 1}.
For the case of the sigmoid cost function in (6), this means
λi (T ) =

λ0 αe−α(xi (T )−θi )
1 + e−αi (xi (T )−θi )

2 ,

(15)

while for the linear cost function (5), we will have:
λi (T ) = λ0 pi .

(16)

Now, Pontryagin’s Maximum Principle (PMP) [26, page 182] gives us the following necessary conditions for an optimal
control:
If:
−
→∗
• u ∈ U is the piecewise continuous optimal control,
−
→∗ ∗ ∗
• x , γ , q are state trajectories to (9) under the optimal control,
−
→∗ ∗ ∗
• Λ , β , z are continuous co-state real-valued functions on [0, T ] that satisfy the terminal time constraints (13) and (14),
and dynamics (11) and (12) at points of continuity of the controls,
−
then for any control →
u ∈ U that respects (2), the following holds:

1) For all 0 ≤ t ≤ T :
−
→
−
→
−
→
−
→
→
−
−
H(x∗ (t),γ ∗ , q ∗ , Λ∗ , β ∗ , z ∗ , u∗ (t)) ≥ H(x∗ (t), γ ∗ , q ∗ , Λ ∗ , β ∗ , z ∗ , →
u (t)),
(17)
−
→
→
−
2) (λ0 , Λ∗ (t), β ∗ (t), z ∗ (t)) 6= 0 n+3 for all 0 ≤ t ≤ T .
Since β˙∗ (t) = 0 (11) for all times at which the controls are continuous, and also due to continuity of the co-states, we obtain:
β ∗ (t) = β ∗ (T ),

∀t∈[0,T ] .

(18)

For i ∈ [m], we will use ϕi (t) to denote the part of the Hamiltonian (10) that depends explicitly on ui . Therefore for all
i ∈ [m] (using (18)):
D−
→
−
→E
ϕi (ui , t) := Λ∗ (t), Bi ui − β ∗ (T )ci (ui ).
(19)
The point-wise Hamiltonian maximizing condition (17) of the PMP leads to the fact that ϕi (u∗i , t) ≥ ϕi (ui , t) for all t
(t)]. Now, due to the differentiability of the co-states, ϕi (·) is a convex function of the bounded ui (t),
and all ui ∈ [0, umax
i
and thus it will be maximized either at one of the upper- or lower-bounds of ui (t), or it will have the same value for all
ui ∈ [0, umax
(t)]. This is because due to the convexity:
i

ui
ui
ui
ui
∗ umax
(t), t ≤ (1 − max ) ∗ ϕi (0, t) + ( max ) ∗ ϕi (umax
(t), t))
ϕi (ui , t) = ϕi (1 − max ) ∗ 0 + max
i
i
ui (t)
ui (t)
ui (t)
ui (t)
ui
ui
≤ (1 − max
+ max ) ∗ max{ϕi (0, t), ϕi (umax
(t), t))} = max{ϕi (0, t), ϕi (umax
(t), t))}.
i
i
ui (t) ui (t)
We will now present different arguments for how the Hamiltonian maximizing condition is refined for strictly convex and
linear ck (·) functions. Note that the arguments in each case only depend on the nature of ck (·), and thus we also consider
−c (·) that simultaneously have elements that are linear and strictly concave:
vector function →
1) For the case of strictly concave
ci (·), Theorem
1 only considers cases where umax
(t) = umax
, i.e., is a constant. At
i
i
D−
→∗
−
→E
∗
each time t, ϕi (ui (t), t) = Λ (t), Bi ui (t) − β (T )ci (ui (t)) is convex in ui (t). Therefore, it is maximized either
at
its upperE or lower-bound (i.e., u∗i (t) ∈ {0, umax
}). Thus, it suffices to compare ϕi (0, t) = 0 and ϕi (umax
, t) =
i
i
D−
→∗
−
→ max
max
15
Λ (t), Bi ui
− βci (ui ). Thus, the Hamiltonian maximizing condition (17) becomes :

D−
→∗
−
→E

ci (umax
)
max
∗

i

Λ
(t),
B
u
,
if
i > β (T ) umax ,
i

i


D−
→∗
−
→E
ci (umax
)
∗
i
(20)
u∗i (t) = 0,
if
Λ
(t),
B
<
β
(T
)
,
i
umax

i


D
E

−
→
−
→

c (umax
)
?,
i
if Λ∗ (t), Bi = β ∗ (T ) iumax
.
i
D−

→
−
→E
2) For the case of linear ci (ui ) = vi ui , at each time t, ϕi (ui (t), t) = Λ∗ (t), Bi − β ∗ (T )vi ui . Thus, the Hamiltonian
maximizing condition (17) becomes:

D−
→∗
−
→E

max
∗


u
(t),
if
Λ
(t),
B
i > β (T )vi ,
i



D−
→
−
→E
u∗i (t) = 0,
(21)
if Λ∗ (t), Bi < β ∗ (T )vi ,



D
E

−
→
−
→

?,
if Λ∗ (t), Bi = β ∗ (T )vi .
As can be seen, the right-hand side of the condition terms in both cases (i.e., β ∗ (T )ci (umax
) in (20) and β ∗ (T )viDin (21)) is Ea
i
−
→
−
→
positive constant. Thus, the structure of the optimal control u∗i can be understood by examining the fluctuations of Λ∗ (t), Bi
c (umax )

i
and β ∗ (T )vi ).16
around two constant values (β ∗ (T ) iumax
i
We can trivially show, using the second PMP necessary optimality condition, that the optimal control is normal [25, page
82] (i.e., λ0 6= 0):

Lemma 2. There is no case for which λ0 = 0.
−
→
−
→
−̇
→
−
→
→
−
Proof. If λ0 = 0, from (13), Λ∗ (T ) = 0. As Λ∗ (t) = 0 n for all t is a solution of the differential equation Λ∗ (t) = LT Λ∗ (t)
with this condition, due to the uniqueness of solutions to differential equations [26, Theorem A.8] it is also the unique solution.
question mark denoting the fact that PMP does not uniquely determine the optimal u∗i at times t when ϕi (t, ui ) does not change with ui .
that according to the system model, ci (·)’s can potentially be a mix of linear and strictly concave, and the above statement for any concave or
linear ci (·) is independent of the nature of all other cj (·)’s (even if they were not concave at all).
15 The

16 Notice

Now, as z ∗ (T ) = 0 (13), the only way for
−
→
→
−
(λ0 , Λ∗ (T ), β ∗ (T ), z ∗ (T )) 6= 0 n+3
(which is the second necessary condition of the PMP) to hold is for β ∗ (t) = β ∗ (T ) 6= 0, which together with (14) leads to
β ∗ (T ) > 0. In this case, for all i, and for all t,
D−
→
−
→E
ϕi (ui , t) = Λ∗ (t), Bi ui − β ∗ (T )ci (ui )
= −β ∗ (T )ci (ui )
and therefore due to the Hamiltonian maximizing condition (17), u∗i (t) = 0 for all such i and all t. This leads to γ˙∗ (t) = 0 for
all t, and thus γ ∗ (T ) = 0. Therefore β ∗ (T )[γ ∗ (T ) + r] = β ∗ (T )r > 0, which is a contradiction with (14). Therefore λ0 = 0
−
→
→
−
leads to (λ0 , Λ∗ (T ), β ∗ (T ), z ∗ (T )) = 0 n+3 , a contradiction with PMP.
Thus, henceforth we will explicitly replace λ0 with 1, and we will have from (13) and Assumption 3 that there will exist a
j ∈ [m] such that:
λ∗j (T ) > 0.

(22)

D
E
~ i = constant:
Zeroes of Λ~∗ (t), B
D−
→
−
→E
In this subsection, we look at the dynamics of the function Λ∗ (t), Bi , especially with regards to how many times it can
fluctuate around a fixed value in the time-horizon. Note that any time that this function crosses the fixed value, due to (20)
and (21), it leads to a switch in the optimal control from one bound to another, and if it is equal to the fixed value over any
interval, then the PMP cannot uniquely determine the optimal controlD(i.e., the optimal
control is singular [25, page 113]).
−
→∗
−
→E
Henceforth, we shall use s ≥ 0 to denote the positive constant that Λ (t), Bi is set equal to. We claim that the expression
D−
→
−
→E
for Λ∗ (t), Bi = s, as a function of time t, at most has N − 1 roots. Therefore due to the continuity of each of the elements
−
→
of Λ∗ , we have that u∗i (t) is either equal to umax
(t), or 0 for all t except maybe at N − 1 points where it can switch between
i
those two values.
−̇
→
−
→
We know that Λ∗ = LT Λ∗ . So we have:
−̇
→
−
→
−
→
Λ∗ = QΞT QT Λ∗ = QΞQT Λ∗ ,
as Ξ is a diagonal matrix.
−
→
We define Y (t) := QT Λ∗ (t). As Q is an orthogonal matrix to each other, therefore
−̇
→
−
→
−
→
→
−̇
Y = QT Λ∗ = (QT Q)ΞQT Λ∗ = ΞQT Λ∗

⇒

→
−
→
−
Y = ΞY ,

−
→
→
−
with Y (T ) = QT Λ∗ (T ). Therefore, due to the uniqueness of solutions to ODEs [26, Theorem A.8], for all i ∈ [m]:
E
D−
→
→ −
yi (t) = yi (T )e−ξi (t−T ) = Qi , Λ∗ (T ) e−ξi (t−T ) .
Again using the fact that Q is unitary, we have:
D


N D
E
E
X
−
→
−
→
→
→
→
−
−
→ −
−
→ −
−
→
Λ∗ (t) = (QQT )Λ∗ (t) = Q Y = Q Qi , Λ∗ (T ) e−ξi (t−T ) =
Qi , Λ∗ (T ) e−ξi (t−T ) Qi .
i

i=1

So, we will have:
D
 X

N 
N D
D−
E
ED−
→∗
→∗
→∗
−
→E X D−
→ −
−
→ −
→E
−
→ −
→ −
→E −ξj (t−T )
−ξj (t−T )
Λ (t), Bi =
Qj , Λ (T ) e
Qj , Bi =
Qj , Λ (T ) Qj , Bi e
= s.
j=1

(23)

j=1

−
→
−
→
1 →
−
As {Qi }i is an eigenvector decomposition of L and therefore ξ1 = 0 and Q1 = √ 1 n , (23) becomes:
N


N
N
N
ED−
X D−
X

→
→ −
→ −
→E
1 X ∗
bhi − s = 0.
Qj , Λ∗ (T ) Qj , Bi e−ξj (t−T ) +
λk (T )
N
j=2
k=1

(24)

h=1

We now present separate arguments depending on whether any of the coefficients of the exponentials in (24) are non-zero
or not.
I) In the case where for some j > 1,
ED−
D−
→
→ −
→ −
→E
Qj , Λ∗ (T ) Qj , Bi 6= 0,

the following lemma provides the last step in the proof of our claim.17
Lemma
, M, P
and j = 1, · · · , wi such
PM3. For K > 1 and M ≤ K, let η1 > η2 > · · · > ηM > 0. Also, for i = 1, · · ·P
M
wi −1
that i=1 wi = K, let di,j be a real number. Then, if in the function f : R → R, f (t) = i=1 j=0
di,j tj ηit , we have
di,wi −1 6= 0 for all i, f (t) has at most K − 1 zeros.
The proof of this lemma is provided in §Appendix-A. Note
that this means
thatEthe number of zeros of (24) in this case
ED−
D−
→
→ −
→ −
→ N
Qj , Λ∗ (T ) Qj , Bi j=2 , which is itself bounded above by
is bounded above by the number of non-zero elements in
D−
−
→
→ −
→E N
Qj , Bi j=2 . This is significant because while Λ∗ (T ) is not known without the state dynamics (it
the number of zeros in
−
→
is a function of the unknown x∗ (T ), and thus implicitly depends on the trajectory), this bound applies to all possible state
→
−
trajectories (i.e., for all
x (0)).EThus the number of switches in this case is trivially bounded by one less than the number of
D→
− →
−
non-zero elements in { Q j , B i }N
j=1 .
ED−
D−
D−
→
→
→ −
→ −
→E
−
→E
Qj , Λ∗ (T ) Qj , Bi
II) This leaves the case where for all 2 ≤ j ≤ n,
= 0. This means that Λ∗ (t), Bi =
PN
PN
1
∗
))( h=1 bhi ), a constant, for all t.
k=1 λk (T
N(
P
PN
N
II-1) If N1 ( j=1 λj (T ))( h=1 bhi ) 6= s, (17) will become:

N
N
P
P


umax
(t), if (
λj (T ))(
bhi ) > sN,

i
j=1
h=1
u∗i (t) =
N
N
P
P



if (
λj (T ))(
bhi ) < sN.
0,
j=1

h=1

This is in keeping with the
statement ofP
the Theorem.
PN
N
II-2) Else we have N1 ( j=1 λj (T ))( h=1 bhi ) = s.
−
→
Since {Qj }nj=1 forms an orthonormal basis for Rn (due to the orthogonality of Q), this means that we can look at the inner
product in this basis:
N
N
N
ED−
ED−
D−
X
→
→
→
→ −
→E
→ −
→E D−
→ −
−
→E X D−
→ −
1 X ∗
λj (T ))(
bki )
λ∗j (T )bji = Λ∗ (T ), Bi =
Qj , Λ∗ (T ) Qj , Bi = Q1 , Λ∗ (T ) Q1 , Bi = (
N j=1
j=1
j=1

N
X

k=1

⇒

N
X
j=1

λ∗j (T ) bji −

1
N

N
X


bki = 0,

(25)

k=1

−
→
which defines a hyper-plane in the space of Λ∗ (T ). But from (24), we have that:
N
X

N
 1 X

λ∗j (T )
bki = s,
N
j=1

(26)

k=1

D−
−
→
→
−
→ E
another hyper-plane. Equations (25) and (26) define the Λ∗ (T )-space over which Λ∗ (t), Bi T = s for all t ∈ [0, T ], and thus
the Hamiltonian maximizing necessary condition (17) does not restrict u∗i over this interval. Such trajectories are known as
singular arcs [25, page 113].
We present different arguments depending on ci (·):
II-2-a) If ci (·) is strictly concave, then we utilize the generalized Legendre-Clebsch necessary condition of optimality on
d2 H
d2 H
singular arcs [41]: we must have →
 0. However,
= −β ∗ (T )c00 (u∗i ) ≥ 0, due to the strict concavity of ci (·). Thus,
−
2
du2i 
du

PN
PN
P
N
1
∗
∗
we must have β ∗ (T ) = 0. So (26) becomes:
j=1 λj (T ) N
k=1 bki = 0. This means that either
j=1 λj (T ) = 0 (a
PN
contradiction with (22)) or k=1 bik = 0 (ruled out by the statement of the theorem). Thus we have a contradiction, meaning
that this case will never arise.
D−
→
−
→E
II-2-b) If ci (·) is linear, we have: ϕi (ui (t), t) = ( Λ∗ (t), Bi − β ∗ (T )vi )ui . For the singular arc case, we must have
D−
→
−
→E
Φ(t) := Λ∗ (t), Bi − β ∗ (T )vi = 0 over all t. Thus, as this function is maximally flat, all its derivatives with respect to time
must also be zero (infinite-order singularity). We must have:

 D
−̇
→
−
→
→
−
→
−
→E −
−
→
dΦ(t)
= Λ∗ (t), Bi = LT Λ∗ (t), Bi = Λ∗T (t)LBi = 0.
dt
17 We state and prove a more general version of the lemma that also applies for the case where the geometric multiplicities of the eigenvalues may be less
than their algebraic multiplicities. This can include cases where L is not symmetric but has real eigenvalues.

Using an induction, we can see that for l ≥ 1:
→∗
→∗T
−
→E −
−
→
dl Φ(t) D T l −
Λ
=
(L
)
(t),
B
(t)Ll Bi = 0.
i =Λ
dtl
So we must have:




−
→∗
→
−
→
n−
= 0.
Λ (t), LBi | . . . |L Bi



−−−→
−
→
−
→
But we have λ∗j > 0 for some j (due to (22)), so Λ∗ (T ) 6= ~0n . This, however, means that we must have rank( LBi | . . . |Ln Bi ) <
−
→
n. However, since the system (L, LBi ) is controllable, this matrix must have row rank n (due to the necessary and sufficient
condition of controllability of linear systems [40, Theorem 6.1]). This is a contradiction, meaning that the singular case will
not arise in this case either.
This concludes the proof of part (2a) of the theorem. We now proceed to part (2b) of the theorem.
−−−→ −
−
−
−
When J(→
x (T )) = h→
p ,→
x (T )i, from (16), we have Λ∗ (T ) = →
p . Thus, we can refine the result stated in part (2a) using
this additional information into the result in (2b). We will, however, require differing, stronger arguments for argument I after
(24) to obtain the tighter bound on the number of switches (as all the cases in II are either trivial or are shown not to arise).
Thus, if we prove that:

N D
ED−
X
→ −
→E −ξj (t−T )
−
→ →
−
Qj , p Qj , Bi e
+
j=2

N
N

1 X X
pk
bhi − s = 0,
N
k=1

Pj
has at most { k=1 sk }N
j=1 zeros, where

(27)

h=1

D→
− →
− E
− − ED→
Qj, B i ,
p
sj := Q j , →

then we are done. This can be seen to be true due to the following generalization of Descartes’ rule of signs (due to [42] and
proved in §Appendix B), as applied to (27).
PN
−t ξi
Lemma 4. The number of positive zeros of the exponential polynomial function f : R → R, f (t) =
is
i=1 di (e )
Pi
upper-bounded by the number of variations in sign in the sequence {si }i , where si = j=1 dj .
E. Water-filling: Optimal Budget Allocation for the Separable Linear Objective
In the proof of Theorem 1, (19) coupled with the Hamiltonian-maximizing condition of the Maximum Principle led to (20)
and (21) as explicit necessary conditions for the optimal controls. We now integrate (23) explicitly into the aforementioned
−
−
−
necessary conditions for the case of J(→
x (T )) = h→
p ,→
x (T )i (i.e., the separable, linear objective). Define
D−
→∗
→ −
→E
−
→E D−
→ − ED−
hi (t) := Λ (t), Bi = Qj , →
p Qj , Bi e−ξj (t−T )
. Now, the concave ci (·) case becomes:




umax
,

i




u∗i (t) = 0,







?,

ci (umax
)
i
,
umax
i
ci (umax
)
i
,
if hi (t) < β ∗ (T ) max
ui
max
ci (ui )
if hi (t) = β ∗ (T ) max
.
ui
if hi (t) > β ∗ (T )

(28)

and for the linear ci (·):




umax (t), if

 i
u∗i (t) = 0,
if





?,
if

hi (t) > β ∗ (T )vi ,
hi (t) < β ∗ (T )vi , .

(29)

hi (t) = β ∗ (T )vi .

Notice that in (28) and (29), the only parameter unknown a priori is β ∗ (T ) (as all the elements in hi (t) are explicitly
−
computable without solving the optimal control problem). Thus, determining β ∗ (T ) will determine →
u (t) for all t except for a
finite, explicitly bounded number of points (notice that the existence of singular controls was ruled out
the proof of Theorem
R T in
Pm
1). However, β ∗ (T ) has to satisfy (14), which means β ∗ (T ) > 0 if and only if γ(T ) + r = 0, or 0
k=1 ck (uk (t)) dt = r.
This last equation is the budget constraint.

Define the equivalent of (28) and (29) as functions of a variable β̂(T ):


)
ci (umax

i
umax
,
,
if
h
(t)
>
β̂(T
)
i

i
max

ui



ci (umax
)
i
ui (t, β̂(T )) = 0,
if hi (t) < β̂(T ) max
,

u

i



ci (umax
)

i

if hi (t) = β̂(T ) max
.
?,
ui

(30)

and for the linear ci (·):




umax (t), if

 i
ui (t, β̂(T )) = 0,
if





?,
if

hi (t) > β̂(T )vi ,
hi (t) < β̂(T )vi , .

(31)

hi (t) = β̂(T )vi .

One can see that in both cases, if βˆ1 (T) > βˆ2 (T ) ≥ 0, ui (t, βˆ2 (T )) ≥ ui (t, βˆ1 (T )) for all i and all t. This, along with
Assumption (1), leads to ci ui (t, βˆ2 (T )) ≥ ci ui (t, βˆ1 (T )) for all i and all t, culminating in:
Z
0

m
T X


ci ui (t,βˆ2 (T )) dt ≥

Z
0

i=1

m
T X


ci ui (t, βˆ1 (T )) dt.

(32)

i=1

−
−
As a corollary, (32) holds with equality if and only if →
u (t, βˆ2 (T )) = →
u (t, βˆ1 (T )) for all i and all t (excluding any switching
points). Thus, if
Z TX
m

ci ui (t, β̂(T )) dt = r,
0

i=1

−
→
−
then →
u (t, β̂(T )) = u∗ (t) also for all t. Therefore:
−
−
−
Theorem 2. For the case of separable, linear Ji (·) functions (5) for all i (i.e, J(→
x (T )) = h→
p ,→
x (T )i) the unique optimal
control can be explicitly calculated using a number of evaluations of (32) that is logarithmic in the range of considered β̂(T )’s.
This is because the process outlined above results in a simple algorithm to find β ∗ (T ) and solve the optimal control problem
using a single-shooting approach (which
 method of finding a zero of a function [38, page 484]). β̂(T ) is
R T Pmis akin to Newton’s
adjusted so as to find the root of 0
c
u
(t,
β̂(T
))
dt = r. This significantly decreases the complexity of calculating
i
i
i=1
the optimal control, as instead of evaluating
and
comparing
potential
optimal solutions that fulfill the necessary conditions

R T Pm
in Theorem 1, one can simply evaluate 0
c
u
(t,
β̂(T
))
dt
using
(30) and (31) over a number of iterations that is
i
i
i=1
logarithmic in the range of β̂(T ) under consideration to explicitly characterize the unique optimal control.
The procedure outlined above is also instructive in understanding the relative importance of different channels at different
hi (t)
umax hi (t)
for linear c(·) with
times graphically. In particular, we will be interested in comparing i max for concave c(·) and
ci (ui )
vi
β̂(T ) (as in (30) and (31)). One can think of the terms containing hi (t) as a topographic relief map, signifying hills and
valleys. β̂(T ) signifies a water-line, below which the valleys are flooded. The budget expenditure in this case is a monotone
function of the area above water (see Fig. 5). Therefore, the algorithm outlined is equivalent to adjusting the water-line so that
the budget expenditure (evaluated as a function of the land above water) matches the budget constraint.
Furthermore, the water-filling procedure shows the relative importance of the use of influence on any time and any channel.
umax hi (t)
As the optimal water-level is a monotone decreasing function of the budget available, one can see that the peaks in i max
ci (ui )
hi (t)
and
signify the time intervals and channels that would be prioritized when the budget is tight, while if the budget is
vi
increased, more and more channels will be utilized at an increasing set of intervals. This lends itself nicely to considering these
explicitly computable values as a direct metric for the effect of advertising on any channel at a given time on the outcome of
the election, which we shall henceforth call cost-effectiveness of a channel.18
One can extract some more insight from the structure of this metric to compare the relative importance of channels at a
given time t:
18 This

persists in the presence of any type of noise in the the state dynamics.

u1max

0
u2max

0

hi (t)
functions for the case of linear ci (·). Areas above the water-line (β̂(T ))
vi
max
translate to ui (t, β̂(T )) = ui (t), while those below translate to ui (t, β̂(T )) = 0. The amount of budget spent for this β̂(T )
can thus be calculated from the resulting ui (t, β̂(T )), and so β̂(T ) can be adjusted to find β ∗ (T ).
Fig. 5: Here, we demonstrate a case with two

1) If |T − t| >> 1 (i.e., early on), the deciding factor in comparing the cost-effectiveness of channels is their total reach
(across all nodes) per unit cost; for example, for the linear c(·) case:
PN
N
hi (t)
1 X
j=1 bji
pj )(
≈(
),
vi
N j=1
vi
2) However, if |T − t| << 1 (i.e., late on), targeting (e.g., how well a channel is aligned with the a priori likelihood of
people to vote) is more important than total reach; for example, for the linear c(·) case:
D −
→E
→
−
p , Bi
hi (t)
≈
,
vi
vi
This is instructive, as it shows that at the start of a campaign, cheap broadcast methods would be preferable to costly (premature)
targeting of likely voters, while as election day approaches, the alignment of a channel with the target demographic gradually
increases in importance.
F. Separable Sigmoid Objective

−
→
In this case, from (15), we can see that Λ∗ (T ) depends strongly on |x∗i (T ) − θi |.The further away x∗i (T ) is from θi (i.e., the
farther they are from changing their mind, or alternatively the more convinced they are), the smaller the relevant λ∗i (T ). For a
−
→
given  << 1, define the set of late-deciders [17] under the optimal advertising action u∗ to be L := {j| |x∗j (T ) − θj | < }.
When L =
6 ∅ (i.e., there are late deciders), we can use the water-filling machinery in §IV-E with the changes outlined below to
approximate the cost-effectiveness of channels and to calculate the optimal allocation using the much faster method described
there-in.
→
−
We define Λ̄ such that:


0
j∈
/L
,
λ̄j :=

 αj pj
j
∈
L
2
Then, the approximate cost-effectiveness metric of channel i with linear c(·) becomes:
D−
− ED−
→ →
→ −
→E
Qj , Λ̄ Qj , Bi e−ξj (t−T )
hi (t)
=
vi
vi

This confirms the practical intuition that identifying the people who will decide late early in the campaign can delineate the
whole trajectory of the campaign.
V. S IMULATION S TUDIES
In this section, we look at a simple example to show that even in small networks, the apportioning of resources across
channels can have complicated structures and can be counter-intuitive. Furthermore, we show that in many cases, the bound
derived from Theorem 1 grows much slower than the number of agents (N ).
−
We first examine a network of 7 agents with linear objectives, with →
p = (3%, 2%, 10%, 100%, 6%, 7%, 1%). Note that om
these conditions, agent 4 is the only reliable voter, with all other agents have small probabilities of voting. The connections
within the network are represented in Fig. 6; the off-diagonal elements of the Laplacian L are such that lij = 1 if there is
an edge in the figure between nodes i and j and zero otherwise. Assume two equal (linear) cost channels are available to
→
−
the advertiser: Channel 1, B 1 = (1, −1, 1, 0, 1, 0, 0)T has a positive impact on agents 1, 3, and 5, but a negative impact on
→
−
agent 2. It has no effect on the likely voter, agent 4. In contrast, channel 2, B 2 = (−1, 1, 0, 1, 0, 0, 0)T , has a positive effect
on the likely voter, but it has more limited effects on the rest of the graph. We solve this allocation problem in Fig. 7 using
the waterfilling methodology of §IV-E. As conjectured, at times t << T = 10, the cost-effectiveness of the two equal cost
channels is measured by:
hi (t) ≈ (

N
N
X
1 X
pj )(
bji ),
N j=1
j=1

which is larger for channel 1, even though it does not do a good job of targeting the likely voter. However, for t close to T ,
we can see that the cost-effectiveness ranking is flipped, as now:
D −
→E
−
hi (t) ≈ →
p , Bi ,
leading to the primacy of targeting. Note that the optimal control is bang-bang with bounded numbers of transitions, as proven
in Theorem 1.

Fig. 6: We examine a network of 7 agents with 2 influence channels. The lines in solid black represent the underlying
communciation network L. The grey and red box delineate the two channels that are available for influence in terms of agents
affected (but not intensity).
One important question, especially from a computational point of view, is how tight the upper-bounds on the number of
switches are. The most general bound (Theorem 2a) grows with the number of agents in the system, potentially leading to
a large computational burden. On the other hand, knowing Λ∗ (T ) will allow us to use tighter bounds, like that in Theorem
2b. We simulated 1000 random geometric graphs with a correspondingly uniformly random linear objective function for the
→
−
→
−
case of B 1 = (1, 0 1∗(N −1) )T , and plotted the mean and variance of the bound in Theorem 2b as the number of agents was
varied. As can be seen in Fig. 8, this latter bound is much smaller (around 10 for 200 agents), and its growth with respect
to the number of agents is negligible. This is significant because it means that from an applied perspective, the advertiser can
enumerate and evaluate a much smaller set of candidate optimals, and yet can be reasonably sure that the best such policy is
globally optimal.
VI. S UMMARY AND D ISCUSSION
We showed that the optimal influence strategy each channel in an explicitly bounded number of waves, then ceases effort
to let influence propagate (it is a bang-bang vector control). This bound is less than the number of agents, and the difference
between these two values can be significant. Furthermore, we showed that the exact optimal control can be calculated using a
water-filling procedure for a linear objective. These methods simplify the search for optimal controls, which in general would
be on the space of vector functionals. From the waterfilling procedure, we rigorously defined “cost-effectiveness” a metric for
ranking and comparing the influence of different channels at differing times on outcomes.

100
50

Bound in switches

150

200

Fig. 7: We plot the cost-effectiveness of these two channels over a time horizon of T = 10 days when they have equal cost
(v1 = v2 = 1). We then derive the water-level β̂ for r = 11 (in green). This determines the optimal utilization rate of the two
channels at different times. As can be seen, the channel with the most reach (channel 1) is prioritized at small t, and the one
that is most aligned with the likelihood to vote (channel 2) is prioritized late as the election draws near.

50

100

150

200

N

Fig. 8: We plot the upper-bounds on the number of switches of the optimal resource allocation derived from Theorem 1 for
1000 random geometric graphs for a channel that only affects the first agent as the size of the network is varied. The bound in
red is from Theorem 2a, and can be seen to grow with the number of agents. For a linear objective (Theorem 2b), the black
line shows that the bound on the number of switches is significantly smaller, and does not seem to grow with the size of the
network.

Applying our results to the sigmoid approximation of the electoral campaign/voting model model confirmed the intuitive
notion that identifying last-deciders determines the campaign strategy.
These results can be generalized in various ways. The notion of channel interaction in this work did not come with any
constraints on the presence or attention of the channel members. Adding such a constraint can more clearly model real-world
interactions. Furthermore, the linear model of influence is also a constraint that may be relaxed to obtain more general structure
on influence control. Finally, this work looked at a single issue where each agents opinion was represented with a scalar - the

same methodology can be extended to find optimal advertising strategies with vectors of opinions.
R EFERENCES
[1] A. S. Gerber, D. Karlan, and D. Bergan, “Does the media matter? a field experiment measuring the effect of newspapers on voting behavior and political
opinions,” American Economic Journal: Applied Economics, vol. 1, no. 2, pp. 35–52, 2009.
[2] M. Brodie, C. Deane, and S. Cho, “Regional variations in public opinion on the affordable care act,” Journal of health politics, policy and law, vol. 36,
no. 6, pp. 1097–1103, 2011.
[3] J. A. Chevalier and D. Mayzlin, “The effect of word of mouth on sales: Online book reviews,” Journal of marketing research, vol. 43, no. 3, pp. 345–354,
2006.
[4] C. Campbell, J. Cohen, and J. Ma, “Advertisements just aren’t advertisements anymore:: a new typology for evolving forms of online” advertising”,”
Journal of Advertising Research, vol. 54, no. 1, pp. 7–10, 2014.
[5] J. Pfeffer, T. Zorbach, and K. M. Carley, “Understanding online firestorms: Negative word-of-mouth dynamics in social media networks,” Journal of
Marketing Communications, vol. 20, no. 1-2, pp. 117–128, 2014.
[6] S. Valenzuela, “Unpacking the use of social media for protest behavior the roles of information, opinion expression, and activism,” American Behavioral
Scientist, vol. 57, no. 7, pp. 920–942, 2013.
[7] D. J. Chung and Z. Lingling, “The air war versus the ground game: An analysis of multi-channel marketing in us presidential elections,” 2014.
[8] D.
Kurtzleben,
“2016
campaigns
will
spend
$4.4
billion
on
tv
ads,
but
why?”
2015.
[Online].
Available:
www.npr.org/sections/itsallpolitics/2015/08/19/432759311/2016-campaign-tv-ad-spending
[9] M. Bagchi, S. Murdoch, and J. Scanlan, “The state of global media spending,” McKinsey Global Media Report 2015, 2015.
[10] R. Hegselmann and U. Krause, “Opinion dynamics and bounded confidence models, analysis, and simulation,” Journal of Artificial Societies and Social
Simulation, vol. 5, no. 3, 2002.
[11] P. Baines, E. K. Macdonald, H. Wilson, and F. Blades, “Measuring communication channel experiences and their influence on voting in the 2010 british
general election,” Journal of Marketing Management, vol. 27, no. 7-8, pp. 691–717, 2011.
[12] D. M. Kahan, E. Peters, M. Wittlin, P. Slovic, L. L. Ouellette, D. Braman, and G. Mandel, “The polarizing impact of science literacy and numeracy on
perceived climate change risks,” Nature Climate Change, vol. 2, no. 10, pp. 732–735, 2012.
[13] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proceedings of the IEEE, vol. 95, no. 1,
pp. 215–233, 2007.
[14] D. P. Spanos, R. Olfati-Saber, and R. M. Murray, “Dynamic consensus on mobile networks,” in IFAC world congress. Citeseer, 2005, pp. 1–6.
[15] K. Kandhway and J. Kuri, “Campaigning in heterogeneous social networks: Optimal control of si information epidemics,” IEEE/ACM Transactions on
Networking, vol. 24, no. 1, pp. 383–396, 2016.
[16] P. A. Naik and K. Raman, “Understanding the impact of synergy in multimedia communications,” Journal of Marketing Research, vol. 40, no. 4, pp.
375–388, 2003.
[17] B. C. Hayes and I. McAllister, “Marketing politics to voters: Late deciders in the 1992 british election,” European Journal of Marketing, vol. 30, no.
10/11, pp. 127–139, 1996.
[18] M. DeGroot, “Reaching a consensus,” Journal of the American Statistical Association, vol. 69, no. 345, pp. 118–121, 1974.
[19] R. Olfati-Saber, “Flocking for multi-agent dynamic systems: Algorithms and theory,” Automatic Control, IEEE Transactions on, vol. 51, no. 3, pp.
401–420, 2006.
[20] W. Ren, R. W. Beard, and E. M. Atkins, “A survey of consensus problems in multi-agent coordination,” in Proceedings of the 2005, American Control
Conference, 2005. IEEE, 2005, pp. 1859–1864.
[21] E. Yildiz, D. Acemoglu, A. Ozdaglar, A. Saberi, and A. Scaglione, “Discrete opinion dynamics with stubborn agents,” Available at SSRN 1744113,
2011.
[22] D. Kempe, J. Kleinberg, and É. Tardos, “Influential nodes in a diffusion model for social networks,” in Automata, languages and programming. Springer,
2005, pp. 1127–1138.
[23] E. Anshelevich, D. Chakrabarty, A. Hate, and C. Swamy, “Approximation algorithms for the firefighter problem: Cuts over time and submodularity,” in
Algorithms and Computation. Springer, 2009, pp. 974–983.
[24] M. Athans and P. L. Falb, Optimal control: an introduction to the theory and its applications. Courier Corporation, 1966.
[25] D. Liberzon, Calculus of variations and optimal control theory: a concise introduction. Princeton University Press, 2012.
[26] A. Seierstad and K. Sydsaeter, Optimal control theory with economic applications. Elsevier North-Holland, Inc., 1986.
[27] S. Eshghi, M. Khouzani, S. Sarkar, N. B. Shroff, and S. S. Venkatesh, “Optimal energy-aware epidemic routing in dtns,” Automatic Control, IEEE
Transactions on, vol. 60, no. 6, pp. 1554–1569, 2015.
[28] K. Kandhway and J. Kuri, “How to run a campaign: Optimal control of sis and sir information epidemics,” Applied Mathematics and Computation, vol.
231, pp. 79–92, 2014.
[29] S. Eshghi, M. Khouzani, S. Sarkar, and S. S. Venkatesh, “Optimal patching in clustered malware epidemics,” IEEE/ACM Transactions on Networking
(TON), vol. 24, no. 1, pp. 283–298, 2016.
[30] A. A. Cárdenas, S. Amin, and S. Sastry, “Research challenges for the security of control systems.” in HotSec, 2008.
[31] Y. Mo, E. Garone, A. Casavola, and B. Sinopoli, “False data injection attacks against state estimation in wireless sensor networks,” in Decision and
Control (CDC), 2010 49th IEEE Conference on. IEEE, 2010, pp. 5967–5972.
[32] R. P. Abelson, “Mathematical models of the distribution of attitudes under controversy,” Contributions to mathematical psychology, vol. 14, pp. 1–160,
1964.
[33] M. Taylor, “Towards a mathematical theory of influence and attitude change,” Human Relations, vol. 21, no. 2, pp. 121–139, 1968.
[34] P. V. Marsden and N. E. Friedkin, “Network studies of social influence,” Sociological Methods & Research, vol. 22, no. 1, pp. 127–151, 1993.
[35] R. Olfati-Saber and R. M. Murray, “Consensus problems in networks of agents with switching topology and time-delays,” IEEE Transactions on automatic
control, vol. 49, no. 9, pp. 1520–1533, 2004.
[36] N. E. Friedkin and E. C. Johnsen, “Social influence and opinions,” Journal of Mathematical Sociology, vol. 15, no. 3-4, pp. 193–206, 1990.
[37] F. R. Chung, Spectral graph theory. American Mathematical Soc., 1997, vol. 92.
[38] S. Boyd and L. Vandenberghe, Convex optimization. Cambridge university press, 2004.
[39] L. Hogben, Handbook of linear algebra. CRC Press, 2006.
[40] C.-T. Chen, Linear system theory and design. Oxford University Press, Inc., 1995.
[41] J. M. Longuski, J. J. Guzmán, and J. E. Prussing, Optimal Control with Aerospace Applications. Springer, 2014.
[42] G. Jameson, “Counting zeros of generalised polynomials: Descartes’ rule of signs and laguerre’s extensions,” The Mathematical Gazette, vol. 90, no.
518, pp. 223–234, 2006.
[43] T. M. Apostol, Calculus, volume I. John Wiley & Sons, 2007, vol. 1.

A PPENDIX A
P ROOF OF L EMMA 3
Proof. By induction on
M.
Pw−1
I) M = 1: f (t) = j=0 dj tj η t = η t g(t), with f (t) = 0 only if g(t) = 0. Due to the fundamental theorem of algebra, g(t)
has at most w − 1 = K − 1 real zeros (as dw−1 > 0), and therefore the base case holds.
II) M = k → M = k + 1:
f (t) =

k+1
i −1
X wX

wk+1 −1
t
di,j tj ηit = ηk+1
(

i=1 j=0

X

dk+1,j tj +

j=0

k wX
i −1
X

di,j tj (

i=1 j=0

ηi
ηk+1

t
)t ) = ηk+1
g(t),

with every zero of f (t) being a zero of g(t). Now:
wk+1 −1

g 0 (t) =

X

dk+1,j jtj−1 +

j=1

k wX
i −1
X
i=1 j=0

wk+1 −2

=

X

di,j jtj−1 (

dk+1,j+1 (j + 1)tj +

j=0

k
X

ηi
ηk+1

di,wi −1 twi −1 (

i=1

)t +

k wX
i −1
X

di,j tj (

i=1 j=0

ηi
ηk+1

)t ln(

ηi
ηk+1

)+

ηi
ηi t
) ln(
)
ηk+1
ηk+1

k wX
i −2
X

di,j+1 tj (

i=1 j=0

ηi
ηi t
) (j + 1 + ln(
)).
ηk+1
ηk+1

Differentiating wk+1 − 1 more times, the first term vanishes, and the other terms only change in their coefficients. Specifically,
ηi wk+1
ηk t
) term will be dk,wk −1 ln(
)
, which is non-zero due to the statement of the
the coefficient of the twk −1 (
ηk+1
ηk+1
wk+1 −1
Pk
g(t)
∂
theorem. Thus, due to the induction hypothesis,
has at most i=1 wi − 1 zeros.
∂twk+1 −1
We now complete the proof by repeatedly appealing to Rolle’s theorem [43, p. 184, Theorem 4.4]:
Theorem 3 (Rolle’s theorem). If h(·) is a continuous-everywhere function on [a, b] and has a derivative at each point in (a, b)
and h(a) = h(b), then there exists c ∈ (a, b) such that h0 (c) = 0.
Pk
∂ wk+1 −1 g(t)
∂ wk+1 −2 g(t)
has strictly more than
will have strictly more than
i=1 wi zeros, then by the theorem,
w
−2
k+1
∂t
∂twk+1 −1
wk+1 −2
Pk
∂
g(t)
will have at most
i=1 wi − 1 zeros, a contradiction. Thus,
i=1 wi zeros. Applying the same reasoning
∂twk+1 −2
Pk+1
reasoning wk+1 − 1 more times shows that g(t), and thus f (t), can have at most i=1 wi − 1 zeros, completing the proof of
the theorem.
If
Pk

A PPENDIX B
P ROOF OF L EMMA 4 REPRODUCED FROM [42]
Proof. We first state and prove two lemmas:
Lemma 5. Suppose g(·) has a zero of order k at t = t0 . Let h(·) be another function such that h(t0 ) 6= 0. Then g(·)h(·) has
a zero of order k at t = t0 .
Proof. For all n, we have:
n−1
X n di g(t) dn−i h(t) dn g(t)
dn
(g(t)h(t)) =
+
h(t).
dtn
i
dti
dtn−i
dtn
i=0

For n = 1, . . . , k both terms on the right-hand side are zero at t = t0 due to the order of the g(·) zero. However, for n = k + 1,
dk+1 g(t0 )
while all the terms in the sum again be zero, as h(t0 ) 6= 0 and
6= 0, then
dtk+1
dk+1
(g(t)h(t)) 6= 0,
dtn k + 1
completing the proof of the lemma.
For every real function g(·), we define Z+ (g) to be the number of zeros of g(·) over t ∈ (0, ∞) (counted with their potential
multiplicities).
Lemma 6. Suppose ι(x) is bounded, continuous, and non-zero on each interval (xi−1 , xi ) such that −∞ < x1 <R . . . < b = xn .
b
We will count xi as a sign change if the sign of ι(x) is different in (xi−1 , xi ) and (xi , xi+1 ). Then, if g(t) = −∞ ι(x)etx dx
and m is the number of sign changes of ι(x) in the interval (−∞, b), Z+ (g) ≤ m.
Proof. We prove Z+ (g) ≤ m by induction on m:

m = 0: If ι(x) > 0 for all x < −ξ1 , it will also be positive in all intervals (xi , xi+1 ). This means that g(t) > 0 for all such
t, and therefore Z+ (g) = 0. The same reasoning applies to ι(x) < 0 over x < −ξ1 .
We now assume the result for m = k and prove the m = k + 1 case. If the number of sign changes of ι(x) is k + 1,
without loss of generality we assume the last zero-crossing
happens at xk . So ι(x) > 0 over x ∈ (xk−1 , xk ) and ι(x) < 0
Rb
over x ∈ (xk , xk+1 ). Define h(t) := e−xk t g(t) = −∞ ι(x)et(x−xk ) dx. From Lemma 5, Z+ (h) = Z+ (g).
dh(t)
We now look at k(t) :=
(using the Leibniz integral rule to change the order of differentiation and integration):
dt
Z b
k(t) =
(x − xk )ι(x)et(x−xk ) dx.
(33)
−∞

The function I(x) = (x − xk )ι(x) fulfills the conditions of the lemma for the same set of {xi } points, with the exception that
it will not change signs at xk (as both terms in I(x) will change signs at that point). Thus, the total number of sign changes of
I(x) over (−∞, b) will be k, and by the induction step, Z+ (k) ≤ k. Using the same Rolle’s theorem (Theorem 3) argument
in the proof of Lemma 3, we can see that thus Z+ (h) ≤ k + 1, completing the proof of this lemma.
Now, we proceed with the proof of Lemma 4. We define S({si }i ) to be the number of sign variations in {si }i . Now, notice
that:
f (t) =

N
X

−t ξi

di (e )

=

i=1

Furthermore, because

tx

de
dt

f (t) =

N
−1
X


si (e−t )ξi − (e−t )ξi+1 + sN (e−t )ξN

i=1

= xetx :

N
−1
X

−t ξi

−t ξi+1

si (e ) − (e )

i=1
N
−1 Z −ξ i
X

=t

i=1

−ξi+1



−t ξN

+ sN (e )

=

N
−1
X
i=1

si etx dx +

Z

Z

−ξ i

si

tx

Z

−ξ N

te dx + sN
−ξi+1

tetx dx

−∞

−ξ N

sN etx dx



(34)

−∞

R −ξN
PN −1 R −ξi
Define g(t) := i=1 −ξi+1 si etx dx + −∞ sN etx dx. Then by Lemma 5, Z+ (f ) = Z+ (g). Now, define ι(x) := si for
−ξi+1 < x < −ξi and ι(x) := sN for x < −ξN .19 Then, from (34):
Z −ξ1
g(t) =
ι(x)etx dx.
(35)
−∞

But ι(x) fulfills the conditions of Lemma 6 with S({si })i number of points where its sign changes. Thus, by that lemma,
Z+ (g) ≤ S({si })i , and therefore Z+ (f ) ≤ S({si })i , completing the proof of this lemma.

19 The

value of ι(x) can be arbitrarily assigned to a bounded value at the overlap points.

