Convergence to approximate Nash equilibria in congestion games

• 成果类型: Article
• 署名作者: Chien, Steve; Sinclair, Alistair
• 署名单位: Microsoft; University of California System; University of California Berkeley
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2009.05.004
• 发表日期: 2011
• 页码: 315-327
• 关键词: Congestion games; Convergence to equilibrium; Approximate Nash equilibria; best-response dynamics; PLS-completeness; Polynomial time; Symmetric congestion games

摘要

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 si, 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. (C) 2009 Elsevier Inc. All rights reserved.