@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}},
}