Communication complexity of approximate Nash equilibria by Yakov Babichenko, Aviad Rubinstein (arXiv)

For a constant ϵ, we prove a poly(N) lower bound on the (randomized) communication complexity of ϵ-Nash equilibrium in two-player NxN games. For n-player binary-action games we prove an exp(n) lower bound for the (randomized) communication complexity of (ϵ,ϵ)-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least (1−ϵ)-fraction of the players are ϵ-best replying.

Suggested by In Game Theory, No Clear Path to Equilibrium by Erica Klarreich (Quanta Magazine)

Related

Author: Chris Aldrich

I’m a biomedical and electrical engineer with interests in information theory, complexity, evolution, genetics, signal processing, theoretical mathematics, and big history.

I’m also a talent manager-producer-publisher in the entertainment industry with expertise in representation, distribution, finance, production, content delivery, and new media.
View all posts by Chris Aldrich