  Recent years have seen many algorithmic advances in the area of submodular
optimization: (SO) $\min/\max~f(S): S \in \mathcal{F}$, where $\mathcal{F}$ is
a given family of feasible sets over a ground set $V$ and $f:2^V \rightarrow
\mathbb{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
\emph{multi-agent submodular optimization} (MASO) which was introduced by Goel
et al. in the minimization setting: $\min \sum_i f_i(S_i): S_1 \uplus S_2
\uplus \cdots \uplus S_k \in \mathcal{F}$. Here we use $\uplus$ 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
$f_i()$. In this paper we explore the extent to which the approximability of
the multi-agent problems are linked to their single-agent {\em primitives},
referred to informally as the {\em 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(\alpha)$-approximation whenever (SO) admits an $\alpha$-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(\alpha \cdot \min \{k,
\log^2 (n)\})$-approximation whenever (SO) admits an $\alpha$-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).
