Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

2018/05/16 by Göös, Mika, Rubinstein, Aviad · 1 citation
#Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1805.06387

Abstract

We prove an N^2-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.

Cited by

• Protocols for Verifying Smooth Strategies in Bandits and Games

Related

• Communication complexity of approximate Nash equilibria
• Communication complexity of Nash equilibrium in potential games
• Communication Complexity of Correlated Equilibrium in Two-Player Games
• On the Communication Complexity of Approximate Nash Equilibria
• Settling the complexity of computing approximate two-player Nash\n equilibria