Multiagent Maximum Coverage Problems: The Trade-off Between Anarchy and Stability
For system operators designing distributed systems, this work provides a theoretical framework to navigate the trade-off between worst-case and best-case equilibrium efficiency.
The paper characterizes a fundamental trade-off between the price of anarchy and price of stability in multiagent covering games, showing that optimizing one metric comes at the expense of the other, and demonstrates how incorporating system-level information about the worst-performing agent can improve both metrics.
The price of anarchy and price of stability are three 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 stability characterizes the quality of the best-performing equilibria. While much of the literature focuses on these metrics from an analysis perspective, in this work we consider these performance metrics from a design perspective. Specifically, we focus on the setting where a system operator is tasked with designing local utility functions to optimize these performance metrics in a class of games termed covering games. Our main result characterizes a fundamental trade-off between the price of anarchy and price of stability in the form of a fully explicit Pareto frontier. Within this setup, optimizing the price of anarchy comes directly at the expense of the price of stability (and vice versa). Our second results 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 system's performance. This valuable piece of system-level information pertains to the performance of worst performing agent in the system.