The Query Complexity of Correlated Equilibria
Sergiu Hart and Noam Nisan
We consider the complexity of finding a correlated equilibrium
game in a model that allows the algorithm to make queries
players' payoffs at
pure strategy profiles. Randomized regret-based dynamics are
yield an approximate correlated equilibrium efficiently, namely,
in time that is
the number of players, n.
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
The results are obtained by bounding from below the number of payoff
queries that are needed.
© Sergiu Hart