  The maximization of submodular functions is an NP-Hard problem for certain
subclasses of functions, for which a simple greedy algorithm has been shown to
guarantee a solution whose quality is within 1/2 of the optimal. When this
algorithm is implemented in a distributed way, agents sequentially make
decisions based on the decisions of all previous agents. This work explores how
limited access to the decisions of previous agents affects the quality of the
solution of the greedy algorithm. Specifically, we provide tight upper and
lower bounds on how well the algorithm performs, as a function of the
information available to each agent. Intuitively, the results show that
performance roughly degrades proportionally to the size of the largest group of
agents which make decisions independently. Additionally, we consider the case
where a system designer is given a set of agents and a global limit on the
amount of information that can be accessed. Our results show that the best
designs partition the agents into equally-sized sets and allow agents to access
the decisions of all previous agents within the same set.
