The central theme in this talk is the study of selfish behaviour of autonomous players in congestion games; important special cases of such games include traffic routing in networks and scheduling. 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$ 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 (PoA) upper bound. We further show that the PoS remains exponential even for singleton games and approximate equilibria. 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 $\rho$-approximate Nash equilibria, which is sensitive to the range $W$ of the player weights and the approximation parameter $\rho$. 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.
Furthermore, we will briefly discuss how this new potential can be used to derive a polynomial-time deterministic algorithm for computing $d^{d+o(d)}$-approximate equilibria. This is an exponential improvement of the approximation factor with respect to the previously best algorithm. An appealing additional feature of our algorithm is that it uses only best-improvement steps in the actual game, as opposed to earlier approaches that first had to transform the game itself. A critical component of the analysis of the algorithm, which is of independent interest, is the derivation of a new bound for PoA of $\rho$-approximate equilibria. More specifically, we show that this PoA is *exactly* equal to $\Phi_{d,\rho}^{d+1}$, where $\Phi_{d,\rho}$ is the unique positive solution of the equation $\rho (x+1)^d=x^{d+1}$.
Venue: Room 02.04.011 (Garching Campus)
Date: Monday, February 4th 2019, 14:00