---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Christoph
foaf_name: Hansknecht, Christoph
foaf_surname: Hansknecht
- foaf_Person:
foaf_givenName: Max
foaf_name: Klimm, Max
foaf_surname: Klimm
- foaf_Person:
foaf_givenName: Alexander
foaf_name: Skopalik, Alexander
foaf_surname: Skopalik
foaf_workInfoHomepage: http://www.librecat.org/personId=40384
bibo_doi: 10.4230/LIPIcs.APPROX-RANDOM.2014.242
dct_date: 2014^xs_gYear
dct_language: eng
dct_title: Approximate pure Nash equilibria in weighted congestion games@
...