The Importance of System-Level Information in Multiagent Systems Design: Cardinality and Covering Problems
For system operators designing distributed control for submodular resource allocation problems, this work provides a method to handle uncertain system-level information without performance loss.
This paper identifies a risk-reward tradeoff in multiagent system design when a key piece of information (cardinality) is uncertain, and proposes a distributed algorithm that learns the cardinality online, achieving performance on par with or better than the optimal design with known cardinality.
A fundamental challenge in multiagent systems is to design local control algorithms to ensure a desirable collective behaviour. The information available to the agents, gathered either through communication or sensing, naturally restricts the achievable performance. Hence, it is fundamental to identify what piece of information is valuable and can be exploited to design control laws with enhanced performance guarantees. This paper studies the case when such information is uncertain or inaccessible for a class of submodular resource allocation problems termed covering problems. In the first part of this work we pinpoint a fundamental risk-reward tradeoff faced by the system operator when conditioning the control design on a valuable but uncertain piece of information, which we refer to as the cardinality, that represents the maximum number of agents that can simultaneously select any given resource. Building on this analysis, we propose a distributed algorithm that allows agents to learn the cardinality while adjusting their behaviour over time. This algorithm is proved to perform on par or better to the optimal design obtained when the exact cardinality is known a priori.