@booklet {sergiuhart-tqcoce2013,
	title = {Query Complexity of Correlated Equilibria, The},
	howpublished = {Discussion Papers},
	year = {2013},
	month = {9},
	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{\textquoteright} 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.},
	url = {http://ma.huji.ac.il/hart/abs/corr-com.html},
	author = {Sergiu Hart, Noam Nisan}
}
