HOW LONG TO EQUILIBRIUM? THE COMMUNICATION COMPLEXITY OF UNCOUPLED EQUILIBRIUM PROCEDURES

Sergiu Hart and Yishay Mansour
Additional contact information
Yishay Mansour: Tel Aviv University, Israel

Chapter 10 in Simple Adaptive Strategies:From Regret-Matching to Uncoupled Dynamics, 2013, pp 215-249 from World Scientific Publishing Co. Pte. Ltd.

Abstract: AbstractWe 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: Game Theory; Dynamics; Equilibrium; Nash Equilibrium; Correlated Equilibrium; Adaptive Dynamics; Simple Strategies; Regret-Based Strategies; Uncoupled Dynamics; Bounded Rationality (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.worldscientific.com/doi/pdf/10.1142/9789814390705_0010 (application/pdf)
https://www.worldscientific.com/doi/abs/10.1142/9789814390705_0010 (text/html)
Ebook Access is available upon purchase.

Related works:
Journal Article: How long to equilibrium? The communication complexity of uncoupled equilibrium procedures (2010)
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:wsi:wschap:9789814390705_0010

Ordering information: This item can be ordered from

Access Statistics for this chapter

More chapters in World Scientific Book Chapters from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().