Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Mika G\"o\"os , Aviad Rubinstein

Authors on Pith no claims yet

classification 💻 cs.CC cs.GT

keywords approximatecommunicationepsilonlowernashboundboundscomplexity

read the original abstract

We prove an $N^{2-o(1)}$ lower bound on the randomized communication complexity of finding an $\epsilon$-approximate Nash equilibrium (for constant $\epsilon>0$) in a two-player $N\times N$ game.

This paper has not been read by Pith yet.

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

discussion (0)