The price of stability of weighted congestion games

Christodoulou G, Gairing M, Giannakopoulos Y, Spirakis PG (2019)

Publication Type: Journal article

Publication year: 2019

Journal

SIAM Journal on Computing Society for Industrial and Applied Mathematics

Book Volume: 48

Pages Range: 1544-1582

Journal Issue: 5

DOI: 10.1137/18M1207880

Open Access Link: https://arxiv.org/abs/1802.09952

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 \sim d/ln d is the unique positive root of the equation xd +1 = (x + 1)d. This almost closes the huge gap between \Theta (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 \Omega ((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 \Theta (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 .

Authors with CRIS profile

Ioannis Giannakopoulos

Involved external institutions

The University of Liverpool GB United Kingdom (GB) Technische Universität München (TUM) DE Germany (DE)

How to cite

APA:

Christodoulou, G., Gairing, M., Giannakopoulos, Y., & Spirakis, P.G. (2019). The price of stability of weighted congestion games. SIAM Journal on Computing, 48(5), 1544-1582. https://dx.doi.org/10.1137/18M1207880

MLA:

Christodoulou, George, et al. "The price of stability of weighted congestion games." SIAM Journal on Computing 48.5 (2019): 1544-1582.

BibTeX: Download