Query Complexity of Correlated Equilibrium
Preprint
Abstract
We study lower bounds on the query complexity of determining correlated equilibrium. In particular, we consider a query model in which an n-player game is specified via a black box that returns players' utilities at pure action profiles. In this model we establish that in order to compute a correlated equilibrium any deterministic algorithm must query the black box an exponential (in n) number of times.Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Settling the complexity of computing two-player Nash equilibriaJournal of the ACM, 2009
- Computing correlated equilibria in multi-player gamesJournal of the ACM, 2008
- Existence of Sparsely Supported Correlated EquilibriaEconomic Theory, 2006
- A Simple Adaptive Procedure Leading to Correlated EquilibriumEconometrica, 2000