research-article

Public Access

Communication complexity of approximate Nash equilibria

Authors:

Yakov Babichenko,

Aviad RubinsteinAuthors Info & Claims

STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

Pages 878 - 889

https://doi.org/10.1145/3055399.3055407

Published: 19 June 2017 Publication History

Abstract

For a constant ϵ, we prove a (N) lower bound on the (randomized) communication complexity of ϵ-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 (ϵ,ϵ)-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least (1-ϵ)-fraction of the players are ϵ-best replying.

Supplementary Material

MP4 File (d3_sb_t8.mp4)

Download
151.43 MB

References

[1]

{AGJ + 17} Anurag Anshu, Naresh B Goud, Rahul Jain, Srijita Kundu, and Priyanka Mukhopadhyay. Lifting randomized query complexity to randomized communication complexity. arXiv preprint arXiv:1703.07521, 2017.

[2]

{AUY83} Alfred V. Aho, Jeffrey D. Ullman, and Mihalis Yannakakis. On notions of information transfer in VLSI circuits. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 133–139, 1983.

Digital Library

[3]

{Bab12} Yakov Babichenko. Completely uncoupled dynamics and nash equilibria. Games and Economic Behavior, 76(1):1–14, 2012.

[4]

{Bab14} Yakov Babichenko. Query complexity of approximate nash equilibria. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 535–544. ACM, 2014.

Digital Library

[5]

{BB15} Yakov Babichenko and Siddharth Barman. Query complexity of correlated equilibrium. ACM Transactions on Economics and Computation, 3(4):22, 2015.

Digital Library

[6]

{BPR16} Yakov Babichenko, Christos H. Papadimitriou, and Aviad Rubinstein. Can almost everybody be almost happy? In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 1–9, 2016.

Digital Library

[7]

{BR16} Yakov Babichenko and Aviad Rubinstein. Communication complexity of approximate nash equilibria. arXiv preprint arXiv:1608.06580, 2016.

[8]

{CCT15} Xi Chen, Yu Cheng, and Bo Tang. Well-supported versus approximate nash equilibria: Query complexity of large games. arXiv preprint arXiv:1511.00785, 2015.

[9]

{CDF + 15} Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis, John Fearnley, Marcin Jurdzinski, and Rahul Savani. Distributed methods for computing approximate equilibria. CoRR, abs/1512.03315, 2015.

[10]

{CDT09} Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. J. ACM, 56(3), 2009.

Digital Library

[11]

{CS04} Vincent Conitzer and Tuomas Sandholm. Communication complexity as a lower bound for learning in games. In Proceedings of the twenty-first international conference on Machine learning, page 24. ACM, 2004.

Digital Library

[12]

{DGP09} Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou. The complexity of computing a nash equilibrium. SIAM Journal on Computing, 39(1):195–259, 2009.

Digital Library

[13]

{FGGS13} John Fearnley, Martin Gairing, Paul W Goldberg, and Rahul Savani. Learning equilibria of games via payoff queries. In EC, pages 397–414, 2013.

Digital Library

[14]

{FY06} Dean P. Foster and H. Peyton Young. Regret testing: learning to play Nash equilibrium without knowing you have an opponent. Theoretical Economics, 1(3):341–367, September 2006.

[15]

{GL07} Fabrizio Germano and Gabor Lugosi. Global nash convergence of foster and young’s regret testing. Games and Economic Behavior, 60(1):135–154, 2007.

[16]

{Göö16} Mika Göös, August 2016. Private Communication.

[17]

{GP14} Paul W Goldberg and Arnoud Pastink. On the communication complexity of approximate nash equilibria. Games and Economic Behavior, 85:19–31, 2014.

[18]

{GPW17} Mika Göös, Toniann Pitassi, and Thomas Watson. Query-tocommunication lifting for bpp. arXiv preprint arXiv:1703.07666, 2017.

[19]

{GS17} Anat Ganor and Karthik C. Srikanta. Communication complexity of correlated equilibrium in two-player games. arXiv preprint arXiv:1704.01104, 2017.

[20]

{HM10} Sergiu Hart and Yishay Mansour. How long to equilibrium? the communication complexity of uncoupled equilibrium procedures. Games and Economic Behavior, 69(1):107–126, 2010.

[21]

{HMC03} Sergiu Hart and Andreu Mas-Colell. Uncoupled dynamics do not lead to nash equilibrium. American Economic Review, 93(5):1830–1836, 2003.

[22]

{HMC06} Sergiu Hart and Andreu Mas-Colell. Stochastic uncoupled dynamics and nash equilibrium. Games and Economic Behavior, 57(2):286–303, 2006.

[23]

{HMC13} Sergiu Hart and Andreu Mas-Colell. Simple adaptive strategies: from regret-matching to uncoupled dynamics, volume 4. World Scientific, 2013.

[24]

{HN13} Sergiu Hart and Noam Nisan. The query complexity of correlated equilibria. arXiv preprint arXiv:1305.4874, 2013.

[25]

{HPV89} Michael D. Hirsch, Christos H. Papadimitriou, and Stephen A. Vavasis. Exponential lower bounds for finding brouwer fix points. J. Complexity, 5(4):379–416, 1989.

Digital Library

[26]

{ JLB15} Albert Xin Jiang and Kevin Leyton-Brown. Polynomial-time computation of exact correlated equilibrium in compact games. Games and Economic Behavior, 91:347–359, 2015.

[27]

{KL93} Ehud Kalai and Ehud Lehrer. Rational learning leads to nash equilibrium. Econometrica: Journal of the Econometric Society, pages 1019–1045, 1993.

[28]

{KRW95} Mauricio Karchmer, Ran Raz, and Avi Wigderson. Super-logarithmic depth lower bounds via the direct sum in communication complexity. Computational Complexity, 5(3-4):191–204, 1995.

[29]

{LMM03} Richard J Lipton, Evangelos Markakis, and Aranyak Mehta. Playing large games using simple strategies. In Proceedings of the 4th ACM conference on Electronic commerce, pages 36–41. ACM, 2003.

Digital Library

[30]

{MT05} Andrew McLennan and Rabee Tourky. From imitation games to kakutani. Manuscript, available at http://www.econ.umn.edu/ mclennan/Papers/papers.html, 2005.

[31]

{Nas51} John Nash. Non-cooperative games. Annals of mathematics, pages 286–295, 1951.

[32]

{Nis09a} Noam Nisan. Communication complexity of mixed-nash equilibria. https://agtb.wordpress.com/2009/09/28/communication-complexityof-mixed-nash-equilibria/, 2009.

[33]

{Nis09b} Noam Nisan. Economists and complexity. https://agtb.wordpress.com/2009/11/27/economists-and-complexity/, 2009.

[34]

{PR08} Christos H Papadimitriou and Tim Roughgarden. Computing correlated equilibria in multi-player games. Journal of the ACM ( JACM), 55(3):14, 2008.

Digital Library

[35]

{RM99} Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. volume 19, pages 403–435, 1999.

[36]

{Rou14} Tim Roughgarden. Barriers to near-optimal equilibria. pages 71–80, 2014.

[37]

{Rub14} Aviad Rubinstein. Computational complexity of approximate nash equilibrium in large games. arXiv preprint arXiv:1405.0524, 2014.

[38]

{Rub15} Aviad Rubinstein. Inapproximability of nash equilibrium. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, pages 409–418. ACM, 2015.

Digital Library

[39]

{Rub16} Aviad Rubinstein. Settling the complexity of computing approximate two-player nash equilibria. In To appear in FOCS, 2016.

[40]

{RW90} Ran Raz and Avi Wigderson. Monotone circuits for matching require linear depth. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA, pages 287–292, 1990.

Digital Library

[41]

{RW16} Tim Roughgarden and Omri Weinstein. On the communication complexity of approximate fixed points. In Electronic Colloquium on Computational Complexity (ECCC), volume 23, page 55, 2016.

[42]

{Shm12} Eran Shmaya. Brouwer implies nash implies brouwer. http://theoryclass.wordpress.com/2012/01/05/brouwer-implies-nashimplies-brouwer/, 2012.

[43]

{You04} H Peyton Young. Strategic learning and its limits. OUP Oxford, 2004.

[44]

{You09} H Peyton Young. Learning by trial and error. Games and economic behavior, 65(2):626–643, 2009.

Cited By

Peng BRubinstein AMohar BShinkar IO'Donnell R(2024)Fast Swap Regret Minimization and Applications to Approximate Correlated EquilibriaProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649691(1223-1234)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649691
Pan XWu SChen JZhou XChen XXin ZDing PXiao R(2024)Toward Efficient Biofuel Production: A Review of Online Upgrading Methods for Biomass PyrolysisEnergy & Fuels10.1021/acs.energyfuels.4c0413138:20(19414-19441)Online publication date: 1-Oct-2024
https://doi.org/10.1021/acs.energyfuels.4c04131
Foster DGolowich NKakade SKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Hardness of independent learning and sparse equilibrium computation in Markov gamesProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618817(10188-10221)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618817
Show More Cited By

Index Terms

Communication complexity of approximate Nash equilibria
1. Theory of computation
  1. Computational complexity and cryptography
    1. Communication complexity
  2. Theory and algorithms for application domains
    1. Algorithmic game theory and mechanism design
      1. Convergence and learning in games
      2. Exact and approximate computation of equilibria

Recommendations

Multi-player Approximate Nash Equilibria
AAMAS '17: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems

In this paper we study the complexity of finding approximate Nash equilibria in multi-player normal-form games. First, for any constant number m, we present a polynomial-time algorithm for computing a relative (1 - 1(1+(m-1)^m))-Nash equilibrium in ...
Computing Approximate Nash Equilibria in Polymatrix Games

In an $$\epsilon $$∈-Nash equilibrium, a player can gain at most $$\epsilon $$∈ by unilaterally changing his behavior. For two-player (bimatrix) games with payoffs in [0, 1], the best-known $$\epsilon $$∈ achievable in polynomial time is 0.3393 (...
Zero-Sum Game Techniques for Approximate Nash Equilibria
AAMAS '17: Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems

We apply existing, and develop new, zero-sum game techniques for designing polynomial-time algorithms to compute additive approximate Nash equilibria in bimatrix games. In particular, we give a polynomial-time algorithm that given an arbitrary bimatrix ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing

June 2017

1268 pages

ISBN:9781450345286

DOI:10.1145/3055399

General Chairs:
Hamed Hatami
McGill University
,
Pierre McKenzie
Université de Montréal
,
Program Chair:
Valerie King
University of Victoria

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 June 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '17

Sponsor:

SIGACT

STOC '17: Symposium on Theory of Computing

June 19 - 23, 2017

Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
562
Total Downloads

Downloads (Last 12 months)134
Downloads (Last 6 weeks)29

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Peng BRubinstein AMohar BShinkar IO'Donnell R(2024)Fast Swap Regret Minimization and Applications to Approximate Correlated EquilibriaProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649691(1223-1234)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649691
Pan XWu SChen JZhou XChen XXin ZDing PXiao R(2024)Toward Efficient Biofuel Production: A Review of Online Upgrading Methods for Biomass PyrolysisEnergy & Fuels10.1021/acs.energyfuels.4c0413138:20(19414-19441)Online publication date: 1-Oct-2024
https://doi.org/10.1021/acs.energyfuels.4c04131
Foster DGolowich NKakade SKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Hardness of independent learning and sparse equilibrium computation in Markov gamesProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618817(10188-10221)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618817
Birmpas GGan JHollender AMarmolejo-Cossío FRajgopal NVoudouris A(2022)Optimally Deceiving a Learning Leader in Stackelberg GamesJournal of Artificial Intelligence Research10.1613/jair.1.1254272(507-531)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1613/jair.1.12542
Anagnostides IDaskalakis CFarina GFishelson MGolowich NSandholm TLeonardi SGupta A(2022)Near-optimal no-regret learning for correlated equilibria in multi-player general-sum gamesProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520031(736-749)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520031
Pisauro MFouragnan EArabadzhiyska DApps MPhiliastides M(2022)Neural implementation of computational mechanisms underlying the continuous trade-off between cooperation and competitionNature Communications10.1038/s41467-022-34509-w13:1Online publication date: 11-Nov-2022
https://doi.org/10.1038/s41467-022-34509-w
Ganor AS. KPálvölgyi D(2021)On Communication Complexity of Fixed Point ComputationACM Transactions on Economics and Computation10.1145/34850049:4(1-27)Online publication date: 16-Oct-2021
https://dl.acm.org/doi/10.1145/3485004
Cseh ÁJuhos A(2021)Pairwise Preferences in the Stable Marriage ProblemACM Transactions on Economics and Computation10.1145/34344279:1(1-28)Online publication date: 2-Jan-2021
https://dl.acm.org/doi/10.1145/3434427
Giannakopoulos YPoças DZhu K(2021)Optimal Pricing for MHR and λ-regular DistributionsACM Transactions on Economics and Computation10.1145/34344239:1(1-28)Online publication date: 2-Jan-2021
https://dl.acm.org/doi/10.1145/3434423
Goldberg PMarmolejo-Cossío F(2021)Learning Convex Partitions and Computing Game-theoretic Equilibria from Best-response QueriesACM Transactions on Economics and Computation10.1145/34344129:1(1-36)Online publication date: 2-Jan-2021
https://dl.acm.org/doi/10.1145/3434412
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents