🔖 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 *

To respond on your own website, enter the URL of your response which should contain a link to this post's permalink URL. Your response will then appear (possibly after moderation) on this page. Want to update or remove your response? Update or delete your post and re-enter your post's URL again. (Learn More)