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’ payoffs at pure strategy profiles. Randomized regret-based dynamics are known to yield an approximate correlated equilibrium quickly, 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. Joint work with Noam Nisan.