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/2482540.2482558

Published: 25 October 2018 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

Babichenko Y(2016)Query Complexity of Approximate Nash EquilibriaJournal of the ACM10.1145/290873463:4(1-24)Online publication date: 10-Oct-2016
https://dl.acm.org/doi/10.1145/2908734
Chen PLu C(2016)Generalized mirror descents in congestion gamesArtificial Intelligence10.1016/j.artint.2016.09.002241(217-243)Online publication date: Dec-2016
https://doi.org/10.1016/j.artint.2016.09.002
Babichenko YBarman S(2015)Query Complexity of Correlated EquilibriumACM Transactions on Economics and Computation (TEAC)10.1145/27856683:4(1-9)Online publication date: 31-Jul-2015
https://dl.acm.org/doi/10.1145/2785668
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

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 October 2018

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%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
6
Total Downloads

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

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Babichenko Y(2016)Query Complexity of Approximate Nash EquilibriaJournal of the ACM10.1145/290873463:4(1-24)Online publication date: 10-Oct-2016
https://dl.acm.org/doi/10.1145/2908734
Chen PLu C(2016)Generalized mirror descents in congestion gamesArtificial Intelligence10.1016/j.artint.2016.09.002241(217-243)Online publication date: Dec-2016
https://doi.org/10.1016/j.artint.2016.09.002
Babichenko YBarman S(2015)Query Complexity of Correlated EquilibriumACM Transactions on Economics and Computation (TEAC)10.1145/27856683:4(1-9)Online publication date: 31-Jul-2015
https://dl.acm.org/doi/10.1145/2785668
Fearnley JSavani RBabaioff MConitzer VEasley D(2014)Finding approximate nash equilibria of bimatrix games via payoff queriesProceedings of the fifteenth ACM conference on Economics and computation10.1145/2600057.2602847(657-674)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1145/2600057.2602847
Goldberg PRoth ABabaioff MConitzer VEasley D(2014)Bounds for the query complexity of approximate equilibriaProceedings of the fifteenth ACM conference on Economics and computation10.1145/2600057.2602845(639-656)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1145/2600057.2602845

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents