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 Ф(s) of any outcome s of a congestion game approximates the optimum potential value Ф(s∗) by a factor Ψ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+ε). Ψ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.
|Title of host publication||Web and Internet Economics|
|Subtitle of host publication||10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings|
|Editors||Tie-Yan Liu, Qi Qi, Yinyu Ye|
|Number of pages||14|
|Publication status||Published - 1 Jan 2014|
|Event||10th Conference on Web and Internet Economics, WINE 2014 - Beijing, China|
Duration: 14 Dec 2014 → 17 Dec 2014
Conference number: 10
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||10th Conference on Web and Internet Economics, WINE 2014|
|Period||14/12/14 → 17/12/14|