Title: The Importance of System-Level Information in Multiagent Systems Design: Cardinality and Covering Problems,
Abstract: 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.