{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T04:12:52Z","timestamp":1750824772693,"version":"3.41.0"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319666990"},{"type":"electronic","value":"9783319667003"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-66700-3_8","type":"book-chapter","created":{"date-parts":[[2017,8,18]],"date-time":"2017-08-18T12:38:47Z","timestamp":1503059927000},"page":"93-105","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Computing Constrained Approximate Equilibria in Polymatrix Games"],"prefix":"10.1007","author":[{"given":"Argyrios","family":"Deligkas","sequence":"first","affiliation":[]},{"given":"John","family":"Fearnley","sequence":"additional","affiliation":[]},{"given":"Rahul","family":"Savani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,8,19]]},"reference":[{"key":"8_CR1","doi-asserted-by":"publisher","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":"8_CR2","doi-asserted-by":"crossref","unstructured":"Babichenko, Y., Barman, S., Peretz, R.: Simple approximate equilibria in large games. In: Proceedings of the EC, pp. 753\u2013770 (2014)","DOI":"10.1145\/2600057.2602873"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Barman, S., Ligett, K.: Finding any nontrivial coarse correlated equilibrium is hard. In: Proceedings of EC, pp. 815\u2013816 (2015)","DOI":"10.1145\/2764468.2764497"},{"key":"8_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/978-3-662-48433-3_22","volume-title":"Algorithmic Game Theory","author":"S Barman","year":"2015","unstructured":"Barman, S., Ligett, K., Piliouras, G.: Approximating Nash equilibria in tree polymatrix games. In: Hoefer, M. (ed.) SAGT 2015. LNCS, vol. 9347, pp. 285\u2013296. Springer, Heidelberg (2015). doi:10.1007\/978-3-662-48433-3_22"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-33996-7_4","volume-title":"Algorithmic Game Theory","author":"V Bil\u00f2","year":"2012","unstructured":"Bil\u00f2, V., Mavronicolas, M.: The complexity of decision problems about Nash equilibria in win-lose games. In: Serna, M. (ed.) SAGT 2012. LNCS, pp. 37\u201348. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-33996-7_4"},{"key":"8_CR6","unstructured":"Bil\u00f2, V., Mavronicolas, M.: A catalog of $$\\exists \\mathbb{R}$$-complete decision problems about Nash equilibria in multi-player games. In: Proceedings of STACS, pp. 17:1\u201317:13 (2016)"},{"key":"8_CR7","unstructured":"Bil\u00f2, V., Mavronicolas, M.: $$\\exists \\mathbb{R}$$-complete decision problems about symmetric Nash equilibria in symmetric multi-player games. In: Proceedings of STACS, pp. 13:1\u201313:14 (2017)"},{"issue":"6","key":"8_CR8","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"8_CR9","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/j.tcs.2008.03.036","volume":"401","author":"V Bonifaci","year":"2008","unstructured":"Bonifaci, V., Di Iorio, U., Laura, L.: The complexity of uniform Nash equilibria and related regular subgraph problems. Theor. Comput. Sci. 401(1\u20133), 144\u2013152 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"8_CR10","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."},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"Braverman, M., Kun-Ko, Y., Weinstein, O.: Approximating the best Nash equilibrium in n$${}^{\\text{o}}$$$${}^{\\text{(log } \\text{ n) }}$$-time breaks the exponential time hypothesis. In: Proceedings of SODA, pp. 970\u2013982 (2015)","DOI":"10.1137\/1.9781611973730.66"},{"issue":"3","key":"8_CR12","doi-asserted-by":"publisher","first-page":"57","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), 57 (2009). Article No. 14","journal-title":"J. ACM"},{"issue":"2","key":"8_CR13","doi-asserted-by":"publisher","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":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-662-54110-4_2","volume-title":"Web and Internet Economics","author":"A Czumaj","year":"2016","unstructured":"Czumaj, A., Deligkas, A., Fasoulakis, M., Fearnley, J., Jurdzi\u0144ski, M., Savani, R.: Distributed methods for computing approximate equilibria. In: Cai, Y., Vetta, A. (eds.) WINE 2016. LNCS, vol. 10123, pp. 15\u201328. Springer, Heidelberg (2016). doi:10.1007\/978-3-662-54110-4_2"},{"key":"8_CR15","unstructured":"Czumaj, A., Fasoulakis, M., Jurdzi\u0144ski, M.: Approximate Nash equilibria with near optimal social welfare. In: Proceedings of IJCAI, pp. 504\u2013510 (2015)"},{"key":"8_CR16","unstructured":"Czumaj, A., Fasoulakis M., Jurdzi\u0144ski, M.: Approximate plutocratic and egalitarian Nash equilibria. In: Proceedings of AAMAS, pp. 1409\u20131410 (2016)"},{"issue":"1","key":"8_CR17","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":"8_CR18","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.H.: Progress in approximate Nash equilibria. In: Proceedings of EC, pp. 355\u2013358 (2007)","DOI":"10.1145\/1250910.1250962"},{"issue":"17","key":"8_CR19","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 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR20","unstructured":"Deligkas, A., Fearnley, J., Igwe, T.P., Savani, R.: An empirical study on computing equilibria in polymatrix games. In: Proceedings of AAMAS, pp. 186\u2013195 (2016)"},{"key":"8_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-3-662-54110-4_3","volume-title":"Web and Internet Economics","author":"A Deligkas","year":"2016","unstructured":"Deligkas, A., Fearnley, J., Savani, R.: Inapproximability results for approximate Nash equilibria. In: Cai, Y., Vetta, A. (eds.) WINE 2016. LNCS, vol. 10123, pp. 29\u201343. Springer, Heidelberg (2016). doi:10.1007\/978-3-662-54110-4_3"},{"issue":"2","key":"8_CR22","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s00453-015-0078-7","volume":"77","author":"A Deligkas","year":"2017","unstructured":"Deligkas, A., Fearnley, J., Savani, R., Spirakis, P.G.: Computing approximate Nash equilibria in polymatrix games. Algorithmica 77(2), 487\u2013514 (2017)","journal-title":"Algorithmica"},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"Elkind, E., Goldberg, L.A., Goldberg, P.W.: Nash equilibria in graphical games on trees revisited. In: Proceedings of EC, pp. 100\u2013109 (2006)","DOI":"10.1145\/1134707.1134719"},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"Elkind, E., Goldberg, L.A., Goldberg, P.W.: Computing good Nash equilibria in graphical games. In: Proceedings of EC, pp. 162\u2013171 (2007)","DOI":"10.1145\/1250910.1250935"},{"key":"8_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-642-33996-7_10","volume-title":"Algorithmic Game Theory","author":"J Fearnley","year":"2012","unstructured":"Fearnley, J., Goldberg, P.W., Savani, R., S\u00f8rensen, T.B.: Approximate well-supported Nash equilibria below two-thirds. In: Serna, M. (ed.) SAGT 2012. LNCS, pp. 108\u2013119. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-33996-7_10"},{"key":"8_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/978-3-662-47672-7_45","volume-title":"Automata, Languages, and Programming","author":"J Garg","year":"2015","unstructured":"Garg, J., Mehta, R., Vazirani, V.V., Yazdanbod, S.: ETR-completeness for decision versions of multi-player (symmetric) Nash equilibria. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 554\u2013566. Springer, Heidelberg (2015). doi:10.1007\/978-3-662-47672-7_45"},{"issue":"1","key":"8_CR27","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0899-8256(89)90006-7","volume":"1","author":"I Gilboa","year":"1989","unstructured":"Gilboa, I., Zemel, E.: Nash and correlated equilibria: some complexity considerations. Games Econ. Behav. 1(1), 80\u201393 (1989)","journal-title":"Games Econ. Behav."},{"issue":"38\u201340","key":"8_CR28","doi-asserted-by":"publisher","first-page":"3901","DOI":"10.1016\/j.tcs.2009.05.030","volume":"410","author":"G Greco","year":"2009","unstructured":"Greco, G., Scarcello, F.: On the complexity of constrained Nash equilibria in graphical games. Theor. Comput. Sci. 410(38\u201340), 3901\u20133924 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"8_CR29","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1137\/090766991","volume":"40","author":"E Hazan","year":"2011","unstructured":"Hazan, E., Krauthgamer, R.: How hard is it to approximate the best Nash equilibrium? SIAM J. Comput. 40(1), 79\u201391 (2011)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"8_CR30","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":"8_CR31","doi-asserted-by":"crossref","unstructured":"Lipton, R.J., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proceedings of EC, pp. 36\u201341 (2003)","DOI":"10.1145\/779928.779933"},{"issue":"4","key":"8_CR32","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1007\/s00454-001-0047-6","volume":"26","author":"C Moore","year":"2001","unstructured":"Moore, C., Robson, J.M.: Hard tiling problems with simple tiles. Discrete Comput. Geom. 26(4), 573\u2013590 (2001)","journal-title":"Discrete Comput. Geom."},{"key":"8_CR33","unstructured":"Ortiz, L.E., Irfan, M.T.: FPTAS for mixed-strategy Nash equilibria in tree graphical games and their generalizations. CoRR, abs\/1602.05237 (2016)"},{"key":"8_CR34","doi-asserted-by":"crossref","unstructured":"Ortiz, L.E., Irfan, M.T.: Tractable algorithms for approximate Nash equilibria in generalized graphical games with tree structure. In: Proceedings of AAAI, pp. 635\u2013641 (2017)","DOI":"10.1609\/aaai.v31i1.10602"},{"key":"8_CR35","doi-asserted-by":"crossref","unstructured":"Rubinstein, A.: Inapproximability of Nash equilibrium. In: Proceedings of STOC, pp. 409\u2013418 (2015)","DOI":"10.1145\/2746539.2746578"},{"issue":"4","key":"8_CR36","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":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-66700-3_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T23:26:38Z","timestamp":1750807598000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-66700-3_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319666990","9783319667003"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-66700-3_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"19 August 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SAGT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Algorithmic Game Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"L'Aquila","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 September 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 September 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sagt2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cs.gssi.infn.it\/sagt2017","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}