The Query Complexity of Correlated Equilibria
Authors:
Preprint
Abstract
We consider the complexity of finding a correlated equilibrium of an $n$-player game in a model that allows the algorithm to make queries on players' payoffs at pure strategy profiles. Randomized regret-based dynamics are known to yield an approximate correlated equilibrium efficiently, namely, in time that is polynomial in the number of players $n$. Here we show that both randomization and approximation are necessary: no efficient deterministic algorithm can reach even an approximate correlated equilibrium, and no efficient randomized algorithm can reach an exact correlated equilibrium. The results are obtained by bounding from below the number of payoff queries that are needed.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- How long to equilibrium? The communication complexity of uncoupled equilibrium proceduresGames and Economic Behavior, 2010
- Computing correlated equilibria in multi-player gamesJournal of the ACM, 2008
- Stochastic uncoupled dynamics and Nash equilibriumGames and Economic Behavior, 2006
- Potential-Based Algorithms in On-Line Prediction and Game TheoryMachine Learning, 2003
- A General Class of Adaptive StrategiesJournal of Economic Theory, 2001
- A Simple Adaptive Procedure Leading to Correlated EquilibriumEconometrica, 2000
- Calibrated Learning and Correlated EquilibriumGames and Economic Behavior, 1997
- Asymptotic analysis of a random walk on a hypercube with many dimensionsRandom Structures & Algorithms, 1990
- A note on the edges of the n-cubeDiscrete Mathematics, 1976
- Subjectivity and correlation in randomized strategiesJournal of Mathematical Economics, 1974