Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria
Not on the map. Why?
Abstract (arXiv)
We prove an N2-o(1) lower bound on the randomized communication complexity of finding an ε-approximate Nash equilibrium (for constant ε>0) in a two-player N× N game.
Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). First posted on arXiv 16 May 2018.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2021: 1; 2022: 0; 2023: 2; 2024: 1; 2025: 1; 2026: 1.
6 papers.
- 2023Fast swap regret minimization and applications to approximate correlated equilibriacited by 32
- 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
- 2023Smooth Nash Equilibria: Algorithms and Complexitycited by 3
- 2026Algorithmic Collusion and the Complexity of Information-Value-Free Equilibriacited by 1
- 2024Computational Lower Bounds for Regret Minimization in Normal-Form Gamescited by 0
- 2025Protocols for Verifying Smooth Strategies in Bandits and Gamescited by 0
- 2026Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria19 Sep 2026
- 2025Protocols for Verifying Smooth Strategies in Bandits and Games8 Jul 2025
- 2024Computational Lower Bounds for Regret Minimization in Normal-Form Games4 Nov 2024
- 2023Fast swap regret minimization and applications to approximate correlated equilibria30 Oct 2023
- 2023Smooth Nash Equilibria: Algorithms and Complexity21 Sep 2023
- 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games17 Feb 2021