How long to equilibrium? The communication complexity of uncoupled equilibrium procedures

• 成果类型: Article
• 署名作者: Hart, Sergiu; Mansour, Yishay
• 署名单位: Hebrew University of Jerusalem; Hebrew University of Jerusalem; Tel Aviv University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2007.12.002
• 发表日期: 2010
• 页码: 107-126
• 关键词: Uncoupled dynamics; Nash equilibrium; communication complexity; correlated equilibrium; speed of convergence

摘要

We study the question of how long it takes players to reach a Nash equilibrium in uncoupled setups, where each player initially knows only his own payoff function. We derive lower bounds on the communication complexity of reaching a Nash equilibrium, i.e., on the number of bits that need to be transmitted, and thus also on the required number of steps. Specifically, we show lower bounds that are exponential in the number of players in each one of the following cases: (I) reaching a pure Nash equilibrium; (2) reaching a pure Nash equilibrium in a Bayesian setting; and (3) reaching a mixed Nash equilibrium. We then show that, in contrast, the communication complexity of reaching a correlated equilibrium is polynomial in the number of players. (C) 2008 Elsevier Inc. All rights reserved.