{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T20:27:39Z","timestamp":1743107259510,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662489949"},{"type":"electronic","value":"9783662489956"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.5"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48995-6_26","type":"book-chapter","created":{"date-parts":[[2015,12,8]],"date-time":"2015-12-08T18:37:29Z","timestamp":1449599849000},"page":"357-369","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Query Complexity of Approximate Equilibria in Anonymous Games"],"prefix":"10.1007","author":[{"given":"Paul W.","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Turchetta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,12,30]]},"reference":[{"issue":"2","key":"26_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."},{"issue":"1","key":"26_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 Econ. Behav. 81(1), 130\u2013144 (2013)","journal-title":"Games Econ. Behav."},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"Babichenko, Y.: Query complexity of approximate Nash equilibria. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing. pp. 535\u2013544. STOC 2014. ACM, USA (2014)","DOI":"10.1145\/2591796.2591829"},{"key":"26_CR4","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/j.jcss.2008.09.001","volume":"75","author":"F Brandt","year":"2009","unstructured":"Brandt, F., Fischer, F., Holzer, M.: Symmetries and the complexity of pure Nash equilibrium. J. Comput. Syst. Sci. 75, 163\u2013177 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"26_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X Chen","year":"2009","unstructured":"Chen, X., Deng, X., Teng, S.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3), 1\u201357 (2009)","journal-title":"J. ACM"},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"Chen, X., Durfee, D., Orfanou, A.: On the complexity of Nash equilibria in anonymous games. In: Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, ACM, pp. 381\u2013390 (2015)","DOI":"10.1145\/2746539.2746571"},{"key":"26_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/978-3-540-92185-1_26","volume-title":"Internet and Network Economics","author":"C Daskalakis","year":"2008","unstructured":"Daskalakis, C.: An efficient PTAS for two-strategy anonymous games. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 186\u2013197. Springer, Heidelberg (2008)"},{"issue":"1","key":"26_CR8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1), 195\u2013259 (2009)","journal-title":"SIAM J. Comput."},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Computing equilibria in anonymous games. In: Proceedings of the 48th Symposium on Foundations of Computer Science (FOCS), pp. 83\u201393 (2007)","DOI":"10.1109\/FOCS.2007.24"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Discretized multinomial distributions and Nash equilibria in anonymous games. In: Proceedings of the 49th Symposium on Foundations of Computer Science (FOCS), pp. 25\u201334 (2008)","DOI":"10.1109\/FOCS.2008.84"},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Papadimitriou, C.H.: On oblivious PTAS\u2019s for Nash equilibrium. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 75\u201384. ACM, USA (2009)","DOI":"10.1145\/1536414.1536427"},{"key":"26_CR12","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Sparse covers for sums of indicators (2013). CoRR abs\/1306.1265"},{"key":"26_CR13","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.jet.2014.02.002","volume":"156","author":"C Daskalakis","year":"2015","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Approximate Nash equilibria in anonymous games. J. Econ. Theory 156, 207\u2013245 (2015)","journal-title":"J. Econ. Theory"},{"issue":"6","key":"26_CR14","doi-asserted-by":"publisher","first-page":"2531","DOI":"10.1137\/080720826","volume":"39","author":"K Etessami","year":"2010","unstructured":"Etessami, K., Yannakakis, M.: On the complexity of Nash equilibria and other fixed points. SIAM J. Comput. 39(6), 2531\u20132597 (2010)","journal-title":"SIAM J. Comput."},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Fearnley, J., Gairing, M., Goldberg, P.W., Savani, R.: Learning equilibria of games via payoff queries. In: Proceedings of the 14th ACM Conference on Electronic Commerce, EC 2013, pp. 397\u2013414. ACM, USA (2013)","DOI":"10.1145\/2492002.2482558"},{"key":"26_CR16","doi-asserted-by":"crossref","unstructured":"Fearnley, J., Savani, R.: Finding approximate Nash equilibria of bimatrix games via payoff queries. In: Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC 2014, pp. 657\u2013674. ACM, USA (2014)","DOI":"10.1145\/2600057.2602847"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"Goldberg, P.W., Roth, A.: Bounds for the query complexity of approximate equilibria. In: Proceedings of the Fifteenth ACM Conference on Economics and Computation, EC 2014, pp. 639\u2013656. ACM, USA (2014)","DOI":"10.1145\/2600057.2602845"},{"key":"26_CR18","series-title":"Lecture Notes in Computer Science","first-page":"268","volume-title":"6th International Symposium on Algorithmic Game Theory, SAGT 2013","author":"S Hart","year":"2013","unstructured":"Hart, S., Nisan, N.: The query complexity of correlated equilibria. In: V\u00f6ckling, B. (ed.) SAGT 2013. LNCS, vol. 8146, p. 268. Springer, Heidelberg (2013)"},{"key":"26_CR19","unstructured":"Kash, I.A., Friedman, E.J., Halpern, J.Y.: Multiagent learning in large anonymous games. In: Eighth International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 765\u2013772 (2009)"},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proceedings of the 4th ACM Conference on Electronic Commerce, EC 2003, pp. 36\u201341. ACM, USA (2003)","DOI":"10.1145\/779928.779933"}],"container-title":["Lecture Notes in Computer Science","Web and Internet Economics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48995-6_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,28]],"date-time":"2023-12-28T09:12:26Z","timestamp":1703754746000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48995-6_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662489949","9783662489956"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48995-6_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"30 December 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}