When smoothness is not enough: toward exact quantification and optimization of the price-of-anarchy
File(s)
Accepted version
Author(s)
Chandan, Rahul
Paccagnan, Dario
Marden, Jason R
Type
Conference Paper
Abstract
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.
Date Issued
2020-03-01
Date Acceptance
2020-03-01
Citation
2019 IEEE 58th Conference on Decision and Control (CDC), 2020, pp.1-6
Publisher
IEEE
Start Page
1
End Page
6
Journal / Book Title
2019 IEEE 58th Conference on Decision and Control (CDC)
Copyright Statement
© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Identifier
https://ieeexplore.ieee.org/document/9030121
Source
2019 IEEE 58th Conference on Decision and Control (CDC)
Publication Status
Published
Start Date
2019-12-11
Finish Date
2019-12-13
Coverage Spatial
Nice, France
Date Publish Online
2020-03-12