{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:27:31Z","timestamp":1759638451798,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,2,17]],"date-time":"2018-02-17T00:00:00Z","timestamp":1518825600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Mexican National Council of Science and Technology","award":["328981"],"award-info":[{"award-number":["328981"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,1]]},"DOI":"10.1007\/s00224-018-9851-8","type":"journal-article","created":{"date-parts":[[2018,2,17]],"date-time":"2018-02-17T00:18:45Z","timestamp":1518826725000},"page":"26-53","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Logarithmic Query Complexity for Approximate Nash Computation in Large Games"],"prefix":"10.1007","volume":"63","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5436-7890","authenticated-orcid":false,"given":"Paul W.","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francisco J.","family":"Marmolejo-Coss\u00edo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiwei Steven","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,2,17]]},"reference":[{"issue":"2","key":"9851_CR1","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1287\/moor.1120.0557","volume":"38","author":"Y Azrieli","year":"2013","unstructured":"Azrieli, Y., Shmaya, E.: Lipschitz games. Math. Oper. Res. 38(2), 350\u2013357 (2013)","journal-title":"Math. Oper. Res."},{"key":"9851_CR2","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/j.geb.2013.04.007","volume":"81","author":"Y Babichenko","year":"2013","unstructured":"Babichenko, Y.: Best-reply dynamics in large binary-choice anonymous games. Games and Economic Behavior 81, 130\u2013144 (2013)","journal-title":"Games and Economic Behavior"},{"key":"9851_CR3","doi-asserted-by":"crossref","unstructured":"Babichenko, Y.: Query complexity of approximate Nash equilibria. In: Proceedings of 46th STOC, pp. 535\u2013544 (2014)","DOI":"10.1145\/2591796.2591829"},{"key":"9851_CR4","doi-asserted-by":"crossref","unstructured":"Babichenko, Y., Barman, S.: Query complexity of correlated equilibrium. ACM Trans. Econ. Comput. 4(3), 22:1\u201322:9 (2015)","DOI":"10.1145\/2785668"},{"key":"9851_CR5","unstructured":"Chen, X., Cheng, Y., Tang, B.: Well-supported versus approximate nash equilibria: query complexity of large games. arXiv: 1511.00785 (2015)"},{"key":"9851_CR6","doi-asserted-by":"crossref","unstructured":"Fearnley, J., Savani, R.: Finding approximate Nash equilibria of bimatrix games via payoff queries. In: Proceedings of 15th ACM EC, pp. 657\u2013674 (2014)","DOI":"10.1145\/2600057.2602847"},{"key":"9851_CR7","first-page":"1305","volume":"16","author":"J Fearnley","year":"2015","unstructured":"Fearnley, J., Gairing, M., Goldberg, P.W., Savani, R.: Learning equilibria of games via payoff queries. J. Mach. Learn. Res. 16, 1305\u20131344 (2015)","journal-title":"J. Mach. Learn. Res."},{"issue":"3","key":"9851_CR8","first-page":"341","volume":"1","author":"DP Foster","year":"2006","unstructured":"Foster, D.P., Young, H.P.: Regret testing: learning to play Nash equilibrium without knowing you have an opponent. Theor. Econ. 1(3), 341\u2013367 (2006)","journal-title":"Theor. Econ."},{"key":"9851_CR9","doi-asserted-by":"crossref","unstructured":"Germano, F., Lugosi, G.: Global nash convergence of foster and young\u2019s regret testing. http:\/\/www.econ.upf.edu\/~lugosi\/nash.pdf (2005)","DOI":"10.2139\/ssrn.678622"},{"key":"9851_CR10","doi-asserted-by":"crossref","unstructured":"Goldberg, P.W., Roth, A.: Bounds for the query complexity of approximate equilibria. In: Proceedings of the 15th ACM-EC Conference, pp. 639\u2013656 (2014)","DOI":"10.1145\/2600057.2602845"},{"key":"9851_CR11","doi-asserted-by":"crossref","unstructured":"Goldberg, P.W., Turchetta, S.: Query complexity of approximate equilibria in anonymous games. In: Proceedings of the 11th WINE Conference, LNCS 9470, pp. 357\u2013369 (2015)","DOI":"10.1007\/978-3-662-48995-6_26"},{"issue":"1","key":"9851_CR12","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.geb.2007.12.002","volume":"69","author":"S Hart","year":"2010","unstructured":"Hart, S., Mansour, Y.: How long to equilibrium? The communication complexity of uncoupled equilibrium procedures. Games and Economic Behavior 69(1), 107\u2013126 (2010)","journal-title":"Games and Economic Behavior"},{"issue":"5","key":"9851_CR13","doi-asserted-by":"publisher","first-page":"1127","DOI":"10.1111\/1468-0262.00153","volume":"68","author":"S Hart","year":"2000","unstructured":"Hart, S., Mas-Colell, A.: A simple adaptive procedure leading to correlated equilibrium. Econometrica 68(5), 1127\u20131150 (2000)","journal-title":"Econometrica"},{"issue":"5","key":"9851_CR14","doi-asserted-by":"publisher","first-page":"1830","DOI":"10.1257\/000282803322655581","volume":"93","author":"S Hart","year":"2003","unstructured":"Hart, S., Mas-Colell, A.: Uncoupled dynamics do not lead to nash equilibrium. Am. Econ. Rev. 93(5), 1830\u20131836 (2003)","journal-title":"Am. Econ. Rev."},{"key":"9851_CR15","unstructured":"Hart, S., Nisan, N.: The query complexity of correlated equilibria. arXiv: 1305.4874 (2013)"},{"issue":"6","key":"9851_CR16","doi-asserted-by":"publisher","first-page":"1631","DOI":"10.1111\/j.1468-0262.2004.00549.x","volume":"72","author":"E Kalai","year":"2004","unstructured":"Kalai, E.: Large robust games. Econometrica 72(6), 1631\u20131665 (2004)","journal-title":"Econometrica"},{"issue":"5","key":"9851_CR17","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1257\/aer.104.5.431","volume":"104","author":"M Kearns","year":"2014","unstructured":"Kearns, M., Pai, M.M., Roth, A., Ullman, J.: Mechanism design in large games: incentives and privacy. Am. Econ. Rev. 104(5), 431\u201335 (2014). https:\/\/doi.org\/10.1257\/aer.104.5.431","journal-title":"Am. Econ. Rev."},{"key":"9851_CR18","doi-asserted-by":"crossref","unstructured":"Young, H.P.: Learning by trial and error. http:\/\/www.econ2.jhu.edu\/people\/young\/Learning5June08.pdf (2009)","DOI":"10.1016\/j.geb.2008.02.011"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9851-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9851-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9851-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,10]],"date-time":"2019-10-10T23:53:09Z","timestamp":1570751589000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9851-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,17]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["9851"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9851-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2018,2,17]]},"assertion":[{"value":"17 February 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}