Communication complexity of approximate Nash equilibria

Yakov Babichenko and Aviad Rubinstein

Games and Economic Behavior, 2022, vol. 134, issue C, 376-398

Abstract: For a constant ϵ, we prove a poly(N) lower bound on the (randomized) communication complexity of ϵ-Nash equilibrium in two-player N×N games. For n-player binary-action games we prove an exp⁡(n) lower bound for the (randomized) communication complexity of (ϵ,ϵ)-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least (1−ϵ)-fraction of the players are ϵ-best replying.

Keywords: Communication complexity; Approximate Nash equilibria; Convergence rate of uncoupled dynamics (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S089982562030097X
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:gamebe:v:134:y:2022:i:c:p:376-398

DOI: 10.1016/j.geb.2020.07.005

Access Statistics for this article

Games and Economic Behavior is currently edited by E. Kalai

More articles in Games and Economic Behavior from Elsevier
Bibliographic data for series maintained by Catherine Liu ().