{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:16:25Z","timestamp":1761621385310,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,6,11]],"date-time":"2018-06-11T00:00:00Z","timestamp":1528675200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/D063191\/1","EP\/L011018\/1"],"award-info":[{"award-number":["EP\/D063191\/1","EP\/L011018\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["#2021296"],"award-info":[{"award-number":["#2021296"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,3]]},"DOI":"10.1007\/s00453-018-0465-y","type":"journal-article","created":{"date-parts":[[2018,6,11]],"date-time":"2018-06-11T09:46:57Z","timestamp":1528710417000},"page":"1205-1231","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Distributed Methods for Computing Approximate Equilibria"],"prefix":"10.1007","volume":"81","author":[{"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Argyrios","family":"Deligkas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michail","family":"Fasoulakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John","family":"Fearnley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Jurdzi\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1262-7831","authenticated-orcid":false,"given":"Rahul","family":"Savani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,11]]},"reference":[{"key":"465_CR1","unstructured":"Babichenko, Y., Rubinstein, A.: Communication complexity of approximate Nash equilibria. CoRR, abs\/1608.06580, (2016). URL \n                    http:\/\/arXiv.org\/abs\/1608.06580"},{"issue":"1","key":"465_CR2","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.tcs.2009.09.023","volume":"411","author":"H Bosse","year":"2010","unstructured":"Bosse, H., Byrka, J., Markakis, E.: New algorithms for approximate Nash equilibria in bimatrix games. Theor. Comput. Sci. 411(1), 164\u2013173 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"465_CR3","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X Chen","year":"2009","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3), 14:1\u201314:57 (2009)","journal-title":"J. ACM"},{"key":"465_CR4","doi-asserted-by":"crossref","unstructured":"Conitzer, V., Sandholm, T.: Communication complexity as a lower bound for learning in games. In: Proc. of ICML, pp. 185\u2013192 (2004)","DOI":"10.1145\/1015330.1015351"},{"key":"465_CR5","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Fasoulakis, M., Jurdzinski, M.: Approximate well-supported Nash equilibria in symmetric bimatrix games. In: Proc. of SAGT, pp. 244\u2013254 (2014)","DOI":"10.1007\/978-3-662-44803-8_21"},{"key":"465_CR6","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.H.: Progress in approximate Nash equilibria. In: Proc. of EC, pp. 355\u2013358 (2007)","DOI":"10.1145\/1250910.1250962"},{"issue":"1","key":"465_CR7","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 (2009a)","journal-title":"SIAM J. Comput."},{"issue":"17","key":"465_CR8","doi-asserted-by":"publisher","first-page":"1581","DOI":"10.1016\/j.tcs.2008.12.031","volume":"410","author":"C Daskalakis","year":"2009","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.H.: A note on approximate Nash equilibria. Theor. Comput. Sci. 410(17), 1581\u20131588 (2009b)","journal-title":"Theor. Comput. Sci."},{"key":"465_CR9","doi-asserted-by":"crossref","unstructured":"Fearnley, J., Savani, R.: Finding approximate Nash equilibria of bimatrix games via payoff queries. In: Proc. of EC, pp. 657\u2013674 (2014)","DOI":"10.1145\/2600057.2602847"},{"key":"465_CR10","doi-asserted-by":"crossref","unstructured":"Fearnley, J., Goldberg, P.W., Savani, R., S\u00f8rensen, T.B.: Approximate well-supported Nash equilibria below two-thirds. In: Proc. of SAGT, pp. 108\u2013119 (2012). To appear in Algorithmica","DOI":"10.1007\/978-3-642-33996-7_10"},{"key":"465_CR11","doi-asserted-by":"crossref","unstructured":"Fearnley, J., Gairing, M., Goldberg, P.W., Savani, R.: Learning equilibria of games via payoff queries. In: Proc. of EC, pp. 397\u2013414 (2013)","DOI":"10.1145\/2492002.2482558"},{"key":"465_CR12","doi-asserted-by":"crossref","unstructured":"Fearnley, J., Igwe, T.P., Savani, R.: An empirical study of finding approximate equilibria in bimatrix games. In: Proc. of SEA, pp. 339\u2013351 (2015)","DOI":"10.1007\/978-3-319-20086-6_26"},{"key":"465_CR13","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.geb.2014.01.009","volume":"85","author":"PW Goldberg","year":"2014","unstructured":"Goldberg, P.W., Pastink, A.: On the communication complexity of approximate Nash equilibria. Games Econ. Behav. 85, 19\u201331 (2014)","journal-title":"Games Econ. Behav."},{"key":"465_CR14","doi-asserted-by":"crossref","unstructured":"Goldberg, P.W., Roth, A.: Bounds for the query complexity of approximate equilibria. In: Proc. of EC, pp. 639\u2013656 (2014)","DOI":"10.1145\/2600057.2602845"},{"issue":"1","key":"465_CR15","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 Econ. Behav. 69(1), 107\u2013126 (2010)","journal-title":"Games Econ. Behav."},{"issue":"4","key":"465_CR16","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/s00453-008-9227-6","volume":"57","author":"SC Kontogiannis","year":"2010","unstructured":"Kontogiannis, S.C., Spirakis, P.G.: Well supported approximate equilibria in bimatrix games. Algorithmica 57(4), 653\u2013667 (2010)","journal-title":"Algorithmica"},{"key":"465_CR17","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proc. of EC, pp. 36\u201341 (2003)","DOI":"10.1145\/779928.779933"},{"issue":"2","key":"465_CR18","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J Nash","year":"1951","unstructured":"Nash, J.: Non-cooperative games. Ann. Math. 54(2), 286\u2013295 (1951)","journal-title":"Ann. Math."},{"key":"465_CR19","doi-asserted-by":"crossref","unstructured":"Rubinstein, A.: Settling the complexity of computing approximate two-player Nash equilibria. In: Proc. of FOCS, pp. 258\u2013265 (2016)","DOI":"10.1109\/FOCS.2016.35"},{"issue":"4","key":"465_CR20","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1080\/15427951.2008.10129172","volume":"5","author":"H Tsaknakis","year":"2008","unstructured":"Tsaknakis, H., Spirakis, P.G.: An optimization approach for approximate Nash equilibria. Internet Math. 5(4), 365\u2013382 (2008)","journal-title":"Internet Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0465-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0465-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0465-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T19:05:18Z","timestamp":1560193518000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0465-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,11]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["465"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0465-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,6,11]]},"assertion":[{"value":"29 January 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 June 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}