The Price of Stability of Weighted Congestion Games

Christodoulou, George, Gairing, Martin, Giannakopoulos, Yannis and Spirakis, PG ORCID: 0000-0001-5396-3749 (2018) The Price of Stability of Weighted Congestion Games. In: International Colloquium on Automata , Languages and Programming (ICALP), 2018-7-9 - 2018-7-13, Prague.

	Text weightedPoS.pdf - Author Accepted Manuscript Available under License : See the attached licence file. Download (639kB)
	Text 1802.09952v1.pdf - Submitted version Available under License : See the attached licence file. Download (775kB)

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 Omega(Phi_d)^{d+1}, where Phi_d ~ d/ln d is the unique positive root of equation x^{d+1}=(x+1)^d. This essentially closes the huge gap between Theta(d) and Phi_d^{d+1} and asymptotically matches the Price of Anarchy upper bound. We further show that the PoS remains exponential even for singleton games. More generally, we also provide a lower bound of Omega((1+1/alpha)^d/d) on the PoS of alpha-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 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 Theta(1) to d+1 in a smooth way with respect to W. Secondly, we show that for unweighted congestion games, the PoS of alpha-approximate Nash equilibria is at most (d+1)/alpha.

Item Type:	Conference or Workshop Item (Unspecified)
Uncontrolled Keywords:	Congestion games, price of stability, Nash equilibrium, approximate equilibrium, potential games
Depositing User:	Symplectic Admin
Date Deposited:	04 Feb 2019 13:50
Last Modified:	19 Jan 2023 01:05
DOI:	10.4230/LIPIcs.ICALP.2018.150
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3032123

Available Versions of this Item

• The Price of Stability of Weighted Congestion Games. (deposited 25 Apr 2018 10:02)
  • The Price of Stability of Weighted Congestion Games. (deposited 04 Feb 2019 13:50) [Currently Displayed]