Approximate pure Nash equilibria in weighted congestion games
C. Hansknecht, M. Klimm, A. Skopalik, in: Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2014, pp. 242–257.
Download
455-HKS14.pdf
512.71 KB
Conference Paper
| English
Author
Hansknecht, Christoph;
Klimm, Max;
Skopalik, AlexanderLibreCat
Department
Abstract
We study the existence of approximate pure Nash equilibria in weighted congestion games and develop techniques to obtain approximate potential functions that prove the existence of alpha-approximate pure Nash equilibria and the convergence of alpha-improvement steps. Specifically, we show how to obtain upper bounds for approximation factor alpha for a given class of cost functions. For example for concave cost functions the factor is at most 3/2, for quadratic cost functions it is at most 4/3, and for polynomial cost functions of maximal degree d it is at at most d + 1. For games with two players we obtain tight bounds which are as small as for example 1.054 in the case of quadratic cost functions.
Publishing Year
Proceedings Title
Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)
forms.conference.field.series_title_volume.label
LIPIcs
Page
242 - 257
LibreCat-ID
Cite this
Hansknecht C, Klimm M, Skopalik A. Approximate pure Nash equilibria in weighted congestion games. In: Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). LIPIcs. ; 2014:242-257. doi:10.4230/LIPIcs.APPROX-RANDOM.2014.242
Hansknecht, C., Klimm, M., & Skopalik, A. (2014). Approximate pure Nash equilibria in weighted congestion games. In Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) (pp. 242–257). https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242
@inproceedings{Hansknecht_Klimm_Skopalik_2014, series={LIPIcs}, title={Approximate pure Nash equilibria in weighted congestion games}, DOI={10.4230/LIPIcs.APPROX-RANDOM.2014.242}, booktitle={Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)}, author={Hansknecht, Christoph and Klimm, Max and Skopalik, Alexander}, year={2014}, pages={242–257}, collection={LIPIcs} }
Hansknecht, Christoph, Max Klimm, and Alexander Skopalik. “Approximate Pure Nash Equilibria in Weighted Congestion Games.” In Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 242–57. LIPIcs, 2014. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242.
C. Hansknecht, M. Klimm, and A. Skopalik, “Approximate pure Nash equilibria in weighted congestion games,” in Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2014, pp. 242–257.
Hansknecht, Christoph, et al. “Approximate Pure Nash Equilibria in Weighted Congestion Games.” Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2014, pp. 242–57, doi:10.4230/LIPIcs.APPROX-RANDOM.2014.242.
Main File(s)
File Name
455-HKS14.pdf
512.71 KB
Access Level
Closed Access
Last Uploaded
2018-03-16T11:23:40Z
Google Scholar