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 Rough-garden's anarchy value.
展开▼
