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

Sergiu Hart and Yishay Mansour

Games and Economic Behavior, 2010, vol. 69, issue 1, 107-126

Abstract: 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: (1) 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.

Keywords: Uncoupled; dynamics; Nash; equilibrium; Communication; complexity; Correlated; equilibrium; Speed; of; convergence (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (26)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0899-8256(08)00012-2
Full text for ScienceDirect subscribers only

Related works:
Chapter: HOW LONG TO EQUILIBRIUM? THE COMMUNICATION COMPLEXITY OF UNCOUPLED EQUILIBRIUM PROCEDURES (2013)
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:69:y:2010:i:1:p:107-126

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 ().