{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T16:26:05Z","timestamp":1759335965786},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744559"},{"type":"electronic","value":"9783540744566"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74456-6_53","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T07:29:48Z","timestamp":1187076588000},"page":"596-608","source":"Crossref","is-referenced-by-count":3,"title":["Well Supported Approximate Equilibria in Bimatrix Games: A Graph Theoretic Approach"],"prefix":"10.1007","author":[{"given":"Spyros C.","family":"Kontogiannis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"53_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 Applications\u00a0199, 339\u2013355 (1994)","journal-title":"Linear Algebra and Applications"},{"key":"53_CR2","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1109\/SFCS.2005.52","volume-title":"Proc. of the 46th IEEE Symp. on Found. of Comp. Sci. (FOCS 2005)","author":"I. B\u00e1r\u00e1ny","year":"2005","unstructured":"B\u00e1r\u00e1ny, I., Vempala, S., Vetta, A.: Nash equilibria in random games. In: Proc. of the 46th IEEE Symp. on Found. of Comp. Sci (FOCS 2005), pp. 123\u2013131. IEEE Computer Society Press, Los Alamitos (2005)"},{"key":"53_CR3","first-page":"261","volume-title":"Proc. of the 47th IEEE Symp. on Found. of Comp. Sci. (FOCS\u00a02006)","author":"X. Chen","year":"2006","unstructured":"Chen, X., Deng, X.: Settling the complexity of 2-player nash equilibrium. In: Proc. of the 47th IEEE Symp. on Found. of Comp. Sci (FOCS\u00a02006), pp. 261\u2013272. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"53_CR4","first-page":"603","volume-title":"Proc. of the 47th IEEE Symp. on Found. of Comp. Sci. (FOCS\u00a02006)","author":"X. Chen","year":"2006","unstructured":"Chen, X., Deng, X., Teng, S.: Computing nash equilibria: Approximation and smoothed complexity. In: Proc. of the 47th IEEE Symp. on Found. of Comp. Sci (FOCS\u00a02006), pp. 603\u2013612. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"53_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/11944874_24","volume-title":"Internet and Network Economics","author":"X. Chen","year":"2006","unstructured":"Chen, X., Deng, X., Teng, S.: Sparse games are hard. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol.\u00a04286, pp. 262\u2013273. Springer, Heidelberg (2006)"},{"unstructured":"Conitzer, V., Sandholm, T.: Complexity results about nash equilibria. In: Proc. of the 18th Int. Joint Conf. on Art. Intel (IJCAI\u00a0 2003), pp. 765\u2013771 (2003)","key":"53_CR6"},{"key":"53_CR7","first-page":"71","volume-title":"Proc. of the 38th ACM Symp. on Th. of Comp. (STOC\u00a02006)","author":"C. Daskalakis","year":"2006","unstructured":"Daskalakis, C., Goldberg, P., Papadimitriou, C.: The complexity of computing a nash equilibrium. In: Proc. of the 38th ACM Symp. on Th. of Comp (STOC\u00a02006), pp. 71\u201378. ACM Press, New York (2006)"},{"key":"53_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/11944874_27","volume-title":"Internet and Network Economics","author":"C. Daskalakis","year":"2006","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.: A note on approximate equilibria. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol.\u00a04286, pp. 297\u2013306. Springer, Heidelberg (2006)"},{"key":"53_CR9","volume-title":"Proc. of the 8th ACM Conf. on El. Comm. (EC\u00a02007)","author":"C. Daskalakis","year":"2007","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.: Progress in approximate nash equilibrium. In: Proc. of the 8th ACM Conf. on El. Comm (EC\u00a02007), ACM Press, New York (2007)"},{"unstructured":"Daskalakis, C., Papadimitriou, C.: Three player games are hard. Technical Report TR05-139, Electr. Coll. on Comp. Compl (ECCC) (2005)","key":"53_CR10"},{"key":"53_CR11","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. Behavior\u00a01, 80\u201393 (1989)","journal-title":"Games & Econ. Behavior"},{"key":"53_CR12","first-page":"61","volume-title":"Proc. of the 38th ACM Symp. on Th. of Comp (STOC\u00a02006)","author":"P. Goldberg","year":"2006","unstructured":"Goldberg, P., Papadimitriou, C.: Reducibility among equilibrium problems. In: Proc. of the 38th ACM Symp. on Th. of Comp (STOC\u00a02006), pp. 61\u201370. ACM Press, New York (2006)"},{"key":"53_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/3-540-45022-X_7","volume-title":"Automata, Languages and Programming","author":"T. Hagerup","year":"2000","unstructured":"Hagerup, T.: Improved shortest paths on the word ram. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 61\u201372. Springer, Heidelberg (2000)"},{"key":"53_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1007\/11944874_26","volume-title":"Internet and Network Economics","author":"S. Kontogiannis","year":"2006","unstructured":"Kontogiannis, S., Panagopoulou, P., Spirakis, P.: Polynomial algorithms for approximating nash equilibria in bimatrix games. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol.\u00a04286, pp. 286\u2013296. Springer, Heidelberg (2006)"},{"key":"53_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1007\/978-3-540-73420-8_52","volume-title":"Proc. of the 34th Int. Col. on Aut. Lang. and Progr (ICALP\u00a02007)","author":"S. Kontogiannis","year":"2007","unstructured":"Kontogiannis, S., Spirakis, P.: Efficient algorithms for constant well supported approximate equilibria in bimatrix games. In: Proc. of the 34th Int. Col. on Aut. Lang. and Progr (ICALP\u00a02007). LNCS, vol.\u00a04596, pp. 595\u2013606. Springer, Heidelberg (2007)"},{"key":"53_CR16","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0112033","volume":"12","author":"C. Lemke","year":"1964","unstructured":"Lemke, C., Howson, J.T.: Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics\u00a012, 413\u2013423 (1964)","journal-title":"Journal of the Society for Industrial and Applied Mathematics"},{"key":"53_CR17","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/779928.779933","volume-title":"Proc. of the 4th ACM Conf. on El. Comm (EC\u00a0 2003)","author":"R. Lipton","year":"2003","unstructured":"Lipton, R., Markakis, E., Mehta, A.: Playing large games using simple strategies. In: Proc. of the 4th ACM Conf. on El. Comm (EC\u00a0 2003), pp. 36\u201341. ACM Press, New York (2003)"},{"key":"53_CR18","doi-asserted-by":"publisher","first-page":"289","DOI":"10.2307\/1969529","volume":"54","author":"J. Nash","year":"1951","unstructured":"Nash, J.: Noncooperative games. Annals of Mathematics\u00a054, 289\u2013295 (1951)","journal-title":"Annals of Mathematics"},{"key":"53_CR19","first-page":"749","volume-title":"Proc. of the 33rd ACM Symp. on Th. of Comp (STOC\u00a02001)","author":"C. Papadimitriou","year":"2001","unstructured":"Papadimitriou, C.: Algorithms, games and the internet. In: Proc. of the 33rd ACM Symp. on Th. of Comp (STOC\u00a02001), pp. 749\u2013753. ACM Press, New York (2001)"},{"issue":"2","key":"53_CR20","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1111\/j.1468-0262.2006.00667.x","volume":"74","author":"R. Savani","year":"2006","unstructured":"Savani, R., von Stengel, B.: Hard-to-solve bimatrix games. Econometrica\u00a074(2), 397\u2013429 (2006)","journal-title":"Econometrica"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74456-6_53.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:29:22Z","timestamp":1619519362000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540744559","9783540744566"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}