The Communication Complexity of Uncoupled Nash Equilibrium Procedures

Sergiu Hart and Yishay Mansour ()

Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem

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 number of bits that need to be transmitted in order to reach a Nash equilibrium, 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. Finally, we show that some very simple and naive procedures lead to similar exponential upper bounds.

Date: 2006-03
New Economics Papers: this item is included in nep-gth
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Published in The 39th ACM Symposium on Theory of Computing (STOC) (2007), 345-353 [extended abstract: "The Communication Complexity of Uncoupled Nash Equilibrium Procedures"] & in Games and Economic Behavior 69 (2010), 1, 107-126

Downloads: (external link)
http://www.ma.huji.ac.il/hart/abs/aumann-n.html (text/html)

Related works:
Working Paper: The Communication Complexity of Uncoupled Nash Equilibrium Procedures (2006)
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:huj:dispap:dp419

Access Statistics for this paper

More papers in Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem Contact information at EDIRC.
Bibliographic data for series maintained by Michael Simkin ().