###
The Query Complexity of Correlated Equilibria

Sergiu Hart and Noam Nisan

**Abstract**

We consider the complexity of finding a *correlated equilibrium*
of an
*n*-player
game in a model that allows the algorithm to make queries
on
players' payoffs at
pure strategy profiles. Randomized regret-based dynamics are
known to
yield an approximate correlated equilibrium efficiently, 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.
The results are obtained by bounding from below the number of payoff
queries that are needed.

- First version: May 2013
- http://arxiv.org/abs/1305.4874
- The Hebrew University of Jerusalem, Center for Rationality DP-647,
September 2013
- Revised: September 2015
- Revised: May 2016
**Games and Economic Behavior**, forthcoming

**Last modified:**

**© Sergiu Hart**