Optimal Budget Allocation:
Theoretical Guarantee and Efficient Algorithm

Tasuku Soma
TASUKU SOMA @ MIST. I . U - TOKYO . AC . JP
Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, 113-8656, andJST, ERATO, Kawarabayashi Large Graph Project, Tokyo, 101-8430
Naonori Kakimura
College of Arts and Sciences, The University of Tokyo, Tokyo, 153-8902

KAKIMURA @ GLOBAL . C . U - TOKYO . AC . JP

Kazuhiro Inaba
Google Inc.

KINABA @ GOOGLE . COM

Ken-ichi Kawarabayashi
National Institute of Informatics, JST, ERATO, Kawarabayashi Project, Tokyo, 101-8430

Abstract
We consider the budget allocation problem overbipartite influence model proposed by Alon etal. (Alon et al., 2012). This problem can beviewed as the well-known influence maximization problem with budget constraints.
We first show that this problem and its much
more general form fall into a general setting;namely the monotone submodular function maximization over integer lattice subject to a knapsack constraint. Our framework includes Alon etal.’s model, even with a competitor and with cost.
We then give a (1 − 1/e)-approximation algorithm for this more general problem. Furthermore, when influence probabilities are nonincreasing, we obtain a faster (1 − 1/e)approximation algorithm, which runs essentiallyin linear time in the number of nodes. This allows us to implement our algorithm up to almost
10M edges (indeed, our experiments tell us that
we can implement our algorithm up to 1 billion
edges. It would approximately take us only 500
seconds.).

1. Introduction
Domingos and Richardson (Domingos & Richardson,
2001; Richardson & Domingos, 2002) introduced viral
Proceedings of the 31 st International Conference on Machine
Learning, Beijing, China, 2014. JMLR: W&CP volume 32. Copyright 2014 by the author(s).

K KENITI @ NII . AC . JP

marketing, which is a cost-effective marketing strategy that
promotes products by giving “free” or “discounted” items
to a selected group of highly influential individuals, inthe hope that through the word-of-mouth effects, a large
number of product adoption will occur. In the same papers, Domingos and Richardson (Domingos & Richardson,
2001; Richardson & Domingos, 2002) considered the following problem: Suppose we have data on a social network, with estimates for the extent to which individuals
influence one another, and we would like to market a new
product that hopefully will be adopted by a large fractionof the network. How should we choose a few “influential”
members of the network that can “trigger” a cascade of influence? This problem, called influence maximization, is tofind a small set of the most influential individuals (which
is sometimes called a seed node set) in a social network
so that their aggregated influence in the network is maximized. The seminal work by Kempe, Kleinberg and Tardos (Kempe et al., 2003) provides the first systematic studyof influence maximization as a combinatorial optimization
problem. The influence maximization problem further motivated the research community to conduct extensive studies on various aspects of the influence maximization problems (e.g., (Chen et al., 2010; 2009)).
Previous work mentioned so far has only focused on theselection of a subset of influencing seeds. But there is one
more important factor we have to consider in the context ofan algorithmic marketing approach; namely Budgets. Certainly one of the major decisions in a marketing plan deals
with the allocation of a given budget among media channels
such as TV, newspaper, and webs, in order to maximize theimpact on a set of potential customers.

Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm

This prompts Alon et al. (Alon et al., 2012) to consider
the following influence maximization problem with budget constraints (which is called a (source-node) bipartite
influence model). First, we may model as a bipartite graphin which one side is the set of possible marketing channels, and the other is the population of customers. Anedge between a channel i and a customer j indicates thati may influence j with some probability that depends on
the budget allocated to i. Formally, the model consistsof a bipartite graph G = (S, T ; E), where S and T arecollections of source nodes and target nodes, respectively,
and E ⊆ S × T is an edge set. Each source node s has(i)a capacity c(s) ∈ Z+ and probabilities ps ∈ [0, 1] fori = 1, . . . , c(s). Each source node s will
P be allocated abudget b(s) ∈ {0, 1, . . . , c(s)} such that s∈S b(s) ≤ B,
where B ∈ Z+ denotes a total budget capacity. If a source
node s is allocated a budget of b(s), the node s makes b(s)independent trials to activate each neighboring target nodet. The probability that t is activated by s in the ith trial is(i)
ps . That is, the probability that t becomes active is1−Y
Y b(s)(1 − p(i)
s ),

(1)

s∈Γ(t) i=1

where Γ(t) denotes the set of source nodes that is adjacent
to t. The objective of this model is to distribute the budget
among the source nodes respecting the capacities of nodes,
and to maximize the expected number of target nodes that
become active. We call this problem the budget allocation
problem over bipartite influence model.
Alon et al. (Alon et al., 2012) devised a (1 − 1/e)approximation algorithm for this problem. Here, for a positive number α ≤ 1, an α-approximation algorithm is one
returning a feasible solution whose value is at least α times
the optimal value. Their algorithm is essentially greedy
with some preprocess (i.e., enumerating all the possible allocations with only three source nodes). The algorithm motivates us to consider the following issues.
1. The scalability. Their algorithm adapts a greedy procedure. Therefore, the time complexity is expensive, because in each iteration, the greedy procedure searches
all the nodes in the graph as a potential candidate forthe next seed node. As a result, the algorithm entails atleast quadratic number of steps in terms of the number ofnodes. In fact, not only due to this issue, but also due tothe expensive preprocess, their algorithm would not work
for more than 5K edges, say1 .
2. Submodularity. For a finite set S, we say that a set
function f : 2S → R is submodular if it satisfies
1
Indeed, as far as we are aware, nobody has implemented theiralgorithm.

f (X) + f (Y ) ≥ f (X ∩ Y ) + f (X ∪ Y ) for all X, Y ⊆ S.
A set function f is monotone if f (X) ≤ f (Y ) for all
X, Y with X ⊆ Y . Submodularity often arises in analyzing influence maximization in a social network (e.g.,(Chen et al., 2010; 2009; Kempe et al., 2003)), and guarantees why a greedy algorithm finds a nearly optimal solution (Fisher et al., 1978). In the budget allocation problem, one may select a node multiple times, and hence
the objective function is not a set function. As suggested
by Alon et al., however, their algorithm is similar to theone for maximizing a monotone submodular set function
subject to a knapsack constraint (Sviridenko, 2004), andhence it seems to us that submodularity can explain the
problem setting.
3. Extending the framework. The budget allocation problem
needs to be extended to adopt more complicated real settings. Alon et al. only considered the case when cost to
allocate a budget is the same for all sources. Since each
media channel such as TV, newspaper, and webs has different scales, it would be more natural to consider different costs for each channel. Moreover, a market may often
have a competitor against us, and we have to change ourallocation according to the competitor’s decision.
Our Contribution
In this paper, we clarify all the issues above. Let us firstconsider the second and the third issues. To deal withchoosing a node multiple times in the model, we extend
a set function to a function over the integer lattice, i.e., theset of the integer vectors in the Euclidean space. We define a submodular function over integer lattice, that is, afunction f satisfying f (x) + f (y) ≥ f (x ∨ y) + f (x ∧ y)for all integer vectors x and y, where x ∨ y and x ∧ y denote the coordinate-wise maxima and minima, respectively.
This definition generalizes submodularity of a set function,
because if we restrict the domain to the unit hypercube thenthe submodularity can be identified with one for a set function. Note that a function f over integer lattice is usually
supposed to be given as an evaluation oracle, a black box
that computes f (x) for any integer vector x.
A submodular set function has been studied extensively
in combinatorial optimization. There are combinatorial
polynomial-time algorithms for minimizing a submodular
set function (see (Fujishige, 2005; Iwata, 2008) for details).
It is known in (Fujishige, 2005) that these minimization algorithms can cope with submodular functions over integer
lattice if bounded, which can be identified with a ring family on some ground set with pseudo-polynomial size, andhence the minimization problem can be solved in pseudopolynomial time. On the other hand, maximizing a submodular function over integer lattice has been done for only
special classes with applications to multi-unit combinato-Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm

rial auctions (Shioura, 2009).
Having defined submodular functions over integer lattice,
our main theoretical contributions in this paper are the following.
• We introduce a general framework using a submodular function over integer lattice. We consider the problem of maximizing a monotone submodular function subject to a knapsack constraint, which is a natural extension of maximizing a submodular set function with constraints (Nemhauser et al., 1978; Sviridenko, 2004).
We then devise a (1 − 1/e)-approximation algorithm forthis problem. Since the budget allocation problem isshown to fall into the problem, this gives a solution of
the second issue.
• We show that our framework includes more generalized
models in which the source costs are nonuniform andthere is a competitor. Our first result implies that themodel can also be solved in polynomial time within (1 −1/e) approximation factor. The result can be compared tosome results in algorithmic game theory (Bharathi et al.,2007; Borodin et al., 2010; Budak et al., 2011).
In the competitor model, we aim at allocating our budget against a competitor’s allocation, which is known inadvance. Such a situation is practical when we consider
advertising (i.e., imagine television commercial messages.
Companies can prepare their strategies based on competitors’ information). This competitor model also considers
the case when the competitor spreads information in advance (i.e., the competitor spreads the information even before we start spreading our information). This means that
we can take “start-up delay” against the competitor into account.
It should be noted that our submodular framework admits
a potential applicability to other problems than the budget
allocation problem. In fact, classical combinatorial optimization problems such as the maximum coverage and facility location can be naturally generalized to our framework over integer lattice. Such problems can be applied totext summarization and sensor placement in machine learning. These applications will be discussed in Section 3.3.
Let us now consider the first issue. Relatively little work
has been done on improving the quadratic nature of thegreedy algorithm, even for the influence maximization
problem without the budget constraint. Perhaps the mostnotable work is (Leskovec et al., 2007), where submodularity is exploited to develop an efficient heuristic algorithm,
based on “lazy-forward” optimization in selecting seeds.
The idea is that the marginal gain of a node in the current
iteration cannot be much better than its marginal gain in

the previous iterations. Then this algorithm exploits submodularity of influence spread function to reduce the number of Monte-Carlo simulations. Empirical results show
700 times faster than the original greedy algorithm, however it still takes a few hours to compute a solution forgraphs with tens of thousands of vertices. Subsequently,
various heuristics (Chen et al., 2009; 2010; Jiang et al.,2011) have been proposed to avoid using Monte-Carlo simulations, however, these algorithms do not guarantee any
theoretical guarantee. Recently, a theoretically fast algorithm is proposed by (Borgs et al., 2014).
In this paper, we deal with the budget allocation problem
with nonincreasing influence probabilities. Let us observethat this problem setting often appears in the real world. Indeed, the impact of advertisement is supposed to be nonincreasing. Using the submodularity of the budget allocation
problem, we obtain a faster (1 − 1/e)-approximation algorithm, which runs essentially in linear time in the numberof nodes. This allows us to implement our algorithm up
to almost 10M edges (indeed, our experiments tell us that
we can implement our algorithm up to 1 billion edges. It
would approximately take us only 500 seconds.). As far as
we are aware, this is perhaps the first case that the greedy(1 − 1/e)-approximation algorithm for the submodularity
scales up to this large size.
The rest of the paper is organized as follows. In Section
2, we design a (1 − 1/e)-approximation algorithm for themonotone submodular function maximization over integer
lattice subject to a knapsack constraint. In Section 3, we apply it to the budget allocation problems and other problems.
Section 4 describes faster algorithms for the budget allocation problem assuming that influence probabilities are nonincreasing. Numerical experiments are presented in Section 5. Finally, Section 6 concludes the paper.

2. Submodular Maximization over Integer
Lattice subject to Knapsack Constraint
Let S be a finite set. We say that a function f over integer lattice is submodular if it satisfies f (x) + f (y) ≥f (x ∨ y) + f (x ∧ y) for all x and y, where x ∨ y and x ∧ ydenote the coordinate-wise maxima and minima, respectively, i.e., (x ∨ y)(s) = max{x(s), y(s)} and (x ∧ y)(s) =min{x(s), y(s)}. A function f is monotone if f (x) ≤ f (y)for all x and y with x ≤ y. We assume that f (0) = 0 without loss of generality.
Let c ∈ ZS+ , w ∈ RS+ and B be a nonnegative integer.
Consider the problem to find b ∈ ZS+ maximizing a monotone submodular
function f subject to 0 ≤ b ≤ c andPw · b := s∈S w(s)b(s) ≤ B. We call this problem themonotone submodular function maximization over integer
lattice subject to a knapsack constraint. We may assume

Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm

without loss of generality that w(s) > 0 for each s in S.

2.1. (1 − 1/e)-Approximation Algorithm

This problem is a generalization of the problem of maximizing a monotone submodular set function subject to a
knapsack constraint. Indeed, if c is the all-one vector, thenf can be identified with a monotone submodular set function. In this case, we can find a (1 − 1/e)-approximate
solution in polynomial time (Sviridenko, 2004). The main
result of this section is the following for a general case.

We next describe our approximation algorithm. In our algorithm, we first enumerate every feasible solution b0 suchthat |supp+ (b0 )| ≤ 3. The number of such solutions isO(B 3 |S|3 ). For each feasible solution b0 , the algorithm
increases each component of b0 in a greedy way using
G REEDY P ROCEDURE, whose description is presented in
Algorithm 1, and obtains a feasible solution b. Finally, thealgorithm returns the best one among the obtained solutions. Since Algorithm 1 requires O(B 2 |S|θ) time, the total complexity is O(B 5 |S|4 θ). Note that the correctness of
our algorithm is omitted due to the space limitation, which
can be found in the appendix.

Theorem 2.1. For the monotone submodular function
maximization over integer lattice subject to a knapsackconstraint, we can find a (1 − 1/e)-approximate solution inO(B 5 |S|4 θ) time, where θ is the running time of an evaluation oracle for f .
Note that the complexity is also bounded by using cmax ,the maximum entry of c, instead of B. The bound isO(c4max |S|5 θ), and this corresponds to the bound by Sviridenko (Sviridenko, 2004) for submodular set function maximization subject to a knapsack constraint, where cmax =1.
We here summarize basic properties for submodular functions over integer lattice. The marginal return with respect
to a feasible solution b, s ∈ S and k ∈ Z+ is the valuef (b+kχs )−f (b), where χs is the characteristic vector of s.
We denote this value by ∆(b, s, k). The average marginal
return with respect to a feasible solution b ∈ ZS+ , s ∈ S andk ∈ Z+ is the value ∆(b, s, k)/(w(s)k), which we denoteby δ(b, s, k).
It is well-known that for a set function f , submodularity isequivalent to the diminishing marginal return property, i.e.,f (X ∪{s})−f (X) ≥ f (Y ∪{s})−f (Y ) for all X ⊆ Y ⊆S and s 6∈ Y . However, submodularity over integer lattice
does not imply the diminishing marginal return property:f (b + χs ) − f (b) ≥ f (b + 2χs ) − f (b + χs )(2)

for arbitrary b and s ∈ S. On the other hand, a weakerversion of this inequality does hold, whose proof can befound in the appendix.
Lemma 2.2. Let f be a monotone submodular function
over integer lattice. For arbitrary s ∈ S, k ∈ Z+ , x and ywith x ≤ y, we havef (x ∨ kχs ) − f (x) ≥ f (y ∨ kχs ) − f (y).

(3)

Algorithm 1 G REEDY P ROCEDURE
Input: a feasible solution b0
1: Let b := b0 .
2: Let Q := {(s, k) : s ∈ S and 1 ≤ k ≤ c(s) − b(s)}.
3: while w · b < B and Q 6= ∅ do
4:
Find s and k maximizing the average marginal return δ(b, s, k) among (s, k) ∈ Q.
5:
if w · b + w(s)k ≤ B then6:
Let b(s) := b(s) + k.
7:
Remove all pairs (s, l) such that b(s) + l > c(s)from Q.
8:else
9:Remove (s, k) from Q.
10:
end if
11: end while
Let us leave some remarks on our algorithm. Although
the worst case complexity of our algorithm is quite expensive, Algorithm 1 can be accelerated using a “lazy evaluation” technique given in (Minoux, 1978), and thus it runs
more efficiently in practice. Also, there is another approach to reduce the time complexity at the expense of agood approximation ratio. We can apply ideas similar to
those for maximizing a submodular set function to makepractical simpler algorithms with somewhat worse approximation factors (Lin & Bilmes, 2010). For example, as in(Alon et al., 2012), if we enumerate solutions with only one
positive support before performing G REEDY P ROCEDURE,
then we can find a 1/2(1 − 1/e)-approximate solution inO(B 2 |S|2 θ) time.

The (positive) support of b, denoted by supp+ (b), is the setof elements s in S such that b(s) > 0.

2.2. Faster Algorithm under Diminishing Marginal
Return Property

Lemma 2.3. Let f be a submodular function. For arbitrary
x and y, we haveXf (x ∨ y) ≤ f (x) +(f (x ∨ y(s)χs ) − f (x)) .

We conclude this section with designing a faster (1 −1/e)-approximation algorithm if f satisfies the diminishing marginal return property (2) and a cost w is uniform,i.e., w(s) = 1 for any s ∈ S. Note that even if f admits
the properties, the problem is still NP-hard and (1 − 1/e)approximation is best possible unless P=NP (Feige, 1998).

s∈supp+ (y−x)(4)

Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm

We execute G REEDY P ROCEDURE with b0 := 0. By (2), we
have δ(b, s, k) ≤ δ(b, s, 1) for arbitrary b, s and k. HenceG REEDY P ROCEDURE always chooses k = 1 for each iteration. Furthermore, the procedure never fails to increase
the tentative solution because w is uniform. Therefore, byfollowing a similar argument to the proof of Theorem 2.1,
we can show that the output is a (1 − 1/e)-approximate
solution. The running time follows from the fact that b increases B times and each iteration requires O(|S|θ) time tofind s maximizing δ(s, b, 1). Thus the following holds.
Theorem 2.4. For the submodular function maximization
over integer lattice, if f admits the diminishing marginal
return property and w is uniform, then we can find a (1 −1/e)-approximate solution in O(B|S|θ) time.

3. Applications of Submodular Maximization
In this section, we focus on the budget allocation problem (as defined in Section 1), and we show that more generalized models fall into our framework. We also mention
applications to other problems such as text summarizationand sensor placement in Section 3.3.
3.1. Budget Allocation Problem with Nonuniform Costs
We extend to the bipartite influence model with nonuniform
costs. That is, in addition to an instance of the budget allocation problem, each source node s has a cost w(s) > 0.
The objective is to distributethe budget respecting the caPpacities of nodes and s∈S w(s)b(s) ≤ B such that the
expected number of activated nodes is maximized. We callthis problem the budget allocation problem over bipartite
influence model with nonuniform costs.
In the model, the probability that t becomes active is equalto (1). Let ft be a function of an allocation vector b definedas (1). We note that we define ft (b) = −∞ if b does notsatisfy 0 ≤ b ≤ c. It is easy to see that the function ft ismonotone for each t ∈ T . In addition, the following lemma
asserts that ft is submodular.
Lemma 3.1. For any t ∈ T , the function ft is submodular.
Q
Qb(s)
(i)
Proof. It suffices to show gt (b) := s∈Γ(t) i=1 (1−ps )is supermodular. Let α := gt (x ∧ y), β := gt (x)/α andγ := gt (y)/α. We can easily check that α, β, γ ∈ [0, 1] andgt (x ∨ y) = αβγ. Then we obtain gt (x ∨ y) + gt (x ∧ y) −gt (x) − gt (y) = α(βγ + 1 − β − γ) = α(1 − β)(1 − γ) ≥0.
Since the expected number of activatednodes for an alP
location b is equal to f (b) :=f(b),the expectedt∈T t
number is also submodular as a function of b. The following result is now immediate from Theorem 2.1, sinceθ = O(B|S||T |).

Theorem 3.2. A (1 − 1/e)-approximate solution for thebudget allocation problem with nonuniform costs can befound in O(B 6 |S|5 |T |) time.
3.2. Budget Allocation Problem with a Competitor
We extend the budget allocation problem with nonuniform
costs to the two-player case. In the model, there is acompetitor against an advertiser. The competitor allocates
his/her budget to S in advance, and will try to influencetarget nodes at the same time as the advertiser’s trials. Under this situation, the advertiser aims at allocating a budget
to source nodes to maximize the expected number of target nodes influenced by his/her trials. We suppose that thetrials of the two players are made in a discrete time step:At each time step i, first the competitor makes the ith trial,
and then the advertiser makes the ith trial. The trials will
be repeated until both budget allocations run out.
Thus each target node t of T has the following three states:
inactive, positively active (influenced by an advertiser), andnegatively active (influenced by a competitor). Since an advertiser is a follower, we assume that it has a chance to activate positively both an inactive node and a negatively activated node. Note that when a node is already influenced
by the competitor, the probability to activate it should besmaller than one to activate an inactive node. In contrast,
we suppose that the competitor can activate an inactive
node, but not a positively active node. Thus the model isprogressive with respect to positively active nodes.
More specifically, the model is defined as follows. For abipartite graph G = (S, T ; E), an advertiser is given a(i)capacity c(s), a cost w(s) and two probabilities ps and
(i)
(i)
(i)
qs with qs ≤ ps for i = 1, . . . , c(s) for each s ∈ S.
In addition, a competitor has already allocated his budget
to source nodes, which is denoted by b̃(s) for each source(i)node s ∈ S. The competitor also has probabilities p̃s for
i = 1, . . . , b̃(s) for each s in S. The probability that t is
activated by s in the ith trial depends on the status of t as
follows. If t is inactive, then the probabilities that t is posi(i)(i)
tively/negatively activated are ps and p̃s , respectively. If
t is already negatively active, then the probability that t is(i)positively activated is qs . In this setting, we aim at maximizing the expected number of positively active nodes. Fort ∈ T and k with 1 ≤ k ≤ 1 + maxs∈S b̃(s), let Et,k be theevent that t becomes negatively active in the kth trial (whenk = 1 + maxs∈Γ(t) b̃(s), Et,k means the event that t never
become negatively active). Conditioned on Et,k , the probability that t becomes positively active is
ft,k (b) = 1−

Y min{b(s),k−1}Ys∈Γ(t)

i=1

1 − p(i)s b(s)Y
1 − qs(i) .

i=k

The probability that t becomes positively active equals

Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm

P

Therefore,k λt,k ft,k (b), where λt,k := Pr(Et,k ).
the expected number Pof positively
activenodes,
denotedPby f (b), is equal to t∈T k λt,k ft,k (b). Similarly toLemma 3.1, ft,k is shown to be monotone and submodular
for any t and k. Since f is a nonnegative linear combination of ft,k ’s, f is also monotone and submodular. Thus
this problem can be reduced to the monotone submodular
function maximization over integer lattice.
Theorem 3.3. For the budget allocation problem with acompetitor, the objective function is monotone and submodular. Thus we can find a (1 − 1/e)-approximate solution inpolynomial time.
3.3. Other Applications
In this section, we present applications of our framework
to problems other than the budget allocation problems.
Submodular set functions arise in several applications (see,e.g., (Krause & Golovin, 2014)). Such applications cannaturaly be extended to our framework allowing multiple
choices.
Maximum Coverage Let us first see that our framework includes a generalization of the well-known maximum coverage problem. In the maximum coverage problem, we are given a finite set V and a family of subsets
C1 , . . . , Cm in V , and the objective is to choose k subsets from C1 , . . . , Cm so that the number of the covered
elements in V is maximized. Here consider covering functions pj : Z+ → 2V (j = 1, . . . , m), each of which ismonotone, and we would like to maximize the number ofthe elements covered by pj ’s, i.e., | ∪m
j=1 pj (bj )|, subject
Pm
to j=1 bj ≤ k. Note that the covering function pj corresponds to the situation where choosing j multiple times
makes the covered set larger. This problem clearly generalizes the maximum coverage problem, that corresponds tothe case when we can only choose each pj at most once. It
is not difficult to see that the objective function is a monotone submodular function over integer lattice, and thereforea (1 − 1/e)-approximate solution can be found in polynomial time by Theorem 2.1.
Facility Location We are given a set V of facilities, andwe aim at deciding how large facilities are opened up inorder to serve a set of m customers, where we represent
scale of facilities as integers 0, 1, . . . , c (“0” means we do
not open a facility). If we open up a facility j of scale
bj , then it provides service of value pi,j (bj ) to customer i,where pi,j : Z+ → R (j = 1, . . . , m) is a given monotone function. We suppose that each customer chooses theopened facility with highest value. That is, when we assign bj to each facility j, the total
Pm value provided to all
customers is given by f (b) =i=1 maxj∈S pi,j (bj ). It
turns out f is monotone and submodular over integer lattice. Thus a (1 − 1/e)-approximate solution can be foundin polynomial time by Theorem 2.1.
Sensor Placement In a standard sensor placement scenario, we can put at most one sensor in each spot to maximize the area covered by sensors. Here we can consider a more general problem where to place sensors withsome specified power in a field subject to budget constraint,
where the area covered by a sensor depends on its power
setting. This problem is almost equivalent to the maximum coverage problem with multiple choices as discussed
before, and hence we can apply our approximation algorithm for the problem. A similar sensor placement problem
where we can put two kinds of sensors in each spot is studied in (Singh et al., 2012).
Text Summarization The objective of text summarization is to find a small set of words that summarizes thefeature of a given text as well as possible. Recently, it isshown that a variety of objective functions used in summarization admits submodularity and that submodular-based
approaches outperform in practice (Lin & Bilmes, 2011).
For example, in the concept-based summarization (Filatova & Hatzivassiloglou, 2004), we are to find a subset S
of sentences maximizing the
P total credit of concepts covered by S, i.e., maximize i∈Γ(S) ci , where Γ(S) is theset of the concepts covered by S and ci ∈ R+ is the creditof a concept i. Indeed, this objective function is submodular. We now extend the submodular summarization modelto the one that incorporates “confidence” of sentences, i.e.,
we can choose a sentence in various confidence level like“low”, “mid” or “high” rather than just choose or not. As in
the maximum coverage, let us introduce a monotone covering function pj for each sentence j. Then the objectivefunction of thePextended model is defined to be the total
credit f (b) =ci , where the sum is taken over concept
i covered by ∪j pj (bj ). Again, this objective function isa monotone submodular function over integer lattice, andhence we can use our approximation algorithm for the extended model.

4. Faster Algorithm for Budget Allocation
with Nonincreasing Influence Probabilities
In this section, we assume the budget allocation problem
has nonincreasing influence probabilities, i.e., for each
(i−1)
(i)
s ∈ S, we have ps≥ ps for i = 2, . . . , c(s). The
property captures the real-world phenomena of marketing.
In our model, multiple trials to activate target nodes can beviewed as discrete-time steps. Thus it is natural to decrease
effectiveness of an advertisement with time.
Lemma 4.1. Under the nonincreasing influence probabilities, the objective function f admits the diminishingmarginal return property.
By Theorem 2.4, performing G REEDY P ROCEDURE with

Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm

Theorem 4.2. For the budget allocation problem with nonincreasing influence probabilities, we can find a (1 − 1/e)approximate solution in O(B(|S| + |T | + |E|)) time.
Similarly to Algorithm 1, we can apply the lazy evaluation
technique to Algorithm 2 to accelerate in practice. We use
this speeding up technique in our experiments.

9000

Influenced nodes: f (b)

8000
7000
6000
5000
4000
3000
2000

Greedy (Ours)
Degree-prob
DegreeRandom

1000
0
0

100

200

300

(i)

(i)

Theorem 4.3. If ps and qs are nonincreasing and thecost is uniform, then we can find a (1 − 1/e)-approximate
solution for the budget allocation problem with a competitor in O(B 2 |E|) time.

5. Experiments
We now verify our theoretical results by implementing Algorithm 2 for the budget allocation problem over bipartite
influence model with nonincreasing influence probabilities.
To demonstrate that the greedy choice indeed performs
well, the expected number f (b) of activated nodes by thegreedy choice is compared to that by other strategies. The

800

900 1000

2000

1500

1000

Greedy (Ours)
Degree-prob
DegreeRandom500

0In addition, under a similar assumption, we design a faster
algorithm for the budget allocation problem with a com(i)
(i−1)
(i)
(i−1)
≥ qs
≥ ps and qs
petitor. Let us assume that psfor arbitrary s ∈ S and i with 2 ≤ i ≤ c(s). Then ft,kadmits the diminishing marginal return property for each t
and k, and hence so does f . Therefore, a greedy algorithm
similar to Algorithm 2 computes a (1 − 1/e)-approximate
solution. A pseudocode description of the greedy algorithm
that runs in O(B 2 |E|) time is presented in the appendix.

700

2500

0

Algorithm 2 S IMPLE G REEDY P ROCEDURE
1: Let b := 0, and let φ(t) := 1 for each t ∈ T andφ(s) := d(s) for each s ∈ S.
2: for i = 1 to B do(b(s)+1)φ(s).
3:Choose s maximizing ps
4:
Let b(s) := b(s) + 1.
(b(s)))φ(t) for each t ∈ Γ(s) and5:
Let φ(t) :=P(1 − pslet φ(s) := t∈Γ(s) φ(t) for each s ∈ S
6: end for7: return b

400 500 600
Budget: B

Figure 1. P=1.0, Yahoo! Bidding Data

Influenced nodes: f (b)b0 := 0 yields a (1−1/e)-approximate solution. Algorithm
2 describes an implementation of the algorithm in Theorem
2.4 with an additional trick to compute the value of f efficiently. Here we use auxiliary variables φ(s) and φ(t) for
each s ∈ S and t ∈ T . During execution of the algorithm,
Q
Qb(s)
(i)
φ(t) traces the value s∈Γ(t) i=1 (1 − ps ) and φ(s) isP
always equal to t∈Γ(s) φ(t). Thus f (b + χs ) − f (b) =P(b(s)+1)(b(s)+1))φ(t)) = psφ(s). Evt∈Γ(s) (φ(t) − (1 − ps
idently the algorithm runs in O(B(|S| + |T | + |E|)) time.
Summarizing the arguments, we have the following theorem.

100

200

300

400 500 600
Budget: B

700

800

900 1000

Figure 2. P=0.1, Yahoo! Bidding Data

“degree” strategy chooses the top B highest degree nodes.
This strategy is based on the intuition that the high degree
nodes should have high influence. In many variants of influence maximization problems, this high-degree-selection
strategy is reported not to outperform the greedy choice(Kempe et al., 2003; Budak et al., 2011). The “degreeprob” strategy takes the influence probability into account,in addition to the degree condition. It chooses the top B
nodes with the largest expected number of influences, i.e.,
degree multiplied with the probability. The “random” strategy is a baseline choice that uniformly randomly chooses
B nodes.
Figures 1 and 2 are our simulation results on Yahoo! SearchMarketing Advertiser Bidding Data (Yah). It is a bipartite graph between 1,000 search keywords and 10,475 accounts, where each edge represents one “bid” to advertisement on the keyword. Note that this data originally does
not represent influence relationship, but it encodes the information “who is interested in what” relationship in thereal world. The motivation of the experiment is to find agood choice of “what” set that maximizes the influenced“who”s, that is, a set of keywords that is maximally associated to advertisers. This would be useful for the publisher
to promote keywords to advertisers. For the purpose, weonly use the graph, although the original data contains bid
prices or time data. The graph has 52,567 edges (representing ‘who bid at least once to what’ relation). The prob(i)ability ps of influence is assigned as follows. Let P be(1)
a parameter. For each s, we have set ps a random value

Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm
9000
1400000

Influenced nodes: f (b)Influenced nodes: f (b)1000000
800000600000400000
Greedy (Ours)
Degree-prob
DegreeRandom200000
0
0

100

200

300

400 500 600
Budget: B

700

800

6000
5000
4000
3000
2000

0
900 1000

03000003000

2500002500

200000150000100000
Greedy (Ours)
Degree-prob
DegreeRandom

50000
0
100

200

300

400 500 600
Budget: B

700

800

200

300

400 500 600
Budget: B

700

800

900 1000

Greedy (Ours)
Greedy-unaware (Ours)
Degree-prob
DegreeRandomCompetitor

2000
1500
1000
500
0

900 1000

Figure 4. P=0.1, Synthesized Graph
(i+1)

100

Figure 5. P=1.0, against a competitor

Influenced nodes: f (b)Influenced nodes: f (b)

7000

1000

Figure 3. P=1.0, Synthesized Graph0

Greedy (Ours)
Greedy-unaware (Ours)
Degree-prob
DegreeRandomCompetitor

8000

1200000(i)

is set to ps · X, where X isbetween 0 and P . Then, ps
a random value between 0 and 1, generated for each i ands. Figures 1 and 2 show the results on P = 1 and P = 0.1
cases.
In order to implement our algorithms for larger scalegraphs, we have also run our experiments on artificiallygenerated graphs. Figures 3 and 4 are simulation resultson synthesized graphs with |S| = 200, 000 and |T | =2, 000, 000 nodes with around 8, 000, 000 edges between
them. The graphs are generated so that the degree distribution of the source nodes obey the power law of γ = 2.0.
After assigning the degrees to each source node s, it is connected to deg(s) nodes uniformly chosen from T . Allocation of 1, 000 budgets in the greedy algorithm took 3.36
seconds (including the graph generation time) in average
on a machine with Xeon E5-2690 2.9GHz CPU and 64GB
memory.
We have also implemented the algorithm when a competitor exists. We have started with the situation that the competitor already allocated 100 budgets by the “degree” strat(i)egy. The probability qs to turn over a node already in(i)fluenced by the competitor is set to 0.2 · ps . Figures 5
and 6 summarize the results in the competitive setting on
the Yahoo! Bidding data graph. The “competitor” line in
the figures shows the number of nodes kept influenced by
the competitor against our greedy algorithm.
In all the configurations, the greedy algorithm outperformed degree-based strategies. “Degree-prob” also
showed a comparable result on the synthesized graphs. In-

0

100

200

300

400 500 600
Budget: B

700

800

900 1000

Figure 6. P=0.1, against a competitor

terestingly, the “greedy-unaware” strategy in the competitive setting, which is to allocate budgets greedily without
taking the existence of the competitor into account at all, isshowing a very close performance to the competitor-aware
one. This may be explained as follows; except for the ex(i)(i)
treme situation that ps is very high and qs is very low,a highly influential set of source nodes would be taken by
the advertiser, even after some part of it is grabbed by thecompetitor.

6. Conclusion
In this paper, we have defined a submodular function overinteger lattice, extending a submodular set function, and introduced the problem of maximizing a monotone submodular function subject to knapsack constraint. This problem
includes the budget allocation problem (Alon et al., 2012)and more general budget allocation problems with nonuniform costs and a competitor. Also, this problem has applications to sensor placement and text summarization. We
have devised a (1 − 1/e)-approximation polynomial-timealgorithm for the problem. In addition, based on the diminishing marginal return property, we have devised a faster algorithm for the budget allocation problem under some natural scenario, and have carried out numerical experiments.

Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm

References
Yahoo!
webscope dataset:ydata-ysm-advertiser-bidshttp://research.yahoo.com/Academic_
v1 0.
Relations.

Kempe, D., Kleinberg, J., and Tardos, E. Maximizing the spreadof influence through a social network. In Proceedings of the 9th
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146. ACM, 2003.

Alon, N., Gamzu, I., and Tennenholtz, M. Optimizing budget allocation among channels and influencers. In Proceedings of the
21st International Conference on World Wide Web, pp. 381–
388, 2012.

Krause, A. and Golovin, D. Submodular function maximization.
In Bordeaux, L., Hamadi, Y., and Kohli, P. (eds.), Tractability:
Practical Approaches to Hard Problems, to appear. Cambridge
University Press, 2014.

Bharathi, S., Kempe, D., and Salek, M. Competitive influencemaximization in social networks. In Proceedings of the 3rdInternational Conference on Internet and Network Economics,
WINE’07, pp. 306–311, 2007.

Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen,J., and Glance, N. S. Cost-effective outbreak detetion in networks. In Proceedings of the 13th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining, pp.
420–429. ACM, 2007.

Borgs, C., Brautbar, M., Chayes, J., and Lucier, B. Maximizing social influence in nearly optimal time. In Proceedings of
the ACM-SIAM Symposium on Discrete Algorithms, SODA’14,
2014.
Borodin, A., Filmus, Y., and Oren, J. Threshold models for competitive influence in social networks. In Proceedings of the 6thInternational Conference on Internet and Network Economics,
WINE’10, pp. 539–550, 2010.
Budak, C., Agrawal, D., and El Abbadi, A. Limiting the spread of
misinformation in social networks. In Proceedings of the 20th
International Conference on World Wide Web, WWW ’11, pp.
665–674, 2011.
Chen, W., Wang, Y., and Yang, S. Efficient influence maximization in social networks. In Proceedings of the 15th ACM
SIGKDD International Conference on Knowledge Discovery
and Data Mining, pp. 199–208. ACM, 2009.
Chen, W., Wang, C., and Wang, Y. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proceedings of the 16th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining, pp.
1029–1038. ACM, 2010.
Domingos, P. and Richardson, M. Mining the network value ofcustomers. In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pp. 57–66. ACM, 2001.
Feige, U. A threshold of ln n for approximating set cover. Journalof ACM, 45:634–652, 1998.
Filatova, E. and Hatzivassiloglou, V. Event-based extractive summarization. In Proceedings of ACL Workshop on Summarization, 2004.
Fisher, M. L., Nemhauser, G. L., and Wolsey, L. A. An analysis
of approximations for maximizing submodular set functions ii.
Mathematical Programming Study, 8:73–87, 1978.
Fujishige, S. Submodular Functions and Optimizations. Number 58 in Annals of Discrete Mathematics. Elsevier, 2nd edition, 2005.
Iwata, S. Submodular function minimization. Math. Program.,
112(1):45–64, 2008.
Jiang, Q., Song, G., Gao, C., Wang, Y., Si, W., and Xie, K. Simulated annealing based influence maximazation in social networks. In Proceedings of the Twenty-fifth Conference on Artificial Intelligence, pp. 127–132. AAAI, 2011.

Lin, H. and Bilmes, J. Multi-document summarization via budgeted maximization of submodular functions. In Proceedingsof the Annual Conference of the North American Chapter of the
Association for Computational Linguistics, pp. 912–920, 2010.
Lin, H. and Bilmes, J. A class of submodular functions for document summarization. In Proceedings of the Annual Conferenceof the North American Chapter of the Association for Computational Linguistics, pp. 510–520, 2011.
Minoux, M. Accelerated greedy algorithms for maximizing submodular set functions. Optimization Techniques, Lecture Notes
in Control and Information Sciences, 7:234–243, 1978.
Nemhauser, G., Wolsey, L., and Fisher, M. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14:265–294, 1978.
Richardson, M. and Domingos, P. Mining knowledge-sharing
sites for viral marcketing. In Proceedings of the 8th ACM
SIGKDD International Conference on Knowledge Discovery
and Data Mining, pp. 61–70. ACM, 2002.
Shioura, A. On the pipage rounding algorithm for submodular
function maximization — a view from discrete convex analysis. Discrete Math., Alg. and Appl., 1(1):1–24, 2009.
Singh, AP, Guillory, A., and Bilmes, J. On bisubmodular maximization. In Proceedings of the 15th International Conferenceon Artificial Intelligence and Statistics, pp. 1055–1063, 2012.
Sviridenko, M. A note on maximizing a submodular set function
subject to a knapsack constraint. Operations Research Letters,
32:41–43, 2004.

A. Proof of Theorem 2.1
Let b∗ be an optimal solution for a given instance of the
problem. We first examine properties of G REEDY P RO CEDURE that hold for arbitrary b0 .
We then showthat there exists some b0 in the enumeration step suchthat G REEDY P ROCEDURE returns b with f (b) ≥ (1 −1/e)f (b∗ ), which proves Theorem 2.1.
Let us fix an initial solution b0 , and analyze behavior of
G REEDY P ROCEDURE with input b0 . We denote by bi thetentative solution b at the beginning of the ith iteration andOptimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm

denote by si and ki s and k chosen in the ith iteration, respectively. Assume that G REEDY P ROCEDURE first has not
updated the tentative solution b in the Lth trial. Equivalently, let L be the minimum number such that bL = bL+1
and bi < bi+1 for i = 1, . . . , L − 1. Note that if such a situation never happens during the execution of G REEDY P RO CEDURE , define L to be the number of iterations.

f (b0 ))/B 0 by Lemma A.2. For i > 1, we havef (b∗ ) − f (b0 ) −Consider the ith iteration of the algorithm. For simplicity, we denote ∆(bi , si , ki ) by ∆i , δ(bi , si , ki ) by δi , andPi−1w(si ) by wi . Note that f (bi ) = f (b0 ) + j=1 ∆i for
i = 1, . . . , L. Let B 0 := B − w · b0 .
Lemma A.2. For i =wi ki(f (b∗ ) − f (bi )) .
B0

1, . . . , L, we have ∆i≥P
Proof. Let us denote bi ∨b∗ = bi + αs χs , where the sum
is taken over s in supp+ (b∗ − bi ) and αs := b∗ (s) − bi (s).
Since bi ∨b∗ (s)χs = bi +αs χs for each s ∈ supp+ (b∗ −bi ),(4) implies
f (bi ∨ b∗ ) ≤ f (bi ) +X(f (bi + αs χs ) − f (bi ))s∈supp+ (b∗ −bi )≤ f (bi ) +X

w(s)αs δi ,∆j = f (b∗ ) − f (b0 ) −j=1≤ f (b∗ ) − f (b0 ) −i−1
X∆ j − ∆i


∆j −



=

i−1
X
j=1

j=1

Lemma A.1. Without loss of generality, we may assume
that b(sL ) + kL ≤ b∗ (sL ).
Proof. Suppose that b(sL ) + kL > b∗ (sL ). Let us consider
a modified instance in which the capacity of sL is decreased
to b(sL ) + kL − 1. The optimal value is unchanged by thismodification because b∗ is still feasible and optimal. Furthermore, G REEDY P ROCEDURE returns the same solution(with respect to same b0 ). Thus it suffices to analyze the algorithm in the modified instance. Repeating this argumentcompletes the proof of this lemma.

i
X

i−1
X

wi ki  ∗f (b ) − f (b0 ) −
∆j 
B0
j=1
(by Lemma A.2)




i−1
X
wi ki  ∗
f
(b
)
−
f
(b
)
−
∆j 
1−
0
B0
j=1




i−1
Y
wi ki
wj kj
∗
· (f (b ) − f (b0 )) ·
,
≤ 1−
1−
B0
B0
j=1
(by the induction hypothesis)
which completes the proof.
Lemma A.4. It holds that f (b∗ ) − f (bi ) ≤ (f (b∗ ) −f (b0 ))/e.
Proof. Let ϕ(x) = ln(1 − x). Note that ϕ is concave inPL[0, 1). By Jensen’s inequality, we have i=1 ϕ(xi )/L ≤PL
ϕ( i=1 xi /L) for x1 , . . . , xL ∈ [0, 1). Putting xi :=wi ki /B 0 , we obtain
!




L
L
wi ki
1 X w i ki
11X
ln 1 −≤ ln 1 −≤ ln 1 −,L i=1
B0
L i=1 B 0L
(5)
PL
where the last inequality follows since i=1 wi ki ≥ B 0
and ϕ is a monotonically decreasing function. Thus we
have
L
 
L 
Y
wi ki
1
1
1−
≤ .
≤ 1−
0
B
L
e
i=1

(6)

s∈supp+ (b∗ −bi )Combining this fact and Lemma A.3 completes the proof.
where the last inequality follows from the fact that (f (bi +kχs ) − f (bi ))/(w(s)k) ≤ δi for all s ∈ S and k. SincePw(s)αs is at most B 0 and f (b∗ ) ≤ f (bi ∨ b∗ ) by themonotonicity of f , it holds that f (b∗ ) ≤ f (bi ) + δi B 0 .
Therefore, we obtain δi ≥ (f (b∗ ) − f (bi ))/B 0 .

Lemma A.3. For i = 1, . . . , L, we have f (b∗ ) − f (bi ) ≤Qi(f (b∗ ) − f (b0 )) · j=1 (1 − wj kj /B 0 ) .

We now move to proving that the greedy procedure returns a (1 − 1/e)-approximate solution for some b0 in
the enumeration step. If the optimal solution b∗ satisfies|supp+ (b∗ )| ≤ 3, it can be found in the enumeration step.
Therefore, we assume that all the optimal solutions havemore than three positive components. Let s∗1 , s∗2 , s∗3 be elements in S satisfying:


∗ ∗
∗
∗
s∗i ∈
argmax∆ ∨i−1j=1 b (sj )χsj , s, b (s)Proof. We prove this lemma by induction on i. For i =1, then the inequality holds because ∆1 ≥ w1 k1 (f (b∗ ) −for i = 1, 2, 3. Since the size of the support of b∗ is morethan three, such s∗1 , s∗2 and s∗3 clearly exist.

Applying Lemma A.2 repeatedly, we have the following
lemmas.

∗s∈S\{s∗
1 ,...,si−1 }Optimal Budget Allocation: Theoretical Guarantee and Efficient Algorithm

Lemma A.5. For the feasible solution b0 with the support{s∗1 , s∗2 , s∗3 } satisfying b0 (s∗i ) = b∗ (s∗i ) for 1 ≤ i ≤ 3, wehave ∆L ≤ f (b0 )/3.

B.3. Proof of Lemma 4.1
Proof. By simple algebra, we can easily check thatf (b + χs ) − f (b)Proof. It follows that ∆L = f (bL + kL χsL ) −f (bL ) ≤ f (bL ∨ b∗ (sL )χsL ) − f (bL ) since bL (sL ) +kL ≤ b∗ (sL ).
By Lemma 2.2, ∆L is at mostf (b∗ (sL )χsL ) − f (0) = f (b∗ (sL )χsL ), and hence ∆L ≤f (b∗ (s∗1 )χs∗1 ) = ∆(0, s∗1 , b∗ (s∗1 )) by the choice of s∗1 .
Similarly, by the choices of s∗2 and s∗3 , we have ∆L ≤∆(b∗ (s∗1 )χs∗1 , s∗2 , b∗ (s∗2 )) and ∆L ≤ ∆(b∗ (s∗1 )χs∗1 ∨b∗ (s∗2 )χs∗2 , s∗3 , b∗ (s∗3 )). Adding these inequalities, we obtain ∆L ≤ f (b0 )/3.
We are now ready to prove Theorem 2.1. Since f (b) ≥PLf (b0 ) + i=1 ∆i − ∆L , Lemmas A.4 and A.5 imply thatf (b) ≥ (1 − 1/3)f (b0 ) + (1 − 1/e)(f (b∗ ) − f (b0 ))≥ (1 − 1/e)f (b∗ )for the initial solution b0 described in Lemma A.5. This
completes the proof of Theorem 2.1.

B. Proof of Lemmas
B.1. Proof of Lemma 2.2
Proof. If k ≤ x(s) then both sides are 0. If x(s) < k ≤y(s) then the inequality (3) is equivalent to f (x ∨ kχs ) −f (x) ≥ 0, which is valid by monotonicity. Lastly, if k >y(s) then we have f (x ∨ kχs ) + f (y) ≥ f (y ∨ kχs ) + f (x)by submodularity, which directly implies (3).
B.2. Proof of Lemma 2.3
Proof. We prove this lemma by induction on the size of
supp+ (y − x). If |supp+ (y − x)| = 0, that is, x ∨ y =x, then (4) is trivial. Suppose that there is an index s ∈supp+ (y − x). We define y1 = y − y(s)χs . Then y =y1 ∨ y(s)χs and y1 ∧ y(s)χs = 0 hold. By submodularityof x ∨ y1 and x ∨ y(s)χs , we have

= p(b(s)+1)
sX

Y b(v)
Y(1 − p(i)v ),f (b + 2χs ) − f (b + χs )= (1 − ps(b(s)+1) )p(b(s)+2)
sX

the above inequality implies thatf (x ∨ y1 ) + f (x ∨ y(s)χs ) − f (x) ≥ f (x ∨ y).
Therefore, applying the induction hypothesis to x and y1 ,we obtain (4). Thus the statement holds.

Y b(v)
Y(1 − p(i)v ).

t∈Γ(s) v∈Γ(t) i=1

(8)
P
Q
Qb(v)
(i)
Let α := t∈Γ(s) v∈Γ(t) i=1 (1−pv ) for simplicity ofnotations. Then we have f (b + χs ) − f (b) − (f (b + 2χs ) −(b(s)+1)(b(s)+2)(b(s)+1)
f (b + χs )) = ps
α − ps(1 − ps)α ≥(b(s)+2) 2(b(s)+2)(b(s)+2)(b(s)+2)) ≥)) = α(ps(1 − ps
− ps
α(ps
0.

C. Pseudocode of Algorithm
Algorithm 3 S IMPLE G REEDY P ROCEDURE F OR C OM PETITOR M ODEL
1: for each t ∈ T do
2:
Let λ := 1
3:
for k = 1 to 1 + maxs∈Γ(t) b̃(s) do
4:
Let
:=
1 and λt,k
:=
k (t)
 φQ
(k)
λ 1 − s∈Γ(t):b̃(s)≥k (1 − p̃s ) .
Q(k)5:Let λ := λ s∈Γ(t):b̃(s)≥k (1 − p̃s ).
6:
end for
7: end for8: Let b := 0.
9: for i = 1 to B do
10:
ChoosesmaximizingPP(b(s)+1)
φk (t).
t∈Γ(s)
k λt,k rs,k11:
Let b(s) := b(s) + 1.
12:
for t ∈ Γ(s) do
13:
for k = 1 to 1 + maxs∈Γ(t) b̃(s) do(b(s))

14:
Let φk (t) := (1 − rs,kf (x∨y1 )+f (x∨y(s)χs ) ≥ f (x∨y)+f ((x∨y1 )∧(x∨y(s)χs )). 15:
end for16:
end forSince it holds that
17: end for
18: return b(x ∨ y1 ) ∧ (x ∨ y(s)χs ) = x ∨ (y1 ∧ y(s)χs ) = x ∨ 0 = x,(7)t∈Γ(s) v∈Γ(t) i=1)φk (t).