Paper Info
Title
Bounding The Potential Function In Congestion Games And Approximate Pure Nash Equilibria
Abstract
In this paper we study the potential function in congestion games. We consider both games with non-decreasing cost functions as well as games with non-increasing utility functions.We show that the value of the potential function Phi(s) of any outcome s of a congestion game approximates the optimum potential value Phi(s*) by a factor Psi(F) which only depends on the set of cost/utility functions F, and an additive term which is bounded by the sum of the total possible improvements of the players in the outcome s.The significance of this result is twofold. On the one hand it provides Price-of-Anarchy-like results with respect to the potential function. On the other hand, we show that these approximations can be used to compute (1 + epsilon). Psi(F)-approximate pure Nash equilibria for congestion games with non-decreasing cost functions. For the special case of polynomial cost functions, this significantly improves the guarantees from Caragiannis et al. [FOCS 2011]. Moreover, our machinery provides the first guarantees for general latency functions.
Year
DOI
Venue
2014
10.1007/978-3-319-13129-0_3
WEB AND INTERNET ECONOMICS
Field
DocType
Volume
Mathematical economics,Mathematical optimization,Congestion game,Computer science,Nash equilibrium,Bounding overwatch
Conference
8877
ISSN
Citations 
PageRank 
0302-9743
3
0.41
References 
Authors
16
3
Name
Order
Citations
PageRank
Matthias Feldotto1145.50
Martin Gairing263347.14
Alexander Skopalik324720.62