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 [19].
展开▼
