Citation:
Sergiu Hart, N. N. . (2013). Query Complexity of Correlated Equilibria, The. Discussion Papers. presented at the 9. Retrieved from http://ma.huji.ac.il/hart/abs/corr-com.html
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.