Approximate Pure Nash Equilibria in Social Context Congestion Games

Martin Gairing; Grammateia Kotsialou; Alexander Skopalik

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

Approximate Pure Nash Equilibria in Social Context Congestion Games

Martin Gairing^*
, Grammateia Kotsialou
, Alexander Skopalik

^*Corresponding author for this work

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

1 Citation (Scopus)

Abstract

We study the existence of approximate pure Nash equilibria in social context congestion games. For any given set of allowed cost functions F, we provide a threshold value μ(F), and show that for the class of social context congestion games with cost functions from F, α- Nash dynamics are guaranteed to converge to α-approximate pure Nash equilibrium if and only if α > μ(F). Interestingly, μ(F) is related and always upper bounded by Roughgarden’s anarchy value [19].

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	480-485
Number of pages	6
ISBN (Electronic)	978-3-319-13129-0
DOIs	https://doi.org/10.1007/978-3-319-13129-0_43
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/Territory	China
City	Beijing
Period	14/12/14 → 17/12/14

Access to Document

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

Cite this

Gairing, M., Kotsialou, G., & Skopalik, A. (2014). Approximate Pure Nash Equilibria in Social Context Congestion Games. 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. 480-485). (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_43

Gairing, Martin ; Kotsialou, Grammateia ; Skopalik, Alexander. / Approximate Pure Nash Equilibria in Social Context Congestion Games. 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. 480-485 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a79989bfa5064bae9aff527bf23a3721,

title = "Approximate Pure Nash Equilibria in Social Context Congestion Games",

abstract = "We study the existence of approximate pure Nash equilibria in social context congestion games. For any given set of allowed cost functions F, we provide a threshold value μ(F), and show that for the class of social context congestion games with cost functions from F, α- Nash dynamics are guaranteed to converge to α-approximate pure Nash equilibrium if and only if α > μ(F). Interestingly, μ(F) is related and always upper bounded by Roughgarden{\textquoteright}s anarchy value [19].",

author = "Martin Gairing and Grammateia Kotsialou and Alexander Skopalik",

year = "2014",

month = jan,

day = "1",

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

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 = "480--485",

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

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",

}

Gairing, M, Kotsialou, G & Skopalik, A 2014, Approximate Pure Nash Equilibria in Social Context Congestion Games. 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. 480-485, 10th Conference on Web and Internet Economics, WINE 2014, Beijing, China, 14/12/14. https://doi.org/10.1007/978-3-319-13129-0_43

Approximate Pure Nash Equilibria in Social Context Congestion Games. / Gairing, Martin; Kotsialou, Grammateia; 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. 480-485 (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 - Approximate Pure Nash Equilibria in Social Context Congestion Games

AU - Gairing, Martin

AU - Kotsialou, Grammateia

AU - Skopalik, Alexander

N1 - Conference code: 10

PY - 2014/1/1

Y1 - 2014/1/1

N2 - We study the existence of approximate pure Nash equilibria in social context congestion games. For any given set of allowed cost functions F, we provide a threshold value μ(F), and show that for the class of social context congestion games with cost functions from F, α- Nash dynamics are guaranteed to converge to α-approximate pure Nash equilibrium if and only if α > μ(F). Interestingly, μ(F) is related and always upper bounded by Roughgarden’s anarchy value [19].

AB - We study the existence of approximate pure Nash equilibria in social context congestion games. For any given set of allowed cost functions F, we provide a threshold value μ(F), and show that for the class of social context congestion games with cost functions from F, α- Nash dynamics are guaranteed to converge to α-approximate pure Nash equilibrium if and only if α > μ(F). Interestingly, μ(F) is related and always upper bounded by Roughgarden’s anarchy value [19].

UR - https://www.scopus.com/pages/publications/84914181664

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

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

M3 - Conference contribution

AN - SCOPUS:84914181664

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 - 480

EP - 485

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 -

Gairing M, Kotsialou G, Skopalik A. Approximate Pure Nash Equilibria in Social Context Congestion Games. In Liu TY, Qi Q, Ye Y, editors, Web and Internet Economics: 10th International Conference, WINE 2014, Beijing, China, December 14-17, 2014. Proceedings. 2014. p. 480-485. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-13129-0_43

Approximate Pure Nash Equilibria in Social Context Congestion Games

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this