On the communication complexity of approximate Nash equilibria

• 成果类型: Article
• 署名作者: Goldberg, Paul W.; Pastink, Arnoud
• 署名单位: University of Oxford; Utrecht University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2014.01.009
• 发表日期: 2014
• 页码: 19-31
• 关键词: Two player; mixed strategy; Approximate equilibria; Efficient algorithms

摘要

We study the problem of computing approximate Nash equilibria of bimatrix games, in a setting where players initially know their own payoffs but not the other player's. In order to find a solution of reasonable quality, some amount of communication is required. We study algorithms where the communication is substantially less than the size of the game. When the communication is polylogarithmic in the number of strategies, we show how to obtain epsilon-approximate Nash equilibrium for epsilon approximate to 0.438, and for well-supported approximate equilibria we obtain epsilon approximate to 0.732. For one-way communication we show that epsilon = 1/2 is the best approximation quality achievable, while for well-supported equilibria, no value of epsilon < 1 is achievable. When the players do not communicate at all, epsilon-Nash equilibria can be obtained for epsilon = 3/4; we also provide a corresponding lower bound of slightly more than 1/2 on the smallest constant epsilon achievable. (C) 2014 Elsevier Inc. All rights reserved.