文章基本信息

标题：Approximate Pure Nash Equilibria in Weighted Congestion Games
本地全文：下载
作者：Christoph Hansknecht ; Max Klimm ; Alexander Skopalik 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：28
页码：242-257
DOI：10.4230/LIPIcs.APPROX-RANDOM.2014.242
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Congestion game; Pure Nash equilibrium; Approximate equilibrium; Existence; Potential function