10.1007/978-3-319-13129-0_3
Feldotto, Matthias
Matthias
Feldotto0000-0003-1348-6516
Gairing, Martin
Martin
Gairing
Skopalik, Alexander
Alexander
Skopalik
Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria
2014
2017-10-17T12:42:20Z
2020-05-07T05:25:49Z
conference
https://ris.uni-paderborn.de/record/453
https://ris.uni-paderborn.de/record/453.json
324307 bytes
application/pdf
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.