Learning Convex Partitions and Computing Game-theoretic Equilibria from Best-response Queries
Article No.: 3, Pages 1 - 36
Abstract
Suppose that an m-simplex is partitioned into n convex regions having disjoint interiors and distinct labels, and we may learn the label of any point by querying it. The learning objective is to know, for any point in the simplex, a label that occurs within some distance ε from that point. We present two algorithms for this task: Constant-Dimension Generalised Binary Search (CD-GBS), which for constant m uses poly(n, log (1/ε)) queries, and Constant-Region Generalised Binary Search (CR-GBS), which uses CD-GBS as a subroutine and for constant n uses poly(m, log (1/ε)) queries.
We show via Kakutani’s fixed-point theorem that these algorithms provide bounds on the best-response query complexity of computing approximate well-supported equilibria of bimatrix games in which one of the players has a constant number of pure strategies. We also partially extend our results to games with multiple players, establishing further query complexity bounds for computing approximate well-supported equilibria in this setting.
References
[1]
Yakov Babichenko. 2016. Query complexity of approximate Nash equilibria. J. ACM 63, 4 (2016), 36:1--36:24.
[2]
Yakov Babichenko, Siddharth Barman, and Ron Peretz. 2017. Empirical distribution of equilibrium play and its testing application. Math. Oper. Res. 42, 1 (2017), 15--29.
[3]
Yakov Babichenko and Aviad Rubinstein. 2017. Communication complexity of approximate Nash equilibria. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC’17). 878--889.
[4]
Elizabeth Baldwin and Paul Klemperer. 2016. Understanding Preferences: “Demand Types” and the Existence of Equilibrium with Indivisibilities. LSE Research Online Documents on Economics 63198. London School of Economics and Political Science, LSE Library. Retrieved from https://ideas.repec.org/p/ehl/lserod/63198.html.
[5]
Keith Ball. 1997. An elementary introduction to modern convex geometry. In Flavors of Geometry, Silvio Levi (Ed.). Cambridge University Press, Cambridge, Chapter 1, 1--58.
[6]
George W. Brown. 1949. Some notes on computation of game solutions. RAND Corp. Rep. (Apr. 1949), 78.
[7]
Nader H. Bshouty, Paul W. Goldberg, Sally A. Goldman, and H. David Mathias. 1998. Exact learning of discretized geometric concepts. SIAM J. Comput. 28, 2 (1998), 674--699.
[8]
Xi Chen, Xiaotie Deng, and Shang-Hua Teng. 2009. Settling the complexity of computing two-player Nash equilibria. J. ACM 56, 3 (2009), 14:1--14:57.
[9]
Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. 2009. The complexity of computing a Nash equilibrium. SIAM J. Comput. 39, 1 (2009), 195--259.
[10]
Constantinos Daskalakis and Qinxuan Pan. 2014. A counter-example to karlin’s strong conjecture for fictitious play. In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS’14). 11--20.
[11]
John Fearnley, Martin Gairing, Paul W. Goldberg, and Rahul Savani. 2015. Learning equilibria of games via payoff queries. J. Mach. Learn. Res. 16 (2015), 1305--1344.
[12]
Drew Fudenberg and David K. Levine. 1998. The Theory of Learning in Games. MIT Press.
[13]
Paul W. Goldberg and Stephen Kwek. 2000. The precision of query points as a resource for learning convex polytopes with membership queries. In Proceedings of the 13th Annual Conference on Learning Theory (COLT’00). Citeseer, 225--235.
[14]
Paul W. Goldberg and Aaron Roth. 2016. Bounds for the query complexity of approximate equilibria. ACM Trans. Econ. Comput. 4, 4 (2016), 24:1--24:25.
[15]
Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen, and Carmine Ventre. 2013. On the approximation performance of fictitious play in finite games. Int. J. Game Theory 42, 4 (2013), 1059--1083.
[16]
Paul W. Goldberg and Stefano Turchetta. 2017. Query complexity of approximate equilibria in anonymous games. J. Comput. Syst. Sci. 90 (2017), 80--98.
[17]
Sergiu Hart and Yishay Mansour. 2010. How long to equilibrium? the communication complexity of uncoupled equilibrium procedures. Games Econ. Behav. 69, 1 (2010), 107--126.
[18]
Sergiu Hart and Noam Nisan. 2018. The query complexity of correlated equilibria. Games Econ. Behav. 108 (2018), 401–410.
[19]
Fritz John. 2014. Extremum Problems with Inequalities as Subsidiary Conditions. Springer, Basel, 197--215.
[20]
Shizuo Kakutani. 1941. A generalization of brouwer’s fixed point theorem. Duke Math. J. 8, 3 (09 1941), 457--459.
[21]
Paul Klemperer. 2010. The product-mix auction: A new auction design for differentiated goods. J. Eur. Econ. Assoc. 8, 2/3 (2010), 526--536.
[22]
Richard J. Lipton, Evangelos Markakis, and Aranyak Mehta. 2003. Playing large games using simple strategies. In Proceedings of the 4th ACM Conference on Economics and Computation (EC’03). 36--41.
[23]
Francisco J. Marmolejo-Cossío. 2020. Equilibrium Computation in Games and Strategic Aspects of Bitcoin Mining. Ph.D. Dissertation. University of Oxford.
[24]
John Nash. 1951. Non-cooperative games. Ann. Math. 54, 2 (1951), 286--295. Retrieved from http://www.jstor.org/stable/1969529.
[25]
Julia Robinson. 1951. An iterative method of solving a game. Ann. Math. 54, 2 (1951), 296--301.
[26]
B. Von Stengel. 2004. Leadership with commitment to mixed strategies. CDAM Research Report LSE-CDAM-2004-01 (2004).
Index Terms
- Learning Convex Partitions and Computing Game-theoretic Equilibria from Best-response Queries
Recommendations
Learning Convex Partitions and Computing Game-Theoretic Equilibria from Best Response Queries
Web and Internet EconomicsAbstractSuppose that an m-simplex is partitioned into n convex regions having disjoint interiors and distinct labels, and we may learn the label of any point by querying it. The learning objective is to know, for any point in the simplex, a label that ...
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 ...
Learning equilibria of games via payoff queries
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerceA 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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2021
182 pages
ISSN:2167-8375
EISSN:2167-8383
DOI:10.1145/3446654
- Editors:
- David Pennock,
- Ilya Segal
Copyright © 2021 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]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 02 January 2021
Accepted: 01 February 2020
Revised: 01 December 2019
Received: 01 April 2019
Published in TEAC Volume 9, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Funding Sources
- Mexican National Council of Science and Technology (CONACyT)
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 78Total Downloads
- Downloads (Last 12 months)6
- Downloads (Last 6 weeks)1
Reflects downloads up to 04 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format