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

Matthias Feldotto; Martin Gairing; Alexander Skopalik

doi:10.1007/978-3-319-13129-0_3

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 proceeding › Conference contribution › Academic › peer-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 language	English
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
Pages	30-43
Number of pages	14
ISBN (Electronic)	978-3-319-13129-0
DOIs	https://doi.org/10.1007/978-3-319-13129-0_3
Publication status	Published - 1 Jan 2014
Externally published	Yes
Event	10th Conference on Web and Internet Economics, WINE 2014 - Beijing, China Duration: 14 Dec 2014 → 17 Dec 2014 Conference number: 10

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Publisher	Springer
Volume	8877
ISSN (Print)	0302-9743

Conference

Conference	10th Conference on Web and Internet Economics, WINE 2014
Abbreviated title	WINE
Country	China
City	Beijing
Period	14/12/14 → 17/12/14

Access to Document

10.1007/978-3-319-13129-0_3

Link to publication in Scopus

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

Feldotto, M., Gairing, M., & Skopalik, A. (2014). Bounding the potential function in congestion games and approximate pure Nash equilibria. In T-Y. Liu, Q. Qi, & Y. Ye (Eds.), Web and Internet Economics: 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings (pp. 30-43). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8877). https://doi.org/10.1007/978-3-319-13129-0_3

Feldotto, Matthias ; Gairing, Martin ; Skopalik, Alexander. / Bounding the potential function in congestion games and approximate pure Nash equilibria. Web and Internet Economics: 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings. editor / Tie-Yan Liu ; Qi Qi ; Yinyu Ye. 2014. pp. 30-43 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e426569210f54d25902fc1ab0e2817dd,

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

author = "Matthias Feldotto and Martin Gairing and Alexander Skopalik",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/978-3-319-13129-0_3",

language = "English",

isbn = "978-3-319-13128-3",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "30--43",

editor = "Tie-Yan Liu and Qi Qi and Yinyu Ye",

booktitle = "Web and Internet Economics",

note = "10th Conference on Web and Internet Economics, WINE 2014, WINE ; Conference date: 14-12-2014 Through 17-12-2014",

}

Feldotto, M, Gairing, M & Skopalik, A 2014, Bounding the potential function in congestion games and approximate pure Nash equilibria. in T-Y Liu, Q Qi & Y Ye (eds), Web and Internet Economics: 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8877, pp. 30-43, 10th Conference on Web and Internet Economics, WINE 2014, Beijing, China, 14/12/14. https://doi.org/10.1007/978-3-319-13129-0_3

Bounding the potential function in congestion games and approximate pure Nash equilibria. / Feldotto, Matthias; Gairing, Martin; Skopalik, Alexander.

Web and Internet Economics: 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings. ed. / Tie-Yan Liu; Qi Qi; Yinyu Ye. 2014. p. 30-43 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8877).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Feldotto, Matthias

AU - Gairing, Martin

AU - Skopalik, Alexander

N1 - Conference code: 10

PY - 2014/1/1

Y1 - 2014/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84914169843&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-13129-0_3

DO - 10.1007/978-3-319-13129-0_3

M3 - Conference contribution

AN - SCOPUS:84914169843

SN - 978-3-319-13128-3

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 30

EP - 43

BT - Web and Internet Economics

A2 - Liu, Tie-Yan

A2 - Qi, Qi

A2 - Ye, Yinyu

T2 - 10th Conference on Web and Internet Economics, WINE 2014

Y2 - 14 December 2014 through 17 December 2014

ER -

Feldotto M, Gairing M, Skopalik A. Bounding the potential function in congestion games and approximate pure Nash equilibria. In Liu T-Y, Qi Q, Ye Y, editors, Web and Internet Economics: 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings. 2014. p. 30-43. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-13129-0_3