{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T13:35:52Z","timestamp":1779888952026,"version":"3.53.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,10,26]],"date-time":"2015-10-26T00:00:00Z","timestamp":1445817600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/L011018\/1"],"award-info":[{"award-number":["EP\/L011018\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000269","name":"Economic and Social Research Council","doi-asserted-by":"publisher","award":["ESRC\/BSB\/09"],"award-info":[{"award-number":["ESRC\/BSB\/09"]}],"id":[{"id":"10.13039\/501100000269","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ALGAME"],"award-info":[{"award-number":["ALGAME"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,2]]},"DOI":"10.1007\/s00453-015-0078-7","type":"journal-article","created":{"date-parts":[[2015,10,26]],"date-time":"2015-10-26T16:37:42Z","timestamp":1445877462000},"page":"487-514","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Computing Approximate Nash Equilibria in Polymatrix Games"],"prefix":"10.1007","volume":"77","author":[{"given":"Argyrios","family":"Deligkas","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Fearnley","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1262-7831","authenticated-orcid":false,"given":"Rahul","family":"Savani","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,10,26]]},"reference":[{"key":"78_CR1","doi-asserted-by":"crossref","first-page":"117","DOI":"10.4086\/toc.2013.v009a003","volume":"9","author":"P Austrin","year":"2013","unstructured":"Austrin, P., Braverman, M., Chlamtac, E.: Inapproximability of NP-complete variants of Nash equilibrium. Theory Comput. 9, 117\u2013142 (2013)","journal-title":"Theory Comput."},{"key":"78_CR2","doi-asserted-by":"crossref","unstructured":"Babichenko, Y., Barman, S., Peretz, R.: Simple approximate equilibria in large games. In: ACM Conference on Economics and Computation, EC\u201914, Stanford , CA, USA, June 8\u201312, 2014, pp. 753\u2013770 (2014)","DOI":"10.1145\/2600057.2602873"},{"issue":"1","key":"78_CR3","doi-asserted-by":"crossref","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."},{"key":"78_CR4","unstructured":"Briest, P., Goldberg, P.W., R\u00f6glin, H.: Approximate equilibria in games with few players. CoRR (2008). arXiv:0804.4524"},{"key":"78_CR5","doi-asserted-by":"crossref","unstructured":"Cai, Y., Daskalakis, C.: On minmax theorems for multiplayer games. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, CA, USA, January 23\u201325, 2011, pp. 217\u2013234 (2011)","DOI":"10.1137\/1.9781611973082.20"},{"issue":"3","key":"78_CR6","doi-asserted-by":"crossref","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":"78_CR7","doi-asserted-by":"crossref","unstructured":"Chen, X., Paparas, D., Yannakakis, M.: The complexity of non-monotone markets. In: Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, CA, USA, June 1\u20134, 2013, pp. 181\u2013190 (2013)","DOI":"10.1145\/2488608.2488632"},{"issue":"2","key":"78_CR8","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1016\/j.geb.2008.02.015","volume":"63","author":"V Conitzer","year":"2008","unstructured":"Conitzer, V., Sandholm, T.: New complexity results about Nash equilibria. Games Econ. Behav. 63(2), 621\u2013641 (2008)","journal-title":"Games Econ. Behav."},{"key":"78_CR9","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Fasoulakis, M., Jurdzinski, M.: Approximate well-supported Nash equilibria in symmetric bimatrix games. In: Proceedings of Algorithmic Game Theory\u20147th International Symposium, SAGT 2014, Haifa, Israel, September 30\u2013October 2, 2014, pp. 244\u2013254 (2014)","DOI":"10.1007\/978-3-662-44803-8_21"},{"issue":"3","key":"78_CR10","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/2483699.2483703","volume":"9","author":"C Daskalakis","year":"2013","unstructured":"Daskalakis, C.: On the complexity of approximating a Nash equilibrium. ACM Trans. Algorithms 9(3), 23 (2013)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"78_CR11","doi-asserted-by":"crossref","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":"78_CR12","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.H.: Progress in approximate Nash equilibria. In: Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), San Diego, CA, USA, June 11\u201315, 2007, pp. 355\u2013358 (2007)","DOI":"10.1145\/1250910.1250962"},{"issue":"17","key":"78_CR13","doi-asserted-by":"crossref","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 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"78_CR14","doi-asserted-by":"crossref","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"},{"key":"78_CR15","doi-asserted-by":"crossref","unstructured":"Deligkas, A., Fearnley, J., Savani, R., Spirakis, P.G.: Computing approximate Nash equilibria in polymatrix games. In: Proceedings of Web and Internet Economics\u201410th International Conference, WINE 2014, Beijing, China, December 14\u201317, 2014, pp. 58\u201371 (2014)","DOI":"10.1007\/978-3-319-13129-0_5"},{"issue":"6","key":"78_CR16","doi-asserted-by":"crossref","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":"78_CR17","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: Proceedings of Algorithmic Game Theory\u20145th International Symposium, SAGT 2012, Barcelona, Spain, October 22\u201323, 2012, pp. 108\u2013119 (2012)","DOI":"10.1007\/978-3-642-33996-7_10"},{"key":"78_CR18","doi-asserted-by":"crossref","unstructured":"Fearnley, J., Igwe, T.P., Savani, R.: An empirical study of finding approximate equilibria in bimatrix games. In: Proceedings of Experimental Algorithms - 14th International Symposium, SEA 2015, Paris, France, June 29\u2013July 1, 2015, pp.\u00a0339\u2013351 (2015)","DOI":"10.1007\/978-3-319-20086-6_26"},{"key":"78_CR19","unstructured":"Feige, U., Talgam-Cohen, I.: A direct reduction from k-player to 2-player approximate Nash equilibrium. In: Proceedings of Algorithmic Game Theory\u2014Third International Symposium, SAGT 2010, Athens, Greece, October 18\u201320, 2010, pp. 138\u2013149 (2010)"},{"issue":"7","key":"78_CR20","doi-asserted-by":"crossref","first-page":"1229","DOI":"10.1016\/S0165-1889(03)00108-8","volume":"28","author":"S Govindan","year":"2004","unstructured":"Govindan, S., Wilson, R.: Computing Nash equilibria by iterated polymatrix approximation. J. Econ. Dyn. Control 28(7), 1229\u20131241 (2004)","journal-title":"J. Econ. Dyn. Control"},{"issue":"1","key":"78_CR21","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s00199-009-0434-4","volume":"42","author":"S Govindan","year":"2010","unstructured":"Govindan, S., Wilson, R.: A decomposition algorithm for n-player games. Econ. Theory 42(1), 97\u2013117 (2010)","journal-title":"Econ. Theory"},{"key":"78_CR22","doi-asserted-by":"crossref","unstructured":"H\u00e9mon, S., de\u00a0Rougemont, M., Santha, M.: Approximate Nash equilibria for multi-player games. In: Proceedings of Algorithmic Game Theory, First International Symposium, SAGT 2008, Paderborn, Germany, April 30\u2013May 2, 2008, pp. 267\u2013278 (2008)","DOI":"10.1007\/978-3-540-79309-0_24"},{"issue":"3","key":"78_CR23","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1287\/mnsc.21.3.313","volume":"21","author":"JT Howson","year":"1974","unstructured":"Howson, J.T., Rosenthal, R.W.: Bayesian equilibria of finite two-person games with incomplete information. Manag. Sci. 21(3), 313\u2013315 (1974)","journal-title":"Manag. Sci."},{"issue":"5","key":"78_CR24","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1287\/mnsc.18.5.312","volume":"18","author":"JT Howson","year":"1972","unstructured":"Howson, J.T.: Equilibria of polymatrix games. Manag. Sci. 18(5), 312\u2013318 (1972)","journal-title":"Manag. Sci."},{"issue":"4","key":"78_CR25","doi-asserted-by":"crossref","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":"78_CR26","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proceedings of 4th ACM Conference on Electronic Commerce (EC-2003), San Diego, CA, USA, June 9\u201312, 2003, pp. 36\u201341 (2003)","DOI":"10.1145\/779928.779933"},{"key":"78_CR27","doi-asserted-by":"crossref","unstructured":"Rubinstein, A.: Inapproximability of Nash equilibrium. In: Proceedings of the Forty- Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14\u201317, 2015, pp. 409\u2013418 (2015)","DOI":"10.1145\/2746539.2746578"},{"issue":"4","key":"78_CR28","doi-asserted-by":"crossref","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\/content\/pdf\/10.1007\/s00453-015-0078-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0078-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0078-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0078-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:22Z","timestamp":1559072842000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0078-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,26]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["78"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0078-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,10,26]]}}}