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)

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 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
Pages480-485
Number of pages6
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 'Approximate Pure Nash Equilibria in Social Context Congestion Games'. Together they form a unique fingerprint.

Cite this