The Query Complexity of Correlated Equilibria

Sergiu Hart and Noam Nisan

Papers from arXiv.org

Abstract: We consider the complexity of finding a correlated equilibrium of an $n$-player game in a model that allows the algorithm to make queries on players' payoffs at pure strategy profiles. Randomized regret-based dynamics are known to yield an approximate correlated equilibrium efficiently, namely, in time that is polynomial in the number of players $n$. Here we show that both randomization and approximation are necessary: no efficient deterministic algorithm can reach even an approximate correlated equilibrium, and no efficient randomized algorithm can reach an exact correlated equilibrium. The results are obtained by bounding from below the number of payoff queries that are needed.

Date: 2013-05, Revised 2017-12
References: View references in EconPapers View complete reference list from CitEc
Citations:

Published in Games and Economic Behavior 108 (2018), 401-410

Downloads: (external link)
http://arxiv.org/pdf/1305.4874 Latest version (application/pdf)

Related works:
Journal Article: The query complexity of correlated equilibria (2018)
Working Paper: The Query Complexity of Correlated Equilibria (2013)
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:arx:papers:1305.4874

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators (help@arxiv.org).