Bounding the potential function in congestion games and approximate pure Nash equilibria

Matthias Feldotto*, Martin Gairing, Alexander Skopalik

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

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 Ф(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.

Original languageEnglish
Title of host publicationWeb and Internet Economics
Subtitle of host publication10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings
EditorsTie-Yan Liu, Qi Qi, Yinyu Ye
Pages30-43
Number of pages14
ISBN (Electronic)978-3-319-13129-0
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes
Event10th Conference on Web and Internet Economics, WINE 2014 - Beijing, China
Duration: 14 Dec 201417 Dec 2014
Conference number: 10

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume8877
ISSN (Print)0302-9743

Conference

Conference10th Conference on Web and Internet Economics, WINE 2014
Abbreviated titleWINE
CountryChina
CityBeijing
Period14/12/1417/12/14

Fingerprint Dive into the research topics of 'Bounding the potential function in congestion games and approximate pure Nash equilibria'. Together they form a unique fingerprint.

Cite this