conference paper
Approximate pure Nash equilibria in weighted congestion games
Christoph
Hansknecht
author
Max
Klimm
author
Alexander
Skopalik
author 40384
541
department
63
department
SFB 901
project
SFB 901 - Subprojekt A3
project
SFB 901 - Project Area A
project
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.
https://ris.uni-paderborn.de/download/455/1341/455-HKS14.pdf
application/pdf
2014
eng
Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)10.4230/LIPIcs.APPROX-RANDOM.2014.242
242 - 257
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.
@inproceedings{Hansknecht_Klimm_Skopalik_2014, series={LIPIcs}, title={Approximate pure Nash equilibria in weighted congestion games}, DOI={<a href="https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242">10.4230/LIPIcs.APPROX-RANDOM.2014.242</a>}, 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 C, Klimm M, Skopalik A. Approximate pure Nash equilibria in weighted congestion games. In: <i>Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)</i>. LIPIcs. ; 2014:242-257. doi:<a href="https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242">10.4230/LIPIcs.APPROX-RANDOM.2014.242</a>
Hansknecht, C., Klimm, M., & Skopalik, A. (2014). Approximate pure Nash equilibria in weighted congestion games. In <i>Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)</i> (pp. 242–257). <a href="https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242">https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242</a>
Hansknecht, Christoph, et al. “Approximate Pure Nash Equilibria in Weighted Congestion Games.” <i>Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)</i>, 2014, pp. 242–57, doi:<a href="https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242">10.4230/LIPIcs.APPROX-RANDOM.2014.242</a>.
C. Hansknecht, M. Klimm, and A. Skopalik, “Approximate pure Nash equilibria in weighted congestion games,” in <i>Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)</i>, 2014, pp. 242–257.
Hansknecht, Christoph, Max Klimm, and Alexander Skopalik. “Approximate Pure Nash Equilibria in Weighted Congestion Games.” In <i>Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)</i>, 242–57. LIPIcs, 2014. <a href="https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242">https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.242</a>.
4552017-10-17T12:42:20Z2019-04-11T14:27:09Z