TY - GEN

T1 - Computational equivalence of fixed points and no regret algorithms, and convergence to equilibria

AU - Hazan, Elad

AU - Kale, Satyen

PY - 2009/12/1

Y1 - 2009/12/1

N2 - We study the relation between notions of game-theoretic equilibria which are based on stability under a set of deviations, and empirical equilibria which are reached by rational players. Rational players are modeled by players using no regret algorithms, which guarantee that their payoff in the long run is close to the maximum they could hope to achieve by consistently deviating from the algorithm's suggested action. We show that for a given set of deviations over the strategy set of a player, it is possible to efficiently approximate fixed points of a given deviation if and only if there exist efficient no regret algorithms resistant to the deviations. Further, we show that if all players use a no regret algorithm, then the empirical distribution of their plays converges to an equilibrium.

AB - We study the relation between notions of game-theoretic equilibria which are based on stability under a set of deviations, and empirical equilibria which are reached by rational players. Rational players are modeled by players using no regret algorithms, which guarantee that their payoff in the long run is close to the maximum they could hope to achieve by consistently deviating from the algorithm's suggested action. We show that for a given set of deviations over the strategy set of a player, it is possible to efficiently approximate fixed points of a given deviation if and only if there exist efficient no regret algorithms resistant to the deviations. Further, we show that if all players use a no regret algorithm, then the empirical distribution of their plays converges to an equilibrium.

UR - http://www.scopus.com/inward/record.url?scp=84858779841&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84858779841&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84858779841

SN - 160560352X

SN - 9781605603520

T3 - Advances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference

BT - Advances in Neural Information Processing Systems 20 - Proceedings of the 2007 Conference

T2 - 21st Annual Conference on Neural Information Processing Systems, NIPS 2007

Y2 - 3 December 2007 through 6 December 2007

ER -