On Distributed Submodular Maximization with Limited Information

This paper considers a class of distributed sub-modular maximization problems in which each agent must choose a single strategy from its strategy set. The objective is to maximize a submodular function of the strategies chosen by each agent. However, each agent has only partial information on the choices of other agents when making its decision. The main objective of this paper is to investigate how the limitation of information about the strategy sets or actions of other agents affects the performance when agents make choices according to a local greedy algorithm. In particular, we provide lower bounds on the performance of greedy algorithms for submodular maximization, which depend on the clique number of the graph. We also characterize graph-theoretic upper bounds in terms of the chromatic number of the graph. Finally, we demonstrate how certain graph properties limit the performance of the greedy algorithm.