Communication complexity of approximate Nash equilibria

• 成果类型: Article
• 署名作者: Babichenko, Yakov; Rubinstein, Aviad
• 署名单位: Technion Israel Institute of Technology; Stanford University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2020.07.005
• 发表日期: 2022
• 页码: 376-398
• 关键词: Communication complexity; Approximate Nash equilibria; Convergence rate of uncoupled dynamics

摘要

For a constant c, we prove a poly(N) lower bound on the (randomized) communication complexity of c-Nash equilibrium in two-player N x N games. For n-player binary-action games we prove an exp(n) lower bound for the (randomized) communication complexity of (c, 0-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least (1 - 0-fraction of the players are c-best replying. (c) 2020 Elsevier Inc. All rights reserved.