skip to main content
research-article

Bounds for the Query Complexity of Approximate Equilibria

Published: 26 August 2016 Publication History

Abstract

We analyze the number of payoff queries needed to compute approximate equilibria of multi-player games. We find that query complexity is an effective tool for distinguishing the computational difficulty of alternative solution concepts, and we develop new techniques for upper- and lower bounding the query complexity. For binary-choice games, we show logarithmic upper and lower bounds on the query complexity of approximate correlated equilibrium. For well-supported approximate correlated equilibrium (a restriction where a player’s behavior must always be approximately optimal, in the worst case over draws from the distribution) we show a linear lower bound, thus separating the query complexity of well supported approximate correlated equilibrium from the standard notion of approximate correlated equilibrium.
Finally, we give a query-efficient reduction from the problem of computing an approximate well-supported Nash equilibrium to the problem of verifying a well supported Nash equilibrium, where the additional query overhead is proportional to the description length of the game. This gives a polynomial-query algorithm for computing well supported approximate Nash equilibria (and hence correlated equilibria) in concisely represented games. We identify a class of games (which includes congestion games) in which the reduction can be made not only query efficient, but also computationally efficient.

References

[1]
S. Arora, E. Hazan, and S. Kale. 2012. The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing 8, 121--164.
[2]
Y. Babichenko. 2013. Query complexity of approximate Nash equilibria. arXiv:1306.6686.
[3]
Y. Babichenko and S. Barman. 2013. Query complexity of correlated equilibrium. arXiv:1306.2437.
[4]
Y. Babichenko, S. Barman, and R. Peretz. 2013. Small-support approximate correlated equilibria. arXiv:1308.6025.
[5]
Y. Babichenko, S. Barman, and R. Peretz. 2014. Simple approximate equilibria in large games. In Proceedings of the 15th ACM Conference on Economics and Computation (EC’14). 753--770.
[6]
A. Blum, J. Jackson, T. Sandholm, and M. Zinkevich. 2004. Preference elicitation and query learning. Journal of Machine Learning Research 5, 649--667.
[7]
A. Blum and Y. Mansour. 2007. Learning, regret minimization, and equilibria. In Algorithmic Game Theory, N. Nisan, T. Roughgarden, E. Tardos, and Vijay V. Vazirani (Eds.). Cambridge University Press, New York, NY, 79--102.
[8]
X. Chen, X. Deng, and S.-H. Teng. 2009. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM 56, 3, 14:1--14:57.
[9]
W. Conen and T. Sandholm. 2001. Preference elicitation in combinatorial auctions. In Proceedings of the 3rd ACM Conference on Electronic Commerce (EC’01). 256--259.
[10]
V. Conitzer. 2009. Eliciting single-peaked preferences using comparison queries. Journal of Artificial Intelligence Research 35, 161--191.
[11]
C. Daskalakis, P. W. Goldberg, and C. H. Papadimitriou. 2009. The complexity of computing a Nash equilibrium. SIAM Journal on Computing 39, 1, 195--259.
[12]
J. Fearnley, M. Gairing, P. W. Goldberg, and R. Savani. 2013. Learning equilibria of games via payoff queries. In Proceedings of the 14th ACM Conference on Electronic Commerce (EC’13). 397--414.
[13]
J. Fearnley, P. W. Goldberg, R. Savani, and T. B. Sørensen. 2012. Approximate well-supported Nash equilibria below two-thirds. In Algorithmic Game Theory. Lecture Notes in Computer Science, Vol. 7615. Springer, 108--119.
[14]
J. Fearnley and R. Savani. 2014. Finding approximate Nash equilibria of bimatrix games via payoff queries. In Proceedings of the 15th ACM Conference on Economics and Computation (EC’14). 657--674.
[15]
Y. Freund and R. Schapire. 1999. Adaptive game playing using multiplicative weights. Games and Economic Behavior 29, 79--103.
[16]
P. W. Goldberg and A. Pastink. 2014. On the communication complexity of approximate Nash equilibria. Games and Economic Behavior 85, 19--31.
[17]
P. W. Goldberg and S. Turchetta. 2014. Query complexity of approximate equilibria in anonymous games. arXiv:1412.6455.
[18]
A. Gupta, A. Roth, and J. Ullman. 2012. Iterative constructions and private data release. In Proceedings of the 9th International Conference on Theory of Cryptography (TCC’12). 339--356.
[19]
M. Hardt and G. Rothblum. 2010. A multiplicative weights mechanism for privacy-preserving data analysis. In Proceedings of the 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS’10). 61--70.
[20]
S. Hart and Y. Mansour. 2010. How long to equilibrium? The communication complexity of uncoupled equilibrium procedures. Games and Economic Behavior 69, 1, 107--126.
[21]
S. Hart and A. Mas-Colell. 2000. A simple adaptive procedure leading to correlated equilibrium. Econometrica 68, 5, 1127--1150.
[22]
S. Hart and N. Nisan. 2013. The query complexity of correlated equilibria. arXiv:1305.4874.
[23]
M. Kearns, M. M. Pai, A. Roth, and J. Ullman. 2013. Mechanism design in large games: Incentives and privacy. arXiv:1207.4084.
[24]
S. C. Kontogiannis and P. G. Spirakis. 2010. Well supported approximate equilibria in bimatrix games. Algorithmica 57, 4, 653--667.
[25]
C. H. Papadimitriou and T. Roughgarden. 2008. Computing correlated equilibria in multi-player games. Journal of the ACM 55, 3, Article No. 14.
[26]
A. Roth and T. Roughgarden. 2010. Interactive privacy via the median mechanism. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC’10). ACM, New York, NY, 765--774.
[27]
H. Tsaknakis and P. G. Spirakis. 2008. An optimization approach for approximate Nash equilibria. Internet Mathematics 5, 4, 365--382.

Cited By

View all
  • (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
  • (2023)PPAD-complete approximate pure Nash equilibria in Lipschitz gamesTheoretical Computer Science10.1016/j.tcs.2023.114218980(114218)Online publication date: Nov-2023
  • (2023)Lower bounds for the query complexity of equilibria in Lipschitz gamesTheoretical Computer Science10.1016/j.tcs.2023.113931962(113931)Online publication date: Jun-2023
  • Show More Cited By

Index Terms

  1. Bounds for the Query Complexity of Approximate Equilibria

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Transactions on Economics and Computation
      ACM Transactions on Economics and Computation  Volume 4, Issue 4
      Special Issue on EC'14
      August 2016
      147 pages
      ISSN:2167-8375
      EISSN:2167-8383
      DOI:10.1145/2983294
      Issue’s Table of Contents
      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 the author(s) 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].

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 26 August 2016
      Accepted: 01 November 2015
      Revised: 01 July 2015
      Received: 01 January 2015
      Published in TEAC Volume 4, Issue 4

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. Payoff queries
      2. correlated equilibrium

      Qualifiers

      • Research-article
      • Research
      • Refereed

      Funding Sources

      • EPSRC
      • NSF CAREER award under NSF
      • Google Faculty Research award

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)26
      • Downloads (Last 6 weeks)3
      Reflects downloads up to 20 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (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
      • (2023)PPAD-complete approximate pure Nash equilibria in Lipschitz gamesTheoretical Computer Science10.1016/j.tcs.2023.114218980(114218)Online publication date: Nov-2023
      • (2023)Lower bounds for the query complexity of equilibria in Lipschitz gamesTheoretical Computer Science10.1016/j.tcs.2023.113931962(113931)Online publication date: Jun-2023
      • (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
      • (2022)PPAD-Complete Pure Approximate Nash Equilibria in Lipschitz GamesAlgorithmic Game Theory10.1007/978-3-031-15714-1_10(169-186)Online publication date: 12-Sep-2022
      • (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
      • (2021)Near-Optimal Communication Lower Bounds for Approximate Nash EquilibriaSIAM Journal on Computing10.1137/19M124206952:6(FOCS18-316-FOCS18-348)Online publication date: 30-Nov-2021
      • (2021)Lower Bounds for the Query Complexity of Equilibria in Lipschitz GamesAlgorithmic Game Theory10.1007/978-3-030-85947-3_9(124-139)Online publication date: 14-Sep-2021
      • (2020)Optimally deceiving a learning leader in stackelberg gamesProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3497456(20624-20635)Online publication date: 6-Dec-2020
      • (2020)Communication complexity of Nash equilibrium in potential games (extended abstract)2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS46700.2020.00137(1439-1445)Online publication date: Nov-2020
      • Show More Cited By

      View Options

      Login options

      Full Access

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media