  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 optimal 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.
