The query complexity of correlated equilibria
From MaRDI portal
Abstract: We consider the complexity of finding a correlated equilibrium of an -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 . 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.
Recommendations
Cites work
- A general class of adaptive strategies
- A note on the edges of the n-cube
- A Simple Adaptive Procedure Leading to Correlated Equilibrium
- Algorithmic Game Theory
- Asymptotic analysis of a random walk on a hypercube with many dimensions
- Calibrated learning and correlated equilibrium
- Computing correlated equilibria in multi-player games
- Existence of Correlated Equilibria
- From external to internal regret
- How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
- Polynomial-time computation of exact correlated equilibrium in compact games
- Potential-based algorithms in on-line prediction and game theory
- Prediction, Learning, and Games
- Query complexity of approximate nash equilibria
- Simple adaptive strategies. From regret-matching to uncoupled dynamics. With the collaboration of Yakov Babichenko, Amotz Cahn, Yishay Mansour and David Schmeidler
- Simple strategies for large zero-sum games with applications to complexity theory
- Stochastic uncoupled dynamics and Nash equilibrium
- Subjectivity and correlation in randomized strategies
Cited in
(19)- Nash and correlated equilibria: Some complexity considerations
- Logarithmic query complexity for approximate Nash computation in large games
- On adaptive heuristics that converge to correlated equilibrium
- Learning convex partitions and computing game-theoretic equilibria from best response queries
- Pricing lotteries
- Achieving target equilibria in network routing games without knowing the latency functions
- Polynomial-time computation of exact correlated equilibrium in compact games
- Lower bounds for the query complexity of equilibria in Lipschitz games
- Query complexity of approximate equilibria in anonymous games
- Welfare-maximizing correlated equilibria using Kantorovich polynomials with sparsity
- Inapproximability of Nash equilibrium
- scientific article; zbMATH DE number 6866347 (Why is no real title available?)
- Financial Cryptography
- Communication complexity of correlated equilibrium with small support
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- Optimally Deceiving a Learning Leader in Stackelberg Games
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- Lower bounds for the query complexity of equilibria in Lipschitz games
- ``Subjectivity and correlation in randomized strategies: back to the roots
This page was built for publication: The query complexity of correlated equilibria
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1651292)
