@inproceedings{3c051fd5da764120b2b353f18ba716fa,
title = "Approximate pure nash equilibria in weighted congestion games",
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 α-approximate pure Nash equilibria and the convergence of α-improvement steps. Specifically, we show how to obtain upper bounds for approximation factor α 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 ℓ it is at at most ℓ + 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.",
keywords = "Approximate equilibrium, Congestion game, Existence, Potential function, Pure Nash equilibrium",
author = "Christoph Hansknecht and Max Klimm and Alexander Skopalik",
note = "Publisher Copyright: {\textcopyright} Moran Feldman and Rani Izsak.; 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 ; Conference date: 04-09-2014 Through 06-09-2014",
year = "2014",
month = sep,
day = "1",
doi = "10.4230/LIPIcs.APPROX-RANDOM.2014.242",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Dagstuhl",
pages = "242--257",
editor = "Klaus Jansen and Rolim, {Jose D. P.} and Devanur, {Nikhil R.} and Cristopher Moore",
booktitle = "Leibniz International Proceedings in Informatics, LIPIcs",
address = "Germany",
}