The price of stability of weighted congestion games
Christodoulou G, Gairing M, Giannakopoulos Y, Spirakis PG (2018)
Publication Type: Conference contribution, Original article
Publication year: 2018
Journal
Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Book Volume: 107
Pages Range: 150:1--150:16
Conference Proceedings Title: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP)
Event location: Prague
ISBN: 9783959770767
DOI: 10.4230/LIPIcs.ICALP.2018.150
Open Access Link: https://drops.dagstuhl.de/opus/volltexte/2018/9154/
Abstract
We give exponential lower bounds on the Price of Stability (PoS) of weighted congestion games with polynomial cost functions. In particular, for any positive integer d we construct rather simple games with cost functions of degree at most d which have a PoS of at least Ω(d)d +1, where d ∼ d/ln d is the unique positive root of equation xd +1 = (x + 1)d. This essentially closes the huge gap between Θ(d) and d+1 and asymptotically matches the Price of Anarchy d upper bound. We further show that the PoS remains exponential even for singleton games. More generally, we also provide a lower bound of Ω((1 + 1/α)d/d) on the PoS of α-approximate Nash equilibria, even for singleton games. All our lower bounds extend to network congestion games, and hold for mixed and correlated equilibria as well. On the positive side, we give a general upper bound on the PoS of α-approximate Nash equilibria, which is sensitive to the range W of the player weights and the approximation parameter α. We do this by explicitly constructing a novel approximate potential function, based on Faulhaber's formula, that generalizes Rosenthal's potential in a continuous, analytic way. From the general theorem, we deduce two interesting corollaries. First, we derive the existence of an approximate pure Nash equilibrium with PoS at most (d+ 3)/2; the equilibrium's approximation parameter ranges from Θ(1) to d+ 1 in a smooth way with respect to W. Secondly, we show that for unweighted congestion games, the PoS of α-approximate Nash equilibria is at most (d+ 1)/α.
Authors with CRIS profile
Involved external institutions
United Kingdom (GB)
Germany (DE)How to cite
APA:
Christodoulou, G., Gairing, M., Giannakopoulos, Y., & Spirakis, P.G. (2018). The price of stability of weighted congestion games. In Christos Kaklamanis, Daniel Marx, Ioannis Chatzigiannakis, Donald Sannella (Eds.), Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP) (pp. 150:1--150:16). Prague, CZ: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
MLA:
Christodoulou, George, et al. "The price of stability of weighted congestion games." Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague Ed. Christos Kaklamanis, Daniel Marx, Ioannis Chatzigiannakis, Donald Sannella, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. 150:1--150:16.
BibTeX: Download