@inproceedings{453,
abstract = {In this paper we study the potential function in congestion games. We consider both games with non-decreasing cost functions as well as games with non-increasing utility functions. We show that the value of the potential function $\Phi(\sf s)$ of any outcome $\sf s$ of a congestion game approximates the optimum potential value $\Phi(\sf s^*)$ by a factor $\Psi_{\mathcal{F}}$ which only depends on the set of cost/utility functions $\mathcal{F}$, and an additive term which is bounded by the sum of the total possible improvements of the players in the outcome $\sf s$. The significance of this result is twofold. On the one hand it provides \emph{Price-of-Anarchy}-like results with respect to the potential function. On the other hand, we show that these approximations can be used to compute $(1+\varepsilon)\cdot\Psi_{\mathcal{F}}$-approximate pure Nash equilibria for congestion games with non-decreasing cost functions. For the special case of polynomial cost functions, this significantly improves the guarantees from Caragiannis et al. [FOCS 2011]. Moreover, our machinery provides the first guarantees for general latency functions.},
author = {Feldotto, Matthias and Gairing, Martin and Skopalik, Alexander},
booktitle = {Proceedings of the 10th International Conference on Web and Internet Economics (WINE)},
pages = {30--43},
title = {{Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria}},
doi = {10.1007/978-3-319-13129-0_3},
year = {2014},
}