conference paper
Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria
Matthias
Feldotto
author 140520000-0003-1348-6516
Martin
Gairing
author
Alexander
Skopalik
author 40384
63
department
541
department
SFB 901
project
SFB 901 - Teilprojekt A
project
SFB 901 - Subprojekt A3
project
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.
https://ris.uni-paderborn.de/download/453/1342/453-WINE14FGS.pdf
application/pdf
2014
Proceedings of the 10th International Conference on Web and Internet Economics (WINE)10.1007/978-3-319-13129-0_3
30-43
Feldotto, M., Gairing, M., & Skopalik, A. (2014). Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria. In <i>Proceedings of the 10th International Conference on Web and Internet Economics (WINE)</i> (pp. 30–43). <a href="https://doi.org/10.1007/978-3-319-13129-0_3">https://doi.org/10.1007/978-3-319-13129-0_3</a>
M. Feldotto, M. Gairing, A. Skopalik, in: Proceedings of the 10th International Conference on Web and Internet Economics (WINE), 2014, pp. 30–43.
Feldotto M, Gairing M, Skopalik A. Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria. In: <i>Proceedings of the 10th International Conference on Web and Internet Economics (WINE)</i>. LNCS. ; 2014:30-43. doi:<a href="https://doi.org/10.1007/978-3-319-13129-0_3">10.1007/978-3-319-13129-0_3</a>
@inproceedings{Feldotto_Gairing_Skopalik_2014, series={LNCS}, title={Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria}, DOI={<a href="https://doi.org/10.1007/978-3-319-13129-0_3">10.1007/978-3-319-13129-0_3</a>}, booktitle={Proceedings of the 10th International Conference on Web and Internet Economics (WINE)}, author={Feldotto, Matthias and Gairing, Martin and Skopalik, Alexander}, year={2014}, pages={30–43}, collection={LNCS} }
M. Feldotto, M. Gairing, and A. Skopalik, “Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria,” in <i>Proceedings of the 10th International Conference on Web and Internet Economics (WINE)</i>, 2014, pp. 30–43.
Feldotto, Matthias, et al. “Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria.” <i>Proceedings of the 10th International Conference on Web and Internet Economics (WINE)</i>, 2014, pp. 30–43, doi:<a href="https://doi.org/10.1007/978-3-319-13129-0_3">10.1007/978-3-319-13129-0_3</a>.
Feldotto, Matthias, Martin Gairing, and Alexander Skopalik. “Bounding the Potential Function in Congestion Games and Approximate Pure Nash Equilibria.” In <i>Proceedings of the 10th International Conference on Web and Internet Economics (WINE)</i>, 30–43. LNCS, 2014. <a href="https://doi.org/10.1007/978-3-319-13129-0_3">https://doi.org/10.1007/978-3-319-13129-0_3</a>.
4532017-10-17T12:42:20Z2020-05-07T05:25:49Z