# The Impact of Message Passing in Agent-Based Submodular Maximization

Authors  David Grimsman, Matthew R. Kirchner, João P. Hespanha and Jason R.
Marden D. Grimsman (davidgrimsman@ucsb.edu), M. R. Kirchner
(kirchner@ucsb.edu), J. R. Marden (jmarden@ece.ucsb.edu), and J. P. Hespanha
<EMAIL_ADDRESS>are with the Department of Electrical and Computer
Engineering, University of California, Santa Barbara, CAThis research was
supported in part by AFRL contracts FA8750-18-C-0014 and FA95550-20-1-0054 and
ONR grant N00014-20-1-2359.© 2020 IEEE. Personal use of this material is
permitted. Permission from IEEE must be obtained for all other uses, in any
current or future media, including reprinting/republishing this material for
advertising or promotional purposes, creating new collective works, for resale
or redistribution to servers or lists, or reuse of any copyrighted component
of this work in other works.

###### Abstract

Submodular maximization problems are a relevant model set for many real-world
applications. Since these problems are generally NP-Hard, many methods have
been developed to approximate the optimal solution in polynomial time. One
such approach uses an agent-based greedy algorithm, where the goal is for each
agent to choose an action from its action set such that the union of all
actions chosen is as high-valued as possible. Recent work has shown how the
performance of the greedy algorithm degrades as the amount of information
shared among the agents decreases, whereas this work addresses the scenario
where agents are capable of sharing more information than allowed in the
greedy algorithm. Specifically, we show how performance guarantees increase as
agents are capable of passing messages, which can augment the allowable
decision set for each agent. Under these circumstances, we show a near-optimal
method for message passing, and how much such an algorithm could increase
performance for any given problem instance.

##  I Introduction

Submodular maximization problems are relevant to many fields and applications,
including sensor placement [1], outbreak detection in networks [2], maximizing
and inferring influence in a social network [3, 4], document summarization
[5], clustering [6], assigning satellites to targets [7], path planning for
multiple robots [8], and leader selection and resource allocation in
multiagent systems [9, 10]. An important similarity among these applications
is the presence of an objective function which exhibits a “diminishing
returns” property. For instance, consider a company choosing locations for its
retail stores. If, for a given city, the company has no retail stores, and
chooses to add a location in that city, the marginal gain in revenue from that
store would be higher than if the company chose a similar city where it
already had 100 retail stores. Objectives (such as revenue in this instance)
satisfying this property are _submodular_.

While submodular minimization can be solved in polynomial time [11],
submodular maximization is an NP-hard problem for certain subclasses of
submodular function. Therefore, much effort has been devoted to finding and
improving algorithms which approximate the optimal solution in polynomial
time. A key result of this line of research is that algorithms exist which
give strong guarantees as to how well the optimal solution can be
approximated.

One such algorithm is the greedy algorithm, first proposed in the seminal work
[12]. Here it was shown that for certain classes of constraints the solution
provided by the greedy algorithm must be within $1-1/e\approx 0.63$ of the
optimal, and within $1/2$ of the optimal for the more general case of
constraints [13]. Since then, more sophisticated algorithms have been
developed to show that there are many instances of the submodular maximixation
problem that can be solved efficiently within the $1-1/e$ guarantee [14, 15].
It has also been shown that progress beyond this level of optimality is not
possible using a polynomial-time algorithm, where the indicator step for the
time complexity is the evaluation of the objective function [16].

In addition to the strong performance guarantees, a nice benefit to using the
greedy algorithm to solve a submodular maximization problem is that it is easy
to implement, even in distributed settings. One recent line of research has
studied a distributed version of the greedy algorithm, which can be
implemented using a set of $n$ agents, each with its own action set [17]. In
this algorithm, the agents are ordered and choose sequentially, each agent
greedily choosing its best action relative to the actions which the previous
agents have chosen. The solution provided is the set of all actions chosen.
Like the standard greedy algorithm, it has been shown that this distributed
greedy algorithm guarantees the solution is within 1/2 the optimal [17].

In this setting, recent literature has emerged which attempts to quantify how
information impacts the performance of the algorithm, specifically as the
information among the agents degrades. For instance, [18] and [19] describe
how the 1/2-guarantee decreases as agents can only observe a subset of the
actions chosen by previous agents. The work in [20] shows how an intelligent
choice of which action to send to future agents can recover some of this loss
in performance. Other work has also begun to explore how additional knowledge
of the structure of the action sets can offset this loss [21, 22].

This paper addresses the impact of information in the other direction: how
increasing the amount of actions that can be shared among the agents improves
the performance. We introduce the concept of _message passing_ , wherein
agents not only choose an action as part of the algorithm solution, but also
choose some actions to share with future agents. Future agents may choose
these shared actions as part of the solution, thus message passing is a way to
augment the action sets of future agents in the sequence to offset any agent
that may not have access to valuable actions.

Message passing gives rise to two key questions: what policy should agents use
to select actions to pass and how does it affect performance? We address the
first question in Section II-C, where we propose an augmented greedy policy
that is near-optimal in the limit of a large number of agents or a large
number of shared messages. The performance question is addressed both from a
worst-case and a best-case perspective. It turns out that it is possible to
find ”bad” problem instances for which message sharing brings little benefit
when the number of agents is large. Moreover, we prove in Theorem 1 that this
is so _regardless of the message passing policy used_. On the flip side, there
are also ”good” problem instances for which message passing can improve
performance significantly, by a multiplicative factor that can be as large as
the number of agents (Theorem 2) and such performance gains are achieved by
the proposed augmented greedy policy.

##  II Model

Let $S$ be a set of elements and $f:2^{S}\to\mathbb{R}$ a scalar-valued
function. We restrict $f$ to have the following three properties:

  * •

Normalized: $f(\emptyset)=0$.

  * •

Monotone: $f(A)\leq f(B)$ for $A\subseteq B\subseteq S$.

  * •

Submodular: $f(A\cup\\{s\\})-f(A)\geq f(B\cup\\{s\\})-f(B)$ for all
$A\subseteq B\subseteq S$ and $s\in S\setminus B$.

This paper focuses on a subclass of distributed submodular optimization
problems. To that end, let $N=\\{1,\dots,n\\}$ be a set of agents where each
$i\in N$ is associated with a local set of elements $S_{i}\subseteq S$ that
contains the various sets of elements from which agent $i$ can choose. For a
given set $A\subseteq S$, we use $(A)^{l}$ to mean the subsets of $A$ of size
at most $l$. We focus on the scenario where each agent $i$ can select as most
$k\geq 1$ elements from $S_{i}$, and hence we express this choice as
$x_{i}\in(S_{i})^{k}$. We denote a choice profile by
$x=(x_{1},\dots,x_{n})\in(S_{1})^{k}\times\cdots(S_{n})^{k}$, and will
evaluate the objective $f$ of this profile $x$ as $f(x)=f(\cup_{i}x_{i})$. The
central goal is to solve

${\rm
OPT}(f,(S_{i})_{i},k)=\underset{x\in(S_{1})^{k}\times\cdots\times(S_{n})^{k}}{\max}\
f(x).$ (1)

We denote $x^{\rm opt}(f,(S_{i})_{i},k)$ to mean a choice profile which
maximizes (1).

###  II-A The Greedy Algorithm

It is well known that characterizing an optimal allocation $x^{\rm
opt}(f,(S_{i})_{i},k)$ is an NP-Hard problem in the number of agents for
certain subclasses of submodular functions $f$. However, there are very simple
algorithms that can attain near optimal behavior for this class of submodular
optimization problems. One such algorithm, termed the greedy algorithm [13],
proceeds according to the following rule: each agent $i\in N$ sequentially
selects their choice $x_{i}\in(S_{i})^{k}$ by greedily choosing the action
which yields the greatest benefit to the objective $f$, i.e.,

$x_{i}^{\rm
ng}\in\operatorname*{arg\,max}_{x_{i}\in(S_{i})^{k}}f\left(x_{i},\\{x^{\rm
ng}_{j}\\}_{j<i}\right).$ (2)

Note that while the greedy algorithm can be implemented in a distributed
fashion, there is an implicit informational demand on the system as each agent
$i\in N$ must be aware of the choices of all previous agents $j<i$, i.e.,
$\\{x_{1},\dots,x_{i-1}\\}$.

In addition to being easy to implement, the greedy algorithm is also high-
performing: it is guaranteed to produce a solution $x^{\rm ng}$ which is
within 1/2 of the optimal [13], i.e., $f(x^{\rm ng})\geq(1/2)\dot{f}(x^{\rm
opt})$. In fact, the greedy algorithm is shown to give the highest performance
guarantees possible for any algorithm which runs in polynomial time for some
classes of distributed submodular maximization problems [16].

###  II-B A Motivating Example

Consider a scenario in which $n$ flying vehicles carry on-board cameras that
capture images of ground vehicles of interest and return their pixel
coordinates. Each vehicle $i\in N$ has access to a large collection of pixel
coordinate measurements taken by its own camera, which comprise the local
element set $S_{i}$. However, each vehicle $i$ needs to select a much smaller
subset of these measurements (no more than $k$) to send to a centralized
location for data fusion. The goal is to select the best set of $k$
measurements that each vehicle should send to the centralized location so that
an optimal estimate $\hat{\theta}$ of the ground vehicle’s position $\theta$
can be recovered by fusing the measurements from all the vehicles. It was
shown in [23] that an optimal estimator that achieves the Cramér–Rao lower
bound results in an error covariance matrix that can be written as

$\displaystyle\operatorname{E}\big{[}(\hat{\theta}-\theta)(\hat{\theta}-\theta)^{\prime}\big{]}=\Big{(}Q_{0}+\sum_{s\in
S}Q_{s}\Big{)}^{-1}$

where $Q_{0}$ is a symmetric positive definite matrix that encodes a-priori
information about the position of the ground vehicle, $S=\cup_{i}S_{i}$ is the
complete set of measurements, and $Q_{s}$ is a symmetric positive semi-
definite matrix that depends on the relative position and orientation of the
flying vehicle’s camera with respect to the ground vehicle for each
measurement $s\in S$. In addition, it was shown that the function
$f:2^{S}\rightarrow\mathbb{R}$ defined for any $A\subseteq S$ as

$\displaystyle f(A)=\log\det\Big{(}Q_{0}+\sum_{s\in A}Q_{s}\Big{)}-\log\det
Q_{0}$ (3)

is normalized, monotone, and submodular [23]. It turns out that maximizing (3)
corresponds to the so-called $D$-optimality, which essentially minimizes the
volume of confidence intervals.

###  II-C The Greedy Algorithm with Message Passing

(a) An example problem, where $n=3$, $k=2$, $m=1$. Each box represents an
element of $S$, and row represents $S_{i}$, i.e., the elements in $S$ to which
agent $i$ has access. The function $f$ is represented by the width of each
box, where the width of elements not specifically labeled in the diagram is 1.
For $A\subseteq S$, $f(A)$ is the total amount of horizontal space covered by
the elements in $A$. For instance, $f(\\{s_{6},s_{8}\\})=2$ and
$f(\\{s_{5},s_{6},s_{8}\\})=3$. Here we assume the use of some policy $\pi$
for selection and message passing. The arrows indicate the message passing
dictated by $\pi$, for instance $z^{\pi}_{1}=\\{s_{4}\\}$. The boxes with the
dashed outline indicate that $s_{4}$ is not in $S_{2}$ or $S_{3}$, but is
included as part of the agents’ augmented action set, should they choose to
use it. The boxes shaded in blue indicate the elements $x_{i}^{\pi}$ chosen by
$\pi$, and the boxes shaded in green are the optimal choices, where those
differ.

(b) A table representing the performance for 4 different solution methods.
First, the optimal solution to (1) is given. Then, the independent solution is
shown, which is the solution where each agent chooses independent of the other
agents. The solution to the greedy algorithm assumes that the agents choose
according to (2). Finally, last row assumes agents choose according to some
policy $\pi$ which employs message passing.

Figure 1: An example problem illustrating the extended model from Section
II-C.

The focus of this work is on understanding the degree to which inter-agent
communications can be exploited to improve the performance guarantees
associated with the greedy algorithm. Accordingly, here we propose message
passing, wherein each agent $i\in N$ is tasked with making both a selection
and communication decision, denoted by $x_{i}$ and $z_{i}$ respectively. We
focus on the situation where agent $i$ can communicate up to $m\geq 0$ of its
measurements to the forthcoming agents $j>i$, i.e., $z_{i}\in(S_{i})^{m}$.
Agent $j$ can then select its choices either from among original set $S_{j}$
or to also include some subset of the communicated measures
$z_{1}\cup\dots\cup z_{j-1}$. Accordingly, we replace the decision-making rule
of each agent $i\in N$ given in (2) with a new rule $\pi_{i}$ which dictates
how the agent selects its choice $x_{i}$ and its message $z_{i}$ in response
to the previous selections and messages. In particular, we focus on rules
$\pi_{i}$ of the form

$\\{x^{\pi}_{i},z^{\pi}_{i}\\}=\pi_{i}(S_{i},\\{x^{\pi}_{j}\\}_{j<i},\\{z^{\pi}_{j}\\}_{j<i}),$
(4)

where $x^{\pi}_{i}\in(S_{i}\cup z^{\pi}_{1}\cup\dots\cup z^{\pi}_{i-1})^{k}$
and $z_{i}^{\pi}\in(S_{i})^{m}$. For $k$, $m$, and $n$, we denote $\Pi(k,m,n)$
as the set of admissible policy profiles $\pi=\\{\pi_{1},\dots,\pi_{n}\\}$. It
is important to highlight that the performance of $\pi$ is ultimately gauged
by the performance of the resulting allocation
$x^{\pi}=(x_{1}^{\pi},\dots,x_{n}^{\pi})$, as the communicated messages
$(z_{1}^{\pi},\dots,z_{n}^{\pi})$ are merely employed to influence these
decision making rules. See Figure 1 for an example which highlights this
extended model.

The following algorithm highlights an opportunity for message passing to
potentially improve the performance guarantees associated with the greedy
algorithm through augmenting the agents’ choice sets.

######  Definition 1 (Augmented Greedy Algorithm)

In the augmented greedy algorithm each agent $i\in N$ is associated with a
selection rule $\pi_{i}$ as in (4) of the form

$\displaystyle x_{i}^{\rm ag}$ $\displaystyle\in$
$\displaystyle\underset{x_{i}\subseteq(S_{i}\cup z_{1}^{\rm ag}\cup\dots\cup
z_{i-1}^{\rm ag})^{k}}{\arg\max}\ f(x_{i},\\{x^{\rm ag}_{j}\\}_{j<i}),$ (5a)
$\displaystyle z_{i}^{\rm ag}$ $\displaystyle=$ $\displaystyle z_{i}^{k}\cup
z_{i}^{m-k},$ (5b) $\displaystyle z^{k}_{i}$ $\displaystyle\in$
$\displaystyle\underset{z_{i}\in(S_{i})^{\min(k,m)}}{\arg\max}\
f(z_{i},\\{x^{\rm ag}_{j}\\}_{j\leq i})$ (5c) $\displaystyle z^{m-k}_{i}$
$\displaystyle\in$ $\displaystyle(S_{i})^{\max(m-k,0)}$ (5d)

The communication depicted above entails that when $m\leq k$ each agent
forwards the best $m$ measurements that it is unable to select to the
remaining agents. When $m>k$, the best $k$ measurements are chosen, and the
remaining $m-k$ measurements can be chosen arbitrarily. Then, each remaining
agent can choose whether or not its selection should include these augmented
choices. Note that we will require a policy to be deterministic, so the rules
in (5a)–(5d) do not constitute a specific policy, since (5d) doesn’t specify a
rule for finding $z_{i}^{m-k}$, and also since the $\operatorname*{arg\,max}$
in (5a) and (5c) may not be unique. Therefore we refer to a policy which has
the form of (5a)–(5d) as an augmented greedy policy.

##  III A Worst-Case Analysis

In this section we explore whether message passing can increase worst-case
guarantees beyond the 1/2 guarantee of the nominal greedy algorithm. We show
that an augmented algorithm is a near-optimal algorithm in this setting, but
also show that the benefits in terms of worst-case analysis decrease as the
number of agents increases. Additionally, we show that even an optimal policy
does not generally increase performance by much.

###  III-A Performance Measure

Given a submodular, monotone, normalized function $f$ with element set $S$, we
measure the performance of a policy $\pi\in\Pi(k,m,n)$ and across all
policies, respectively, as

$\displaystyle\gamma_{\pi}(f,S,k):=\min_{\\{S_{i}\subseteq S\\}_{i\in
N}}\frac{f(x^{\pi})}{{\rm OPT}(f,(S_{i})_{i},k)},$ (6)
$\displaystyle\gamma(\Pi(k,m,n),f,S):=\max_{\pi\in\Pi(k,m,n)}\gamma_{\pi}(f,S,k),$
(7)

where the minimization in (6) captures the notion that we are interested in
how well $\pi$ performs regardless of how the base set $S$ is distributed
among the different agents.

This section focuses on worst-case guarantees over all criteria $f$, which are
characterized by

$\displaystyle\gamma_{\pi}=\inf_{f:2^{S}\rightarrow\mathbb{R}}\gamma_{\pi}(f,S,k),$
(8)
$\displaystyle\gamma=\inf_{f:2^{S}\rightarrow\mathbb{R}}\gamma(\Pi(k,m,n),f,S,k),$
(9)

where the (worst-case) $\inf$ are taken over all possible criteria $f$ that
are submodular, monotone, and normalized. When we only consider decision-rules
aligned with the greedy algorithm, as in (2), the bound given in (8) is $1/2$
(see [13, 17]).

###  III-B Main Result

###### Theorem 1

For any $k\geq 1,m\geq 0$ and $n\geq 2$,

$\displaystyle\gamma\leq\frac{1}{2-\frac{\min((n-1)m/k,1)}{n-1+\min((n-1)m/k,1)}},$
(10)

i.e., no policy can guarantee a performance higher than the above expression.
Furthermore, when $\pi$ is an augmented greedy policy, then

$\gamma\geq\gamma_{\pi}\geq\frac{1}{2-\frac{(\min(m/k,1))^{n-1}}{\sum_{i=0}^{n-1}(\min(m/k,1))^{i}}}.$
(11)

We will give the formal proof for the theorem below, with a brief description
here. The statement in (10) is shown by presenting a canonical example, for
which no policy can guarantee a performance above the expression in (10). The
lower bound in (11) is proven by showing that if an augmented greedy policy is
implemented, the system performance cannot be below the expression in (11).

Assuming that one could design a policy $\pi^{*}$ such that $\gamma$ meets the
upper bound in (10), we see that in general the guaranteed performance does
not increase much above the 1/2 guaranteed by the standard greedy algorithm
given by (2), especially for large $n$. However, in cases where $n$ is small,
one could see a nontrivial increase in guaranteed performance: for instance,
when $n=2$ and $m/k=1$, then $\gamma=2/3$.

Another observation about Theorem 1 is that the bounds in (10) and (11) are
equal when $m/k\geq 1$ \- a range for $m$ where increasing $m$ does not affect
$\gamma$. This implies that increasing $m$ higher than $k$ does not offer any
benefit in terms of worst-case performance guarantees. Therefore, when
considering constraints on how much information agents may share with one
another, it may not benefit the system to increase capacity beyond that bound.

We also see that the upper and lower bounds are equal depending on how many
agents are in the system. For instance, when $n=2$, the lower and upper bounds
are equal. This implies that an augmented greedy policy is optimal in this
setting. Likewise, as $n\to\infty$, we see that the bounds are increasingly
tighter, showing that for high $n$, any augmented greedy policy is a near-
optimal policy. This provides motivation for further studying the augmented
greedy algorithm in the next section.

(a) An example for proving (10) when $m(n-1)\leq k$. The key is that
$|S_{n}|\leq k$, and the orange elements offer no value beyond $S_{n}$. Each
small box has width 1 and $s^{\rm big}$ has width $k(n-1)+1$. Thus
$f(x^{\pi})=k(n-1)+m(n-1)$ and $f(x^{\rm opt})=2k(n-1)+m(n-1)$.

(b) An example for proving (10) when $m(n-1)\geq k$. Unlike the example above,
here $S_{n}$ consists of exactly $k$ elements, thus $f(x^{\pi})=k(n-1)+k$ and
$f(x^{\rm opt})=2k(n-1)+k$.

Figure 2: Problem instances used in the proof for Theorem 1. This
representation is similar to that in Figure 1, in that each row represents
some $S_{i}$ and $f(A)$ is the amount of horizontal space covered by the boxes
in $A\subseteq S$. Blue squares represent elements chosen by policy $\pi$,
orange are those elements which are passed as messages using policy $\pi$, and
green are the optimal choices $x^{\rm opt}$, when those differ from the
algorithm. We have omitted the dashed boxes, with the understanding that an
orange box in $S_{i}$ is available to agents $j>i$.

###  III-C Proof for Theorem 1

To show (10), we introduce a problem instance $(f,(S_{i})_{i},k)$ such that
for any $\pi$, $f(x^{\pi})/f(x^{\rm opt})$ is lower than the bound in (10).

Fix $\pi$ and assume first that $(n-1)m\leq k$. Suppose that $f$ and
$(S_{i})_{i}$ are as represented in Figure 2(a). Here the format of example is
the same as in Figure 1. We assume that all of the small rectangles are of
width 1, and that the large rectangle $s^{\rm big}$ is of length $k(n-1)+1$.
Essentially, for agent $i\in\\{1,\dots,n-1\\}$, all elements in $S_{i}$ are
identical according to $f$, since none of these agents is aware of the
elements in $S_{n}$.

Therefore, without loss of generality, assume that $\pi_{i}$ selects the blue
elements for $x^{\pi}_{i}$, $i=1,\dots,n-1$. Likewise, assume without loss of
generality that $\pi_{i}$ selects the orange elements for $z^{\pi}_{i}$,
$i=1,\dots,n-1$. Notice that $|S_{n}|=m(n-1)\leq k$, so $x_{n}^{\pi}=S_{n}$ is
feasible, and an optimal choice regardless of the previous agents’ decisions.
This implies that $f(x^{\pi})=k(n-1)+m(n-1)$.

A set of optimal selections, where different from blue, are shaded in green,
showing that $f(x^{\rm opt})=2k(n-1)+m(n-1)$. It follows that for this problem
instance,

$\displaystyle\frac{f(x^{\pi})}{f(x^{\rm opt})}=$
$\displaystyle\frac{k(n-1)+m(n-1)}{2k(n-1)+m(n-1)}$ $\displaystyle=$
$\displaystyle\frac{1}{2-\frac{\min((n-1)m/k,1)}{n-1+\min((n-1)m/k,1)}}.$ (12)

In the case where $m(n-1)\geq k$, we leverage the example in Figure 2(b). Here
$S_{i}$ are the same as in Figure 2(a), for $i=1,\dots,n-1$, implying again
without loss of generality that $x^{\pi}_{1},\dots,x^{\pi}_{n-1}$ are the
respective blue elements. In this case, however, $|S_{n}|=k$, but note that
$f(x^{\pi}_{1},\dots,x^{\pi}_{n-1},x_{n})=kn$ for any $x_{n}\in(S_{n})^{k}$,
thus $f(x^{\pi})=kn$. The green elements are the optimal selection, where
different from the blue, showing that $f(x^{\rm opt})=2k(n-1)+k$. In this case
we see that

$\displaystyle\frac{f(x^{\pi})}{f(x^{\rm opt})}=$
$\displaystyle\frac{kn}{2k(n-1)+k}=\frac{n}{2(n-1)+1}.$ (13)

Equations (12) and (13) establish (10) for all cases.

We now show the lower bound on $\gamma$ in (11) by assuming $\pi$ takes on the
form in (5a)–(5d), and showing that for any $(f,(S_{i})_{i},k)$,
$f(x^{\pi})/f(x^{\rm opt})$ cannot be lower than the expression in (11). We
first define the function $\Delta$:

$\Delta(A|B):=f(A\cup B)-f(B),$ (14)

for $A,B\subseteq S$. This can be thought of as the marginal contribution of
$A$ given $B$ according to $f$. Likewise, define

$\Delta^{l}(A|B):=\max_{\tilde{A}\in(A)^{l}}\Delta(\tilde{A}|B).$ (15)

This can be thought as the value of the highest-valued subset of $A$ with size
at most $l$, with respect to $B$. Note that if $l\geq|A|$, then
$\Delta^{l}(A|B)=\Delta(A|B)$. It should also be clear that

$\displaystyle\Delta^{l}(A|B)\geq$
$\displaystyle\frac{\min(l,|A|)}{|A|}\Delta(A|B)$ $\displaystyle=$
$\displaystyle\min(l/|A|,1)\Delta(A|B).$ (16)

We also appeal to the following result:

###### Lemma 1

Assume a policy $\pi$ is applied to problem instance $(f,(S_{i})_{i},k)$ such
that for $\alpha\geq 1$

$\displaystyle\alpha\Delta^{k}(z_{i}^{\pi}|x^{\pi}_{1:i})\geq\Delta(x_{i}^{\rm
opt}|x^{\pi}_{1:i}).$ (17a)

Then

$\frac{f(x^{\pi})}{f(x^{\rm
opt})}\geq\frac{1}{2-\frac{1}{\sum_{i=0}^{n-1}\alpha^{i}}}$ (18)

The proof is found in Appendix -A. In the current setting it suffices to show
a valid value for $\alpha$ in order to show the lower bound on $\gamma_{\pi}$
(11). It follows that

$\displaystyle\Delta^{k}$ $\displaystyle(z^{\rm ag}_{i}|x^{\rm
ag}_{1:i})\geq\Delta(z^{k}_{i}|x^{\rm ag}_{1:i})\geq\Delta(x^{\rm
opt}_{i}|x_{1:i}^{\rm apx})$ (19a) $\displaystyle\geq$
$\displaystyle\Delta^{m}(x^{\rm opt}_{i}|x_{1:i}^{\rm
apx})\geq\min(m/k,1)\Delta(x^{\rm opt}_{i}|x_{1:i}^{\rm apx})$ (19b)

where (19a) is true by (5c) (recall that $z_{i}^{k}$ is defined in (5c)), and
(19b) is true by (16). Thus we can set ${\alpha=1/\min(m/k,1)}$. Then by Lemma
1,

$\displaystyle\frac{f(x^{\rm apx})}{f(x^{\rm opt})}\geq$
$\displaystyle\frac{1}{2-\frac{1}{\sum_{i=0}^{n-1}(1/\min(m/k,1))^{i}}}$
$\displaystyle=$
$\displaystyle\frac{1}{2-\frac{(\min(m/k,1))^{n-1}}{\sum_{i=0}^{n-1}(\min(m/k,1))^{i}}}.$

$\blacksquare$

##  IV A Best-Case Analysis

In this section we consider an optimistic approach to understanding how an
increase in message passing affects the performance of the system. We assume
the use of an augmented greedy policy, which Theorem 1 shows is near-optimal,
and study its potential effects. In particular, since the nominal greedy
algorithm in (2) is merely the augmented greedy algorithm when $m=0$,
comparing solutions of the two on an instance-by-instance basis can give
insight into the potential benefits of message passing. While the previous
section focused on worst-case scenarios, here we ask the question: how much
_could_ action sharing increase performance for any individual problem
instance? The following result gives insight on the answer to this question:

###### Theorem 2

For any $n\geq 2$, any $m\geq 0$, and any problem instance
$(f,(S_{i})_{i},k)$, the following holds:

$2+\min\left(\frac{m}{k},n-1\right)\geq\frac{f(x^{\rm ag})}{f(x^{\rm
ng})}\geq\frac{1}{2-\frac{(\min(m/k,1))^{n-1}}{\sum_{i=0}^{n-1}(\min(m/k,1))^{i}}},$
(20)

where $x^{\rm ag}$ is the solution to an augmented greedy algorithm and
satisfies (5a) for all $i$, and $x^{\rm ng}$ is the solution to a nominal
greedy algorithm and satisfies (2) for all $i$.

The proof is given in Appendix LABEL:app:optproof. While the result in Theorem
1 was a somewhat negative result (in general, increasing $m$ does not provide
much higher performance guarantees), here we see a strong upside to message
passing. For any given problem instance $(f,(S_{i})_{i},k)$, one could
increase $f(x)$ by a factor of $n+1$. And, though this will not be the case
for every problem instance, we will see in the next section that one can
expect $f(x)$ to increase by some amount.

Theorem 2 also gives insight into how much increasing $m$ might help any given
problem instance. Whereas previously we saw that increasing $m$ above $k$
offered no further guarantees, here we see potential benefits to increasing
$m$ all the way up to $k(n-1)$. We also see the potential drawback: on any
given instance, $f(x)$ could decrease by almost a factor of 1/2, although we
will see in the next section that such scenarios aren’t necessarily common.

##  V Numerical Example

Figure 3: Histograms of the relative performance for 1 million random
simulations of the vehicle camera estimation problem, where $k=m=2$ and $n=3$.
About $1/3$ of samples are at 1 (bar cropped to improve visualization), which
is interpreted as augmented greedy performing the same as nominal greedy.
Roughly 2/3 of examples showed improvement, whereas only about 1% showed a
decrease in performance. The orange bars indicate the theoretical bounds
provided in Theorem 2.

In this section, we present the results for instances of the state estimation
problem in Section II-B, where $n=3$ flying vehicles move along curved paths,
each carrying a side-looking camera with a 90-degree field of view, with focal
length $50$ pixels and measurement noise in the image plane with standard
deviation $\sigma=1$ pixel. In each problem instance, the start/stop positions
and curvature of each vehicle path are uniformly randomly selected. Vehicle
$i$ collects $10$ images along its path, which are processed into $|S_{i}|=10$
measurement estimates of $3$ targets (which are uniformly randomly placed) by
sending $k=2$ measurement estimates to the fusion center. Each measurement
estimate $s\in S$ has an associated matrix $Q_{s}$ which carries information
about the quality of that estimate, based on the vehicle location and camera
angle. Details of how to construct the objective function $f$ given in (3),
along with the matrices $Q_{0}$ and $Q_{s}$, are found in [23].

Figure 3 compares the resulting decision set of the augmented greedy algorithm
(5a)–(5d), where $m=2$, and that of the nominal greedy algorithm (2). The
orange bars show the Theorem 2 bounds for these problem instances:

$0.5714\leq\frac{f(x^{\rm ag})}{f(x^{\rm ng})}\leq 3.$ (21)

While one could construct problem instances that meet either bound, our 1
million randomly-generated simulations did not yield a value of $f(x^{\rm
ag})/f(x^{\rm ng})$ lower than $0.9$ or higher than $2$. The results show,
however, that about 2/3 of the problem instances showed a performance increase
with the augmented greedy algorithm. Only about 1% of instances showed a
decrease in performance. Therefore, while the theoretical bounds were not seen
in simulation, we see that message passing improves performance on average.

##  VI Conclusion

In this paper we have shown how message passing affects the performance
guarantees of a group of agents using the greedy algorithm. We showed that
when $m>k$, we receive no additional guarantees. We also showed that a simple
augmented greedy policy gives near-optimal performance guarantees. Using such
a policy, this paper explored how much performance could increase for any
problem instance, and showed by simulation that these results are relevant in
a real-world application.

Future work will continue to explore message passing, first by attempting to
create tighter bounds on $\gamma$. We also have some preliminary results
related to settings where (5a) and (5c) cannot be computed directly, only
approximated. Another direction could be to apply these results to situations
where agents can only see the actions of a subset of previous agents, and
again ask questions about what actions should be shared and selected.

## References

  * [1] A. Krause, C. Guestrin, A. Gupta, and J. Kleinberg, “Near-optimal sensor placements: Maximizing information while minimizing communication cost,” in _Proceedings of the International Conference on Information Processing in Sensor Networks_. ACM, 2006, pp. 2–10.
  * [2] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, C. Faloutsos, J. VanBriesen, and N. Glance, “Cost-effective outbreak detection in networks,” in _Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, 2007, pp. 420–429.
  * [3] D. Kempe, J. Kleinberg, and É. Tardos, “Maximizing the spread of influence through a social network,” in _Proceedings of the ACM SIGKDD international conference on Knowledge discovery and data mining_. ACM, 2003, pp. 137–146.
  * [4] M. Gomez-Rodriguez, J. Leskovec, and A. Krause, “Inferring networks of diffusion and influence,” _ACM Transactions on Knowledge Discovery from Data (TKDD)_ , vol. 5, no. 4, p. 21, 2012.
  * [5] H. Lin and J. Bilmes, “A class of submodular functions for document summarization,” in _Proceedings of the Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1_. Association for Computational Linguistics, 2011, pp. 510–520.
  * [6] B. Mirzasoleiman, A. Karbasi, R. Sarkar, and A. Krause, “Distributed submodular maximization: Identifying representative elements in massive data,” in _Advances in Neural Information Processing Systems_ , 2013, pp. 2049–2057.
  * [7] G. Qu, D. Brown, and N. Li, “Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions,” _Automatica_ , vol. 105, pp. 206–215, 2019.
  * [8] A. Singh, A. Krause, C. Guestrin, W. J. Kaiser, and M. A. Batalin, “Efficient planning of informative paths for multiple robots.” in _International Joint Conferences on Artificial Intelligence_ , vol. 7, 2007, pp. 2204–2211.
  * [9] A. Clark and R. Poovendran, “A submodular optimization framework for leader selection in linear multi-agent systems,” in _Conference on Decision and Control and European Control Conference_. IEEE, 2011, pp. 3614–3621.
  * [10] J. R. Marden, “The role of information in distributed resource allocation,” _IEEE TCNS_ , vol. 4, no. 3, pp. 654–664, Sept 2017.
  * [11] M. Grötschel, L. Lovász, and A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization,” _Combinatorica_ , vol. 1, no. 2, pp. 169–197, 1981.
  * [12] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions I,” _Mathematical Programming_ , vol. 14, no. 1, pp. 265–294, 1978.
  * [13] M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, “An analysis of approximations for maximizing submodular set functions II,” in _Polyhedral combinatorics_. Springer, 1978, pp. 73–87.
  * [14] G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, “Maximizing a submodular set function subject to a matroid constraint,” in _International Conference on Integer Programming and Combinatorial Optimization_. Springer, 2007, pp. 182–196.
  * [15] M. Gairing, “Covering games: Approximation through non-cooperation,” in _International Workshop on Internet and Network Economics_. Springer, 2009, pp. 184–195.
  * [16] U. Feige, “A threshold of ln $n$ for approximating set cover,” _Journal of the ACM (JACM)_ , vol. 45, no. 4, pp. 634–652, 1998.
  * [17] B. Gharesifard and S. L. Smith, “Distributed submodular maximization with limited information,” _Trans. on Control of Network Systems_ , vol. 5, no. 4, pp. 1635–1645, 2017.
  * [18] D. Grimsman, M. S. Ali, J. P. Hespanha, and J. R. Marden, “The impact of information in greedy submodular maximization,” _Trans. on Control of Network Systems_ , 2018.
  * [19] D. Grimsman, J. H. Seaton, P. N. Brown, and J. R. Marden, “The cost of denied observation in multiagent submodular optimization,” in _IEEE Conference on Decision and Control (CDC)_. IEEE, 2020\.
  * [20] D. Grimsman, J. P. Hespanha, and J. R. Marden, “Strategic information sharing in greedy submodular maximization,” in _2018 IEEE Conference on Decision and Control (CDC)_. IEEE, 2018, pp. 2722–2727.
  * [21] M. Corah and N. Michael, “Distributed submodular maximization on partition matroids for planning on large sensor networks,” in _Conference on Decision and Control_. IEEE, 2018, pp. 6792–6799.
  * [22] ——, “Distributed matroid-constrained submodular maximization for multi-robot exploration: Theory and practice,” _Autonomous Robots_ , vol. 43, no. 2, pp. 485–501, 2019.
  * [23] M. R. Kirchner, J. P. Hespanha, and D. Garagic, “Heterogeneous measurement selection for vehicle tracking using submodular optimization,” in _Proc. of the 2020 IEEE Aerospace Conf._ , 2020, pp. 1–10.

###  -A Proof for Lemma 1

We begin with

$\displaystyle f($ $\displaystyle x^{\rm opt})\leq
f(x^{\pi}_{1:n-1})+\Delta(x^{\rm opt}|x^{\pi}_{1:n-1})$ (22a) $\displaystyle=$
$\displaystyle f(x^{\pi}_{1:n-1})+\Delta(x^{\rm opt}_{n}|x^{\rm
opt}_{1:n-1},x^{\pi}_{1:n-1})$ $\displaystyle+\sum_{i=1}^{n-1}\Delta(x^{\rm
opt}_{i}|x^{\rm opt}_{1:i-1},x^{\pi}_{1:n-1})$ (22b) $\displaystyle\leq$
$\displaystyle f(x^{\pi}_{1:n-1})+\Delta(x^{\rm
opt}_{n}|x^{\pi}_{1:n-1})+\sum_{i=1}^{n-1}\Delta(x^{\rm
opt}_{i}|x^{\pi}_{1:i})$ (22c) $\displaystyle\leq$ $\displaystyle
f(x^{\pi}_{1:n-1})+\Delta(x^{\pi}_{n}|x^{\pi}_{1:n-1})+\sum_{i=1}^{n-1}\Delta(x^{\rm
opt}_{i}|x^{\pi}_{1:i})$ (22d)

where (22a) and (22c) follow from submodularity of $f$, (22b) follows from the
definition of $\Delta(\cdot)$, and (22d) follows from (5a). Focusing on the
sum in (22d), for any $0\leq\varepsilon_{1},\dots\varepsilon_{n-1}\leq 1$ (and
defining ${\varepsilon_{0}=0}$), we see that

$\displaystyle\sum_{i=1}^{n-1}$ $\displaystyle\Delta(x^{\rm
opt}_{i}|x^{\pi}_{1:i})=\sum_{i=1}^{n-1}(1-\varepsilon_{i})\Delta(x^{\rm
opt}_{i}|x^{\pi}_{1:i})$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
+\sum_{i=1}^{n-1}\varepsilon_{i}\Delta(x^{\rm opt}_{i}|x^{\pi}_{1:i})$ (23a)
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{n-1}(1-\varepsilon_{i})\Delta(x^{\rm
opt}_{i}|x^{\pi}_{1:i-1})+\sum_{i=1}^{n-1}\alpha\varepsilon_{i}\Delta^{k}(z^{\pi}_{i}|x^{\pi}_{1:i})$
(23b) $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{n-1}(1-\varepsilon_{i})\Delta(x^{\pi}_{i}|x^{\pi}_{1:i-1})+\sum_{i=1}^{n-1}\alpha\varepsilon_{i}\Delta(x^{\pi}_{i+1}|x^{\pi}_{1:i})$
(23c) $\displaystyle=$
$\displaystyle\alpha\varepsilon_{n-1}\Delta(x^{\pi}_{n}|x^{\pi}_{1:n-1})$
$\displaystyle+\sum_{i=1}^{n-1}(1-\varepsilon_{i}+\alpha\varepsilon_{i-1})\Delta(x^{\pi}_{i}|x^{\pi}_{1:i-1}),$
(23d)

where (23b) is true by submodularity of $f$ (1st term) and (17a) (2nd term),
(23c) is true by (5a). Applying this to (22d) yields

$\displaystyle f($ $\displaystyle x^{\rm opt})\leq
f(x^{\pi}_{1:n-1})+(1+\alpha\varepsilon_{n-1})\Delta(x^{\pi}_{n}|x^{\pi}_{1:n-1})$
$\displaystyle+\sum_{i=1}^{n-1}(1-\varepsilon_{i}+\alpha\varepsilon_{i-1})\Delta(x^{\pi}_{i}|x^{\pi}_{1:i-1})$
(24a) $\displaystyle=$
$\displaystyle(1+\alpha\varepsilon_{n-1})\Delta(x^{\pi}_{n}|x^{\pi}_{1:n-1})$
$\displaystyle+\sum_{i=1}^{n-1}(2-\varepsilon_{i}+\alpha\varepsilon_{i-1})\Delta(x^{\pi}_{i}|x^{\pi}_{1:i-1}).$
(24b)

Suppose that for a particular choice of $\varepsilon_{i}$, we let

$\varepsilon_{i}=\frac{\sum_{j=0}^{i-1}\alpha^{j}}{\sum_{j=0}^{n-1}\alpha^{j}}.$
(25)

Since $\alpha\geq 1$, this satisfies the requirement that
${0\leq\varepsilon_{i}\leq 1}$ for $i\in\\{1,\dots,n-1\\}$. Then

$\displaystyle-\varepsilon_{i}+\alpha\varepsilon_{i-1}=$
$\displaystyle-\frac{\sum_{j=0}^{i-1}\alpha^{j}}{\sum_{j=0}^{n-1}\alpha^{j}}+\frac{\sum_{j=1}^{i-1}\alpha^{j}}{\sum_{j=0}^{n-1}\alpha^{j}}=-\frac{1}{\sum_{j=0}^{n-1}\alpha^{j}}$
(26)

Likewise

$\displaystyle\varepsilon_{n-1}=$
$\displaystyle\frac{\alpha\sum_{j=0}^{n-2}\alpha^{j}}{\sum_{j=0}^{n-1}\alpha^{j}}=\frac{\sum_{j=1}^{n-1}\alpha^{j}}{\sum_{j=0}^{n-1}\alpha^{j}}=1-\frac{1}{\sum_{j=0}^{n-1}\alpha^{j}}$
(27)

Applying (26) and (27) to (24b) yields

$\displaystyle f($ $\displaystyle x^{\rm
opt})\leq\left(2-\frac{1}{\sum_{j=0}^{n-1}\alpha^{j}}\right)\Delta(x^{\pi}_{n}|x^{\pi}_{1:n-1})$
$\displaystyle+\sum_{i=1}^{n-1}\left(2-\frac{1}{\sum_{j=0}^{n-1}\alpha^{j}}\right)\Delta(x^{\pi}_{i}|x^{\pi}_{1:i-1})$
(28) $\displaystyle=$
$\displaystyle\left(2-\frac{1}{\sum_{j=0}^{n-1}\alpha^{j}}\right)f(x^{\pi})$
(29)

$\blacksquare$

###  -B Proof for Theorem 2

The lower bound in (20) is a consequence of Theorem 1, since $f(x^{\rm
ng})\leq f(x^{\rm opt})$. To prove the upper bound, begin with the following:

$\displaystyle f$ $\displaystyle(x^{\rm ag})\leq f(x^{\rm ng})+\Delta(x^{\rm
ag}|x^{\rm ng})$ (30a) $\displaystyle\leq$ $\displaystyle f(x^{\rm
ng})+\Delta(z_{1:n-1}^{\rm ag}\cap x^{\rm ag}|x^{\rm ng})+\Delta(x^{\rm
ag}\setminus z_{1:n-1}^{\rm ag}|x^{\rm ng})$ (30b) $\displaystyle=$
$\displaystyle f(x^{\rm ng})+\Delta(z_{1:n-1}^{\rm ag}\cap x^{\rm ag}|x^{\rm
ng})$ $\displaystyle+\sum_{i}\Delta(x^{\rm ag}_{i}\setminus z_{1:n-1}^{\rm
ag}|x^{\rm ng},x^{\rm ag}_{1:i-1}\setminus z_{1:n-1}^{\rm ag})$ (30c)
$\displaystyle\leq$ $\displaystyle f(x^{\rm ng})+\Delta(z_{1:n-1}^{\rm ag}\cap
x^{\rm ag}|x^{\rm ng})$ $\displaystyle+\sum_{i}\Delta(x^{\rm ag}_{i}\setminus
z_{1:n-1}^{\rm ag}|x^{\rm ng}_{1:i-1})$ (30d) $\displaystyle\leq$
$\displaystyle f(x^{\rm ng})+\Delta(z_{1:n-1}^{\rm ag}\cap x^{\rm ag}|x^{\rm
ng})+\sum_{i}\Delta(x^{\rm ag}_{i}|x^{\rm ng}_{1:i-1})$ (30e) $\displaystyle=$
$\displaystyle 2f(x^{\rm ng})+\Delta(z_{1:n-1}^{\rm ag}\cap x^{\rm ag}|x^{\rm
ng})$ (30f)

where (30a), (30b), (30d) are true by submodularity of $f$, and (30e) is true
by (5a).

We denote $\tilde{z}^{\rm ag}_{i}$ to mean $z^{\rm ag}_{i}\cap x^{\rm ag}$,
and suppose that there exists $\alpha$ such that $\Delta(\tilde{z}^{\rm
ag}_{i}|x^{\rm ng}_{1:i})\leq\alpha\Delta(x^{\rm ng}_{i}|x^{\rm ng}_{1:i-1})$.
Then the second term in (30f) can be upper bounded by the following:

$\displaystyle\Delta(\tilde{z}_{1:n-1}|x^{\rm ng})\leq$
$\displaystyle\sum_{i=1}^{n-1}\Delta(\tilde{z}^{\rm ag}_{i}|\tilde{z}^{\rm
ag}_{1:i-1},x^{\rm ng})$ (31a) $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{n-1}\Delta(\tilde{z}^{\rm ag}_{i}|x^{\rm ng}_{1:i})$
(31b) $\displaystyle\leq$ $\displaystyle\sum_{i=1}^{n-1}\alpha\Delta(x^{\rm
ng}_{i}|x^{\rm ng}_{1:i})$ (31c) $\displaystyle=$ $\displaystyle\alpha
f(x^{\rm ng}_{1:n-1})\leq\alpha f(x^{\rm ng}),$ (31d)

where (31b) and (31d) are true by the submodularity of $f$. Substituting this
upper bound back into (30f), we see that

$f(x^{\rm ag})\leq(2+\alpha)f(x^{\rm ng}).$

We now show that such an $\alpha$ exists and define it for two cases: when
$m\leq k$ and when $m\geq k$. First suppose that $m\leq k$. Denote
$x^{k-m}_{i}$ to be the $\operatorname*{arg\,max}$ of (15) when $l=k-m$,
$A=x^{\rm ng}_{i}$ and $B=x^{\rm ng}_{1:i-1}$. Then

$\displaystyle\Delta($ $\displaystyle x^{\rm ng}_{i}|x^{\rm
ng}_{1:i-1})\geq\Delta(\tilde{z}^{\rm ag}_{i}\cup x^{k-m}_{i}|x^{\rm
ng}_{1:i-1})$ (32a) $\displaystyle=$ $\displaystyle\Delta(\tilde{z}^{\rm
ag}_{i}|x^{\rm ng}_{1:i-1},x_{i}^{k-m})+\Delta(x^{k-m}_{i}|x^{\rm
ng}_{1:i-1})$ (32b) $\displaystyle\geq$ $\displaystyle\Delta(\tilde{z}^{\rm
ag}_{i}|x^{\rm ng}_{1:i})+\Delta^{k-m}(x^{\rm ng}_{i}|x^{\rm
ng}_{1:i-1})\implies$ (32c) $\displaystyle\Delta($
$\displaystyle\tilde{z}^{\rm ag}_{i}|x^{\rm ng}_{1:i})\leq\Delta(x^{\rm
ng}_{i}|x^{\rm ng}_{1:i-1})-\Delta^{k-m}(x^{\rm ng}_{i}|x^{\rm ng}_{1:i-1})$
(32d) $\displaystyle\leq$ $\displaystyle\Delta(x^{\rm ng}_{i}|x^{\rm
ng}_{1:i-1})-\frac{k-m}{k}\Delta(x^{\rm ng}_{i}|x^{\rm ng}_{1:i-1})$ (32e)
$\displaystyle=$ $\displaystyle(m/k)\Delta(x^{\rm ng}_{i}|x^{\rm
ng}_{1:i-1}),$ (32f)

where (32a) is true since $x_{i}^{\rm ng}$ is selected by (5a), (32c) is true
by submodularity of $f$ and by (15), and (32d) is true by (16). We conclude
that when $m\leq k$, $\alpha=m/k$.

Next suppose that $m\geq k$. Observe that $|\tilde{z}^{\pi}_{i}|\leq k(n-1)$,
since using the approximated augmented greedy policy, no more than $k(n-1)$
elements of $z^{\rm ag}_{i}$ can be chosen by other agents. This implies the
following:

$\displaystyle\Delta($ $\displaystyle\tilde{z}_{i}^{\rm ag}|x^{\rm
ng}_{1:i})\leq(1/\min(k/|\tilde{z}_{i}^{\rm
ag}|,1))\Delta^{k}(\tilde{z}_{i}^{\rm ag}|x^{\rm ng}_{1:i})$ (33a)
$\displaystyle\leq$ $\displaystyle\max(|\tilde{z}_{i}^{\rm
ag}|/k,1)\Delta^{k}(\tilde{z}_{i}^{\rm ag}|x^{\rm ng}_{1:i})$ (33b)
$\displaystyle\leq$
$\displaystyle\max(\min(k(n-1),m)/k,1)\Delta^{k}(\tilde{z}_{i}^{\rm ag}|x^{\rm
ng}_{1:i})$ (33c) $\displaystyle=$
$\displaystyle\min(n-1,m/k)\Delta^{k}(\tilde{z}_{i}^{\rm ag}|x^{\rm
ng}_{1:i})$ (33d) $\displaystyle\leq$ $\displaystyle\min(n-1,m/k)\Delta(x^{\rm
ng}_{i}|x^{\rm ng}_{1:i-1})$ (33e)

We conclude that when $m\geq k$, $\alpha=\min(n-1,m/k)$, implying that for
this case:

$f(x^{\rm ag})\leq(2+\min(n-1,m/k))f(x^{\rm ng}).$

$\blacksquare$