期刊
GAMES AND ECONOMIC BEHAVIOR
卷 71, 期 2, 页码 315-327出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.geb.2009.05.004
关键词
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据