{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T02:23:59Z","timestamp":1743042239989,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642450457"},{"type":"electronic","value":"9783642450464"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45046-4_2","type":"book-chapter","created":{"date-parts":[[2013,12,9]],"date-time":"2013-12-09T12:53:01Z","timestamp":1386593581000},"page":"15-23","source":"Crossref","is-referenced-by-count":6,"title":["Polylogarithmic Supports Are Required for Approximate Well-Supported Nash Equilibria below 2\/3"],"prefix":"10.1007","author":[{"given":"Yogesh","family":"Anbalagan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergey","family":"Norin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Savani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adrian","family":"Vetta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0024-3795(94)90357-3","volume":"199","author":"I. Alth\u00f6fer","year":"1994","unstructured":"Alth\u00f6fer, I.: On sparse approximations to randomized strategies and convex combinations. Linear Algebra and its Applications\u00a0199, 339\u2013355 (1994)","journal-title":"Linear Algebra and its Applications"},{"issue":"4","key":"2_CR2","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1002\/rsa.20199","volume":"31","author":"I. B\u00e1r\u00e1ny","year":"2007","unstructured":"B\u00e1r\u00e1ny, I., Vempala, S., Vetta, A.: Nash equilibria in random games. Random Struct. Algorithms\u00a031(4), 391\u2013405 (2007)","journal-title":"Random Struct. Algorithms"},{"issue":"1","key":"2_CR3","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. Theoretical Computer Science\u00a0411(1), 164\u2013173 (2010)","journal-title":"Theoretical Computer Science"},{"key":"2_CR4","first-page":"181","volume":"21","author":"L. Caccetta","year":"1978","unstructured":"Caccetta, L., H\u00e4ggkvist, R.: On minimal digraphs with given girth. Congressus Numerantium\u00a021, 181\u2013187 (1978)","journal-title":"Congressus Numerantium"},{"issue":"3","key":"2_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. Journal of the ACM\u00a056(3), 1\u201357 (2009)","journal-title":"Journal of the ACM"},{"issue":"1","key":"2_CR6","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C. Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P., Papadimitriou, C.: The complexity of computing a Nash equilibrium. SIAM Journal on Computing\u00a039(1), 195\u2013259 (2009)","journal-title":"SIAM Journal on Computing"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.: Progress in approximate Nash equilibria. In: ACM Conference on Electronic Commerce (EC), pp. 355\u2013358 (2007)","DOI":"10.1145\/1250910.1250962"},{"issue":"17","key":"2_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.: A note on approximate Nash equilibria. Theoretical Computer Science\u00a0410(17), 1581\u20131588 (2009)","journal-title":"Theoretical Computer Science"},{"key":"2_CR9","doi-asserted-by":"crossref","unstructured":"Even-Zohar, C., Linial, N.: Triply existentially complete triangle-free graphs, arxiv.org\/1306.5637 (2013)","DOI":"10.1002\/jgt.21808"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Fearnley, J., Goldberg, P., Savani, R., S\u00f8rensen, T.: Approximate well-supported Nash equilibria below two-thirds. In: International Symposium on Algorithmic Game Theory (SAGT), pp. 108\u2013119 (2012)","DOI":"10.1007\/978-3-642-33996-7_10"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"Feder, T., Nazerzadeh, H., Saberi, A.: Approximating Nash equilibria using small-support strategies. In: ACM Conference on Electronic Commerce, EC (2007)","DOI":"10.1145\/1250910.1250961"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Goldberg, P., Papadimitriou, C.: Reducability among equilibrium problems. In: STOC (2006)","DOI":"10.1145\/1132516.1132526"},{"key":"2_CR13","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/s00453-008-9227-6","volume":"57","author":"S. Kontogiannis","year":"2010","unstructured":"Kontogiannis, S., Spirakis, P.: Well supported approximate equilibria in bimatrix games. Algorithmica\u00a057, 653\u2013667 (2010)","journal-title":"Algorithmica"},{"key":"2_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/978-3-540-73420-8_52","volume-title":"Automata, Languages and Programming","author":"S.C. Kontogiannis","year":"2007","unstructured":"Kontogiannis, S.C., Spirakis, P.G.: Efficient algorithms for constant well supported approximate equilibria in bimatrix games. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 595\u2013606. Springer, Heidelberg (2007)"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"Lipton, R., Markakis, E., Mehta, A.: Playing large games using simple startegies. In: ACM Conference on Electronic Commerce (EC), pp. 36\u201341 (2003)","DOI":"10.1145\/779928.779933"},{"issue":"1","key":"2_CR16","doi-asserted-by":"crossref","first-page":"6","DOI":"10.37236\/1667","volume":"9","author":"J. Shen","year":"2002","unstructured":"Shen, J., Yuster, R.: A note on the number of edges guaranteeing a C\n                        4 in Eulerian bipartite digraphs. Electronic Journal of Combinatorics\u00a09(1), Note 6 (2002)","journal-title":"Electronic Journal of Combinatorics"},{"issue":"4","key":"2_CR17","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.: An optimization approach for approximate Nash equilibria. Internet Mathematics\u00a05(4), 365\u2013382 (2008)","journal-title":"Internet Mathematics"}],"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-642-45046-4_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,14]],"date-time":"2023-02-14T09:19:12Z","timestamp":1676366352000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-45046-4_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450457","9783642450464"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45046-4_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}