skip to main content
10.1145/2600057.2602845acmconferencesArticle/Chapter ViewAbstractPublication PagesecConference Proceedingsconference-collections
research-article

Bounds for the query complexity of approximate equilibria

Published: 01 June 2014 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]
Arora, E. Hazan, and S. Kale. 2012.s The Multiplicative Weights Update Method: a Meta-Algorithm and Applications. Theory of Computing 8 (May 2012), 121--164.
[2]
Y. Babichenko. 2013. Query Complexity of Approximate Nash Equilibria. ArXiv tech rept. 1306.6686 (2013).
[3]
Y. Babichenko and S. Barman. 2013. Query complexity of correlated equilibrium. ArXiv tech rept. 1306.2437 (2013).
[4]
Y. Babichenko, S. Barman, and R. Peretz. 2013. Small-Support Approximate Correlated Equilibria. ArXiv tech rept. 1308.6025 (2013).
[5]
A. Blum, J. Jackson, T. Sandholm, and M. Zinkevich. 2004. Preference Elicitation and Query Learning. Journal of Machine Learning Research 5 (Dec. 2004), 649--667.
[6]
A. Blum and Y. Mansour. 2007. Learning, Regret Minimization and Equilibria. In Algorithmic Game Theory, Cambridge University Press (2007).
[7]
X. Chen, X. Deng, and S-H. Teng. 2009. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM 56, 3 (2009), 14:1--14:57.
[8]
W. Conen and T. Sandholm. 2001. Preference Elicitation in Combinatorial Auctions {Extended Abstract}. In Proceedings of the ACM Conference on Electronic Commerce. 256--259.
[9]
V. Conitzer. 2009. Eliciting Single-Peaked Preferences Using Comparison Queries. Journal of Artificial Intelligence Research 35 (2009), 161--191.
[10]
C. Daskalakis, P.W. Goldberg, and C.H. Papadimitriou. 2009. The Complexity of Computing a Nash Equilibrium. SIAM J. Comput. 39, 1 (2009), 195--259.
[11]
J. Fearnley, M. Gairing, P.W. Goldberg, and R. Savani. 2013. Learning Equilibria of Games via Payoff Queries. In Procs. of 14th ACM EC. 397--414.
[12]
J. Fearnley, P.W Goldberg, R. Savani, and T.B. Sørensen. 2012. Approximate Well-supported Nash Equilibria Below Two-thirds. In Procs of the 5th SAGT LNCS 7615. 108--119.
[13]
J. Fearnley and R. Savani. 2013. Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries. Arxiv rept. http://arxiv.org/abs/1310.7419 (2013).
[14]
Y. Freund and R. Schapire. 1999. Adaptive game playing using multiplicative weights. Games and Economic Behavior 29 (Oct. 1999), 79--103.
[15]
P.W. Goldberg and A. Pastink. 2014. On the Communication Complexity of Approximate Nash Equilibria. Games and Economic Behavior 85 (May 2014), 19--31.
[16]
A. Gupta, A. Roth, and J. Ullman. 2012. Iterative Constructions and Private Data Release. In Procs of the 9th TCC. 339--356.
[17]
M. Hardt and G. Rothblum. 2010. A multiplicative weights mechanism for privacy-preserving data analysis. In Procs of the 51st FOCS. 61--70.
[18]
S. Hart and Y. Mansour. 2010. How long to equilibrium' The communication complexity of uncoupled equilibrium procedures. Games and Economic Behavior 69, 1 (2010), 107--126.
[19]
S. Hart and A. Mas-Colell. 2000. A Simple Adaptive Procedure Leading to Correlated Equilibrium. Econometrica 68, 5 (Sept. 2000), 1127--1150.
[20]
S. Hart and N. Nisan. 2013. The Query Complexity of Correlated Equilibria. ArXiv tech rept. 1305.4874 (2013).
[21]
M. Kearns, M.M. Pai, A. Roth, and J. Ullman. 2013. Mechanism Design in Large Games: Incentives and Privacy. Arxiv rept. http://arxiv.org/abs/1207.4084 (2013).
[22]
S.C. Kontogiannis and P.G. Spirakis. 2010. Well Supported Approximate Equilibria in Bimatrix Games. Algorithmica 57, 4 (2010), 653--667.
[23]
C.H. Papadimitriou. 2005. Computing correlated equilibria in multi-player games. In Procs. of the 37th STOC. ACM. 49--56.
[24]
A. Roth and T. Roughgarden. 2010. Interactive Privacy via the Median Mechanism. In Procs. of the 42nd STOC. ACM. 765--774.
[25]
H. Tsaknakis and P.G. Spirakis. 2008. An Optimization Approach for Approximate Nash Equilibria. Internet Mathematics 5, 4 (2008), 365--382.

Cited By

View all

Index Terms

  1. Bounds for the query complexity of approximate equilibria

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    EC '14: Proceedings of the fifteenth ACM conference on Economics and computation
    June 2014
    1028 pages
    ISBN:9781450325653
    DOI:10.1145/2600057
    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].

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 01 June 2014

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. approximate equilibrium
    2. correlated equilibrium
    3. payoff queries

    Qualifiers

    • Research-article

    Funding Sources

    Conference

    EC '14
    Sponsor:
    EC '14: ACM Conference on Economics and Computation
    June 8 - 12, 2014
    California, Palo Alto, USA

    Acceptance Rates

    EC '14 Paper Acceptance Rate 80 of 290 submissions, 28%;
    Overall Acceptance Rate 664 of 2,389 submissions, 28%

    Upcoming Conference

    EC '25
    The 25th ACM Conference on Economics and Computation
    July 7 - 11, 2025
    Stanford , CA , USA

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

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

    Other Metrics

    Citations

    Cited By

    View all
    • (2019)Distributed Methods for Computing Approximate EquilibriaAlgorithmica10.1007/s00453-018-0465-y81:3(1205-1231)Online publication date: 1-Mar-2019
    • (2019)Logarithmic Query Complexity for Approximate Nash Computation in Large GamesTheory of Computing Systems10.1007/s00224-018-9851-863:1(26-53)Online publication date: 1-Jan-2019
    • (2017)Learning Game-Theoretic Equilibria Via Query ProtocolsExtended Abstracts Summer 201510.1007/978-3-319-51753-7_11(67-72)Online publication date: 28-Feb-2017
    • (2016)Bounds for the Query Complexity of Approximate EquilibriaACM Transactions on Economics and Computation10.1145/29565824:4(1-25)Online publication date: 26-Aug-2016
    • (2016)Query Complexity of Approximate Nash EquilibriaJournal of the ACM10.1145/290873463:4(1-24)Online publication date: 10-Oct-2016
    • (2016)Settling the Complexity of Computing Approximate Two-Player Nash Equilibria2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2016.35(258-265)Online publication date: Oct-2016
    • (2016)Distributed Methods for Computing Approximate EquilibriaProceedings of the 12th International Conference on Web and Internet Economics - Volume 1012310.1007/978-3-662-54110-4_2(15-28)Online publication date: 11-Dec-2016
    • (2016)Logarithmic Query Complexity for Approximate Nash Computation in Large GamesAlgorithmic Game Theory10.1007/978-3-662-53354-3_1(3-14)Online publication date: 1-Sep-2016
    • (2015)Learning equilibria of games via payoff queriesThe Journal of Machine Learning Research10.5555/2789272.288679216:1(1305-1344)Online publication date: 1-Jan-2015
    • (2015)Query Complexity of Correlated EquilibriumACM Transactions on Economics and Computation10.1145/27856683:4(1-9)Online publication date: 31-Jul-2015
    • Show More Cited By

    View Options

    Login options

    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