Query Complexity of Correlated Equilibrium

Yakov Babichenko · Siddharth Barman

35 citations0/0 files storedACM Transactions on Economics and Computation

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Game Theory and Applications Complexity and Algorithms in Graphs Game Theory and Voting Systems

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.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 35 citations exist upstream.

References

1951Non-Cooperative Games 1989Non-cooperative games 1974Subjectivity and correlation in randomized strategies 1987Correlated Equilibrium as an Expression of Bayesian Rationality 2000A Simple Adaptive Procedure Leading to Correlated Equilibrium 2009The Complexity of Computing a Nash Equilibrium 2004Strategic Learning and its Limits 2008Computing correlated equilibria in multi-player games

Cited by

2014Query complexity of approximate nash equilibria

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.