Back to Search
Start Over
THE PRICE OF STABILITY OF WEIGHTED CONGESTION GAMES.
- Source :
-
SIAM Journal on Computing . 2019, Vol. 48 Issue 5, p1544-1582. 39p. - Publication Year :
- 2019
-
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 the equation xd+1 = (x + 1)d. This almost closes the huge gap between θ(d) and Φd+1d. Our bound extends also to network congestion games. We further show that the PoS remains exponential even for singleton games. More generally, we provide a lower bound of Ω ((1+1/α)d/d) on the PoS of α -approximate Nash equilibria for singleton games. All our lower bounds 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. Second, we show that for unweighted congestion games, the PoS of α-approximate Nash equilibria is at most (d + 1)/α. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 48
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 140949124
- Full Text :
- https://doi.org/10.1137/18M1207880