Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
From MaRDI portal
Publication:6139831
DOI10.1137/19m1242069OpenAlexW3216275777MaRDI QIDQ6139831
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
Cites Work
- Completely uncoupled dynamics and Nash equilibria
- Exponential lower bounds for finding Brouwer fixed points
- How long to equilibrium? The communication complexity of uncoupled equilibrium procedures
- A note on approximate Nash equilibria
- Polynomial algorithms for approximating Nash equilibria of bimatrix games
- New algorithms for approximate Nash equilibria in bimatrix games
- On sparse approximations to randomized strategies and convex combinations
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- The query complexity of correlated equilibria
- Communication complexity of approximate Nash equilibria
- Simple complexity from imitation games
- On the communication complexity of approximate Nash equilibria
- Non-cooperative games
- An iterative method of solving a game
- Inapproximability of Nash Equilibrium
- Distributed Methods for Computing Approximate Equilibria
- Rational Learning Leads to Nash Equilibrium
- Query Complexity of Approximate Nash Equilibria
- Settling the complexity of computing two-player Nash equilibria
- An Optimization Approach for Approximate Nash Equilibria
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Query-to-Communication Lifting for BPP
- On oblivious PTAS's for nash equilibrium
- The Complexity of Computing a Nash Equilibrium
- The communication complexity of local search
- Communication lower bounds via critical block sensitivity
- On the virtue of succinct proofs
- Probability and Computing
- Rectangles Are Nonnegative Juntas
- Settling the complexity of Nash equilibrium in congestion games
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
