The Query Complexity of Correlated Equilibria
Sergiu Hart () and
Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem
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.
New Economics Papers: this item is included in nep-gth, nep-hpe and nep-mic
References: Add references at CitEc
Citations: Track citations by RSS feed
Downloads: (external link)
Journal Article: The query complexity of correlated equilibria (2018)
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)
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 ().