The Communication Complexity of Uncoupled Nash Equilibrium Procedures

Sergiu Hart () and Yishay Mansour ()

Discussion Paper Series from Center for Rationality and Interactive Decision Theory, 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.

New Economics Papers: this item is included in nep-gth
Date: Written
View citations in EconPapers

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: http://EconPapers.repec.org/RePEc:huj:dispap:dp419

Access Statistics for this paper

More papers in Discussion Paper Series from Center for Rationality and Interactive Decision Theory, Hebrew University, Jerusalem
Contact information at EDIRC.
Series data maintained by Ron Peretz ().