HackerPapers

arXiv:1608.06580cs.GT

Communication complexity of approximate Nash equilibria

Yakov Babichenko, Aviad Rubinstein

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

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.

arXiv comments
Second revision extends the lower bounds to randomized communication
Journal reference
DOI
Subjects
cs.GTComputer Science and Game Theory cs.CCComputational Complexity

On Hacker News

Linked by 1 identifiable commenter in 3 comments across 3 threads, from Oct 2017 to Oct 2020. Found in 2 HN submissions from Aug 2017 to Oct 2017. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments3 threads

  1. Markets are efficient if and only if P=NP (2010) 1 comment

    • Yeah, even with unbounded computational power, Nash equilibria are communication-hard; i.e., you need exponentially many bits for an n-player game to converge to an equilibrium, even when all players have unbounded computational power. See https://arxiv.org/pdf/1608.06580.pdf.

      LolWolfView on HNParent context

  2. What concept would improve everybody's cognitive toolkit? Kayfabe (2011) 1 comment

    • Upvoted due to the interesting story, but the point is conceptually unclear (at least to me, but I'm quite slow) how would this improve my cognitive toolkit? I understand the (one) example presented apart from wrestling, but it is not quite obvious that the actual framework of…

      LolWolfView on HNParent context

  3. MIT Economist Has a New Theory of Finance 1 comment

    • I've seen this paper enough to warrant a comment. The paper makes no reduction that the market is computing in P, so it's unclear to me how this conclusion of P=NP iff EMH is warranted by the paper. Perhaps more clearly showing the connection between 'complexity' in the general…

      LolWolfView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.