 Convergence to approximate Nash equilibria in congestion gamesSteve Chien and Alistair Sinclair Games and Economic Behavior, 2011, vol. 71, issue 2, 315-327 Abstract: We study the ability of decentralized, local dynamics in non-cooperative games to rapidly reach an approximate (pure) Nash equilibrium. Our main result states that for symmetric congestion games in which the cost function associated with each resource satisfies a "bounded jump" condition, convergence to an [epsilon]-Nash equilibrium occurs within a number of steps that is polynomial in the number of players and [epsilon]-1. We show moreover that this result holds under a variety of conventions governing the move orders among the players, including the minimal liveness assumption that no player is indefinitely blocked from moving. We also prove that in the generalized setting where players have different "tolerances" [epsilon]i, the number of moves a player makes before equilibrium is reached depends only on his associated [epsilon]i, and not on those of other players. Finally, we show that polynomial time convergence holds even when a constant number of resources have arbitrary cost functions. Keywords: Congestion; games; Convergence; to; equilibrium; Approximate; Nash; equilibria; Best-response; dynamics; PLS-completeness; Polynomial; time; Symmetric; congestion; games (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:71:y:2011:i:2:p:315-327 Access Statistics for this article Games and Economic Behavior is currently edited by E. Kalai More articles in Games and Economic Behavior from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.