# Query Complexity of Correlated Equilibrium

arXiv: https://arxiv.org/abs/1306.2437 · HTML: https://mlsanity.com/paper/1306.2437/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2013.

## Built on by (most cited first, 4 of 4)

- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Barriers to Welfare Maximization with No-Regret Learning](https://mlsanity.com/paper/2411.01720/) (2024)
- [Computational Lower Bounds for Regret Minimization in Normal-Form Games](https://mlsanity.com/paper/2411.01721/) (2024)

## Abstract (arXiv)

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.