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 proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)


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 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
Number of pages6
ISBN (Electronic)978-3-319-13129-0
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)
ISSN (Print)0302-9743


Conference10th Conference on Web and Internet Economics, WINE 2014
Abbreviated titleWINE

Fingerprint Dive into the research topics of 'Approximate Pure Nash Equilibria in Social Context Congestion Games'. Together they form a unique fingerprint.

Cite this