License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.242
URN: urn:nbn:de:0030-drops-47005
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4700/
Go to the corresponding LIPIcs Volume Portal

Hansknecht, Christoph ; Klimm, Max ; Skopalik, Alexander

Approximate Pure Nash Equilibria in Weighted Congestion Games

pdf-format:
17.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{hansknecht_et_al:LIPIcs:2014:4700,
  author =	{Christoph Hansknecht and Max Klimm and Alexander Skopalik},
  title =	{{Approximate Pure Nash Equilibria in Weighted Congestion Games}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{242--257},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4700},
  URN =		{urn:nbn:de:0030-drops-47005},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.242},
  annote =	{Keywords: Congestion game, Pure Nash equilibrium, Approximate equilibrium, Existence, Potential function}
}

Keywords: Congestion game, Pure Nash equilibrium, Approximate equilibrium, Existence, Potential function
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI