Multiagent Maximum Coverage Problems: The Tradeoff Between Anarchy and Stability

doi:10.1109/TAC.2021.3069809

2022-04-01

Vinod Ramaswamy

Dario Paccagnan

Jason R. Marden *

DOI：10.1109/TAC.2021.3069809

原文链接

查看原文

摘要

En 中文

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.

Keyword:

Stability analysis

Games

Linear programming

Measurement

Decision making

Resource management

Multi-agent systems

Games

multiagent systems

optimization destributed algoritms