Optimal price of anarchy in cost-sharing games
File(s)
Accepted version
Author(s)
Chandan, Rahul
Paccagnan, Dario
Marden, Jason R
Type
Conference Paper
Abstract
The design of distributed algorithms is central to the study of multiagent systems control. In this paper, we consider a class of combinatorial cost-minimization problems and propose a framework for designing distributed algorithms with a priori performance guarantees that are near-optimal. We approach this problem from a game-theoretic perspective, assigning agents cost functions such that the equilibrium efficiency (price of anarchy) is optimized. Once agents' cost functions have been specified, any algorithm capable of computing a Nash equilibrium of the system inherits a performance guarantee matching the price of anarchy. Towards this goal, we formulate the problem of computing the price of anarchy as a tractable linear program. We then present a framework for designing agents' local cost functions in order to optimize for the worst-case equilibrium efficiency. Finally, we investigate the implications of our findings when this framework is applied to systems with convex, nondecreasing costs.
Date Issued
2019-08-29
Date Acceptance
2019-08-01
Citation
2019 American Control Conference (ACC), 2019, pp.2277-2282
Publisher
IEEE
Start Page
2277
End Page
2282
Journal / Book Title
2019 American Control Conference (ACC)
Copyright Statement
© 2019 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/8815011
Source
2019 American Control Conference (ACC)
Publication Status
Published
Start Date
2019-07-10
Finish Date
2019-07-12
Coverage Spatial
Philadelphia, PA, USA
Date Publish Online
2019-08-29