The Query Complexity of Correlated Equilibria
Sergiu Hart and Noam Nisan
We consider the complexity of finding a Correlated Equilibrium in an
game in a model that allows the algorithm to make queries for players'
pure strategy profiles. Many randomized regret-matching dynamics are
yield an approximate correlated equilibrium quickly: in time that is
the number of players, n, the number of strategies of each player,
and the approximation error, 1/ε.
Here we show that both randomization and
are necessary: no efficient deterministic algorithm can reach even an
equilibrium and no efficient randomized algorithm can reach an exact
© Sergiu Hart