The Impact of Message Passing in Agent-Based Submodular Maximization

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.