A fundamental challenge in multiagent systems is to design local control algorithms to ensure a desirable collective behavior. 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 paper, 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 behavior 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 .
@cite_15: We propose approximation algorithms under game-theoretic considerations. We indroduce and study the general covering problem which is a natural generalization of the well-studied max-n -cover problem. In the general covering problem, we are given a universal set of weighted elements E and n collections of subsets of the elements. The task is to choose one subset from each collection such that the total weight of their union is as large as possible. In our game-theoretic setting, the choice in each collection is made by an independent player. For covering an element, the players receive a payoff defined by a non-increasing utility sharing function. This function defines the fraction that each covering player receives from the weight of the elements. We show how to construct a utility sharing function such that every Nash Equilibrium approximates the optimal solution by a factor of @math . We also prove that any sequence of unilateral improving steps is polynomially bounded. This gives rise to a polynomial-time local search approximation algorithm whose approximation ratio is best possible.
@cite_7: How does the control architecture of a multiagent system impact the achievable performance guarantees? In this paper we answer this question relative to a class of resource allocation problems, termed multiagent set covering problems. More specifically, we demonstrate how the degree of information available to each agent imposes constraints on the achievable efficiency guarantees associated with the emergent collective behavior. We measure these efficiency guarantees using the well-known metrics of price of anarchy and price of stability, which seek to bound the performance of the worst and best performing equilibria, respectively. Our first result demonstrates that when agents only know local information about the resources they can select, a system operator is forced to manage an inherent trade-off between the price of anarchy and price of stability, i.e., improving the quality of the worst equilibria comes at the expenses of the best equilibria. Our second result demonstrates that a system operator can move well beyond this price of anarchy price of stability frontier by designing a communication protocol that provides agents with a limited amount of system-level information beyond these local quantities.
The problem of designing a distribution rule so as to maximise @math has been studied in @cite_15 and @cite_7 . Both works impose a natural constraint on the admissible @math , requiring @math and @math to be non-increasing. The optimal distribution rule is explicitly derived in the former work, while the latter shows how @math is fully characterised by a single scalar quantity @math defined in , measuring how fast the distribution rule @math decreases. We intend to build upon these results, which are summarised in the following proposition. Given @math and a distribution rule @math , we define j k-1 j f(j)-f(j+1),(k-1) f(k) ,.