When Smoothness is Not Enough: Toward Exact Quantification and Optimization of the Price-of-Anarchy
For researchers designing distributed algorithms via game theory, this work provides a more precise tool to quantify and optimize equilibrium efficiency, though it is an incremental improvement over the traditional smoothness framework.
The paper introduces generalized smoothness to obtain tighter efficiency bounds for the price-of-anarchy in multiagent systems, and demonstrates its application to local resource allocation games, enabling optimization of equilibrium performance via a tractable linear program.
Today's multiagent systems have grown too complex to rely on centralized controllers, prompting increasing interest in the design of distributed algorithms. In this respect, game theory has emerged as a valuable tool to complement more traditional techniques. The fundamental idea behind this approach is the assignment of agents' local cost functions, such that their selfish minimization attains, or is provably close to, the global objective. Any algorithm capable of computing an equilibrium of the corresponding game inherits an approximation ratio that is, in the worst case, equal to its price-of-anarchy. Therefore, a successful application of the game design approach hinges on the possibility to quantify and optimize the equilibrium performance. Toward this end, we introduce the notion of generalized smoothness, and show that the resulting efficiency bounds are significantly tighter compared to those obtained using the traditional smoothness approach. Leveraging this newly-introduced notion, we quantify the equilibrium performance for the class of local resource allocation games. Finally, we show how the agents' local decision rules can be designed in order to optimize the efficiency of the corresponding equilibria, by means of a tractable linear program.