The Price of Stability of Weighted Congestion Games



Christodoulou, George, Gairing, M, Giannakopoulos, Yiannis and Spirakis, PG ORCID: 0000-0001-5396-3749
(2019) The Price of Stability of Weighted Congestion Games. SIAM Journal on Computing, 48 (5). pp. 1544-1582.

[img] Text
weightedPoS.pdf - Author Accepted Manuscript

Download (534kB) | Preview

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 $\varOmega(\Phi_d)^{d+1}$, where $\Phi_d\sim d/\ln d$ is the unique positive root of the equation $x^{d+1}=(x+1)^d$. This almost closes the huge gap between $\varTheta(d)$ and $\Phi_d^{d+1}$. 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 $\varOmega((1+1/\alpha)^d/d)$ on the PoS of $\alpha$-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 $\alpha$-approximate Nash equilibria, which is sensitive to the range $W$ of the player weights and the approximation parameter $\alpha$. 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 $\varTheta(1)$ to $d+1$ in a smooth way with respect to $W$. Second, we show that for unweighted congestion games, the PoS of $\alpha$-approximate Nash equilibria is at most $(d+1)/\alpha$. Read More: https://epubs.siam.org/doi/10.1137/18M1207880

Item Type: Article
Uncontrolled Keywords: congestion games, price of stability, Nash equilibrium, approximate equilibrium, potential games
Depositing User: Symplectic Admin
Date Deposited: 27 Aug 2019 08:39
Last Modified: 19 Jan 2023 00:28
DOI: 10.1137/18M1207880
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3052625