###
The Query Complexity of Correlated Equilibria

Sergiu Hart and Noam Nisan

**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.

**Last modified:**

**© Sergiu Hart**