Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

05/16/2018

∙

by   Mika Göös, et al.

∙

0

∙

share

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.