Approximate pure Nash equilibria in weighted congestion games
Hansknecht, Christoph
Klimm, Max
Skopalik, Alexander
ddc:040
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.
2014
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://ris.uni-paderborn.de/record/455
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>
eng
info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.APPROX-RANDOM.2014.242
info:eu-repo/semantics/closedAccess