The Query Complexity of Correlated Equilibria
Speaker
Noam Nisan
Date
11/12/2013 - 12:00 - 10:00Add To Calendar
2013-12-11 10:00:00
2013-12-11 12:00:00
The Query Complexity of Correlated Equilibria
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, the number of strategies of each player, and the approximation error. 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.
אוניברסיטת בר-אילן - Department of Economics
Economics.Dept@mail.biu.ac.il
Asia/Jerusalem
public
Affiliation
Hebrew University
Abstract
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, the number of strategies of each player, and the approximation error. 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 Updated Date : 01/12/2013