 On the communication complexity of approximate Nash equilibriaPaul W. Goldberg and Arnoud Pastink Games and Economic Behavior, 2014, vol. 85, issue C, 19-31 Abstract: 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 ϵ-approximate Nash equilibrium for ϵ≈0.438, and for well-supported approximate equilibria we obtain ϵ≈0.732. For one-way communication we show that ϵ=12 is the best approximation quality achievable, while for well-supported equilibria, no value of ϵ<1 is achievable. When the players do not communicate at all, ϵ-Nash equilibria can be obtained for ϵ=34; we also provide a corresponding lower bound of slightly more than 12 on the smallest constant ϵ achievable. Keywords: Two player; Mixed strategy; Approximate equilibria; Efficient algorithms (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:85:y:2014:i:c:p:19-31 DOI: 10.1016/j.geb.2014.01.009 Access Statistics for this article Games and Economic Behavior is currently edited by E. Kalai More articles in Games and Economic Behavior from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.