4.7 Article

Multiagent Maximum Coverage Problems: The Tradeoff Between Anarchy and Stability

Journal

IEEE TRANSACTIONS ON AUTOMATIC CONTROL
Volume 67, Issue 4, Pages 1698-1712

Publisher

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TAC.2021.3069809

Keywords

Stability analysis; Games; Linear programming; Measurement; Decision making; Resource management; Multi-agent systems; Games; multiagent systems; optimization destributed algoritms

Funding

  1. SNSF [P2EZP2-181618]
  2. ONR [N00014-20-1-2359]
  3. AFOSR [FA9550-20-1-0054]
  4. NSF [ECCS-1351866]

Ask authors/readers for more resources

This article examines the application of the price of anarchy and price of stability performance metrics in designing distributed systems. The study reveals a tradeoff between these metrics, where optimizing one comes at the expense of the other. The article also proposes incorporating system-level information to enhance the efficiency guarantees of equilibrium points.
The price of anarchy and price of stability are two well-studied performance metrics that seek to characterize the inefficiency of equilibria in distributed systems. The distinction between these two performance metrics centers on the equilibria that they focus on: the price of anarchy characterizes the quality of the worst-performing equilibria, while the price of the stability characterizes the quality of the best-performing equilibria. While much of the literature focuses on these metrics from an analysis perspective, in this article, we consider these performance metrics from a design perspective. Specifically, we focus on the setting where a system operator is tasked with designing local agent utility functions to optimize these performance metrics in a class of games termed covering games. Our main result characterizes a fundamental tradeoff between the price of anarchy and price of the stability in the form of a fully explicit Pareto frontier. Within this setup, we observe that optimizing the price of anarchy comes directly at the expense of the price of stability (and vice versa). Our second result demonstrates how a system operator could incorporate an additional piece of system-level information into the design of the agents' utility functions to breach these limitations and improve the efficiency guarantees associated with the resulting equilibria. Informally, this valuable piece of system-level information pertains to the value of the largest uncovered resource in our covering game.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available