@inproceedings{455,
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.},
author = {Hansknecht, Christoph and Klimm, Max and Skopalik, Alexander},
booktitle = {Proceedings of the 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)},
pages = {242 -- 257},
title = {{Approximate pure Nash equilibria in weighted congestion games}},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.242},
year = {2014},
}