The Query Complexity of Correlated Equilibria

Sergiu Hart and Noam Nisan

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

Abstract: We consider the complexity of finding a Correlated Equilibrium in an n-player game in a model that allows the algorithm to make queries for players' utilities at pure strategy profiles. Many randomized regret-matching dynamics are known to yield an approximate correlated equilibrium quickly: in time that is polynomial in the number of players, n, the number of strategies of each player, m, and the approximation error, 1/?. Here we show that both randomization and approximation are necessary: no efficient deterministic algorithm can reach even an approximate equilibrium and no efficient randomized algorithm can reach an exact equilibrium.

Date: 2013-09
New Economics Papers: this item is included in nep-gth, nep-hpe and nep-mic
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://ma.huji.ac.il/hart/abs/corr-com.html (text/html)

Related works:
Journal Article: The query complexity of correlated equilibria (2018)
Working Paper: The Query Complexity of Correlated Equilibria (2017)
Working Paper: The Query Complexity of Correlated Equilibria (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:huj:dispap:dp647

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 (menahem.simkin@mail.huji.ac.il).