Query Complexity of Correlated Equilibrium
Authors:
Open Access
- 31 July 2015
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Economics and Computation
- Vol. 3 (4) , 1-9
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
Funding Information
- Linde/SISL Postdoctoral Fellowship
- NSF (CNS-0846025 and CCF-1101470)
This publication has 19 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
- Matching algorithmic bounds for finding a Brouwer fixed pointJournal of the ACM, 2008
- Adaptive HeuristicsEconometrica, 2005
- A Simple Adaptive Procedure Leading to Correlated EquilibriumEconometrica, 2000
- Asymptotic calibrationBiometrika, 1998
- The Weighted Majority AlgorithmInformation and Computation, 1994
- Correlated Equilibrium as an Expression of Bayesian RationalityEconometrica, 1987
- Subjectivity and correlation in randomized strategiesJournal of Mathematical Economics, 1974
- Non-Cooperative GamesAnnals of Mathematics, 1951