Noname manuscript No.
(will be inserted by the editor)

Multi-Agent Submodular Optimization

arXiv:1803.03767v1 [] 10 Mar 2018

Richard Santiago · F. Bruce Shepherd

Received: date / Accepted: date

Abstract Recent years have seen many algorithmic advances in the area of submodular
optimization: (SO) min / max f (S) : S ∈ F , where F is a given family of feasible sets over a
ground set V and f : 2V → R is submodular. This progress has been coupled with a wealth
of new applications for these models. Our focus is on a more general class of multi-agent
submodular optimization
(MASO) which was introduced by Goel et al. in the minimization
P
setting: min i fi (Si ) : S1 ⊎ S2 ⊎ · · · ⊎ Sk ∈ F . Here we use ⊎ to denote disjoint union
and hence this model is attractive where resources are being allocated across k agents, each
with its own submodular cost function fi (). In this paper we explore the extent to which
the approximability of the multi-agent problems are linked to their single-agent primitives,
referred to informally as the multi-agent gap.
We present different reductions that transform a multi-agent problem into a single-agent
one. For maximization we show that (MASO) admits an O(α)-approximation whenever
(SO) admits an α-approximation over the multilinear formulation, and thus substantially
expanding the family of tractable models. We also discuss several family classes (such as
spanning trees, matroids, and p-systems) that have a provable multi-agent gap of 1. In
the minimization setting we show that (MASO) has an O(α · min{k, log(n) log( logn n )})approximation whenever (SO) admits an α-approximation over the convex formulation. In
addition, we discuss the class of “bounded blocker” families where there is a provably tight
O(log n) gap between (MASO) and (SO).
Keywords submodular optimization · approximation algorithms · multi-agent
1 Introduction
A function f : 2V → R is submodular if f (S) + f (T ) ≥ f (S ∪ T ) + f (S ∩ T ) for any S, T ⊆ V .
We say that f is monotone if f (S) ≤ f (T ) whenever S ⊆ T . Throughout, all submodular
Richard Santiago
McGill University, Montreal, Canada
E-mail: richard.santiagotorres@mail.mcgill.ca
F. Bruce Shepherd
McGill University, Montreal, Canada
E-mail: bruce.shepherd@mcgill.ca

2

Richard Santiago, F. Bruce Shepherd

functions are nonnegative, and we usually assume that f (∅) = 0. Our functions are given
by a value oracle, where for a given set S an algorithm can query the oracle to find its value
f (S).
For a family of feasible sets S ∈ F on a finite ground set V we consider the following
broad class of submodular optimization (SO) problems:
SO(F )

Min / Max f (S) : S ∈ F

(1)

where f is a nonnegative submodular set function on V . There has been an impressive
recent stream of activity around these problems for a variety of set families F . We explore
the connections between these (single-agent) problems and their multi-agent incarnations. In
the multi-agent (MA) version, we have k agents each of which has an associated nonnegative
submodular set function fi , i ∈ [k]. As before, we are looking for sets S ∈ F , however, we
now have a 2-phase task: the elements of S must also
P be partitioned amongst the agents.
Hence we have set variables Si and seek to optimize i fi (Si ). This leads to the multi-agent
submodular optimization (MASO) versions:
MASO(F )

Min / Max

Pk

i=1

fi (Si ) : S1 ⊎ S2 ⊎ · · · ⊎ Sk ∈ F .

(2)

The special case when F = {V } has been previously examined both for minimization
(the minimum submodular cost allocation problem [19,41,9,5]) and maximization (submodular welfare problem [32,42]). For general families F , however, we are only aware of
the development in Goel et al. [14] for the minimization setting. A natural first question is
whether any multi-agent problem could be directly reduced (or encoded) to a single-agent
one over the same ground set V . Goel et al. give an explicit example where such a reduction
does not exist. More emphatically, they show that when F consists of vertex covers in a
graph, the single-agent (SA) version (i.e., (1)) has a 2-approximation while the MA version
has an inapproximability lower bound of Ω(log n).
Our first main objective is to explain the extent to which approximability for multi-agent
problems is intrinsically connected to their single-agent versions, which we also refer to as
the primitive associated with F . We refer to the multi-agent (MA) gap as the approximationfactor loss incurred by moving to the MA setting. For general families, we are only aware
of Goel et al.’s work on MA Submodular Minimization, where most of the approximability
results are negative (polynomial inapproximability).
Our second objective is to extend the multi-agent model and show that in some cases this
larger class remains tractable. Specifically, we define the capacitated multi-agent submodular
optimization (CMASO) problem as follows:
CMASO(F )

Pk
max / min
i=1 fi (Si )
s.t. S1 ⊎ · · · ⊎ Sk ∈ F
Si ∈ Fi , ∀i ∈ [k]

(3)

where we are supplied with subfamilies Fi . Many existing applications fit into this framework
and some of these can be enriched through the added flexibility of the capacitated model.
For instance, one may include set bounds on the variables: Li ⊆ Si ⊆ Ui for each i, or simple
cardinality constraints: |Si | ≤ bi for each i. A well-studied ([13,16,4]) application of CMASO
in the maximization setting is the Separable Assignment Problem (SAP) , which corresponds
to the setting where the objectives are taken to be modular, the Fi downward closed (i.e.
hereditary) families, and F to be the trivial 2V . We believe the CMASO framework has

Multi-Agent Submodular Optimization

3

considerable potential for future applications and we illustrate this with concrete examples
in Section 1.2.
Prior work in both the single and multi-agent settings is summarized in Section 1.3. We
present our main results next.
1.1 Our contributions
We first discuss the minimization side of MASO (i.e. (2)). Here the work of [9] showed
that for general nonnegative submodular functions the problem is in fact inapproximable
within any multiplicative factor even in the case where F = {V } and k = 3 (since it is
NP-Hard to decide whether the optimal value is zero). Hence we focus almost completely
on nonnegative monotone submodular objectives fi . In fact, even in the single-agent setting
with a nonnegative monotone submodular function f , there exist a number of polynomial
hardness results over fairly simple set families F ; examples include minimizing a submodular
function subject to a cardinality constraint [40] or over the family of spanning trees [14].
We show, however, that if the SA primitive for a family F admits approximation via a
natural “blocking” convex relaxation (see Appendices A and B), then we may extend this
to its multi-agent version with a modest blow-up in the approximation factor.
Theorem 1 Suppose there is a (polytime) α(n)-approximation for monotone SO(F ) minimization via the blocking convex relaxation. Then there is a (polytime) O(α(n)·min{k, log(n) log( logn n )})approximation for monotone MASO(F ) minimization.
We note that the log(n) log( logn n ) approximation loss due to having multiple agents
(i.e the MA gap) is in the right ballpark. This is because for the vertex cover problem
there is a factor 2-approximation for SA submodular minimization, and a tight O(log n)approximation for the multi-agent version [14].
We also discuss how Goel et al’s O(log n)-approximation for MA vertex cover is a special
case of a more general phenomenon. Their analysis only relies on the fact that the feasible
family (or at least its upwards closure) has a bounded blocker property. Given a family F ,
the blocker B(F ) of F consists of the minimal sets B such that B ∩ F 6= ∅ for each F ∈ F .
We say that B(F ) is β-bounded if |B| ≤ β for all B ∈ B(F ).
Families with bounded blockers have been previously studied in the SA minimization
setting, where the works [25,23] show that β-approximations are always available. Our next
result (combined with these) establishes an O(log n) MA gap for bounded blocker families,
thus improving the O(log(n) log( logn n )) factor in Theorem 1 for general families. We remark
that this O(log n) MA gap is tight due to examples like vertex covers (2-approximation
for SA and a tight O(log n)-approximation for MA) or submodular facility location (1approximation for SA and a tight O(log n)-approximation for MA).
Theorem 2 Let F be a family with a β-bounded blocker. Then there is a β ln(n)-approximation
algorithm for monotone MASO(F ) minimization.
While our work focuses almost completely on monotone objectives, we show in Section
2.4 that upwards closed families with a bounded blocker remain tractable under some special
types of nonmonotone objectives introduced by Chekuri and Ene.
We conclude our minimization work by discussing a class of families which behaves well
for MA minimization despite not having a bounded blocker. More specifically, in Section 2.5
we observe that crossing (and ring) families have an MA gap of O(log n).

4

Richard Santiago, F. Bruce Shepherd

Theorem 3 There is a tight ln(n)-approximation for monotone MASO(F ) minimization
over crossing families F .

We now discuss our contributions for the maximization setting. Our main result, whose
proof we present in Section 3.3, is establishing that if the SA primitive for a family F admits
approximation via its multilinear relaxation (see Section 3.2), then we may extend this to
its multi-agent version up to a constant factor loss.

Theorem 4 If there is a (polytime) α(n)-approximation for monotone SO(F ) maximization
via its multilinear relaxation, then there is a (polytime) (1 − 1/e) · α(n)-approximation for
monotone MASO(F ) maximization. Furthermore, given a downwards closed family F , if
there is a (polytime) α(n)-approximation for nonmonotone SO(F ) maximization via its
multilinear relaxation, then there is a (polytime) 0.385·α(n)-approximation for nonmonotone
MASO(F ) maximization.
We remark that the (1 − 1/e) MA gap in the monotone case is tight due to examples
like F = {V }, where there is a trivial 1-approximation for the SA problem and a tight
(1 − 1/e)-approximation for the MA version [42].
In Section 3 we also describe a generic reduction that transforms any CMASO(F ) problem (i.e. any multi-agent problem (3)) into a SO(F ′ ) problem. We use the simple idea of
viewing assignments of elements v to agents i in a multi-agent bipartite graph. This was
first proposed by Lehmann et al in [32] and also used in Vondrak’s work [42]. In those cases
F = {V } and Fi = 2V . Here we discuss the impact of the reduction on more general families
F and Fi , where there is a priori no reason that this should be well-behaved. We show how
several properties of the objective and certain family of feasible sets stay invariant (i.e.
preserved) under the reduction. These lead to several algorithmic consequences, the most
important ones being for maximization where we show a MA gap of 1 for several families.
Theorem 5 Let F be a matroid, a p-matroid intersection, or a p-system. Then, if there is a
(polytime) α-approximation algorithm for monotone (resp. nonmonotone) SO(F ) maximization, there is a (polytime) α-approximation algorithm for monotone (resp. nonmonotone)
MASO(F ) maximization.
In the setting of CMASO (i.e. (3)) our invariance results provide additional modelling
flexibility. This allows us to combine several constraints while keeping approximation factors fairly good. For instance, for a monotone maximization instance of CMASO where F
corresponds to a p-matroid intersection and the Fi are all matroids, our results from Section 3 lead to a (p + 1 + ǫ)-approximation algorithm. We believe that these, combined with
the other results from Section 3, substantially expand the family of tractable models for
maximization.
While the impact of this reduction is more for maximization, it also has some interesting
consequences in the minimization setting. We discuss in Section 3.4 how some of our results
help explaining why for the family of spanning trees, perfect matchings, and st-paths, the
approximations factors revealed in [14] for the monotone minimization problem are the same
for both the single-agent and multi-agent versions.
1.2 Some applications of capacitated multi-agent optimization
In this section we present several problems in the literature which are special cases of
Problem (3). We also indicate cases where the extra generality of CMASO gives modelling
advantages. We start with the maximization setting.

Multi-Agent Submodular Optimization

5

Example 1 (The Submodular Welfare Problem) The most basic problem in the maximization setting arises when we take the feasible space F = {V }. This describes a well-known
model (introduced in [32]) for allocating goods to agents, each of which has a submodular
valuation (utility) function over baskets of goods. This is formulated as (3) by considering
nonnegative monotone functions fi , F = {V }, and Fi = 2V for all i.
Example 2 (The Separable Assignment Problem) An instance of the Separable Assignment
Problem (SAP) consists of m items and n bins. Each bin j has an associated downwards
closed collection of feasible sets Fj , and a modular function vj (i) that denotes the value of
placing
item i in bin j. The goal is to choose disjoint feasible sets Sj ∈ Fj so as to maximize
Pn
v
j=1 j (Sj ). This well-studied problem ([13,16,4]) corresponds to a CMASO instance where
all the objectives are modular, F = 2V , and the families Fi are downwards closed.
We next discuss an example where using matroid-capacity constraints Fi in CMASO is
beneficial.
Example 3 (Recommendation Systems and Matroid Constraints) This is a widely deployed
class of problems that entails the targeting of product ads to a mass of (largely unknown)
buyers or “channels”. In [7] a “meta” problem is considered where (known) prospective
buyers are recommended to interested sellers. This type of recommendation system incurs
additional constraints such as (i) bounds on the size of the buyer list provided to each seller
(e.g., constrained by a seller’s budget) and (ii) bounds on how often a buyer appears on a
list (to not bombard buyers). These constraints are modelled as a “b-matching” problem
in a bipartite buyer-seller graph GB . They also consider a more sophisticated model which
incorporates “conflict-aware” constraints on the buyer list for each seller, e.g., no more than
one buyer from a household should be recommended to a seller. They model conflicts using
extra edges amongst the buyer nodes and they specify an upper bound on the number of
allowed conflict edges induced by a seller’s recommendation list. Heuristics for this (linearobjective) model [7] are successfully developed on Ebay data, even though the computational
problem is shown to be NP-hard. In fact, subsequent work [6] shows that conflict-aware bmatching suffers an inapproximability bound of O(n1−ǫ ). We now propose an alternative
model which admits anPO(1)-approximation. Moreover, we allow a more general submodular
multi-agent objective i fi (Bi ) where Bi are the buyers recommended to seller i.
To formulate this in the CMASO model (3) we consider the same complete buyer-seller
bipartite graph from previous work. We now represent a buyer list Bi as a set of edges Si .
In order that each buyer v is not recommended more than its allowed maximum b(v), we
add the constraint that the number of edges in F = ∪Si which are incident to buyer node v
is at most b(v). The family F of such sets F forms a partition matroid. Hence the problem
can be formulated as:
Pk
max
i=1 fi (Si )
s.t. S1 ⊎ S2 · · · ⊎ Sk ∈ F
Si ∈ Fi , ∀i ∈ [k]
We now define Fi to enforce conflict constraints for the seller as follows. Let Vi denote
the edges from seller node i to allowable buyers for i (possibly Vi is all buyers). We may then
partition Vi into “households” Vij . In order to model conflicts, we insist that Si is allowed
to include at most 1 element from each Vij . The resulting family Fi is a partition or laminar
matroid. Our results imply that this new version has a polytime O(1)-approximation (in the
value oracle model).

6

Richard Santiago, F. Bruce Shepherd

Example 4 (Sensor Placement) The problem of placing sensors and information gathering
has been popular in the submodularity literature [26,28,27]. We are given a set of sensors V
and a set of possible locations {1, 2, . . . , k} where the sensors can be placed. There is also a
budget constraint restricting the total number of sensors that can be deployed. The goal is
to place sensors at some of the locations so as to maximize the “informativeness” gathered.
It is again natural to consider a diminishing return property for P
this information gathering
objective. Consider a multi-agent submodular objective function i∈[k] fi (Si ), where fi (Si )
measures the “informativeness” of placing sensors Si at location i. A natural formulation
for sensor placement is then
Pk
max
i=1 fi (Si )
s.t. S1 ⊎ · · · ⊎ Sk ∈ F
Si ∈ F i ,

where F := {S ⊆ V : |S| ≤ b} imposes the budget constraint and Fi gives additional
modelling flexibility. For instance, we may define Fi = {S ⊆ V : S ⊆ Vi , |S| ≤ bi }, where Vi
are the allowed sensors for location i and bi is an upper bound on the sensors located there.
Notice that both F and the Fi are matroids and hence our algorithms apply.
We now discuss Problem (3) in the minimization setting.
Example 5 (Minimum Submodular Cost Allocation) Similar to the maximization setting,
the most basic problem in the minimization setting arises when we simply take the feasible
space F = {V }, and the agents are allowed to take any subset of V (i.e. Fi = 2V for all i).
This problem,
Pk
min
i=1 fi (Si )
s.t. S1 ⊎ · · · ⊎ Sk = V,

has been widely considered in the literature for both monotone and nonmonotone functions
[41,9,5], and is referred to as the Minimum Submodular Cost Allocation (MSCA)
problem1 (introduced in [19,41] and further developed in [5]).
The framework from (3) allows us to incorporate additional constraints into the MSCA
problem by defining the families Fi appropriately. The most natural are to impose cardinality
constraints on the number of elements that an agent can take, or to only allow agent i
to take a set Si of elements satisfying some bounds Li ⊆ Si ⊆ Ui . For instance, in the
Submodular Facility Location problem, one can model that a potential facility must serve
some customers, and may only serve customers within a pre-specified region given by Ui .
We discuss this in detail on separate work (see [38] Section 5).
Example 6 (Multi-agent Minimization) Goel et al [14] consider the special case of Problem
(3) for monotone submodular functions in which F is a nontrivial collection of subsets of V
(i.e. F ⊂ 2V ) and there is no restriction on the Fi (i.e. Fi = 2V for all i). In particular, given
a graph G they consider the families of vertex covers, spanning trees, perfect matchings,
and shortest st paths.
1.3 Related work
Single Agent Optimization. The high level view of the tractability status for unconstrained (i.e., F = 2V ) submodular optimization is that both maximization and minimization generally behave well. Minimizing a submodular set function is a classical combinatorial
1

Sometimes referred to as submodular procurement auctions.

Multi-Agent Submodular Optimization

7

optimization problem which can be solved in polytime [17,39,21]. Unconstrained maximization on the other hand is known to be inapproximable for general submodular set functions
but admits a polytime constant-factor approximation algorithm when f is nonnegative [2,
10].
In the constrained maximization setting, the classical work [37,36,12] already established an optimal (1 − 1/e)-approximation factor for maximizing a nonnegative monotone
submodular function subject to a cardinality constraint, and a (1/(k +1))-approximation for
maximizing a nonnegative monotone submodular function subject to k matroid constraints.
This approximation is almost tight in the sense that there is an (almost matching) factor
Ω(log(k)/k) inapproximability result [20]. For nonnegative monotone functions, [42,4] give
an optimal (1 − 1/e)-approximation based on multilinear extensions when F is a matroid;
[29] provides a (1−1/e−ǫ)-approximation when F is given by a constant number of knapsack
constraints, and [31] gives a local-search algorithm that achieves a (1/k − ǫ)-approximation
(for any fixed ǫ > 0) when F is a k-matroid intersection. For nonnegative nonmonotone
functions, a 0.385-approximation is the best factor known [1] for maximization under a matroid constraint, in [30] a 1/(k + O(1))-approximation is given for k matroid constraints with
k fixed. A simple “multi-greedy” algorithm [18] matches the approximation of Lee et al. but
is polytime for any k. Vondrak [43] gives a 21 (1 − ν1 )-approximation under a matroid base
constraint where ν denotes the fractional base packing number. Finally, Chekuri et al [44]
introduce a general framework based on relaxation-and-rounding that allows for combining
different types of constraints. This leads, for instance, to 0.38/k and 0.19/k approximations
for maximizing nonnegative submodular monotone and nonmonotone functions respectively
under the combination of k matroids and ℓ = O(1) knapsacks constraints.
For constrained minimization, the news is worse [14,40,22]. If F consists of spanning
trees (bases of a graphic matroid) Goel et al [14] show a lower bound of Ω(n), while in the
case where F corresponds to the
√ cardinality constraint {S : |S| ≥ k} Svitkina and Fleischer
[40] show a lower bound of Ω̃( n). There are a few exceptions. The problem can be solved
exactly when F is a ring family ([39]), triple family ([17]), or parity family ([15]). In the
context of NP-Hard problems, there are almost no cases where good (say O(1) or O(log n))
approximations exist. We have that the submodular vertex cover admits a 2-approximation
([14,22]), and the k-uniform hitting set has O(k)-approximation.
Multi-agent Problems. In the maximization setting the main multi-agent problem
studied is the Submodular Welfare Maximization (F = {V }) for which the initial 1/2approximation [32] was improved to 1 − 1/e by Vondrak [42] who introduced the continuous
greedy algorithm. This approximation is in fact optimal [24,34]. We are not aware of maximization work for Problem (2) for a nontrivial family F .
For the multi-agent minimization setting, MSCA (i.e. F = {V }) is the most studied
application of Problem (2). For nonnegative monotone functions, MSCA is equivalent to the
Submodular Facility Location problem considered in [41], where a tight O(log n) approximation is given. If the functions fi are nonnegative and nonmonotone, then no multiplicative
factor approximation exists [9]. If, however, the functions can be written as fi = gi + h
for some nonnegative monotone submodular gi and a nonnegative symmetric submodular
function h, an O(log n) approximation is given in [5]. In the more general case where h is
nonnegative submodular, an O(k log n) approximation is provided in [9], and this is tight
[35].
Goel et al [14] consider the minimization case of (3) for nonnegative monotone submodular functions, in which F is a nontrivial collection of subsets of V (i.e. F ⊂ 2V ) and there is
no restriction on the Fi (i.e. Fi = 2V for all i). In particular, given a graph G they consider

8

Richard Santiago, F. Bruce Shepherd

the families of vertex covers, spanning trees, perfect matchings, and shortest st paths. They
provide a tight O(log n) approximation for the vertex cover problem, and show polynomial
hardness for the other cases. To the best of our knowledge [14] is the only work on Problem
(2) for nontrivial collections F .
2 Multi-agent submodular minimization
In this section we seek generic reductions for multi-agent minimization problems to their
single-agent primitives. We mainly focus on the case of nonnegative monotone submodular
objective functions and we work with a natural blocking convex relaxation that is obtained
via the Lovász extension of a set function (cf. Appendices A and B). We show that if the
SA primitive admits approximation via such relaxation, then we may extend this to its MA
version up to an O(min{k, log(n) log( logn n )}) factor loss.
As noted already, the log(n) log( logn n ) approximation factor loss due to having multiple
agents is in the right ballpark since for vertex covers there is a factor 2-approximation for SA
submodular minimization, and a tight O(log n)-approximation for the multi-agent version
[14]. In Section 2.4 we discuss an extension of this vertex cover result to a larger class of
families with a MA gap of O(log n).
2.1 The single-agent and multi-agent formulations
Due to monotonicity, one may often assume that we are working with a family F which
is upwards-closed, aka a blocking family (cf. [23]). The advantage is that to certify whether
F ∈ F , we only need to check that F ∩ B 6= ∅ for each element B of the family B(F ) of
minimal blockers of F . We discuss the details in Appendix A.
For a set function f : {0, 1}V → R with f (∅) = 0 one can define its Lovász extension
L
f : RV+ → R (introduced in [33]) as follows. Let 0 < v1 < v2 < ... < vm be the distinct
positive values taken in some vector z ∈ RV+ , and let v0 = 0. For each i ∈ {0, 1, ..., m} define
the set Si := {j : zj > vi }. In particular, S0 is the support of z and Sm = ∅. One then
defines (see Appendix B.1 for equivalent definitions):
L

f (z) =

m−1
X
i=0

(vi+1 − vi )f (Si ).

It follows from the definition that f L is positively homogeneous, that is f L (αz) = αf L (z)
for any α > 0 and z ∈ RV+ . Moreover, it is also straightforward to see that f L is a monotone
function if f is. We have the following result due to Lovász.
Lemma 1 (Lovász [33]) The function f L is convex if and only if f is submodular.
This now gives rise to natural convex relaxations for the single-agent and multi-agent
problems (see Appendix B) based on the blocking formulation P ∗ (F ) := {z ≥ 0 : z(B) ≥
1 for all B ∈ B(F )}. The single-agent Lovász extension formulation (used in [22,23]) is:
(SA-LE)

min f L (z) : z ∈ P ∗ (F ),

and the multi-agent Lovász extension formulation (used in [5] for F = {V }) is:
X
fiL (zi ) : z1 + z2 + · · · + zk ∈ P ∗ (F ).
(MA-LE)
min
i∈[k]

(4)

(5)

Multi-Agent Submodular Optimization

9

By standard methods (see Appendix B) one may solve these problems in polytime if one
can separate over the blocking formulation P ∗ (F ). This is often the case for many natural
families such as spanning trees, perfect matchings, st-paths, and vertex covers. Moreover,
if the single-agent formulation (SA-LE) can be solved in polytime so can the corresponding
multi-agent formulation (MA-LE) (see Appendix B.3).
2.2 Rounding the (MA-LE) formulation for upwards closed families F
It is shown in [5] that in the setting of monotone objectives and F = {V }, a fractional
solution of (MA-LE) can be rounded into an integral one at an O(log n) factor loss. Moreover,
they show this still holds for some special types of nonmonotone objectives.
Theorem 6 ([5]) Let z1 +
Pz2 + · · · + zVk be a feasible solution for (MA-LE) in the setting where F = {V } (i.e.
i∈[k] zi = χ ) and fi = gi + h where the gi are nonnegative
monotone submodular and h is nonnegative symmetric submodular. Then there is a randomized rounding
procedure that outputs
an integral feasible solution z̄1 + z̄2 + · · · + z̄k
P
P
such that i∈[k] fiL (z̄i ) ≤ O(log n) i∈[k] fiL (zi ) on expectation. That is, we get a partition
P
P
S1 , S2 , . . . , Sk of V such that i∈[k] fi (Si ) ≤ O(log n) i∈[k] fiL (zi ) on expectation.
Our next result shows that the above rounding procedure can be adapted in a straightforward way to the setting where we have a general upwards closed family F . We omit the
proof to Appendix C.
Theorem 7 Consider an instance of (MA-LE) where F is an upwards closed family and
fi = gi +h where the gi are nonnegative monotone submodular and hP
is nonnegative symmetric submodular. Let z1 + z2 + · · ·+ zk be a feasible solution such that i∈[k] zi ≥ χU for some
U ∈ F . Then there is a randomized
feasible soluP that outputs an integral P
P rounding procedure
tion z̄1 + z̄2 + · · · + z̄k such that i∈[k] z̄i ≥ χU and i∈[k] fiL (z̄i ) ≤ O(log |U |) i∈[k] fiL (zi )
U
on expectation. That is, we get a subpartition S1 , S2 , . . . , Sk such that i∈[k] Si ⊇ U ∈ F
P
P
and i∈[k] fi (Si ) ≤ O(log |U |) i∈[k] fiL (zi ) on expectation.
2.3 A multi-agent O(α(n) · min{k, log(n) log( logn n )})-approximation
In this section we present the proof of Theorem 1. The main idea behind our reductions is
the following. We start with an optimal solution z ∗ = z1∗ + z2∗ + · · · + zk∗ to the multi-agent
relaxation (MA-LE) and build a new feasible solution ẑ = ẑ1 + ẑ2 + · · ·+ ẑk where the ẑi have
supports Vi that are pairwise disjoint. We interpret the Vi as the set of items associated (or
pre-assigned) to agent i. Once we have such a pre-assignment we consider the single-agent
problem min g(S) : S ∈ F where
X
fi (S ∩ Vi ).
(6)
g(S) =
i∈[k]

It is clear that g is nonnegative monotone submodular since the fi are as well. Moreover,
for any solution S ∈ F for this single-agent problem wePobtain a MA solution
P of the same
cost by setting Si = S ∩ Vi , since we then have g(S) = i∈[k] fi (S ∩ Vi ) = i∈[k] fi (Si ).
For a set S ⊆ V and a vector z ∈ [0, 1]V we denote by z|S the truncation of z to elements
of S. That is, we set z|S (v) = z(v) for each v ∈ S and to zero otherwise. Then notice that

10

Richard Santiago, F. Bruce Shepherd

P
by definition of g we have that g L (z) = i∈[k] fiL (z|Vi ). Moreover, if we also have that the
P
P
Vi are pairwise disjoint, then i∈[k] fiL (z|Vi ) = i∈[k] fiL (zi ). We formalize this observation
in the following result.

Proposition 1 Let z = z1 +z2 +· · ·+zk be a feasibleP
solution to (MA-LE)
P where the vectors
zi have pairwise disjoint supports Vi . Then g L (z) = i∈[k] fiL (z|Vi ) = i∈[k] fiL (zi ).
The next two results show how one can get a feasible solution ẑ = ẑ1 + ẑ2 + · · · + ẑk
where the ẑi have pairwise disjoint supports, by losing a factor of O(log(n) log( logn n )) and
k respectively. We remark that these two results combined prove Theorem 1.

Theorem 8 Suppose there is a (polytime) α(n)-approximation for monotone SO(F ) minimization based on rounding (SA-LE). Then there is a (polytime) O(α(n) log(n) log( logn n ))approximation for monotone MASO(F ) minimization.
Proof Let z ∗ = z1∗ +z2∗ +· · ·+zk∗ denote an optimal solution to (MA-LE) with value OP Tf rac .
As discussed in Appendix B.3, this can be found in polytime under fairly mild assumptions.
In order to apply a black box single-agent rounding algorithm we must create a different
multi-agent solution. This is done in several steps, the first few of which are standard. The
key steps are the fracture, expand and return steps which arise later in the process.
P
1
. Note that v small z ∗ (v) ≤ 21 , and so for any
Call an element v small if z ∗ (v) ≤ 2n
blocking set B ∈ B(F ), we have that at most 12 of z ∗ (B) is contributed by small elements.
We obtain a new feasible solution z ′ = z1′ + z2′ + · · · + zk′ by removing all small elements
from the support of the zi∗ and then doubling the resulting vectors. By the monotonicity
and homogeneity of the fiL , this at most doubles the cost of OP Tf rac .
We now prune the solution z ′ = z1′ + z2′ + · · · + zk′ a bit more. Let Zj be the elements
1
for any element in
v such that z ′ (v) ∈ (2−(j+1) , 2−j ] for j = 0, 1, 2, . . . , L. Since z ′ (v) > 2n
the support, we have that L ≤ log(n). We call Zj bin j and define rj = 2j . We round up
each v ∈ Zj so that z ′ (v) = 2−j by augmenting the zi′ values by at most a factor of 2. We
may do this simultaneously for all v by possibly “truncating” the values associated to some
of the elements. As before, this is fine since the fiL are monotone. In the end, we call this a
uniform solution z ′′ = z1′′ + z2′′ + · · · + zk′′ in the sense that each z ′′ (v) is some power of 2.
Note that its cost is at most 4 · OP Tf rac .
′′
Fracture. We now fracture the vectors zi′′ by defining vectors zi,j
= zi′′ |Zj for each
i ∈ [k] and each j ∈ {0, 1, . . . , L}, where recall that the notation z|S denotes the truncation
PL
′′
.
of z to elements of S. Notice that zi′′ = j=0 zi,j
′′
Expand. Now for each j ∈ {0, 1, . . . , L} we blow up the vectors zi,j
by a factor rj .
1
′′
(Don’t worry, this scaling is temporary.) Since z (v) = rj for each v ∈ Zj , this means that
the resulting values yield a (probably fractional) cover of Zj . We can then use the rounding
procedure discussed in P
Theorem 6 (with ground P
set Zj and taking h ≡ 0) to get an integral
′′
′′′
′′′
) on expectation.
) ≤ O(log |Zj |) i fiL (rj · zi,j
solution zi,j
such that i fiL (zi,j
Return.
Now
we
go
back
to
get
a
new
MA-LE
solution
ẑ
=
ẑ1 + ẑ2 + · · · + ẑk by setting
PL 1 ′′′
′′
z
.
Note
that
ẑ
=
z
and
so
this
is
indeed
feasible
(and again uniform).
ẑi =
j=0 rj i,j

Multi-Agent Submodular Optimization

11

Moreover, we have that the cost of this new solution satisfies
k
X

fiL (ẑi ) =

i=1

L
k X
L
L
k
X
X
X
1 ′′′
1 L ′′′
1 X L ′′′
fiL (
fi (zi,j )
zi,j ) ≤
fi (zi,j ) =
r
r
r
j=0 j
i=1
i=1 j=0 j
j=0 j i=1

k
X

k
L
L X
k
X
X
X
n
′′
fiL (zi′′ )) ≤ O(log(n) log(
log(|Zj |)
log(|Zj |)fiL (zi,j
)) ≤ O(
))·OP TMA ,
≤ O(
log n
i=1
j=0
j=0 i=1

where in the first inequality we use the convexity and homogeneity of the fiLP
, in the second
′′′
), in
inequality we use again the homogeneity together with the upper bound for i fiL (zi,j
′′
′′
the third inequality we use monotonicity and the fact that zi,j ≤ zi for all j, and in the last
Pk
one we use that i=1 fiL (zi′′ ) ≤ 4 · OP Tf rac ≤ 4 · OP TMA and
L
X
j=0

log |Zj | = log(

L
Y

j=0

|Zj |) ≤ log(

PL

j=0

|Zj |

L+1

)L+1 = (L+1)·log(

n
n
) = O(log(n) log(
)),
L+1
log n

where the inequality follows from the AM-GM inequality.
Single-Agent Rounding. In the last step we use the function g defined in (6), with sets
Vi corresponding to the support of the ẑi . Given our α-approximation rounding assumption
for (SA-LE), we can round ẑ to find a set Ŝ such that g(Ŝ) ≤ αg L (ẑ). Then, by setting
Ŝi = Ŝ ∩ Vi we obtain a MA solution satisfying:
X

i∈[k]

fi (Ŝi ) = g(Ŝ) ≤ αg L (ẑ) = α

X
i

fiL (ẑi ) ≤ α · O(log(n) log(

n
)) · OP TMA ,
log n

where the second equality follows from Proposition 1. This completes the proof.

⊓
⊔

We now give an approximation in terms of the number of agents, which becomes preferable when k < log(n) log( logn n ).
Lemma 2 Suppose there is a (polytime) α(n)-approximation for monotone SO(F ) minimization based on rounding (SA-LE). Then there is a (polytime) kα(n)-approximation for
monotone MASO(F ) minimization.
Proof Let z ∗ = z1∗ +z2∗ +· · ·+zk∗ denote an optimal solution to (MA-LE) with value OP Tf rac .
We build a new feasible solution ẑ = ẑ1 + ẑ2 + · · · + ẑk as follows. For each element v ∈ V
let i′ = arg maxi∈[k] zi∗ (v), breaking ties arbitrarily. Then set ẑi′ (v) = kzi∗ (v) and ẑi (v) = 0
for each i 6= i′ . By construction we have ẑ ≥ z ∗ , and hence this is indeed a feasible solution.
Moreover, by construction we also have that ẑi ≤ kzi∗ for each i ∈ [k]. Hence, given the
monotonicity and homogeneity of the fiL we have
X
i∈[k]

fiL (ẑi ) ≤

X
i∈[k]

fiL (kzi∗ ) = k

X
i∈[k]

fiL (zi∗ ) = k · OP Tf rac ≤ k · OP TMA .

Since the ẑi have disjoint supports Vi , we can now use the function g defined in (6) and do
a single-rounding argument as in Theorem 8. This completes the proof.
⊓
⊔

12

Richard Santiago, F. Bruce Shepherd

We note that the above result does not particularly depend on the blocking formulation
P ∗ (F ). It still holds true for any other upwards closed relaxation of conv({χS : S ∈ F })
that we decide to use in the (SA-LE) convex formulation.
The above lemma has interesting consequences in the case where F = {V }. This is the
submodular facility location problem considered by Svitkina and Tardos in [41]. They give an
O(log n)-approximation where n denotes the number of customers/clients/demands. Lemma
2 implies we also have a k-approximation which is preferable in facility location problems
where the number of customers swamps the number of facility locations (for instance, for
Amazon).
Corollary 1 There is a polytime k-approximation for submodular facility location, where k
denotes the number of facilities.
Proof The single-agent version of the problem is the trivial min f (S) : S ∈ {V }. Hence a
polytime exact algorithm is available for the single-agent problem and thus by Lemma 2 a
polytime k-approximation is available for the multi-agent version.
⊓
⊔
2.4 Multi-agent minimization with bounded blockers
In Section 2.3 we established an O(log(n) log( logn n )) MA gap whenever there is a SA approximation algorithm based on the (SA-LE) formulation. For the vertex cover problem,
however, there is an improved MA gap of O(log n) due to Goel et al. In this section we
generalize their result by describing a larger class of families wtih such MA gap.
The 2 ln(n)-approximation algorithm of Goel et al. for multi-agent vertex cover relies
only on the fact that the feasible set family has the following bounded blocker property. We
call a clutter (family of noncomparable sets) F β-bounded if |F | ≤ β for all F ∈ F . Recall
that the blocker of a clutter F , denoted by B(F ), is the set of all minimal B such that
B ∩ F 6= ∅ for all F ∈ F . We then say that F has a β-bounded blocker if |B| ≤ β for each
B ∈ B(F ). The main SA minimization result for such families is the following.
Theorem 9 ([23, 25]) Let F be a family with a β-bounded blocker. Then there is a βapproximation algorithm for monotone SO(F ) minimization. If P ∗ (F ) has a polytime separation oracle, then this is a polytime algorithm.
Our next result establishes an O(log n) MA gap for families with a bounded blocker.
In fact, while our work has focused on monotone objectives (due to the inapproximabiltiy
results for general submodular fi ) the next result extends to some special types of nonmonotone objectives. These were introduced in [5] and [9], where a tractable middle-ground is
found for the minimum submodular cost allocation problem (where F = {V }). They work
with objectives fi = gi + h where the gi are monotone submodular and h is symmetric
submodular (in [5]) or just submodular (in [9]).
We remark that by taking h ≡ 0 (which is symmetric submodular), we obtain a result
for monotone functions. We note that in this setting we do not need F to be upwards closed,
since due to monotonicity we can work with the upwards closure of F without loss of generality as previously discussed on Section 2.1 (see Appendix A for further details). Moreover,
as previously pointed out, this O(log n) MA gap is tight due to examples like vertex covers
(2-approximation for SA and a tight O(log n)-approximation for MA) or submodular facility
location (1-approximation for SA and a tight O(log n)-approximation for MA).

Multi-Agent Submodular Optimization

13

Theorem 10 Let F be an upwards closed family with a β-bounded blocker. Let the objectives
be of the form fi = gi + h where each gi is nonnegative monotone submodular and h is
nonnegative symmetric submodular. Then there is a randomized O(β log n)-approximation
algorithm for the associated M ASO(F ) minimization problem. If P ∗ (F ) has a polytime
separation oracle, then this is a polytime algorithm.
P
Proof Let z ∗ = i∈[k] zi∗ be an optimal solution to (MA-LE) with value OP Tf rac . Consider
P
the new feasible solution given by βz ∗ = i∈[k] βzi∗ and let U = {v ∈ V : βz ∗ (v) ≥ 1}. Since
P
F has a β-bounded blocker it follows that U ∈ F . We now have that i∈[k] βzi∗ is a feasible
P
solution such that i∈[k] βzi∗ ≥ χU . Thus, we can use Theorem 7 to get an integral feasible
P
P
P
P
solution i∈[k] z̄i such that i∈[k] z̄i ≥ χU and i∈[k] fiL (z̄i ) ≤ O(log |U |) i∈[k] fiL (βzi∗ ) ≤
β · O(log n) · OP Tf rac on expectation.
⊓
⊔
It is shown in [9] (see their Proposition 10) that given any nonnegative submodular
′
function h, one may define a nonnegative
P submodular function h such that for
P ′ symmetric
any partition S1 , S2 , . . . , Sk we have i h (Si ) ≤ k i h(Si ). This, with our previous result,
yields the following corollary.
Corollary 2 Let F be an upwards closed family with a β-bounded blocker. Let the objectives
be of the form fi = gi + h where each gi is nonnegative monotone submodular and h is
nonnegative submodular. Then there is a randomized O(kβ log n)-approximation algorithm
for the associated M ASO(F ) minimization problem.
One may wish to view the above results through the lens of MA gaps, leading to the
question of what is the associated SA primitive? For gi + h objectives, the SA version
should be for general (or symmetric) nonnegative submodular objectives. Moreover, as we
only use upwards closed families, one may deduce that these single-agent versions have βappoximations via the concept of the monotone closure of a nonmonotone objective from
[23]. Hence our results establish MA gaps of O(log n) (resp. O(k log n)) in these nonmonotone
settings (and the factor of k is tight [35]).
Before concluding this section, we note that Theorems 1 and 9 imply a kβ-approximation
for families with bounded blockers, which becomes preferable when k < O(log n).
Corollary 3 Let F be a family with a β-bounded blocker. Then there is a kβ-approximation
algorithm for the associated monotone M ASO(F ) minimization problem.
2.5 Multi-agent minimization over ring and crossing families
It is well known ([39]) that submodular minimization can be solved exactly in polynomial
time over a ring family. In this section we observe that the MA problem over this type of
constraint admits a tight ln(n)-approximation. More generally, we consider crossing families.
A family F of subsets of V forms a ring family (aka lattice family) if for each A, B ∈ F
we also have A ∩ B, A ∪ B ∈ F . A crossing family is one where we only require it for sets
where A \ B, B \ A, A ∩ B, V − (A ∪ B) are all non-empty. Hence any ring family is a crossing
family.
For any crossing family F and any u, v ∈ V , let Fuv = {A ∈ F : u ∈ A, v 6∈ A}. It
is easy to see that Fuv is a ring family. Moreover, we may solve the original MA problem
by solving the associated MA problem for each non-empty Fuv and then selecting the best
output solution.

14

Richard Santiago, F. Bruce Shepherd

So we assume now that we are given a ring family in such a way that we may compute
its minimal set M (which is unique). This is a standard assumption when working with ring
families (cf. submodular minimization algorithm described in [39]). Then, due to monotonicity and the fact that F is closed under intersections, it is not hard to see that the original
problem reduces to the facility location problem
min

k
X
i=1

fi (Si ) : S1 ⊎ · · · ⊎ Sk = M ,

which admits a tight (ln |M |)-approximation ([41]). In particular, for the special case where
we have the trivial ring family F = {V } we get a tight ln(n)-approximation. The next result
summarizes these observations.
Theorem 11 There is a tight ln(n)-approximation for monotone M ASO(F ) minimization
over crossing families F .
3 Multi-agent submodular maximization
In this section we describe two different reductions. The first one is a completely generic
reduction of the capacitated multi-agent problem (3) to a single-agent problem. The reduction transforms the solution space into a lifted space. The new space lives in an associated
bipartite graph and facilitates the encoding of “ownership” in the multi-agent setting. We
show that several properties of the objective and family of feasible sets are invariant (i.e.
preserved) under the reduction. This allows us to leverage existing results for single-agent to
the multi-agent setting, and thus establishing a MA gap of 1 for several families. Examples
of such families include spanning trees, matroids, and p-systems.
Our second reduction is based on the multilinear extension of a set function. We establish
that if the SA primitive admits approximation via its multilinear relaxation (see Section 3.2),
then we may extend this to its MA version up to a constant factor loss, in both the monotone
and nonmonotone settings. Moreover, we discuss how for the monotone case our MA gap is
in fact tight.

3.1 The lifting reduction
In this section we describe a generic reduction of (3) to a single-agent problem
max / min f (S) : S ∈ L.
This reduction, i.e. the definition of f and L, is independent of whether we are considering
a maximization or minimization problem. The argument is based on an observation of
Lehmann et al. in [32], where they point out that the Submodular Welfare Problem is a
special case of submodular maximization subject to a matroid constraint.
Consider the complete bipartite graph G = ([k] + V, E). We think of E as our new
ground set (or lifted space), where an edge (i, v) ∈ E corresponds to assigning item v to
agent i. Notice that every subset of edges S ⊆ E can be written (or decomposed) uniquely
as S = ⊎i∈[k] (S ∩ δG (i)) = ⊎i∈[k] ({i} × Si ) for some sets Si ⊆ V . This now allows us to go
from a multi-agent objective (such as the one in (3)) to a univariate objective f : 2E → R

Multi-Agent Submodular Optimization

15

P
over the lifted space. Namely, for each set S ⊆ E we define f (S) = i∈[k] fi (Si ). Notice
that the fact that f is well-defined follows from the observation that each subset S ⊆ E can
be uniquely written as S = ⊎i∈[k] ({i} × Si ) for some Si ⊆ V .
We next give a description of the feasible sets in the lifted space E. We define two families
of sets over E that capture the original constraints:
F ′ := {S ⊆ E : S1 ⊎ · · · ⊎ Sk ∈ F }

and

H := {S ⊆ E : Si ∈ Fi , ∀i ∈ [k]}.

Notice that in the definitions of F ′ and H we are again strongly using the fact that each
S ⊆ E can be written uniquely as S = ⊎i∈[k] ({i} × Si ) where Si ⊆ V .
Now, it should be clear that with the above definitions of f, F ′ and H, we have:
P
= max / min
f (S)
= max / min f (S)
max / min
i∈[k] fi (Si )
′
s.t.
S1 ⊎ · · · ⊎ Sk ∈ F
s.t.
S ∈F ∩H
s.t.
S ∈ L,
Si ∈ Fi , ∀i ∈ [k]
where in the last step we just let L := F ′ ∩ H.
Clearly, this reduction is interesting if our new function f and family of sets L have
properties which allows us to handle them computationally. This will depend on the original
structure of the functions fi , and the families of sets F and Fi . In terms of the objective, it
is straightforward to check (as previously pointed out in [32]) that if the fi are (nonnegative,
respectively monotone) submodular functions, then f as defined above is also (nonnegative,
respectively monotone) submodular. In Section 3.4 we discuss several properties of the
families F and Fi that are preserved under this reduction.
3.2 The single-agent and multi-agent formulations
For a set function f : {0, 1}V → R we define its multilinear extension f M : [0, 1]V → R
(introduced in [3]) as
X
Y Y
f M (z) =
(1 − zv ).
f (S)
zv
S⊆V

v∈S

v ∈S
/

M

An alternative way to define f is in terms of expectations. To see this consider a vector
z ∈ [0, 1]V and let Rz denote a random set that contains element vi independently with
probability zvi . Then notice that f M (z) = E[f (Rz )], where the expectation is taken over
random sets generated from the probability distribution induced by z.
This now gives rise to natural single-agent and multi-agent relaxations. The single-agent
multilinear extension relaxation is:
(SA-ME)

max f M (z) : z ∈ P (F ),

and the multi-agent multilinear extension relaxation is:
X
fiM (zi ) : z1 + z2 + · · · + zk ∈ P (F ),
(MA-ME)
max

(7)

(8)

i∈[k]

where P (F ) denotes some relaxation of conv({χS : S ∈ F }). While the relaxation (SA-ME)
has been used extensively [4,30,11,8,1] in the submodular maximization literature, we are
not aware of any previous work using the multi-agent relaxation (MA-ME).
The following result shows that when f is nonnegative submodular and the formulation
P (F ) is downwards closed and admits a polytime separation oracle, the relaxation (SA-ME)
can be solved approximately in polytime.

16

Richard Santiago, F. Bruce Shepherd

Theorem 12 ([1, 42]) Let f : 2V → R+ be a nonnegative submodular function and f M :
[0, 1]V → R+ its multilinear extension. Let P ⊆ [0, 1]V be any downwards closed polytope
that admits a polytime separation oracle, and denote OP T = max f M (z) : z ∈ P . Then
there is a polytime algorithm ([1]) that finds z ∗ ∈ P such that f M (z ∗ ) ≥ 0.385 · OP T .
Moreover, if f is monotone there is a polytime algorithm ([42]) that finds z ∗ ∈ P such that
f M (z ∗ ) ≥ (1 − 1/e)OP T .
Note that for monotone objectives the assumption that P is downwards closed is without loss of generality. This is not the case, however, when the objective is nonmonotone.
Nonetheless, this restriction is unavoidable, as Vondrák [43] showed that no algorithm can
find z ∗ ∈ P such that f M (z ∗ ) ≥ c · OP T for any constant c > 0 when P admits a polytime
separation oracle but it is not downwards closed.
We remark that we can solve (MA-ME) to the same approximation factor as (SA-ME).
This follows from the fact that thePMA problem has the form {max g(w) : w ∈ W ⊆ Rnk }
where g(w) = g(z1 , z2 , . . . , zk ) = i∈[k] fiM (zi ) and W is the downwards closed polytope
P
{w = (z1 , ..., zk ) :
i zi ∈ P (F )}. Clearly we have a polytime separation oracle for W
given that we have one for P (F ). Moreover, it is straightforward to check (see Lemma 6 on
Appendix D) that g(w) = f M (w), where f is the function on the lifted space after applying
the lifting reduction from Section 3.1. Thus, g is the multilinear extension of a nonnegative
submodular function, and we can now use Theorem 12.
3.3 A multi-agent α(1 − 1/e)-approximation
In this section we present the proof of Theorem 4. The high-level idea behind our reduction
is the same as in the minimization setting (see Section 2.3). That is, we start with an
(approximate) optimal solution z ∗ = z1∗ +z2∗ +· · ·+zk∗ to the multi-agent (MA-ME) relaxation
and build a new feasible solution ẑ = ẑ1 + ẑ2 + · · · + ẑk where the ẑi have supports Vi that
are pairwise disjoint. We then use for the SA rounding step the single-agent problem (as
previously
defined in (6) for the minimization setting) max g(S) : S ∈ F where g(S) =
P
f
(S
∩ Vi ).
i∈[k] i
Similarly to Proposition 1 which dealt with the Lovász extension, we have the following
result for the multilinear extension.
P
Proposition 2 Let z = i∈[k] zi be a feasible solution to (MA-ME) where the vectors zi
P
P
have pairwise disjoint supports Vi . Then g M (z) = i∈[k] fiM (z|Vi ) = i∈[k] fiM (zi ).
We now have all the ingredients to prove our main result in the maximization setting.
Theorem 13 If there is a (polytime) α(n)-approximation for monotone SO(F ) maximization based on rounding (SA-ME), then there is a (polytime) (1 − 1/e) · α(n)-approximation
for monotone MASO(F ) maximization. Furthermore, given a downwards closed family F ,
if there is a (polytime) α(n)-approximation for nonmonotone SO(F ) maximization based on
rounding (SA-ME), then there is a (polytime) 0.385 · α(n)-approximation for nonmonotone
MASO(F ) maximization.
Proof We discuss first the case of monotone objectives.
STEP 1. Let z ∗ = z1∗ + z2∗ + · · · + zk∗ denote an approximate solution to (MA-ME)
obtained via
P Theorem 12, and let OP Tf rac be the value of an optimal solution. We then
have that i∈[k] fiM (zi∗ ) ≥ (1 − 1/e)OP Tf rac ≥ (1 − 1/e)OP TMA .

Multi-Agent Submodular Optimization

17

STEP 2. For an element v ∈ V let ev denote the characteristic vector of {v}, i.e. the
vector in RV which has value 1 in the v-th component and zero elsewhere. Notice that
by definition of the multilinear extension we have that the functions fiM are linear along
directions ev for any v ∈ V . It then follows that the function
X
∗
h(t) = fiM (zi∗ + tev ) + fiM
fjM (zj∗ )
′ (zi′ − tev ) +
j∈[k],j6=i,i′

is also linear for any v ∈ V and i 6= i′ ∈ [k], since it is the sum of linear functions (on t). In
particular, given any v ∈ V such that there exist i 6= i′ ∈ [k] with zi∗ (v), zi∗′ (v) > 0, there
is always a choice so that increasing one component and decreasing the other by the same
amount does not decrease the objective value. We use this as follows.
Let v ∈ V be such that there exist i 6= i′ ∈ [k] with zi∗ (v), zi∗′ (v) > 0. Then, we either
set zi∗ (v) = zi∗ (v) + zi∗′ (v) and zi∗′ (v) = 0, or zi∗′ (v) = zi∗ (v) + zi∗′ (v) and zi∗ (v) = 0, whichever
does not decrease the objective value. We repeat until the vectors
zi∗ have pairwise disjoint
P
support. Let us denote these new vectors by ẑi and let ẑ = i∈[k] ẑi . Then notice that the
P
vector z ∗ = i∈[k] zi∗ remains invariant after performing each of the above updates (i.e.
ẑ = z ∗ ), and hence the new vectors ẑi remain feasible.
STEP 3. In the last step we use the function g defined in (6), with sets Vi corresponding
to the support of the ẑi . Given our α-approximation rounding assumption for (SA-ME), we
can round ẑ to find a set Ŝ such that g(Ŝ) ≥ αg M (ẑ). Then, by setting Ŝi = Ŝ ∩ Vi we
obtain a MA solution satisfying
X
X
X
fiM (zi∗ ) ≥ α(1 − 1/e)OP TMA ,
fiM (ẑi ) ≥ α
fi (Ŝi ) = g(Ŝ) ≥ αg M (ẑ) = α
i∈[k]

i

i

where the second equality follows from Proposition 2. This completes the proof for monotone
objectives.
In the nonmonotone case the proof is very similar. Here we restrict our attention to
downwards closed families, since then we can get a 0.385-approximation at STEP 1 via
Theorem 12. We then apply STEP 2 and 3 in the same fashion as we did for monotone
objectives. This leads to a 0.385 · α(n)-approximation for the multi-agent problem.
⊓
⊔
3.4 Invariance under the lifting reduction
In Section 3.3 we established a MA gap of (1 − 1/e) for monotone objectives and of 0.385
for nonmonotone objectives and downwards closed families based on the multilinear formulations. In this section we describe several families with a provable MA gap of 1. Examples
of these family classes include spanning trees, matroids, and p-systems. Moreover, the reduction in this case is completely black box, and hence do not depend on the multilinear
(or some other particular) formulation.
We saw in Section 3.1 how if the original functions fi are all submodular, then the lifted
function f is also submodular. We now focus on the properties of the original families Fi
and F that are also preserved under the lifting reduction. We show, for instance, that if the
family F induces a matroid (or more generally a p-system) over the original ground set V ,
then so does the family F ′ over the lifted space E. We summarize these results in Table
1, and present most of the proofs in this section. We next discuss some of the algorithmic
consequences of these invariance results.

18

Richard Santiago, F. Bruce Shepherd

Table 1 Invariant properties under the lifting reduction
1
2
3
4
5
6
7
8
9
10
11
12

Multi-agent problem
fi submodular
fi monotone
(V, F ) a p-system
F = bases of a p-system
(V, F ) a matroid
F = bases of a matroid
(V, F ) a p-matroid intersection
(V, Fi ) a matroid for all i ∈ [k]
Fi a ring family for all i ∈ [k]
F = forests (resp. spanning trees)
F = matchings (resp. perfect matchings)
F = st-paths

Single-agent (i.e. reduced) problem
f submodular
f monotone
(E, F ′ ) a p-system
F ′ = bases of a p-system
(E, F ′ ) a matroid
F ′ = bases of a matroid
(E, F ′ ) a p-matroid intersection
(E, H) a matroid
H a ring family
F ′ = forests (resp. spanning trees)
F ′ = matchings (resp. perfect matchings)
F ′ = st-paths

Result
[32]
[32]
Prop 3
Corollary 4
Corollary 5
Corollary 6
Appendix D
Appendix D
Appendix D
Section 3.4
Section 3.4
Section 3.4

In the setting of MASO (i.e. (2)) this invariance allows us to leverage several results from
the single-agent to the multi-agent setting. These are based on the following result, which
uses the fact that the size of the lifted space E is nk.
Theorem 14 Let F be a matroid, a p-matroid intersection, or a p-system. If there is a
(polytime) α(n)-approximation algorithm for monotone (resp. nonmonotone) SO(F ) maximization (resp. minimization), then there is a (polytime) α(nk)-approximation algorithm
for monotone (resp. nonmonotone) MASO(F ) maximization (resp. minimization).
Notice that in both the monotone and nonmonotone maximization settings, the approximation factors α(n) for the family classes described in the theorem above are independent
of n. Hence, we immediately get that α(nk) = α(n) for these cases, and thus approximation
factors for the corresponding MA problems are the same as for the SA versions. In our MA
gap terminology this implies a MA gap of 1 for such problems.
In the setting of CMASO (i.e. (3)) the results described on entries 8 and 9 of Table
1 provide additional modelling flexibility. This allows us to combine several constraints
while keeping approximation factors fairly good. For instance, for a monotone maximization
instance of CMASO where F corresponds to a p-matroid intersection and the Fi are all
matroids, the above invariance results lead to a (p + 1 + ǫ)-approximation.
We now prove some of the results from Table 1. We start by presenting some definitions
that will be useful. For a subset of edges S ⊆ E we define its coverage cov(S) as the set of
nodes v ∈ V saturated by S. That is, v ∈ cov(S) if there exists i ∈ [k] such that (i, v) ∈ S.
We then note that by definition of F ′ it is straightforward to see that for each S ⊆ E we
have that
S ∈ F ′ ⇐⇒ cov(S) ∈ F and |S| = |cov(S)|.
(9)
For a set S ⊆ E, a set B ⊆ S is called a basis of S if B is an inclusion-wise maximal
independent subset of S. Our next result describes how bases and their cardinalities behave
under the lifting reduction.
Lemma 3 Let S be an arbitrary subset of E. Then for any basis B (over F ′ ) of S there
exists a basis B ′ (over F ) of cov(S) such that |B ′ | = |B|. Moreover, for any basis B ′ of
cov(S) there exists a basis B of S such that |B| = |B ′ |.
Proof For the first part, let B be a basis of S and take B ′ := cov(B). Since B ∈ F ′ we have
by (9) that B ′ ∈ F and |B ′ | = |B|. Now, if B ′ is not a basis of cov(S) then we can find
an element v ∈ cov(S) − B ′ such that B ′ + v ∈ F . Moreover, since v ∈ cov(S) there exists

Multi-Agent Submodular Optimization

19

i ∈ [k] such that (i, v) ∈ S. But then we have that B + (i, v) ⊆ S and B + (i, v) ∈ F ′ , a
contradiction with the fact that B was a basis of S.
For the second part, let B ′ be a basis of cov(S). For each v ∈ B ′ let iv be such that
(iv , v) ∈ S, and take B := ⊎v∈B ′ (iv , v). It is clear by definition of B that cov(B) = B ′ and
|B| = |B ′ |. Hence B ∈ F ′ by (9). If B is not a basis of S there exists an edge (i, v) ∈ S − B
such that B + (i, v) ∈ F ′ . But then by (9) we have that cov(B + (i, v)) ∈ F and B ′ (
cov(B + (i, v)) ⊆ cov(S), a contradiction since B ′ was a basis of cov(S).
⊓
⊔
We say that (V, F ) is a p-system if for each U ⊆ V , the cardinality of the largest basis
of U is at most p times the cardinality of the smallest basis of U . Our following result is a
direct consequence of Lemma 3.
Proposition 3 If (V, F ) is a p-system, then (E, F ′ ) is a p-system.
Corollary 4 If F corresponds to the set of bases of a p-system (V, I), then F ′ also corresponds to the set of bases of some p-system (E, I ′ ).
Proof Consider (E, I ′ ) where I ′ := {S ⊆ E : cov(S) ∈ I and |cov(S)| = |S|}. Then by
Proposition 3 we have that (E, I ′ ) is a p-system. It is now straightforward to check that F ′
corresponds precisely to the set of bases of (E, I ′ ).
⊓
⊔
The following two results follow from Proposition 3 and Corollary 4 and the fact that
matroids are precisely the class of 1-systems.
Corollary 5 If (V, F ) is a matroid, then (E, F ′ ) is a matroid.
Corollary 6 Assume F is the set of bases of some matroid M = (V, I), then F ′ is the set
of bases of some matroid M′ = (E, I ′ ).
We now focus on families defined over the set of edges of some graph G. To be consistent
with our previous notation we denote by V the set of edges of G, since this is the ground
set of the original problem. The lifting reduction is based on the idea of making k disjoint
copies for each original element, and visualize the new ground set (or lifted space) as edges
in a bipartite graph. However, when the original ground set corresponds to the set of edges
of some graph G, we may just think of the lifted space as being the set of edges of the graph
G′ obtained by taking k disjoint copies of each original edge. We think of the edge that
corresponds to the ith copy of v as assigning element v to agent i. We can formalize this
by defining a mapping π : E → E ′ that takes an edge (i, v) ∈ E from the lifted space to
the edge in G′ that corresponds to the ith copy of the original edge v. It is clear that π is
a bijection. Moreover, notice that given any graph G and family F of forests (as subset of
edges) of G, the bijection π : E → E ′ also satisfies that F̄ := {π(S) : S ∈ F ′ } is precisely
the family of forests of G′ . That is, there is a one-to-one correspondence between forests of
G′ and assignments S1 ⊎ S2 · · · ⊎ Sk = S ∈ F for the original MA problem where S is a
forest of G. The same holds for spanning trees, matchings, perfect matchings, and st-paths.
This observation becomes algorithmically useful given that G′ has the same number of
nodes of G. Thus, any approximation factor or hardness result for the above combinatorial
structures that depend on the number of nodes (and not on the number of edges) of the
underlying graph, will remain the same in the MA setting. We note that this explains why
for the family of spanning trees, perfect matchings, and st-paths, the approximations factors
revealed in [14] for the monotone minimization problem are the same for both the SA and
MA versions. Our next result summarizes this.

20

Richard Santiago, F. Bruce Shepherd

Theorem 15 Let F be the family (seen as edges) of forests, spanning trees, matchings,
perfect matchings, or st-paths of a graph G with m nodes and n edges. Then, if there is a
(polytime) α(n)-approximation algorithm for monotone (resp. nonmonotone) SO(F ) maximization (resp. minimization), there is a (polytime) α(nk)-approximation algorithm for
monotone (resp. nonmonotone) MASO(F ) maximization (resp. minimization). Moreover,
if there is a (polytime) α(m)-approximation algorithm for monotone (resp. nonmonotone)
SO(F ) maximization (resp. minimization), then there is a (polytime) α(m)-approximation
algorithm for monotone (resp. nonmonotone) MASO(F ) maximization (resp. minimization).
4 Conclusions
A number of interesting questions remain. Perhaps the main one being whether the α log(n) log( logn n )approximation for MA Minimization can be improved to α log(n)? We have shown this gap
can be improved for bounded blocker and crossing families. Another question is whether the
α log(n) log( logn n ) argument can be extended to arbitrary relaxations of conv({χS : S ∈ F }),
instead of only for the blocking formulation P ∗ (F ). We showed this is the case for the αkapproximation.
We believe that the notion of invariance under the lifting reduction (Section 3.4) could
be used to extend single-agent algorithms for new families to the multi-agent setting, i.e.
finding more families with a MA gap of 1. On separate work ([38]) we discuss multivariate
submodular objectives. We show that the lifting reduction behaves well algorithmically and
this opens up more tractable models (for maximization). This is the topic of planned future
work.
References
1. Buchbinder, N., Feldman, M.: Constrained submodular maximization via a non-symmetric technique.
arXiv preprint arXiv:1611.03253 (2016)
2. Buchbinder, N., Feldman, M., Seffi, J., Schwartz, R.: A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM Journal on Computing 44(5), 1384–1402 (2015)
3. Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a submodular set function subject to a
matroid constraint. In: Integer programming and combinatorial optimization, pp. 182–196. Springer
(2007)
4. Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a monotone submodular function subject
to a matroid constraint. SIAM Journal on Computing 40(6), 1740–1766 (2011)
5. Chekuri, C., Ene, A.: Submodular cost allocation problem and applications. In: International Colloquium
on Automata, Languages, and Programming, pp. 354–366. Springer (2011). Extended version: arXiv
preprint arXiv:1105.2040
6. Chen, C., Chester, S., Srinivasan, V., Wu, K., Thomo, A.: Group-aware weighted bipartite b-matching.
In: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, pp. 459–468. ACM (2016)
7. Chen, C., Zheng, L., Srinivasan, V., Thomo, A., Wu, K., Sukow, A.: Conflict-aware weighted bipartite
b-matching and its application to e-commerce. IEEE Transactions on Knowledge and Data Engineering
28(6), 1475–1488 (2016)
8. Ene, A., Nguyen, H.L.: Constrained submodular maximization: Beyond 1/e. In: Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pp. 248–257. IEEE (2016)
9. Ene, A., Vondrák, J.: Hardness of submodular cost allocation: Lattice matching and a simplex coloring conjecture. Approximation, Randomization, and Combinatorial Optimization. Algorithms and
Techniques (APPROX/RANDOM 2014) 28, 144–159 (2014)
10. Feige, U., Mirrokni, V.S., Vondrak, J.: Maximizing non-monotone submodular functions. SIAM Journal
on Computing 40(4), 1133–1153 (2011)

Multi-Agent Submodular Optimization

21

11. Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. In: Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pp.
570–579. IEEE (2011)
12. Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular
set functions-II. Springer (1978)
13. Fleischer, L., Goemans, M.X., Mirrokni, V.S., Sviridenko, M.: Tight approximation algorithms for maximum general assignment problems. In: Proceedings of the seventeenth annual ACM-SIAM symposium
on Discrete algorithm, pp. 611–620. Society for Industrial and Applied Mathematics (2006)
14. Goel, G., Karande, C., Tripathi, P., Wang, L.: Approximability of combinatorial problems with multiagent submodular cost functions. In: Foundations of Computer Science, 2009. FOCS’09. 50th Annual
IEEE Symposium on, pp. 755–764. IEEE (2009)
15. Goemans, M.X., Ramakrishnan, V.: Minimizing submodular functions over families of sets. Combinatorica 15(4), 499–513 (1995)
16. Goundan, P.R., Schulz, A.S.: Revisiting the greedy approach to submodular set function maximization.
Optimization online pp. 1–25 (2007)
17. Grötschel, M., Lovász, L., Schrijver, A.: Geometric algorithms and combinatorial optimization, vol. 2.
Springer Science & Business Media (2012)
18. Gupta, A., Roth, A., Schoenebeck, G., Talwar, K.: Constrained non-monotone submodular maximization: Offline and secretary algorithms. In: International Workshop on Internet and Network Economics,
pp. 246–257. Springer (2010)
19. Hayrapetyan, A., Swamy, C., Tardos, É.: Network design for information networks. In: Proceedings of
the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 933–942. Society for Industrial
and Applied Mathematics (2005)
20. Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. computational
complexity 15(1), 20–39 (2006)
21. Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing
submodular functions. Journal of the ACM (JACM) 48(4), 761–777 (2001)
22. Iwata, S., Nagano, K.: Submodular function minimization under covering constraints. In: Foundations
of Computer Science, 2009. FOCS’09. 50th Annual IEEE Symposium on, pp. 671–680. IEEE (2009)
23. Iyer, R., Jegelka, S., Bilmes, J.: Monotone closure of relaxed constraints in submodular optimization:
Connections between minimization and maximization: Extended version
24. Khot, S., Lipton, R.J., Markakis, E., Mehta, A.: Inapproximability results for combinatorial auctions
with submodular utility functions. In: International Workshop on Internet and Network Economics, pp.
92–101. Springer (2005)
25. Koufogiannakis, C., Young, N.E.: Greedy δ-approximation algorithm for covering with arbitrary constraints and submodular cost. Algorithmica 66(1), 113–152 (2013)
26. Krause, A., Guestrin, C.: Near-optimal observation selection using submodular functions. In: AAAI,
vol. 7, pp. 1650–1654 (2007)
27. Krause, A., Leskovec, J., Guestrin, C., VanBriesen, J., Faloutsos, C.: Efficient sensor placement optimization for securing large water distribution networks. Journal of Water Resources Planning and
Management 134(6), 516–526 (2008)
28. Krause, K., Goodwin, M., Smith, R.: Optimal software test planning through automated network analysis. TRW Systems Group (1973)
29. Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular set functions subject to multiple linear
constraints. In: Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms,
pp. 545–554. Society for Industrial and Applied Mathematics (2009)
30. Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Non-monotone submodular maximization under
matroid and knapsack constraints. In: Proceedings of the forty-first annual ACM symposium on Theory
of computing, pp. 323–332. ACM (2009)
31. Lee, J., Sviridenko, M., Vondrák, J.: Submodular maximization over multiple matroids via generalized
exchange properties. Mathematics of Operations Research 35(4), 795–806 (2010)
32. Lehmann,
B.,
Lehmann,
D.,
Nisan,
N.:
Combinatorial
auctions
with
decreasing
marginal utilities.
Games and Economic Behavior 55(2), 270–296 (2006).
URL
http://EconPapers.repec.org/RePEc:eee:gamebe:v:55:y:2006:i:2:p:270-296
33. Lovász, L.: Submodular functions and convexity. In: Mathematical Programming The State of the Art,
pp. 235–257. Springer (1983)
34. Mirrokni, V., Schapira, M., Vondrák, J.: Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions. In: Proceedings of the 9th ACM conference on Electronic commerce,
pp. 70–77. ACM (2008)
35. Mirzakhani, M., Vondrák, J.: Sperner’s colorings, hypergraph labeling problems and fair division. In:
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 873–886.
SIAM (2014)

22

Richard Santiago, F. Bruce Shepherd

36. Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set
function. Mathematics of operations research 3(3), 177–188 (1978)
37. Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular
set functions - i. Mathematical Programming 14(1), 265–294 (1978)
38. Santiago, R., Shepherd, F.B.: Multi-agent and multivariate submodular optimization.
CoRR
abs/1612.05222 (2016). URL http://arxiv.org/abs/1612.05222
39. Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
Journal of Combinatorial Theory, Series B 80(2), 346–355 (2000)
40. Svitkina, Z., Fleischer, L.: Submodular approximation: Sampling-based algorithms and lower bounds.
SIAM Journal on Computing 40(6), 1715–1737 (2011)
41. Svitkina, Z., Tardos, É.: Facility location with hierarchical facility costs. ACM Transactions on Algorithms (TALG) 6(2), 37 (2010)
42. Vondrák, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In:
Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 67–74. ACM (2008)
43. Vondrák, J.: Symmetry and approximability of submodular maximization problems. SIAM Journal on
Computing 42(1), 265–304 (2013)
44. Vondrák, J., Chekuri, C., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: Proceedings of the forty-third annual ACM symposium on
Theory of computing, pp. 783–792. ACM (2011)

APPENDIX

A Upwards-closed (aka blocking) families
In this section, we give some background for blocking families. As our work for minimization is restricted to
monotone functions, we can often convert an arbitrary set family into its upwards-closure (i.e., a blocking
version of it) and work with it instead. We discuss this reduction as well. The technical details discussed in
this section are fairly standard and we include them for completeness. Several of these results have already
appeared in [23].

A.1 Blocking families and a natural relaxation for P (F )
A set family F , over a ground set V is upwards-closed if F ⊆ F ′ and F ∈ F , implies that F ′ ∈ F ; these
are sometimes referred to as blocking families. Examples of such families include vertex-covers or set covers
more generally, whereas spanning trees are not.
For a blocking family F one often works with the induced sub-family F min of minimal sets. Then F min
has the property that it is a clutter, that is, F min does not contain a pair of comparable sets, i.e., sets
F ⊂ F ′ . If F is a clutter, then F = F min and there is an associated blocking clutter B(F ), which consists
of the minimal sets B such that B ∩ F 6= ∅ for each F ∈ F . We refer to B(F ) as the blocker of F .
One also checks that for an arbitrary upwards-closed family F , we have the following.
Claim (Lehman)
1. F ∈ F if and only if F ∩ B 6= ∅ for all B ∈ B(F min ).
2. B(B(F min )) = F min .
Thus the significance of blockers is that one may assert membership in an upwards-closed family F by
checking intersections on sets from the blocker B(F min ). If we define B(F ) to be the minimal sets which
intersect every element of F , then one checks that B(F ) = B(F min ). These observations lead to a natural relaxation for minimization problems over the integral polyhedron P (F ) = conv({χF : F ∈ F }). The
blocking formulation for F is:
min
P ∗ (F ) = {z ∈ RV
) = B(F )}.
≥0 : z(B) ≥ 1 ∀B ∈ B(F

Clearly we have P (F ) ⊆ P ∗ (F ).

(10)

Multi-Agent Submodular Optimization

23

A.2 Reducing to blocking families
Now consider an arbitrary set family F over V . We may define its upwards closure by F ↑ = {F ′ : F ⊆
F ′ for some F ∈ F }. In this section we argue that in order to solve a monotone optimization problem over
sets in F it is often sufficient to work over its upwards-closure.
As already noted B(F ) = B(F ↑ ) = B(F min ) and hence one approach is via the blocking formulation
P ∗ (F ) = P ∗ (F ↑ ). This requires two ingredients. First, we need a separation algorithm for the blocking
relaxation, but indeed this is often available for many natural families such as spanning trees, perfect
matchings, st-paths, and vertex covers. The second ingredient needed is the ability to turn an integral
′
solution χF from P ∗ (F ↑ ) or P (F ↑ ) into an integral solution χF ∈ P (F ). We now argue that this is the
case if a polytime separation algorithm is available for the blocking relaxation P ∗ (F ↑ ) or for the polytope
P (F ) := conv({χF : F ∈ F }).
For a polyhedron P , we denote its dominant by P ↑ := {z : z ≥ x for some x ∈ P }. The following
observation is straightforward.
Claim Let H be the set of vertices of the hypercube in RV . Then
H ∩ P (F ↑ ) = H ∩ P (F )↑ = H ∩ P ∗ (F ↑ ).
In particular we have that χS ∈ P (F )↑ ⇐⇒ χS ∈ P ∗ (F ↑ ).
We can now use this observation to prove the following.
Lemma 4 Assume we have a separation algorithm for P ∗ (F ↑ ). Then for any χS ∈ P ∗ (F ↑ ) we can find
in polytime χM ∈ P (F ) such that χM ≤ χS .
Proof Let S = {1, 2, . . . , k}. We run the following routine until no more elements can be removed:
For i ∈ S
If χS−i ∈ P ∗ (F ↑ ) then S = S − i
Let χM be the output. We show that χM ∈ P (F ). Since χM ∈ P ∗ (F ↑ ), by Claim A.2 we know that
χM ∈ P (F )↑ . Then by definition of dominant
there exists x ∈ P (F ) such that x ≤ χM ∈PP (F )↑ . It follows
P
that the vector x can be written as x = i λi χUi for some Ui ∈ F and λi ∈ (0, 1] with i λi = 1. Clearly
we must have that Ui ⊆ M for all i, otherwise x would have a non-zero component outside M . In addition,
if for some i we have Ui ( M , then there must exist some j ∈ M such that Ui ⊆ M − j ( M . Hence
M − j ∈ F ↑ , and thus χM −j ∈ P (F )↑ and χM −j ∈ P ∗ (F ↑ ). But then when component j was considered in
the algorithm above, we would have had S such that M ⊆ S and so χS−j ∈ P ∗ (F ↑ ) (that is χS−j ∈ P (F )↑ ),
and so j should have been removed from S, contradiction.
⊓
⊔
We point out that for many natural set families F we can work with the relaxation P ∗ (F ↑ ) assuming that
′
it admits a separation algorithm. Then, if we have an algorithm which produces χF ∈ P ∗ (F ↑ ) satisfying
some approximation guarantee for a monotone problem, we can use Lemma 4 to construct in polytime
F ∈ F which obeys the same guarantee.
Moreover, notice that for Lemma 4 to work we do not need an actual separation oracle for P ∗ (F ↑ ), but
rather all we need is to be able to separate over 0−1 vectors only. Hence, since the polyhedra P ∗ (F ↑ ), P (F ↑ )
and P (F )↑ have the same 0−1 vectors (see Claim A.2), a separation oracle for either P (F ↑ ) or P (F )↑ would
be enough for the routine of Lemma 4 to work. We now show that this is the case if we have a polytime
separation oracle for P (F ). The following result shows that if we can separate efficiently over P (F ) then we
can also separate efficiently over the dominant P (F )↑ .
Claim If we can separate over a polyhedron P in polytime, then we can also separate over its dominant P ↑
in polytime.
Proof Given a vector y, we can decide whether y ∈ P ↑ by solving
x+s= y
x∈P
s ≥ 0.
Since can we easily separate over the first and third constraints, and a separation oracle for P is given (i.e.
we can also separate over the set of constraints imposed by the second line), it follows that we can separate
over the above set of constraints in polytime.
⊓
⊔

24

Richard Santiago, F. Bruce Shepherd

Now we can apply the same mechanism from Lemma 4 to turn feasible sets from F ↑ into feasible sets
in F .
Corollary 7 Assume we have a separation algorithm for P (F )↑ . Then for any χS ∈ P (F )↑ we can find
in polytime χM ∈ P (F ) such that χM ≤ χS .
′

We conclude this section by making the remark that if we have an algorithm which produces χF ∈
P (F ↑ ) satisfying some approximation guarantee for a monotone problem, we can use Corollary 7 to construct
F ∈ F which obeys the same guarantee.

B Relaxations for constrained submodular minimization
Submodular optimization techniques for minimization on a set family have involved two standard relaxations,
one being linear [14] and one being convex [5, 22, 23]. We introduce the latter in this section.

B.1 A convex relaxation
We will be working with upwards-closed set families F , and their blocking relaxations P ∗ (F ). As we now
work with arbitrary vectors z ∈ [0, 1]n , we must specify how our objective function f (S) behaves on all
points z ∈ P ∗ (F ). Formally, we call g : [0, 1]V → R an extension of f if g(χS ) = f (S) for each S ⊆ V .
For a submodular objective function f (S) there can be many extensions of f to [0, 1]V (or to RV ). The
most popular one has been the so-called Lovász Extension (introduced in [33]) due to several of its desirable
properties.
We present two of several equivalent definitions for the Lovász Extension. Let 0 < v1 < v2 < ... < vm ≤ 1
be the distinct positive values taken in some vector z ∈ [0, 1]V . We also define v0 = 0 and vm+1 = 1 (which
may be equal to vm ). Define for each i ∈ {0, 1, ..., m} the set Si = {j : zj > vi }. In particular, S0 is the
support of z and Sm = ∅. One then defines:
f L (z) =

m
X

(vi+1 − vi )f (Si ).

i=0

It is not hard to check that the following is an equivalent definition of f L (e.g. see [5]). For a vector z ∈ [0, 1]V
and θ ∈ [0, 1], let z θ := {v ∈ V : z(v) ≥ θ}. We then have that
f L (z) = Eθ∈[0,1] f (z θ ) =

Z

1

f (z θ )dθ,

0

where the expectation is taken over the uniform distribution in [0, 1].
Lemma 5 (Lovász [33]) The function f L is convex if and only if f is submodular.
One could now attack constrained submodular minimization by solving the problem
(SA-LE)

min f L (z) : z ∈ P ∗ (F ),

(11)

and then seek rounding methods for the resulting solution. This is the approach used in [5, 22, 23]. We refer
to the above as the single-agent Lovász extension formulation, abbreviated as (SA-LE).

B.2 Tractability of the single-agent formulation (SA-LE)
In this section we show that one may solve (SA-LE) approximately as long as a polytime separation algorithm
for P ∗ (F ) is available. This is useful in several settings and in particular for our methods which rely on the
multi-agent Lovász extension formulation (discussed in the next section).
Polytime Algorithms. One may apply the Ellipsoid Method to obtain a polytime algorithm which
approximately minimizes a convex function over a polyhedron K as long as various technical conditions
hold. For instance, one could require that there are two ellipsoids E(a, A) ⊆ K ⊆ E(a, B) whose encoding

Multi-Agent Submodular Optimization

25

descriptions are polynomially bounded in the input size for K. We should also have polytime (or oracle)
access to the convex objective function defined over Rn . In addition, one must be able to polytime solve the
subgradient problem for f .2 One may check that the subgradient problem is efficiently solvable for Lovász
extensions of polynomially encodable submodular functions. We call f polynomially encodable if the values
f (S) have encoding size bounded by a polynomial in n (we always assume this for our functions). If these
conditions hold, then methods from [17] imply that for any ǫ > 0 we may find an approximately feasible
solution for K which is approximately optimal. By approximate here we mean for instance that the objective
value is within ǫ of the real optimum. This can be done in time polynomially bounded in n (size of input
say) and log 1ǫ . Let us give a few details for our application.
Our convex problem’s feasible space is P ∗ (F ) and it is easy to verify that our optimal solutions will
lie in the 0 − 1 hypercube H. So we may define the feasible space to be H and the objective function to
be g(z) = f L (z) if z ∈ H ∩ P ∗ (F ) and = ∞ otherwise. (Clearly g is convex in Rn since it is a pointwise
maximum of two convex functions; alternatively, one may define the Lovász Extension on Rn which is also
fine.) Note that g can be evaluated in polytime by the definition of f L as long as f is polynomially encodable.
We can now easily find an ellipsoid inside H and one containing H each of which has poly encoding size.
We may thus solve the convex problem to within ±ǫ-optimality in time bounded by a polynomial in n and
log 1ǫ .
Corollary 8 Consider a class of problems F , f for which f ’s are submodular and polynomially-encodable
in n = |V |. If there is a polytime separation algorithm for the family of polyhedra P ∗ (F ), then the convex
program (SA-LE) can be solved to accuracy of ±ǫ in time bounded by a polynomial in n and log 1ǫ .

B.3 The multi-agent formulation
The single-agent formulation (SA-LE) discussed above has a natural extension to the multi-agent setting.
This was already introduced in [5] for the case F = {V }.
X
(MA-LE)
min
fiL (zi ) : z1 + z2 + · · · + zk ∈ P ∗ (F ).
(12)
i∈[k]

We refer to the above as the multi-agent Lovász extension formulation, abbreviated as (MA-LE).
We remark that we can solve (MA-LE) as long as we have polytime separation of P ∗ (F ). This follows
the approach from the previous section (see Corollary 8) P
except our convex program now has k vectors of
variables z1 , z2 , . . . , zk (one for each agent) such that z = i zi . This problem has the formP
{min g(w) : w ∈
W ⊆ Rnk } where g is convex and W is the full-dimensional convex body {w = (z1 , ..., zk ) : i zi ∈ P ∗ (F )}.
Clearly we have a polytime separation routine for W , and hence we may apply Ellipsoid as in the single-agent
case.
Corollary 9 Assume there is a polytime separation oracle for P ∗ (F ). Then we can solve the multi-agent
formulation (MA-LE) in polytime.
Corollary 10 Assume we can solve the single-agent formulation (SA-LE) in polytime. Then we can also
solve the multi-agent formulation (MA-LE) in polytime.
Proof If we can solve (SA-LE) in polytime then we can also separate over P ∗ (F ) in polynomial time. Now
the statement follows from Corollary 9.
⊓
⊔

C Dealing with some special types of nonmonotone objectives
We present the proof of Theorem 7 discussed in Section 2.1.
P
P
U for
Proof (Theorem 7) Let z = i∈[k] zi be a feasible solution to (MA-LE) and such that
i∈[k] zi ≥ χ
some U ∈ F . Consider the below CE-Rounding procedure originally described in the work of [5] for the case
F = {V }.
It is discussed in [5] and not difficult to see that the first while loop assigns all the elements from U
in O(k log |U |) iterations with high probability. Since F is upwards closed and U ∈ F , this implies that
2

For a given y, find a subgradient of f at y.

26

Richard Santiago, F. Bruce Shepherd

Algorithm 1: CE-Rounding
S ← ∅ /* set of assigned elements */
Si ← ∅ for all i ∈ [k] /* set of elements assigned to agent i */
while S ∈
/ F do
Pick i ∈ [k] uniformily at random
Pick θ ∈ [0, 1] uniformily at random
S(i, θ) := {v ∈ V : zi (v) ≥ θ}
Si ← Si ∪ S(i, θ)
S ← S ∪ S(i, θ)
end
/* Uncross S1 , S2 , . . . , Sk */
Si′ ← Si for all i ∈ [k]
while there exist i 6= j such that Si′ ∩ Sj′ 6= ∅ do
if h(Si′ ) + h(Sj′ − Si′ ) ≤ h(Si′ ) + h(Sj′ ) then
Sj′ ← Sj′ − Si′
else
Si′ ← Si′ − Sj′
end
end
Output (S1′ , S2′ , . . . , Sk′ )

the first while loop terminates in O(k log |U |) iterations with high probability. Moreover, it is clear that the
uncrossing step takes a polynomial number of iterations.
Let S1 , S2 , . . . , Sk be the output after the first while loop and S1′ , S2′ , . . . , Sk′ the final output of the
rounding. At each iteration of the first while loop, the expected cost associated to the random set S(i, θ) is
given by
k
k
1X L
1X
Eθ [fi (S(i, θ))] =
f (zi ).
Ei,θ [fi (S(i, θ))] =
k i=1
k i=1 i
Hence, given the subadditivity of the objectives (since the functions are submodular and nonnegative), the
P
expected cost increase at each iteration of the first while loop is upper bounded by k1 ki=1 fiL (zi ). Since
the first while loop terminates w.h.p. in O(k log |U |) iterations, it now follows by linearity of expectation
P
P
that the total expected cost of i fi (Si ) is at most O(log |U |) ki=1 fiL (zi ).
Finally, we use a result (see Lemma 3.1) from [5]
that if h is symmetric submodular
P that ′guarantees
P
then the uncrossing step ofPthe rounding
satisfies
i h(Si ) ≤
i h(Si ). Moreover, by monotonicity of
P
′
′
′
′
the gi it is also clear that
i gi (Si ) ≤
i gi (Si ). Thus, we have that S1 ⊎ S2 ⊎ · · · ⊎ Sk = S ∈ F and
P
P
Pk
′
L
⊓
⊔
i fi (Si ) ≤
i fi (Si ) ≤ O(log |U |)
i=1 fi (zi ) on expectation. This concludes the argument.

D Invariance under the lifting reduction
Corollary 11 If (V, F ) is a p-matroid intersection, then so is (E, F ′ ).
Proof Let F = ∩pi=1 Ii for some matroids (V, Ii ). Then we have that
F ′ ={S ⊆ E : S1 ⊎ · · · ⊎ Sk ∈ F }
={S ⊆ E : S1 ⊎ · · · ⊎ Sk ∈ ∩pi=1 Ii }
={S ⊆ E : S1 ⊎ · · · ⊎ Sk ∈ Ii , ∀i ∈ [p]}
\
=
{S ⊆ E : S1 ⊎ · · · ⊎ Sk ∈ Ii }
i∈[p]

=

\

Ii′ .

i∈[p]

Moreover, from Corollary 5 we know that (E, Ii′ ) is a matroid for each i ∈ [p], and the result follows.

⊓
⊔

Multi-Agent Submodular Optimization

27

We now discuss some invariant properties with respect to the families Fi .
Proposition 4 If (V, Fi ) is a matroid for each i ∈ [k], then (E, H) is also a matroid.
Proof Let Mi := ({i} × V, Ii ) for i ∈ [k], where Ii := {{i} × S : S ∈ Fi }. Since (V, Fi ) is a matroid, we
have that Mi is also a matroid. Moreover, by taking the matroid union of the Mi ’s we get (E, H). Hence,
(E, H) is a matroid.
⊓
⊔
Proposition 5 If Fi is a ring family over V for each i ∈ [k], then H is a ring family over E.
U
U
Proof Let S, T ∈ H and notice that S ∪ T = i∈[k] ({i} × (Si ∪ Ti )) and S ∩ T = i∈[k] ({i} × (Si ∩ Ti )).
Since Fi is a ring family for each i ∈ [k], it follows that Si ∪ Ti ∈ Fi and Si ∩ Ti ∈ Fi for each i ∈ [k]. Hence
S ∪ T ∈ H and S ∩ T ∈ H, and thus H is a ring family over E.
⊓
⊔
We saw in Section 3.1 that if the original functions fi are all submodular, then the lifted function f is
also submodular. Recall that for any set S ⊆ E in the lifted space, there are unique sets Si ⊆ V such that
S = ⊎i∈[k] ({i} × Si ). We think of Si as the set of items assigned to agent i. In a similar way, given any
vector z̄ ∈ [0, 1]E , there are unique vectors zi ∈ [0, 1]V such that z̄ = (z1 , z2 , . . . , zk ), where we think of
zi as the vector
P associated to agent i. Our following result establishes the relationship between the values
f M (z̄) and i∈[k] fiM (zi ).
Lemma 6 Let the functions fi and f be as described in the lifting reduction on Section 3.1. Then for any
vector z̄ = (z1 , z2 , . . . , zk ) ∈ [0,P
1]E , where zi ∈ [0, 1]V is the vector associated with agent i, we have that
f M (z̄) = f M (z1 , z2 , . . . , zk ) = i∈[k] fiM (zi ).
Proof
f M (z̄) = E[f (Rz̄ )] =
=

X

X

X X

f (S)Pz̄ (S)

S⊆E

···

S1 ⊆V S2 ⊆V

=

X

X

fi (Si )] · P(z1 ,z2 ,...,zk ) (S1 , S2 , . . . , Sk )

X

···

X

fi (Si ) · P(z1 ,z2 ,...,zk ) (S1 , S2 , . . . , Sk )

Sk ⊆V

X

X X

fi (Si )

X X

fi (Si )Pzi (Si ) =

i∈[k] Si ⊆V

=

X

Sk ⊆V i∈[k]

i∈[k] S1 ⊆V S2 ⊆V

=

[

i∈[k] Si ⊆V

P(z1 ,z2 ,...,zk ) (S1 , S2 , . . . , Sk )

Sj ⊆V,j6=i

X

i∈[k]

z

E[fi (Si i )] =

X

fiM (zi ).

i∈[k]

⊓
⊔

