Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

DOI10.1137/19M1242069MaRDI QIDQ6139831OpenAlexFDO

Authors Mika Göös, Aviad Rubinstein

Publication date 19 December 2023

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/19m1242069

zbMATH Keywords

game theoryNash equilibriumcommunication complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05)

Cites work

• scientific article; zbMATH DE number 6866347 (Why is no real title available?)
• scientific article; zbMATH DE number 3069635 (Why is no real title available?)
• A note on approximate Nash equilibria
• An iterative method of solving a game
• An optimization approach for approximate Nash equilibria
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Communication lower bounds via critical block sensitivity
• Completely uncoupled dynamics and Nash equilibria
• Complexity theory, game theory, and economics: the Barbados lectures
• Distributed Methods for Computing Approximate Equilibria
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Exponential lower bounds for finding Brouwer fixed points
• From external to internal regret
• How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
• Inapproximability of Nash equilibrium
• Learning equilibria of games via payoff queries
• New algorithms for approximate Nash equilibria in bimatrix games
• Non-cooperative games
• On oblivious PTAS's for nash equilibrium
• On sparse approximations to randomized strategies and convex combinations
• On the virtue of succinct proofs
• Polynomial algorithms for approximating Nash equilibria of bimatrix games
• Probability and Computing
• Query complexity of approximate Nash equilibria
• Query-to-communication lifting for BPP
• Rational Learning Leads to Nash Equilibrium
• Rectangles are nonnegative juntas
• Settling the complexity of Nash equilibrium in congestion games
• Settling the complexity of computing two-player Nash equilibria
• Simple complexity from imitation games
• The communication complexity of local search
• The complexity of computing a Nash equilibrium
• The query complexity of correlated equilibria

This page was built for publication: Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139831)