🔖 Communication complexity of approximate Nash equilibria | arXiv

Bookmarked Communication complexity of approximate Nash equilibria (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)

Syndicated copies to:

One response on “🔖 Communication complexity of approximate Nash equilibria | arXiv”

Leave a Reply

Your email address will not be published. Required fields are marked *