2026-07-22T08:34:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4700 2024-03-06T10:35:16Z ddc:004 open_access

Approximate Pure Nash Equilibria in Weighted Congestion Games Hansknecht, Christoph Klimm, Max Skopalik, Alexander Congestion game Pure Nash equilibrium Approximate equilibrium Existence Potential function 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christoph Hansknecht and Max Klimm and Alexander Skopalik 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.242 urn:nbn:de:0030-drops-47005 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.242 eng https://creativecommons.org/licenses/by/3.0/legalcode