Approximate Pure Nash Equilibria in Social Context Congestion Games

Martin Gairing; Grammateia Kotsialou; Alexander  Skopalik

Approximate Pure Nash Equilibria in Social Context Congestion Games

Martin Gairing, Grammateia Kotsialou, Alexander Skopalik

Political Economy

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › 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 of Economics (WINE)
Publisher	Springer
Pages	480-485
Publication status	Published - 2014

Cite this

@inbook{a06338eb4cd34443af93ea54c5306538,

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

language = "English",

pages = "480--485",

booktitle = "Web and Internet of Economics (WINE)",

publisher = "Springer",

}

TY - CHAP

T1 - Approximate Pure Nash Equilibria in Social Context Congestion Games

AU - Gairing, Martin

AU - Kotsialou, Grammateia

AU - Skopalik, Alexander

PY - 2014

Y1 - 2014

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

M3 - Conference paper

SP - 480

EP - 485

BT - Web and Internet of Economics (WINE)

PB - Springer

ER -

Approximate Pure Nash Equilibria in Social Context Congestion Games

Abstract

Fingerprint

Cite this