Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
From MaRDI portal
Publication:5020727
DOI10.1137/19M1242069OpenAlexW3216275777MaRDI QIDQ5020727
Publication date: 7 January 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.06387
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
