The query complexity of correlated equilibria

DOI10.1016/j.geb.2016.11.003zbMath1400.91006arXiv1305.4874OpenAlexW2119548912MaRDI QIDQ1651292

Sergiu Hart, Noam Nisan

Publication date: 12 July 2018

Published in: Games and Economic Behavior (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.4874

zbMATH Keywords

complexityrandomized algorithmqueryquery complexitycorrelated equilibriaapproximate equilibriaregret-based

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) (n)-person games, (n>2) (91A06)

Related Items (14)

Inapproximability of Nash Equilibrium ⋮ Query Complexity of Approximate Equilibria in Anonymous Games ⋮ Communication complexity of approximate Nash equilibria ⋮ Lower bounds for the query complexity of equilibria in Lipschitz games ⋮ On adaptive heuristics that converge to correlated equilibrium ⋮ Learning convex partitions and computing game-theoretic equilibria from best response queries ⋮ Logarithmic query complexity for approximate Nash computation in large games ⋮ Pricing lotteries ⋮ Achieving target equilibria in network routing games without knowing the latency functions ⋮ Lower bounds for the query complexity of equilibria in Lipschitz games ⋮ Unnamed Item ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria ⋮ Optimally Deceiving a Learning Leader in Stackelberg Games

Cites Work

• Unnamed Item
• Stochastic uncoupled dynamics and Nash equilibrium
• How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
• Subjectivity and correlation in randomized strategies
• A note on the edges of the n-cube
• Calibrated learning and correlated equilibrium
• Potential-based algorithms in on-line prediction and game theory
• Polynomial-time computation of exact correlated equilibrium in compact games
• Simple strategies for large zero-sum games with applications to complexity theory
• Simple Adaptive Strategies
• Asymptotic analysis of a random walk on a hypercube with many dimensions
• Existence of Correlated Equilibria
• A Simple Adaptive Procedure Leading to Correlated Equilibrium
• Query complexity of approximate nash equilibria
• Algorithmic Game Theory
• Prediction, Learning, and Games
• Computing correlated equilibria in multi-player games
• A general class of adaptive strategies

This page was built for publication: The query complexity of correlated equilibria