Fast Convergence of Best-Reply Dynamics in Aggregative Games

• 成果类型: Article
• 署名作者: Babichenko, Yakov
• 署名单位: Technion Israel Institute of Technology
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0868
• 发表日期: 2018
• 页码: 333-346
• 关键词: Congestion games; potential games; Nash equilibria

摘要

We consider small-influence aggregative games with a large number of players n. For this class of games we present a best-reply dynamic with the following two properties. First, the dynamic reaches Nash approximate equilibria in quasi-linear (in n) number of steps, and the quasi-linear bound is tight. Second, Nash approximate equilibria are played by the dynamic with a limit frequency that is exponentially (in n) close to 1.