More Web Proxy on the site http://driver.im/

research-article

Learning equilibria of games via payoff queries

Authors:

Martin Gairing,

Rahul SavaniAuthors Info & Claims

EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

Pages 397 - 414

https://doi.org/10.1145/2492002.2482558

Published: 16 June 2013 Publication History

Abstract

A recent body of experimental literature has studied empirical game-theoretical analysis, in which we have partial knowledge of a game, consisting of observations of a subset of the pure-strategy profiles and their associated payoffs to players. The aim is to find an exact or approximate Nash equilibrium of the game, based on these observations. It is usually assumed that the strategy profiles may be chosen in an on-line manner by the algorithm. We study a corresponding computational learning model, and the query complexity of learning equilibria for various classes of games. We give basic results for bimatrix and graphical games. Our focus is on symmetric network congestion games. For directed acyclic networks, we can learn the cost functions (and hence compute an equilibrium) while querying just a small fraction of pure-strategy profiles. For the special case of parallel links, we have the stronger result that an equilibrium can be identified while only learning a small fraction of the cost values.

References

[1]

Alon, N., Emek, Y., Feldman, M., and Tennenholtz, M. 2011. Economical graph discovery. In Proc. of ICS. 476--486.

[2]

Angluin, D. 1987. Learning regular sets from queries and counterexamples. Information and Computation 75, 2, 87--106.

Digital Library

[3]

Berenbrink, P., Friedetzky, T., Goldberg, L., Goldberg, P., and Martin, R. 2007. Distributed selfish load balancing. SIAM Journal on Computing 37, 1163--1181.

Digital Library

[4]

Briest, P., Goldberg, P. W., and Röglin, H. 2008. Approximate equilibria in games with few players. CoRR abs/0804.4524.

[5]

Chien, S. and Sinclair, A. 2011. Convergence to approximate Nash equilibria in congestion games. Games and Economic Behavior 71, 2, 315--327.

[6]

Daskalakis, C., Frongillo, R., Papadimitriou, C., Pierrakos, G., and Valiant, G. 2010. On learning algorithms for Nash equilibria. In Proc. of SAGT. 114--125.

Digital Library

[7]

Daskalakis, C., Goldberg, P., and Papadimitriou, C. 2009a. The complexity of computing a Nash equilibrium. SIAM Journal on Computing 39, 1, 195--259.

Digital Library

[8]

Daskalakis, C., Mehta, A., and Papadimitriou, C. H. 2009b. A note on approximate Nash equilibria. Theoretical Computer Science 410, 17, 1581--1588.

Digital Library

[9]

Daskalakis, C. and Papadimitriou, C. 2009. On oblivious PTAS's for Nash equilibrium. In Proc. of 41st STOC. 75--84.

Digital Library

[10]

Duong, Q., Vorobeychik, Y., Singh, S., and Wellman, M. 2009. Learning graphical game models. In Proceedings of the 21st IJCAI. 116--121.

Digital Library

[11]

Even-Dar, E., Kesselmann, A., and Mansour, Y. 2003. Convergence time to Nash equilibria. In Proc. of ICALP. 502--513.

Digital Library

[12]

Fabrikant, A., Papadimitriou, C. H., and Talwar, K. 2004. The complexity of pure Nash equilibria. In Proc. of STOC. 604--612.

Digital Library

[13]

Feder, T., Nazerzadeh, H., and Saberi, A. 2007. Approximating Nash equilibria using small-support strategies. In Proc. of 8th ACM EC. 352--354.

Digital Library

[14]

Feldmann, R., Gairing, M., Lücking, T., Monien, B., and Rode, M. 2003. Nashification and the coordination ratio for a selfish routing game. In Proc. of ICALP. 514--526.

Digital Library

[15]

Fischer, S., Räcke, H., and Vöcking, B. 2006. Fast convergence to Wardrop equilibria by adaptive sampling methods. In Proc. of the 38th STOC. pp. 653--662.

Digital Library

[16]

Fudenberg, D. and Levine, D. 1998. The Theory of Learning in Games. MIT Press.

[17]

Gairing, M., Lücking, T., Mavronicolas, M., Monien, B., and Rode, M. 2008. Nash equilibria in discrete routing games with convex latency functions. Journal of Computer and System Sciences 74, 1199--1225.

Digital Library

[18]

Goldberg, P. 2004. Bounds for the convergence rate of randomized local search in a multiplayer, load-balancing game. In Proc. of PODC. 131--140.

Digital Library

[19]

Goldberg, P. and Pastink, A. 2012. On the communication complexity of approximate Nash equilibria. In Proc. of 5th SAGT. LNCS 7615. 192--203.

Digital Library

[20]

Goldberg, P. W., Savani, R., Sørensen, T. B., and Ventre, C. 2013. On the approximation performance of fictitious play in finite games. International Journal of Game Theory, 1--25.

[21]

art and Mansour2010}HM10 Hart, S. and Mansour, Y. 2010. How long to equilibrium? The communication complexity of uncoupled equilibrium procedures. Games and Economic Behavior 69, 107--126.

[22]

Hart, S. and Mas-Colell, A. 2003. Uncoupled dynamics do not lead to Nash equilibrium. American Economic Review 93, 5, 1830--1836.

[23]

Hart, S. and Mas-Colell, A. 2006. Stochastic uncoupled dynamics and Nash equilibrium. Games and Economic Behavior 57, 2, 286--303.

[24]

Hémon, S., de Rougemont, M., and Santha, M. 2008. Approximate Nash equilibria for multi-player games. In SAGT. 267--278.

Digital Library

[25]

Jordan, P., Schvartzman, L., and Wellman, M. 2010. Strategy exploration in empirical games. In Proc. of 9th AAMAS. 1131--1138.

Digital Library

[26]

Jordan, P., Vorobeychik, Y., and Wellman, M. 2008. Searching for approximate equilibria in empirical games. In Proc. of 7th AAMAS, Vol. 2. 1063--1070.

Digital Library

[27]

Kearns, M., Littman, M., and Singh, S. 2001. Graphical models for game theory. In Proc.\ of the 17th UAI. 253--260.

Digital Library

[28]

Nudelman, E., Wortman, J., Shoham, Y., and Leyton-Brown, K. 2004. Run the GAMUT: A comprehensive approach to evaluating game-theoretic algorithms. In Proc. of 3rd AAMAS. 880--887.

Digital Library

[29]

Sureka, A. and Wurman, P. 2005. Using tabu best-response search to find pure strategy Nash equilibria in normal form games. In Proc: of AAMAS. 1023--1029.

Digital Library

[30]

Vorobeychik, Y., Wellman, M., and Singh, S. 2007. Learning payoff functions in infinite games. Machine Learning 67, 145--168.

Digital Library

[31]

Wellman, M. 2006. Methods for empirical game-theoretic analysis. In Proc. of AAAI. 1552--1555.

Digital Library

Cited By

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
Czumaj ADeligkas AFasoulakis MFearnley JJurdziński MSavani R(2019)Distributed Methods for Computing Approximate EquilibriaAlgorithmica10.1007/s00453-018-0465-y81:3(1205-1231)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s00453-018-0465-y
Wellman MNguyen TWright M(2019)Empirical Game-Theoretic Methods for Adaptive Cyber-DefenseAdversarial and Uncertain Reasoning for Adaptive Cyber Defense10.1007/978-3-030-30719-6_6(112-128)Online publication date: 31-Aug-2019
https://doi.org/10.1007/978-3-030-30719-6_6
Show More Cited By

Index Terms

Learning equilibria of games via payoff queries
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Learning equilibria of games via payoff queries
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

A recent body of experimental literature has studied empirical game-theoretical analysis, in which we have partial knowledge of a game, consisting of observations of a subset of the pure-strategy profiles and their associated payoffs to players. The aim ...
Learning equilibria of games via payoff queries

A recent body of experimental literature has studied empirical game-theoretical analysis, in which we have partial knowledge of a game, consisting of observations of a subset of the pure-strategy profiles and their associated payoffs to players. The aim ...
Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries
Special Issue on EC'14

We study the deterministic and randomized query complexity of finding approximate equilibria in a k × k bimatrix game. We show that the deterministic query complexity of finding an ϵ-Nash equilibrium when ϵ < ½ is Ω(k²), even in zero-one constant-sum ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

June 2013

924 pages

ISBN:9781450319621

DOI:10.1145/2492002

General Chair:
Michael Kearns
University of Pennsylvania., USA
,
Program Chairs:
Preston McAfee
Google, USA
,
Éva Tardos
Cornell University, USA

Copyright © 2013 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

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '13

Sponsor:

SIGecom

EC '13: ACM Conference on Electronic Commerce

June 16 - 20, 2013

Pennsylvania, Philadelphia, USA

Acceptance Rates

EC '13 Paper Acceptance Rate 72 of 223 submissions, 32%;

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
174
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

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
Czumaj ADeligkas AFasoulakis MFearnley JJurdziński MSavani R(2019)Distributed Methods for Computing Approximate EquilibriaAlgorithmica10.1007/s00453-018-0465-y81:3(1205-1231)Online publication date: 1-Mar-2019
Wellman MNguyen TWright M(2019)Empirical Game-Theoretic Methods for Adaptive Cyber-DefenseAdversarial and Uncertain Reasoning for Adaptive Cyber Defense10.1007/978-3-030-30719-6_6(112-128)Online publication date: 31-Aug-2019
Rubinstein A(2019)Hardness of Approximation Between P and NPundefinedOnline publication date: 30-May-2019
Babichenko YRubinstein AHatami HMcKenzie PKing V(2017)Communication complexity of approximate Nash equilibriaProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055407(878-889)Online publication date: 19-Jun-2017
Goldberg P(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
Goldberg PRoth A(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
Fearnley JSavani R(2016)Finding Approximate Nash Equilibria of Bimatrix Games via Payoff QueriesACM Transactions on Economics and Computation10.1145/29565794:4(1-19)Online publication date: 26-Aug-2016
Babichenko Y(2016)Query Complexity of Approximate Nash EquilibriaJournal of the ACM10.1145/290873463:4(1-24)Online publication date: 10-Oct-2016
Chen PLu C(2016)Generalized mirror descents in congestion gamesArtificial Intelligence10.1016/j.artint.2016.09.002241(217-243)Online publication date: Dec-2016
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents