首页|Communication complexity of approximate Nash equilibria
Communication complexity of approximate Nash equilibria
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
For a constant c, we prove a poly(N) lower bound on the (randomized) communication complexity of c-Nash equilibrium in two-player N x N games. For n-player binary-action games we prove an exp(n) lower bound for the (randomized) communication complexity of (c, 0-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least (1 - 0-fraction of the players are c-best replying. (c) 2020 Elsevier Inc. All rights reserved.
Communication complexityApproximate Nash equilibriaConvergence rate of uncoupled dynamicsUNCOUPLED DYNAMICS
NSTL
Elsevier
