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