# Execution Order Matters in Greedy Algorithms with Limited Information

Rohit Konda, David Grimsman, Jason R. Marden R. Konda and J. R. Marden are
with the Department of Electrical and Computer Engineering at the University
of California, Santa Barbara, CA and D. Grimsman is with the Department of
Computer Science at Brigham Young University. This work is supported by AFOSR
Grant #FA9550-20-1-0054 and AFOSR Grant #FA9550-21-1-0203.

###### Abstract

In this work, we study the multi-agent decision problem where agents try to
coordinate to optimize a given system-level objective. While solving for the
global optimum is intractable in many cases, the _greedy algorithm_ is a well-
studied and efficient way to provide good approximate solutions - notably for
submodular optimization problems. Executing the greedy algorithm requires the
agents to be ordered and execute a local optimization based on the solutions
of the previous agents. However, in limited information settings, passing the
solution from the previous agents may be nontrivial, as some agents may not be
able to directly communicate with each other. Thus the communication time
required to execute the greedy algorithm is closely tied to the order that the
agents are given. In this work, we characterize interplay between the
communication complexity and agent orderings by showing that the complexity
using the best ordering is $O(n)$ and increases considerably to $O(n^{2})$
when using the worst ordering. Motivated by this, we also propose an algorithm
that can find an ordering and execute the greedy algorithm quickly, in a
distributed fashion. We also show that such an execution of the greedy
algorithm is advantageous over current methods for distributed submodular
maximization.

##  I Introduction

Many real-world problems are well-modeled as multiagent decision problems,
including building energy management [1], stock trading [2], water resource
allocation [3, 4], traffic light management [5], the power grid [6], and robot
path planning [7]. In these scenarios, the set of $n$ decision makers, or
agents, coordinate to a joint decision that maximizes some objective function.

In general, finding the optimal decision set is computationally intractable,
even for a centralized authority. Therefore, there exist a multitude of
techniques for arriving at a joint decision, which may be an approximation of
the optimal. For instance, consensus algorithms offer a way for agents to
converge as a group toward a unified decision [8, 9, 10]. In other settings, a
game-theoretic approach is advantageous, where agents arrive at a joint
decision which is some form of equilibrium (e.g., Nash equilibrium [11],
Wardrop equilibrium [12], Stackelberg equilibrium [13], etc.). Of course even
finding such equilibria can be challenging [14], but there are subclasses of
problems where this can be done efficiently [15].

Another common approach to multiagent decision problems is a greedy algorithm
[16, 17]. A common theme among greedy algorithms is that at each iteration of
the algorithm, a myopic choice is made: simply pick the best immediate option,
ignoring the effect on future iterations of the algorithm. As with the other
algorithms mentioned above, greedy algorithms in general are not always
guaranteed to find an optimal solution to a given problem, however, they are
often easy to implement, execute quickly, and in some cases provide some
degree of optimality.

This work focuses on the scenario where a greedy algorithm is used to solve a
multiagent decision problem. In this setting, a greedy algorithm is
implemented by first ordering the agents. Then each agent sequentially makes
its decision by choosing the action that maximizes the objective function,
based solely on the decisions of previous agents in the sequence. An
underlying element of the greedy algorithm is that the agents are able to
coordinate with each other via some network. In the best case, such a network
would allow for each agent to communicate with all other agents directly. In
many applications, however, this is not realistic; communication between
agents $i$ and $j$ must pass through other agents in the network. If $i$ and
$j$ are on opposite ends of the network, or if the network has highly-limited
bandwidth, this communication may be delayed. In light of this, two questions
arise:

  1. 1.

Given the structure of the communication network, how does the ordering of the
agents affect the time it takes to complete the greedy algorithm?

  2. 2.

Can the agents coordinate among themselves to find the ordering that will
cause the greedy algorithm to complete as fast as possible?

We address the first question by showing, given a network structure, that the
greedy algorithm finishes in $O(n^{2})$ time steps for the worst ordering and
$O(n)$ time steps for the best ordering. We then address the second question
by presenting a fully-distributed algorithm whereby agents can find a near-
optimal ordering while simultaneously runnning the greedy algorithm.

Of particular import in this work are submodular maximization problems, which
are prevalent in modeling many applications, such as sensor placement [18],
data summarization [19, 20], robot path planning [21, 22], task allocation
[23], inferring influence in a social network [24], image segmentation [25],
outbreak detection in networks [26], and leader selection in multiagent
systems [27]. A key feature that is shared among the objective functions in
these various domains is a property of _diminishing returns_. For example, in
outbreak detection, the added benefit of placing an outbreak sensor on a node
in a network is valuable when there are few other sensors in the network, and
less valuable when there are already many other sensors present. Objectives
that exhibit such properties are _submodular_.

While such problems are NP-Hard in general, the property of submodularity can
be exploited to show that certain algorithms can achieve near-optimal results.
The seminal work in [28] shows that a centralized greedy algorithm can, in
fact, provide a solution that is guaranteed to be within $1/2$ of the optimal
solution. More sophisticated algorithms have pushed this guarantee from $1/2$
to $1-1/e\approx 0.63$ [29, 30]. Progress beyond this approximation frontier
is not possible for polynomial time algorithms as it was also shown that no
such algorithm can achieve higher guarantees than $1-1/e$, unless $P=NP$ [31].

Recently, work has emerged wherein submodular maximization problems are
modeled as multiagent decision problems [32, 33, 34, 35]. In Section V, we
will show how our version of the greedy algorithm applies to this setting
111It should be noted that the work in [36] also explores the idea of
performing the standard greedy algorithm on a network for a submodular
maximization problem. It was shown that as links are removed from the network,
the performance guarantee decreases. The setting of our current paper differs
in that we allow $k$-hop communication, which is why the $1/2$ guarantee is
maintained. It also differs in that the work in [36] assumes an implicit
ordering of the agents, whereas in this paper the agents must coordinate to
find an ordering., and how this algorithms compares to existing techniques in
terms of runtime and performance guarantees. It will be shown that the greedy
algorithm will complete in fewer time steps than existing methods, while still
maintaining 1/2-optimality in the resulting decision set.

In Section II, we introduce our model. In Section III, we present our main
results on communication time guarantees versus different orderings. We
empirically verify our theoretical results in Section IV and discuss the
implications in submodular maximization problems in Section V. We conclude in
Section VI. The relevant code is found at [37]. We sincerely thank Gilberto
Diaz-Garcia for the helpful discussions.

##  II Model

Consider a distributed optimization problem with $n$ agents
$\mathcal{I}=\\{1,\dots,n\\}$, where each agent is endowed with a decision or
action set $\mathcal{A}_{i}$. We denote an action as
$a_{i}\in\mathcal{A}_{i}$, and a joint action profile as
$a\in\mathcal{A}=\mathcal{A}_{1}\times\cdots\mathcal{A}_{n}$. We assume that
each agent $i$ has the ability to “opt out” of participating in the decision
process. This is modeled by having an action
$a^{\varnothing}_{i}\in\mathcal{A}_{i}$, so that when agent $i$ chooses action
$a^{\varnothing}_{i}$, agent $i$ is opting out. The quality of each joint
action profile is evaluated with a global objective function
$\mathrm{W}(a):\mathcal{A}\to\mathbb{R}_{\geq 0}$ that a system designer seeks
to maximize. In other words, the goal of the system designer is to coordinate
the agents to a joint action profile that satisfies

$a^{\mathrm{opt}}\in\operatorname*{arg\,max}_{a\in\mathcal{A}}\mathrm{W}(a).$
(1)

In general, solving the multi-agent decision problem in Eq. $\eqref{eq:opt}$
is infeasible, due to computational, informational, communication constraints
etc. Therefore, fast, distributed algorithms are employed to compute good
approximate solutions. The _greedy algorithm_ has cemented its place as a
universal approach to arrive at approximate solutions in many application
domains. In this algorithm, the set of agents is ordered (for instance,
according to its index $i$) and then each agent sequentially solves the
reduced optimization problem

$\tilde{a}_{i}\in\operatorname*{arg\,max}_{a_{i}\in\mathcal{A}_{i}}\mathrm{W}(\tilde{a}_{1},\dots,\tilde{a}_{i-1},a_{i},a^{\varnothing}_{i+1},\dots,a^{\varnothing}_{n}),$
(2)

where each agent $i$ chooses the best action $\tilde{a}_{i}$ given that the
previous agents in the sequence have also played their best action and the
successive agents in the sequence have opted out. After each agent chooses
according to Eq. (2), then the algorithm is complete and the resulting set of
decisions $(\tilde{a}_{1},\dots,\tilde{a}_{n})$ comprises the joint decision
set $\tilde{a}$. The process completes in $n$ time steps, where a time step is
comprised of an agent making a decision and communicating that decision to
future agents in the sequence.

However, the greedy algorithm makes a key assumption that agents have access
to the decisions of the previous agents. In purely distributed systems, this
assumption may be infeasible. There have been prior works that study the
performance of the greedy algorithm with relaxed informational assumptions, in
that agent $i$ only knows the decisions of some strict subset of the previous
agents $S\subset\\{1,\dots,i-1\\}$ [36, 17]. However, this work takes a
different approach, where we assume that agents can make up for their
informational deficiencies through a communication infrastructure. We model
the communication constraints through an underlying graph structure
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where each vertex in $\mathcal{V}$
corresponds to an agent in $\mathcal{I}$ and each edge
$(i,j)\in\mathcal{E}=\mathcal{V}\times\mathcal{V}$ implies that agents $i$ and
$j$ can communicate with one another. The graph $\mathcal{G}$ is assumed to be
connected and undirected throughout this paper, unless explicitly stated. The
set of agents that agent $i$ can communicate with is agent $i$’s neighborhood
$\mathcal{N}_{i}$.

The primary focus of this work is to examine the interplay between the
communication graph $\mathcal{G}$ and the order in which the greedy algorithm
in Eq. (2) is solved under. For a given graph $\mathcal{G}$, the order
$\pi:\mathcal{V}\to\mathcal{I}$ is defined by which label $i$ given to each
vertex $v$. Therefore, given $\mathcal{G}$, we would like the characterize the
communication time guarantees of the worst order and the best order. To
analyze the spectrum of possible guarantees with respect to different ordering
methods, we define the following two quantities

$\displaystyle T_{\min}(\mathcal{G})$ $\displaystyle=\min_{\pi}\
T(\mathcal{G},\pi),$ (3) $\displaystyle T_{\max}(\mathcal{G})$
$\displaystyle=\max_{\pi}\ T(\mathcal{G},\pi),$ (4)

where $T(\mathcal{G},\pi)$ refers to the time it takes for the communication
process to finish for a given graph $\mathcal{G}$ and ordering $\pi$. We will
use $\pi_{\mathrm{best}}$ and $\pi_{\mathrm{worst}}$ to refer to the orderings
that are the solutions of Eq. (3) and Eq. (4) respectively. We remark that
only in the full information setting, where $\mathcal{G}_{c}$ is the complete
graph, is the run-time for any order the same, with
$T_{\max}(\mathcal{G}_{c})=T_{\min}(\mathcal{G}_{c})=n-1$.

We can describe the $k$-hop communication, in which an agent $i$’s greedy
action $\tilde{a}_{i}$ is passed along to agents outside of its neighborhood
$\mathcal{N}_{i}$, using the following graph-theoretic notation. A _walk_ on
the graph $\mathcal{G}$ is a sequence of vertices
$\gamma=(v_{1},\dots,v_{m})$, in which each successive pair
$(v_{j},v_{j+1})\in\mathcal{E}$ for all $1\leq j<m$. We denote the length of
the walk as $|\gamma|$ being the number of vertices in the sequence. A
_spanning walk_ is a walk in which all vertices in the graph are visited and a
_minimum spanning walk_ is a spanning walk with shortest length. A _path_ $p$
is a walk in which all the vertices $\\{v_{j}\\}_{j\leq m}$ are all distinct.
The expression of $T(\mathcal{G},\pi)$ is given as

$T(\mathcal{G},\pi)=\sum_{i=1}^{n-1}\Big{(}\min_{p_{i\to i+1}}|p_{i\to
i+1}|-1\Big{)},$ (5)

where $p_{i\to i+1}$ is a path on the graph from the vertex (labeled with) $i$
to the vertex $i+1$. This expression is motivated by a natural communication
process, where initially agent $1$ computes its greedy action $\tilde{a}_{1}$
at time $0$. Then agent $1$ communicates $\tilde{a}_{1}$ to agent $2$ through
a $k$-hop walk through the graph, where each hop is assumed to take $1$ time
step. Then agent $2$ computes $\tilde{a}_{2}$ given $\tilde{a}_{1}$ and passes
both actions to agent $3$ through another $k$-hop walk. Continuing this
process, agent $n-1$ passes $\\{\tilde{a}_{j}\\}_{j<n}$ to agent $n$ and agent
$n$ computes $\tilde{a}_{n}$ finishing the process. To isolate the run-time
analysis with respect to only the communication time, we also assume that
agents can solve for their greedy action $\tilde{a}_{i}$ arbitrarily fast.

##  III Main Results on Communication Time

###  III-A Motivating Example

To make the communication process concrete, consider when the given
communication graph is a line graph as shown in Figure 1. In this graph
scenario, agent $1$ initially computes its greedy response $\tilde{a}_{1}$ and
passes the action it has played to agent $2$ at $t=0$. Then at $t=1$, agent
$2$ (knowing $\tilde{a}_{1}$) can compute $\tilde{a}_{2}$ and passes both
$\tilde{a}_{1}$ and $\tilde{a}_{2}$ along to agent $3$. Continuing this to
$t=5$, agent $6$ will have been passed the greedy actions of all previous
agents $1$ through $5$ and play its greedy action $\tilde{a}_{6}$, completing
the greedy algorithm in Eq. (2). This will complete in $T(\mathcal{G},\pi)=5$
time steps, which is the best that one can hope for when implementing the
greedy algorithm in a limited information setting.

Figure 1: Example of a line graph, where we have labeled the vertices
according to the best ordering $\pi_{\mathrm{best}}$. In this example, the
agents compute their greedy action and pass it down the line.

However, consider the following order in Figure 2. This situation can occur if
the order $\pi$ is improperly picked by the system operator. Under this
ordering, agent $2$ can only receive the greedy action of agent $1$ through a
$3$-hop path through agents $6$ and $4$, since there is not a direct
communication link between agent $1$ and agent $2$. Following this logic, the
greedy algorithm will complete at time $T(\mathcal{G},\pi)=3+5+4+3+2=17$,
which can be seen to be significantly higher than the previous well chosen
order.

Figure 2: Example of a line graph, but instead we consider the adversarial
ordering $\pi_{\mathrm{worst}}$ in which the vertices are labeled
intermittently. In this instance, the $k$-hop communication path must bounce
back and forth between agents to complete the greedy algorithm.

Extending this argument to $n$ agents, under a line graph, the greedy
algorithm under the best ordering $\pi_{\mathrm{best}}$ will complete in
$T(\mathcal{G},\pi_{\mathrm{best}})=n-1$ steps and under the worst ordering
$\pi_{\mathrm{worst}}$ will complete in
$T(\mathcal{G},\pi_{\mathrm{worst}})=\left\lfloor n^{2}/2\right\rfloor-1$
steps, where $\left\lfloor a\right\rfloor$ is the floor function. Therefore,
there may be a significant gap in the communication complexity that results
from choosing different orderings. We analyze the possible gap by
characterizing the quantities $T_{\max}(\mathcal{G})$ and
$T_{\min}(\mathcal{G})$ in this paper.

###  III-B Communication Run-time Characterizations

We outline the main theorem of the paper below, where the worst case
communication time over any graph structure is given for the best and worst
orderings. The corresponding graph structures and orders that attain the
worst-case communication time are displayed in Figure 2 and Figure 3.

Figure 3: A $7$ node star graph with agent $2$ in the center. We note that the
communication time $T(\mathcal{G},\pi)$ on this graph using any ordering must
be greater than $2\cdot 7-4=10$. For $n\geq 3$ agents, the $n$-node star graph
is the worst case graph for the best ordering $\pi_{\mathrm{best}}$.

######  Theorem 1.

Let $n\geq 3$ be the number of agents. The maximum communication time required
to complete the greedy algorithm in Eq. (2) for any undirected, connected
communication graph $\mathcal{G}$ with the best and worst orderings is equal
to

$\displaystyle\max_{\mathcal{G}}\ T_{\min}(\mathcal{G})$ $\displaystyle=2n-4$
(6) $\displaystyle\max_{\mathcal{G}}\ T_{\max}(\mathcal{G})$
$\displaystyle=\left\lfloor n^{2}/2\right\rfloor-1,$ (7)

where $T_{\min}(\mathcal{G})$ is defined in Eq. (3) and
$T_{\max}(\mathcal{G})$ is defined in Eq. (4) and $\left\lfloor
a\right\rfloor$ is the largest integer that is below $a$.

###### Proof.

Proof is found in the Appendix. ∎

###  III-C Distributed Orderings that are Near-Optimal

According to Theorem 1, there is a significant complexity gap between using
the best ordering $\pi_{\mathrm{best}}$ and worst ordering
$\pi_{\mathrm{worst}}$ for the communication time. However, finding the best
order $\pi_{\mathrm{best}}$ in general is not practical either due to
computational restrictions or lack of information about the graph. So we would
like to be able compute orderings that get as close to the run-time with
$\pi_{\mathrm{best}}$ as possible in a feasible manner. Therefore in this
section, we construct an algorithm that can quickly compute a good ordering in
conjunction with executing the greedy algorithm. An outline of the proposed
algorithm is in Algorithm 1 with a fully distributed implementation found in
[37]. The proposed design in essence computes a spanning walk on the graph
that is close to the length of the minimum spanning walk through a variant of
a depth-first search algorithm.

The distributed implementation of Algorithm 1 to compute an approximate
solution to Eq. (1) offers significant benefits over other distributed
approaches. The communication scheme is simple, which allows for linear-time
guarantees. This also means that the message complexity is low, where the bulk
of the message is comprised of the previous agent’s actions and the
communication is robust to time delays. Lastly, since the base of Algorithm 1
is the greedy algorithm, we also inherit the corresponding performance
guarantees. To be able to run Algorithm 1, we assume that each agent (vertex)
can store and access the following variables.

  * •

$v\mathrm{.actions}=\varnothing$ is the set of greedy actions that $v$ knows.

  * •

$v\mathrm{.order}=\varnothing$ is the index in $\mathcal{I}$ that $v$ is
labeled with.

  * •

$v\mathrm{.parent}=\varnothing$ is $v$’s parent in the depth first search.

  * •

$v\mathrm{.neighborhood}$ is the neighborhood set of $v$.

We also assume that a seed $v_{\mathrm{seed}}$ is given as the starting point
of the Algorithm 1. The communication time of Algorithm 1 is equivalent to the
total number of calls to message, where the vertex $v$ messages either a
vertex that hasn’t been visited or its parent $v\mathrm{.parent}$. We keep
track of the communication time through the variable $t$. The communication
time guarantees of Algorithm 1 is given below.

######  Proposition 1.

Let $n$ be the number of agents and
$T_{\mathrm{alg}}(\mathcal{G},v_{\mathrm{seed}})$ be the output of Algorithm 1
given a communication graph $\mathcal{G}$ and a seed vertex
$v_{\mathrm{seed}}\in\mathcal{V}$. The maximum communication time for any
undirected, connected $\mathcal{G}$ and seed $v_{\mathrm{seed}}$ is

$\max_{\mathcal{G},v_{\mathrm{seed}}}T_{\mathrm{alg}}(\mathcal{G},v_{\mathrm{seed}})=2n-2$
(8)

###### Proof.

Consider an arbitrary graph $\mathcal{G}$ with $n$ agents and a seed vertex
$v_{\mathrm{seed}}$. Let $\ell$ be the number of calls to message where a
vertex $v$ messages another unvisited vertex and $m$ be the number of calls to
message where a vertex $v$ messages its parent. It can be seen that Algorithm
1 will eventually visit all the vertices in the graph, so $\ell$ must equal
$n-1$. Additionally, since $v_{\mathrm{seed}}$ does not have a parent and
Algorithm 1 terminates if $v_{\mathrm{seed}}$ does not send a message to an
unvisited neighbor, $m\leq\ell=n-1$. Therefore for any $\mathcal{G}$ and
$v_{\mathrm{seed}}$ the communication time is bounded above by
$T_{\mathrm{alg}}(\mathcal{G},v_{\mathrm{seed}})=m+\ell=2n-2$. Furthermore, it
can be seen that for the star graph with $n$ vertices, $m=\ell=n-1$, and the
equality in Eq. (8) is shown. ∎

Thus the communication guarantees of Algorithm 1 is only off by a constant of
$2$ from the optimal communication guarantee of $2n-4$ from the best ordering
$\pi_{\mathrm{best}}$. We remark that this difference can be further reduced
if the termination condition is changed from ‘$v\mathrm{.parent}$ is not
empty’ to ‘$v\mathrm{.order}=n$’, where $n$ is the number of agents.

Algorithm 1 Distributed Near-Optimal Ordering

graph $\mathcal{G}$ and a vertex $v_{\mathrm{seed}}\in\mathcal{V}$

Output: time $t$

initialize the time $t\leftarrow 0$

init($v_{\mathrm{seed}}$, $\varnothing$, $\varnothing$, 1)

return $t$

procedure init($v$, $v_{\mathrm{par}}$, $\alpha$, $i$)

label $v$ as $\mathrm{done}$

update $v\mathrm{.order}\leftarrow i$ and $v\mathrm{.parent}\leftarrow
v_{\mathrm{par}}$

let $v$ compute $\tilde{a}_{i}$ from Eq. (2) given actions $\alpha$

update $v\mathrm{.actions}\leftarrow\alpha\cup\\{\tilde{a}_{i}\\}$

message($v$, $v\mathrm{.actions}$)

end procedure

procedure message($v$, $\alpha$)

update $v\mathrm{.actions}\leftarrow\alpha$

if exists $w$ in $v\mathrm{.neighborhood}$ not labeled $\mathrm{done}$ then

increment $t\leftarrow t+1$

init($w$, $v$, $\alpha$, $|\alpha|$+1)

else if $v\mathrm{.parent}$ is not empty then

increment $t\leftarrow t+1$

message($v\mathrm{.parent}$, $\alpha$)

end if

end procedure

###  III-D Directed Communication Graphs

In this section, we consider the communication time guarantees with respect to
the more general class of connected, directed graphs using different
orderings. Under the class of undirected graphs, there is a significant gap in
the communication time guarantees for the best $\pi_{\mathrm{best}}$ and the
worst $\pi_{\mathrm{worst}}$ orderings. Not surprisingly, when we relax to the
optimization problem
$\max_{\mathcal{G}_{\mathrm{dir}}}T_{\max}(\mathcal{G}_{\mathrm{dir}})$ over
the class of directed graphs, the worst case guarantees also increase.
However, when considering the optimization problem for the best ordering over
directed graphs
$\max_{\mathcal{G}_{\mathrm{dir}}}T_{\min}(\mathcal{G}_{\mathrm{dir}})$, we
have that the worst case guarantees are also of quadratic order. Therefore in
directed graphs, the gap between the performance guarantees under different
orderings is relatively small.

Figure 4: Example of a directed cycle graph, where the vertices are labeled
adversarially with $\pi_{\mathrm{worst}}$. Here, the $k$-hop communication
must cycle back to get to the next agent.

For the graph example in Figure 4 using the worst ordering
$\pi_{\mathrm{worst}}$, notice that to get from $i$ to $i+1$, every edge but
one in the directed graph must be traversed, resulting in a communication time
of $5\times 5$ for $6$ agents. For the graph example in Figure 5 using any
ordering $\pi$, the vertices labeled with $2$, $3$, and $4$ must be traversed
every time to reach the vertices labeled with $5$, $6$, $7$, $8$ in order,
starting from the vertex labeled $1$. Thus the communication time for the
graph under the best ordering is $4\times 4$ for $8$ agents. Extending these
constructions to $n$ agents, we arrive at the following lemma.

Figure 5: Example of a directed graph that has the worst communication
complexity for the best ordering $\pi_{\mathrm{best}}$. Here, the vertices in
the latter half must cycle back to get to the next labeled vertex.

######  Proposition 2.

Let $n\geq 3$ be the number of agents. The maximum communication time required
to complete the greedy algorithm in Eq. (2) for any directed, connected
communication graph $\mathcal{G}_{\mathrm{dir}}$ with the best and worst
ordering is

$\displaystyle\max_{\mathcal{G}_{\mathrm{dir}}}\
T_{\min}(\mathcal{G}_{\mathrm{dir}})$
$\displaystyle=\left\lfloor\frac{n}{2}\right\rfloor\cdot\left\lceil\frac{n}{2}\right\rceil,$
(9) $\displaystyle\max_{\mathcal{G}_{\mathrm{dir}}}\
T_{\max}(\mathcal{G}_{\mathrm{dir}})$ $\displaystyle=(n-1)^{2},$ (10)

where $\left\lfloor a\right\rfloor$ is largest integer smaller than $a$ and
$\left\lceil a\right\rceil$ is the smallest integer larger than $a$.

###### Proof.

Proof is found in the Appendix. ∎

##  IV Simulations

We analyze our theoretical results for the communication time guarantees
empirically through a simulation, presented in Figure 6 and Figure 7. The code
used to generate the simulations can be found in [37]. We use the model of
Erdos-Renyi networks [38], where each possible undirected pair of edges
$(i,j)$ has a probability $P\leq 1$ of existing, to generate a sample set of
possible graph structures. For Figure 6, we sample $200$ instances of Erdos-
Renyi networks with $6$ nodes and a probability parameter of $P=.3$. For each
graph, we calculate the communication time for the greedy algorithm using the
best ordering $\pi_{\mathrm{best}}$, the ordering given by Algorithm 1, and a
randomly assigned ordering. For Figure 7, we sample $300$ instances of Erdos-
Renyi networks with $40$ nodes and a probability parameter of $P=.05$. In
Figure 7, we calculate the communication time for only the ordering given by
Algorithm 1 and a randomly assigned ordering.

We observe in Figure 6 that indeed the best ordering $\pi_{\mathrm{best}}$
achieves the lowest distribution of communication times, centered closely to
$n=6$. The distribution of communication times of the ordering given in
Algorithm 1 is noticeably close to the one of $\pi_{\mathrm{best}}$, with
indeed no run-times over $2n=12$. The distribution of the communications using
random orderings does perform the worst with the largest spread. In Figure 7,
we compare communication times from the ordering from Algorithm 1 directly
with the random ordering, as computing the best ordering $\pi_{\mathrm{best}}$
is infeasible for large $n$. We see the same trends in Figure 6 reflected in a
more extreme fashion. The distribution of communication times using the
ordering of Algorithm 1 is still upper bounded by $2n=80$. However, the
distribution times of communication times using the random ordering is now
centered much higher with a larger spread as well. Therefore, we see
significant benefits from using the ordering from Algorithm 1 rather than the
naive approach of using random ordering.

Figure 6: We show the distribution over of communication times needed to
complete the greedy algorithm for $200$ instances of random graphs generated
by a Erdos-Renyi process with respect to the random ordering, the best
ordering $\pi_{\mathrm{best}}$, and the ordering from Algorithm 1. For the
graph parameters $n=6$ number of agents and $P=.3$ probability of an edge
existing, we see that $\pi_{\mathrm{best}}$ gives slightly lower average
communication times than the ordering from Algorithm 1, but both offer
significant improvements over the random ordering. Figure 7: We compare the
communication times under the random ordering to the times under the ordering
algorithm proposed in Algorithm 1. For the graph parameters $n=40$ number of
agents and $P=.05$ probability of an edge existing, we see a marked decrease
in the communication time from the random ordering to using the proposed
algorithm over a set of $300$ randomly generated graphs.

##  V Submodular Maximization

In this section, we discuss submodular maximization problems, which can be
modeled as multiagent decision problems. Consider a base set of elements $E$,
and let $a_{i}\subseteq E$, $\mathcal{A}_{i}\subseteq 2^{E}$, and
$a^{\varnothing}_{i}=\emptyset$. The objective function takes the form
$W(a)=f\left(\cup_{a_{i}\in a}a_{i}\right)$, where $f:2^{E}\to\mathbb{R}$ has
the following properties for any $A\subseteq B\subseteq E$:

  1. 1.

_Submodular_ : $f(A\cup\\{x\\})-f(A)\geq f(B\cup\\{x\\})-f(B)$ for all $x\in
E\setminus B$

  2. 2.

_Monotone_ : $f(A)\leq f(B)$

  3. 3.

_Normalized_ : $f(\emptyset)=0$

In this setting, it has been shown that the greedy algorithm that is
implemented in Algorithm 1 guarantees that
$W(\tilde{a})\geq(1/2)W(a^{\mathrm{opt}})$, where $\tilde{a}$ is defined in
Eq. (2).

###  V-A Comparison with Other Distributed Algorithms

As mentioned previously, much work has been done to develop other algorithms
to solve submodular maximization. For instance, [34] presents a similar
distributed algorithm, using a multilinear extension, and a distributed pipage
rounding technique. At each time step, each agent performs a calculation for
each action based on a sample of $K$ actions drawn from a probability
distribution. After $T$ time steps, the performance guarantee is
$(1-1/e)(1-(2d(\mathcal{G})n+n/2+1)(n/T))$ with probability at least
$1-2nTe^{-K/(8T^{2})}$. Thus, for high $T$ and $K=O(T^{2})$, there is a high
probability that the algorithm gives the $1-1/e$ guarantee. Using this
information, the algorithm could provide a $1/2$ guarantee only for $T\geq
4.78(2d(\mathcal{G})n^{2}+n^{2}/2+1)$, and only with high probability when
$K=O(T^{2})$.

The paper [35] describes a Jacobi-style algorithm, where at each time step
agent $i$ creates a strategy profile, i.e., a probability distribution across
each of its actions. Then, it chooses $K$ of those values to share with its
neighbors to propagate through the network. It was shown that the resulting
decision set approaches being within $1/2$ the optimal as the number of
iterations increases. It is only shown in the paper that the probability of
achieving the $1/2$ guarantee is $1-O(1/T)$ rather than an explicit time
expectation. However, the examples in the paper suggest that it may take
$T\geq n^{2}$ or more time steps to realize this.

In another example, [33] presents the Constraint-Distributed Continuous Greedy
(CDCG), a consensus-style algorithm, in which agent $i$ shares an $m$-vector
with all its neighbors at each time step, where $m$ is the number of actions
available to $i$. It is shown that the resulting decision set approaches being
within $1-1/e$ of the optimal as the number of iterations $T$ increases. The
error in the performance guarantee vanishes at a rate of $O(n^{5/2}/T)$, and
therefore, it may require $T\geq n^{5/2}$ time steps in order to reach an
acceptable error.

In each of the three methods listed above, each time step requires each agent
do perform some calculation for each of its actions. The time requirement for
each to reach an acceptable solution is expected to be greater than $2n-2$,
which is the number of time steps it takes to complete Algorithm 1. This
suggests that there is a tradeoff between performance guarantees and time
complexity: Algorithm 1 achieves the 1/2 guarantee quickly, but other
algorithms converge to a solution within $1-1/e$, but more slowly 222Although
we do not present a rigorous analysis here, we assert that Algorithm 1 also
requires less information exchange at each time step. This will be a topic of
future work..

##  VI Conclusion

In this work, we analyze the greedy algorithm in a multi-agent context. More
specifically, when the agents have limited information about the other agents
but can communicate with a subset of the other agents, we characterize the
effects of using different agent orderings on the communication time over the
network. First, we have shown that under the best ordering over any graph, the
communication time is $2n-4$, where $n$ is the number of agents. When
considering the worst ordering, we also show that this bound increases to
$\left\lfloor n^{2}/2\right\rfloor-1$ holding for any communication network.
We also provide an algorithm that can be used in a distributed fashion to
obtain a communication time guarantee of $2n-2$, which is a constant factor
away from the best communication guarantee. Furthermore, we verify these
results computationally in Section IV and describe the implications in the
context of submodular optimization problems in Section V. Future work is
comprised of extending this work to analyze the interplay between agent
orderings, the communication time guarantees, and possible performance
guarantees.

## References

  * [1] P. Zhao, S. Suryanarayanan, and M. G. Simoes, “An energy management system for building structures using a multi-agent decision-making control methodology,” IEEE Transactions on Industry Applications, vol. 49, no. 1, pp. 322–330, 2013.
  * [2] Y. Luo, K. Liu, and D. N. Davis, “A multi-agent decision support system for stock trading,” IEEE Network, vol. 16, pp. 20–27, jan 2002.
  * [3] M. T. Kahil, A. Dinar, and J. Albiac, “Cooperative water management and ecosystem protection under scarcity and drought in arid and semiarid regions,” Water Resources and Economics, vol. 13, pp. 60–74, 2016.
  * [4] K. Madani, “Game theory and water resources,” Journal of Hydrology, vol. 381, no. 3-4, pp. 225–238, 2010.
  * [5] L. Cruz-Piris, D. Rivera, S. Fernandez, and I. Marsa-Maestre, “Optimized sensor network and multi-agent decision support for smart traffic light management,” Sensors (Switzerland), vol. 18, no. 2, 2018.
  * [6] H. Bai and B. Zhao, “A survey on application of swarm intelligence computation to electric power system,” Proceedings of the World Congress on Intelligent Control and Automation (WCICA), vol. 2, no. 60421002, pp. 7587–7591, 2006.
  * [7] N. SinghPal and S. Sharma, “Robot Path Planning using Swarm Intelligence: A Survey,” International Journal of Computer Applications, vol. 83, no. 12, pp. 5–12, 2013.
  * [8] G. T. Nguyen and K. Kim, “A survey about consensus algorithms used in Blockchain,” Journal of Information Processing Systems, vol. 14, no. 1, pp. 101–128, 2018.
  * [9] S. Kar and J. M. Moura, “Distributed consensus algorithms in sensor networks: Quantized data and random link failures,” IEEE Transactions on Signal Processing, vol. 58, no. 3 PART 1, pp. 1383–1400, 2010.
  * [10] D. Ongaro and J. Ousterhout, “In search of an understandable consensus algorithm,” Proceedings of the 2014 USENIX Annual Technical Conference, USENIX ATC 2014, pp. 305–319, 2019.
  * [11] J. F. Nash et al., “Equilibrium points in n-person games,” Proceedings of the national academy of sciences, vol. 36, no. 1, pp. 48–49, 1950\.
  * [12] J. G. Wardrop, “Road paper. some theoretical aspects of road traffic research.,” Proceedings of the institution of civil engineers, vol. 1, no. 3, pp. 325–362, 1952.
  * [13] H. Von Stackelberg, Market structure and equilibrium.  Springer Science & Business Media, 2010.
  * [14] I. Gilboa and E. Zemel, “Nash and correlated equilibria: Some complexity considerations,” Games and Economic Behavior, vol. 1, no. 1, pp. 80–93, 1989.
  * [15] D. Monderer and L. S. Shapley, “Potential games,” Games and economic behavior, vol. 14, no. 1, pp. 124–143, 1996.
  * [16] B. Marzouki, O. Belkahla Driss, and K. Ghédira, “Multi Agent model based on Chemical Reaction Optimization with Greedy algorithm for Flexible Job shop Scheduling Problem,” Procedia Computer Science, vol. 112, pp. 81–90, 2017.
  * [17] B. Gharesifard and S. L. Smith, “On distributed submodular maximization with limited information,” American Control Conference, vol. 2016-July, pp. 1048–1053, 2016.
  * [18] A. Krause, A. Singh, and C. Guestrin, “Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies,” Journal of Machine Learning Research, vol. 9, pp. 235–284, 2008.
  * [19] A. Badanidiyuru, B. Mirzasoleiman, A. Karbasi, and A. Krause, “Streaming submodular maximization: Massive data summarization on the fly,” in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 671–680, 2014.
  * [20] H. Lin and J. Bilmes, “A class of submodular functions for document summarization,” in Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, vol. 1, pp. 510–520, 2011.
  * [21] A. Singh, W. Kaiser, M. Batalin, A. Krause, and C. Guestrin, “Efficient planning of informative paths for multiple robots,” in International Joint Conference on Artificial Intelligence, pp. 2204–2211, 2007.
  * [22] M. Corah and N. Michael, “Distributed matroid-constrained submodular maximization for multi-robot exploration: theory and practice,” Autonomous Robots, vol. 43, no. 2, pp. 485–501, 2019.
  * [23] G. Arslan, J. R. Marden, and J. S. Shamma, “Autonomous vehicle-target assignment: a game-theoretical formulation,” Journal of Dynamic Systems, Measurement and Control, Transactions of the ASME, vol. 129, no. 5, pp. 584–596, 2007.
  * [24] M. Gomez-Rodriguez, J. Leskovec, and A. Krause, “Inferring networks of diffusion and influence,” ACM Transactions on Knowledge Discovery from Data, vol. 5, no. 4, 2012.
  * [25] G. Kim, E. P. Xing, L. Fei-Fei, and T. Kanade, “Distributed cosegmentation via submodular optimization on anisotropic diffusion,” Proceedings of the IEEE International Conference on Computer Vision, pp. 169–176, 2011.
  * [26] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. Vanbriesen, and N. Glance, “Cost-effective outbreak detection in networks,” in ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 420–429, 2007.
  * [27] A. Clark and R. Poovendran, “A submodular optimization framework for leader selection in linear multi-agent systems,” in IEEE Conference on Decision and Control, pp. 3614–3621, IEEE, 2011.
  * [28] 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.
  * [29] G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, “Maximizing a monotone submodular function subject to a matroid constraint,” SIAM Journal on Computing, vol. 40, no. 6, pp. 1740–1766, 2011.
  * [30] Y. Filmus and J. Ward, “The power of local search: maximum coverage over a matroid,” in Symposium on Theoretical Aspects of Computer Science, pp. 601–612, LIPIcs, 2012.
  * [31] U. Feige, “A threshold of ln n for approximating set cover,” Journal of the ACM, vol. 45, no. 4, pp. 634–652, 1998.
  * [32] B. Mirzasoleiman, A. Karbasi, R. Sarkar, and A. Krause, “Distributed submodular maximization,” Journal of Machine Learning Research, vol. 17, no. 1, pp. 8330–8373, 2016.
  * [33] A. Robey, A. Adibi, B. Schlotfeldt, G. J. Pappas, and H. Hassani, “Optimal algorithms for submodular maximization with distributed constraints,” arXiv, vol. xxx, pp. 1–20, 2019.
  * [34] N. Rezazadeh and S. S. Kia, “Distributed strategy selection: A submodular set function maximization approach,” arXiv preprint arXiv:2107.14371, 2021\.
  * [35] B. Du, K. Qian, C. Claudel, and D. Sun, “Jacobi-style iteration for distributed submodular maximization,” arXiv preprint arXiv:2010.14082, 2020\.
  * [36] D. Grimsman, M. S. Ali, J. P. Hespanha, and J. R. Marden, “Impact of information in greedy submodular maximization,” in 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp. 2900–2905, IEEE, 2017.
  * [37] R. Konda, “Kondaacc2021.” https://github.com/rohit-konda/KondaACC2021.git, 2021.
  * [38] P. Erdos, A. Rényi, et al., “On the evolution of random graphs,” Publ. Math. Inst. Hung. Acad. Sci, vol. 5, no. 1, pp. 17–60, 1960.
  * [39] L. Bulteau, S. Giraudo, and S. Vialette, “Disorders and Permutations,” in 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) (P. Gawrychowski and T. Starikovskaya, eds.), vol. 191 of Leibniz International Proceedings in Informatics (LIPIcs), (Dagstuhl, Germany), pp. 11:1–11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021\.

###### Proof of Theorem 1.

We first show the equality in Eq. (6). For a given graph $\mathcal{G}$ and the
optimal ordering $\pi_{\mathrm{best}}$, we claim that the communication time
is equal to

$T_{\min}(\mathcal{G})=|\gamma_{\min}|,$ (11)

where $\gamma_{\min}$ is a minimum spanning walk of $\mathcal{G}$. Note that
for any given ordering $\pi$, the communication time for $T(\mathcal{G},\pi)$
is given in Eq. (5). Let $p_{i\to i+1}^{*}$ be the shortest path from $i$ to
$i+1$. The walk $\gamma_{\mathrm{cat}}=p^{*}_{1\to 2}p^{*}_{2\to 3}\dots
p^{*}_{n-1\to n}$ is defined as the concatenation of the shortest paths from
$1$ to $n$ with the duplicate vertices from $p_{i\to i+1}^{*}$ and $p_{i+1\to
i+2}^{*}$ removed. Then according to Eq. (5), we have that
$T(\mathcal{G},\pi)=|\gamma_{\mathrm{cat}}|$. We note that since $\pi^{-1}(i)$
and $\pi^{-1}(i+1)$ are in $p_{i\to i+1}^{*}$, then $\gamma_{\mathrm{cat}}$ is
a spanning walk and thus $|\gamma_{\mathrm{cat}}|\geq|\gamma_{\min}|$. Since
the ordering $\pi$ was arbitrary and
$T(\mathcal{G},\pi)=|\gamma_{\mathrm{cat}}|$, we have that
$\min_{\pi}T(\mathcal{G},\pi)\geq|\gamma_{\min}|$. This expression actually
holds with equality, as $\pi_{\mathrm{best}}$ can be taken as the order that
the vertices first appear in $\gamma_{\min}$, matching Eq. (11) and the claim
is shown.

Notice that a spanning walk for the graph
$\mathcal{G}_{1}=(\mathcal{V}_{1},\mathcal{E}_{1})$ is also a spanning walk
for the graph $\mathcal{G}_{2}=(\mathcal{V}_{1},\mathcal{E}_{1}\cup\\{e\\})$
with the added edge $e$. Then the length of the minimal spanning walk
$|\gamma^{1}_{\min}|$ for $\mathcal{G}_{1}$ must be at least
$|\gamma^{2}_{\min}|$ for $\mathcal{G}_{2}$. Thus
$T_{\min}(\mathcal{G}_{1})\geq T_{\min}(\mathcal{G}_{2})$, and to calculate
$\max_{\mathcal{G}}T_{\min}(\mathcal{G})$, it is sufficient to restrict to the
class of tree graphs, which is the class of connected graphs with the least
number of edges.

Consider any spanning walk $\gamma$ on the tree graph
$\mathcal{G}_{\mathcal{T}}=(\mathcal{V}_{\mathcal{T}},\mathcal{E}_{\mathcal{T}})$
starting at the vertex $v_{1}$ and ending at the vertex $v_{n}$. Let
$\mathcal{E}^{p}_{\mathcal{T}}\subset\mathcal{E}_{\mathcal{T}}$ be the set of
edges that belong to the unique path $p$ between $v_{1}$ and $v_{n}$. We claim
that $\gamma$ must visit each edge $e\in\mathcal{E}_{\mathcal{T}}$ at least
once and every edge
$e\in\mathcal{E}_{\mathcal{T}}\setminus\mathcal{E}_{\mathcal{T}}^{p}$ at least
twice. If there exist an edge $\hat{e}\in\mathcal{E}_{\mathcal{T}}$ such that
$\hat{e}\notin\gamma$, then since $\gamma$ is a spanning walk, then the graph
$\hat{\mathcal{G}}=(\mathcal{V}_{\mathcal{T}},\mathcal{E}_{\mathcal{T}}\setminus\\{\hat{e}\\})$
must also be a connected graph. But this is a contradiction, since
$\mathcal{G}_{\mathcal{T}}$ is assumed to be a tree graph. If an edge
$\bar{e}\in\mathcal{E}_{\mathcal{T}}\setminus\mathcal{E}_{\mathcal{T}}^{p}$ is
removed from $\mathcal{G}_{\mathcal{T}}$, there must be two nonempty
components, one containing both $v_{1}$ and $v_{n}$ and another containing
neither. Thus if $\bar{e}$ is only traversed once in the walk, it must hop
from $v_{1}$ from the first component to the other component once. However,
the spanning walk $\gamma$ cannot come back to the first component again,
contradicting our definition of $v_{n}$ and the claim is shown.

Therefore for a tree graph $\mathcal{G}_{\mathcal{T}}$ and any spanning walk
$\gamma$, we have that $|\gamma|\geq
2|\mathcal{E}_{\mathcal{T}}|-|\mathcal{E}^{p}_{\mathcal{T}}|$. Moreover there
exists a spanning walk that has the length equal to
$|\gamma|=2|\mathcal{E}_{\mathcal{T}}|-|\mathcal{E}^{p}_{\mathcal{T}}|$ in
which the vertices that are not along the path $p$ from $v_{1}$ to $v_{n}$ are
reached through a cycle that visits each edge not part of $p$ twice. Thus, the
length of the minimum spanning walk can be written as the following
optimization problem. Here, $\mathrm{diam}(\mathcal{G}_{\mathcal{T}})$ is the
diameter of the graph $\mathcal{G}_{\mathcal{T}}$ and
$\Gamma_{\mathcal{G}_{\mathcal{T}}}$ is the set of spanning walks.

$\displaystyle|\gamma_{\min}|$
$\displaystyle=\min_{\gamma\in\Gamma_{\mathcal{G}_{\mathcal{T}}}}|\gamma|$
$\displaystyle=2|\mathcal{E}_{\mathcal{T}}|-\max_{v_{1},v_{n}}|\mathcal{E}^{p}_{\mathcal{T}}|=2(n-1)-\mathrm{diam}(\mathcal{G}_{\mathcal{T}}).$

For a given tree graph $\mathcal{G}_{\mathcal{T}}$ with more than $n\geq 3$
vertices, the diameter must be greater than
$\mathrm{diam}(\mathcal{G}_{\mathcal{T}})\geq 2$. Therefore, the length of the
minimum spanning walk must be less than $2n-4$ for any tree graph
$\mathcal{G}_{\mathcal{T}}$. Moreover, the star graph is the tree graph with a
graph diameter of $2$, so $\max_{\mathcal{G}}T_{\min}(\mathcal{G})=2n-4$.

Now, we show the equality in Eq. (7). We claim that the connected, undirected
graph that attains $\max_{\mathcal{G}}T_{\max}(\mathcal{G})$ is the line
graph. We observe, similarly as before, that if a path $p_{i\to i+1}$ exists
from $i$ to $i+1$ for the graph
$\mathcal{G}_{1}=(\mathcal{V}_{1},\mathcal{E}_{1})$, then it must also exist
for the graph $\mathcal{G}_{2}=(\mathcal{V}_{1},\mathcal{E}_{1}\cup\\{e\\})$
with the added edge $e$ for any $1\leq i\leq n-1$. As the run-time in Eq. (5)
is defined by the shortest path from $i$ to $i+1$, the run-time for
$\mathcal{G}_{2}$ is lower bounded by $T(\mathcal{G}_{1},\pi)\geq
T(\mathcal{G}_{2},\pi)$. Thus, we can assume that worst-case graph is a tree
graph without loss of generality. If $\mathcal{G}_{\mathcal{T}}$ is a tree
graph, then the path $p_{i\to i+1}$ from $\pi^{-1}(i)$ to $\pi^{-1}(i+1)$ is
unique.

We now claim that for any tree graph $\mathcal{G}_{\mathcal{T}}$ for some
ordering $\pi$, there exists an ordering $\pi_{L}$ with the line graph that
achieves at least the same run-time. If $\mathcal{G}_{\mathcal{T}}$ is a tree
graph that is not the line graph, there exists at least one vertex $v_{c}$ of
$\mathcal{G}_{\mathcal{T}}$ with degree $d\geq 3$. Let $\\{v_{j}\\}_{1\leq
j\leq d}$ be the vertices in the neighborhood of $v_{c}$. Also, let
$\mathcal{T}_{j}\subset\mathcal{G}_{\mathcal{T}}$ be the corresponding tree
component containing $v_{j}$ that results from removing the edge
$(v_{j},v_{c})$. Let $v_{j}^{\mathrm{d}}\in\mathcal{T}_{j}$ be the vertex
farthest away from $v_{j}$ and $\mathrm{d}_{j}$ be the distance from $v_{j}$
to $v_{j}^{\mathrm{d}}$. Additionally let
$H=\\{(\pi^{-1}(i),\pi^{-1}(i+1))\\}_{i<n}$ and

$H^{j}=\\{(v,v^{\prime})\in
H:v\in\mathcal{T}_{1},v^{\prime}\in\mathcal{T}_{j}\text{ or
}v\in\mathcal{T}_{j},v^{\prime}\in\mathcal{T}_{1}\\}.$

We also denote that $(v,v_{c})$ and $(v_{c},v)$ are included in $H^{1}$.
Consider the modified graph $\mathcal{G}^{J}_{\mathcal{T}}$, where the edge
$(v_{j=1},v_{c})$ is replaced with $(v_{j=1},v_{j=J}^{\mathrm{d}})$ for some
$1<J\leq d$. Then the communication time for the graph
$\mathcal{G}^{J}_{\mathcal{T}}$ is

$\displaystyle T(\mathcal{G}^{J}_{\mathcal{T}},\pi)$
$\displaystyle=\sum_{(v,v^{\prime})\in
H}p^{\mathcal{G}^{J}_{\mathcal{T}}}_{v,v^{\prime}}=\sum_{j\geq
1}\sum_{(v,v^{\prime})\in
H^{j}}p^{\mathcal{G}^{J}_{\mathcal{T}}}_{v,v^{\prime}}$
$\displaystyle\geq\sum_{(v,v^{\prime})\in
H}p^{\mathcal{G}_{\mathcal{T}}}_{v,v^{\prime}}+\sum_{j>1}\sum_{(v,v^{\prime})\in
H^{j}}\mathrm{d}_{J}-2\sum_{(v,v^{\prime})\in H^{J}}\mathrm{d}_{J}$
$\displaystyle\geq T(\mathcal{G},\pi)\text{ for some }J.$

Here, $p^{\mathcal{G}^{J}_{\mathcal{T}}}_{v,v^{\prime}}$ refers to the path
from $v$ to $v^{\prime}$ in $\mathcal{G}^{J}_{\mathcal{T}}$. The first
equality comes from rewriting Eq. (5) using $H^{j}$. The last inequality comes
from the fact that the degree $d\geq 3$ and that

$\max_{J>1}\Big{\\{}\sum_{j>1}\sum_{(v,v^{\prime})\in
H^{j}}\mathrm{d}_{J}-2\sum_{(v,v^{\prime})\in
H^{J}}\mathrm{d}_{J}\Big{\\}}\geq 0.$

By applying a similar argument inductively for every tree $\mathcal{T}_{j}$
for $j\leq d-2$ and for every vertex $v_{c}$ with degree more than $3$, we
have the claim.

The worst ordering for the line graph and the corresponding guarantee of
$\left\lfloor n^{2}/2\right\rfloor-1$ is given by the work in [39, Theorem 8].
We give a sketch of the proof for completeness. Let $v_{i}$ be the $i$’th
vertex in the line graph. Consider any ordering $\pi$. If $\pi$ has any of the
following properties, then there must exist another ordering $\pi^{\prime}$
that has a larger communication time that results from swapping positions of
some $\pi(v)$ and $\pi(v^{\prime})$.

  1. 1.

For some $1<i<n$, either $(\pi(v_{1}),\pi(v_{i}),\pi(v_{i+1}))$ or
$(\pi(v_{i}),\pi(v_{i+1}),\pi(v_{n}))$ is monotonic.

  2. 2.

For some $i,j<n$, there are two pairs $(\pi(v_{i}),\pi(v_{i+1}))$ and
$(\pi(v_{j}),\pi(v_{j+1}))$ that are separated by some threshold
$1\leq\ell\leq n$.

  3. 3.

There is a triple $(\pi(v_{i}),\pi(v_{i+1}),\pi(v_{i+2}))$ that is monotonic.

If an ordering $\pi$ does not have any of the previous three properties, then
it must have all even indexed vertices $\\{v_{i}\\}_{i\ \mathrm{even}}$ below
the threshold $\left\lfloor n/2\right\rfloor$ and all odd indexed vertices
$\\{v_{i}\\}_{i\ \mathrm{odd}}$ above the threshold with the middle vertices
corresponding to the endpoints $1$ and $n$. An example of this configuration
is shown in Figure 2. It can be seen that the line graph with this
configuration has a $T(\mathcal{G},\pi)=\left\lfloor n^{2}/2\right\rfloor-1$.
∎

###### Proof of Proposition 2.

First, extending the directed cycle graph $\mathcal{C}_{n}$ in Figure 4 to $n$
agents with the given worst case labeling $\pi_{\rm{worst}}$ produces a lower
bound

$\max_{\mathcal{G}_{\mathrm{dir}}}T_{\max}(\mathcal{G}_{\mathrm{dir}})\geq
T(\mathcal{C}_{n},\pi_{\rm{worst}})=(n-1)^{2}.$

The upper bound
$\max_{\mathcal{G}_{\mathrm{dir}}}T_{\max}(\mathcal{G}_{\mathrm{dir}})\leq(n-1)^{2}$
also holds, since for any graph $\mathcal{G}$ and ordering $\pi$, the
communication time must satisfy $T(\mathcal{G},\pi)\leq\sum_{i=1}^{n-1}(n-1)$
as the length of any path in the graph cannot be greater than $n-1$.

Now we show that
$\max_{\mathcal{G}_{\mathrm{dir}}}T_{\min}(\mathcal{G}_{\mathrm{dir}})\geq\left\lfloor\frac{n}{2}\right\rfloor\cdot\left\lceil\frac{n}{2}\right\rceil$
by extending the graph construction, denoted $\mathcal{D}_{n}$, in Figure 5 to
$n$ agents. Formally, the edge set of $\mathcal{D}_{n}$ includes
$(v_{j},v_{j+1})$ for every $1\leq j\leq\left\lceil n/2\right\rceil-2$ as well
as the edges $(v_{\left\lceil n/2\right\rceil-1},v_{j})$ and $(v_{j},v_{1})$
for every $\left\lceil n/2\right\rceil\leq j\leq n$. We confirm that
$T(\mathcal{D}_{n},\pi_{\rm{best}})=\left\lfloor\frac{n}{2}\right\rfloor\cdot\left\lceil\frac{n}{2}\right\rceil$
for the best order. Consider any ordering $\pi$ and without loss of
generality, assume that $\pi(v_{j})<\pi(v_{j+1})$ for all $\left\lceil
n/2\right\rceil\leq j\leq n$. Thus the communication time has to be lower
bounded by

$T(\mathcal{D}_{n},\pi)\geq\sum_{j\geq\left\lceil
n/2\right\rceil}^{n-1}\min_{p_{v_{j}\to v_{j+1}}}|p_{v_{j}\to
v_{j+1}}|-1\geq\left\lfloor\frac{n}{2}\right\rfloor\cdot\left\lceil\frac{n}{2}\right\rceil,$

as $(v_{j},v_{1},v_{2},\dots,v_{\left\lceil n/2\right\rceil-1},v_{j+1})$ is
the unique path $p_{v_{j}\to v_{j+1}}$ from $v_{j}$ to $v_{j+1}$ with a length
of $\left\lceil n/2\right\rceil+1$. Observe that the ordering $\pi(v_{j})=j+1$
for $1\leq j\leq n-1$ and $\pi(v_{n})=1$ achieves this communication time and
so the lower bound is indeed tight.

Now we show that for any given directed graph $\mathcal{G}$, there exists an
ordering $\hat{\pi}$ in which
$T(\mathcal{G},\hat{\pi})\leq\left\lfloor\frac{n}{2}\right\rfloor\cdot\left\lceil\frac{n}{2}\right\rceil$.
Let $p_{\rm{long}}=(v_{1},\dots,v_{l})$ be the longest path of the graph,
where $l=|p_{\rm{long}}|$. If $l=n$, then $p_{\rm{long}}$ is a spanning walk
on the graph and the ordering $\pi(v_{j})=j$ along the longest path results in
a communication time of
$T(\mathcal{G},\hat{\pi})=n-1\leq\left\lfloor\frac{n}{2}\right\rfloor\cdot\left\lceil\frac{n}{2}\right\rceil$.
Otherwise, since $\mathcal{G}$ is assumed to be strongly connected there
exists a vertex $v_{J}$ in $p_{\rm{long}}$ that is adjacent to another vertex
$\bar{v}$ that is not in the path $p_{\rm{long}}$. We construct the ordering
$\hat{\pi}$ as follows. The vertices in $p_{\rm{long}}$ are labeled as
$\hat{\pi}(v_{j})=j$ for $j\leq J$ and $\hat{\pi}(v_{j})=n-l+j$ for $j>J$. The
vertex $\bar{v}$ is labeled with $\hat{\pi}(\bar{v})=J+1$ and the labels for
the rest of the vertices in $\mathcal{G}$ can be arbitrarily selected from
$\\{J+2,\dots,n-l+J\\}$. The resulting communication time along this order,
using Eq. (8), is

$\displaystyle T(\mathcal{G},\hat{\pi})$
$\displaystyle=\sum_{i=1}^{n-1}\Big{(}\min_{p_{i\to i+1}}|p_{i\to
i+1}|-1\Big{)}$ $\displaystyle=(l-1)+\sum_{i=J+1}^{n-l+J}\Big{(}\min_{p_{i\to
i+1}}|p_{i\to i+1}|-1\Big{)},$

as the vertices $\hat{\pi}^{-1}(i)$ and $\hat{\pi}^{-1}(i+1)$ are adjacent to
each other if $1\leq i\leq J$ or $n-l+J+1\leq i\leq n-1$ according to the
prescribed order $\hat{\pi}$. For any $i\in\mathcal{I}$, we observe that
$\min_{p_{i\to i+1}}|p_{i\to i+1}|\leq l$ by definition of $p_{\rm{long}}$.
Now we have the upper bound

$T(\mathcal{G},\hat{\pi})\leq(l-1)+(n-l)(l-1)\leq\left\lfloor\frac{n}{2}\right\rfloor\cdot\left\lceil\frac{n}{2}\right\rceil,$

where the expression achieves the maximum at $l=\left\lceil
n/2\right\rceil+1$. Thus, since $\mathcal{G}$ was arbitrary chosen,

$\max_{\mathcal{G}_{\mathrm{dir}}}T_{\min}(\mathcal{G}_{\mathrm{dir}})=\max_{\mathcal{G}_{\mathrm{dir}}}T(\mathcal{G},\hat{\pi})\leq\left\lfloor\frac{n}{2}\right\rfloor\cdot\left\lceil\frac{n}{2}\right\rceil,$

and thus we have shown equality. ∎