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 Simple Adaptive Procedure Leading to Correlated Equilibrium
- A general class of adaptive strategies
- A note on the edges of the n-cube
- 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)- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- scientific article; zbMATH DE number 6866347 (Why is no real title available?)
- Logarithmic query complexity for approximate Nash computation in large games
- Financial Cryptography
- Query complexity of approximate equilibria in anonymous games
- Achieving target equilibria in network routing games without knowing the latency functions
- Inapproximability of Nash equilibrium
- Nash and correlated equilibria: Some complexity considerations
- Pricing lotteries
- ``Subjectivity and correlation in randomized strategies: back to the roots
- Optimally Deceiving a Learning Leader in Stackelberg Games
- Lower bounds for the query complexity of equilibria in Lipschitz games
- Polynomial-time computation of exact correlated equilibrium in compact games
- On adaptive heuristics that converge to correlated equilibrium
- Welfare-maximizing correlated equilibria using Kantorovich polynomials with sparsity
- Learning convex partitions and computing game-theoretic equilibria from best response queries
- Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
- Communication complexity of correlated equilibrium with small support
- Lower bounds for the query complexity of equilibria in Lipschitz games
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)
