Conference proceeding
Optimal Cost-Sharing in Weighted Congestion Games
WEB AND INTERNET ECONOMICS, v 8877, pp 72-88
01 Jan 2014
Featured in Collection : UN Sustainable Development Goals @ Drexel
Abstract
We identify how to share costs locally in weighted congestion games with polynomial cost functions in order to minimize the worst-case price of anarchy (PoA). First, we prove that among all cost-sharing methods that guarantee the existence of pure Nash equilibria, the Shapley value minimizes the worst-case PoA. Second, if the guaranteed existence condition is dropped, then the proportional cost-sharing method minimizes the worst-case PoA over all cost-sharing methods. As a byproduct of our results, we obtain the first PoA analysis of the simple marginal contribution cost-sharing rule, and prove that marginal cost taxes are ineffective for improving equilibria in (atomic) congestion games.
Metrics
Details
- Title
- Optimal Cost-Sharing in Weighted Congestion Games
- Creators
- Vasilis Gkatzelis - Stanford UniversityKonstantinos Kollias - Stanford UniversityTim Roughgarden - Stanford University
- Contributors
- T Y Liu (Editor)Q Qi (Editor)Y Ye (Editor)
- Publication Details
- WEB AND INTERNET ECONOMICS, v 8877, pp 72-88
- Series
- Lecture Notes in Computer Science
- Publisher
- Springer Nature
- Number of pages
- 17
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Web of Science ID
- WOS:000354785800006
- Scopus ID
- 2-s2.0-84914105648
- Other Identifier
- 991021868728204721
UN Sustainable Development Goals (SDGs)
This publication has contributed to the advancement of the following goals:
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Web of Science research areas
- Computer Science, Interdisciplinary Applications
- Computer Science, Theory & Methods
- Mathematics, Interdisciplinary Applications