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