2017/10/03 by Ramaswamy, Vinod, Paccagnan, Dario, Marden, Jason R.
#Combinatorics (math.CO) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Multiagent Systems (cs.MA) #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · doi:10.48550/arxiv.1710.01409
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.