{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:04:10Z","timestamp":1725563050295},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_24","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"312-325","source":"Crossref","is-referenced-by-count":5,"title":["Exploiting Concavity in Bimatrix Games: New Polynomially Tractable Subclasses"],"prefix":"10.1007","author":[{"given":"Spyros","family":"Kontogiannis","sequence":"first","affiliation":[]},{"given":"Paul","family":"Spirakis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"24_CR1","doi-asserted-by":"crossref","first-page":"309","DOI":"10.7155\/jgaa.00147","volume":"11","author":"L. Addario-Berry","year":"2007","unstructured":"Addario-Berry, L., Olver, N., Vetta, A.: A polynomial time algorithm for finding nash equilibria in planar win-lose games. Journal of Graph Algorithms and Applications\u00a011(1), 309\u2013319 (2007)","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"24_CR2","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":"24_CR3","volume-title":"Nonlinear Programming: Theory and Algorithms","author":"M.S. Bazaraa","year":"1993","unstructured":"Bazaraa, M.S., Sherali, H.D., Shetty, C.: Nonlinear Programming: Theory and Algorithms, 2nd edn. John Wiley & Sons, Inc., Chichester (1993)","edition":"2"},{"key":"24_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-540-77105-0_6","volume-title":"Internet and Network Economics","author":"H. Bosse","year":"2007","unstructured":"Bosse, H., Byrka, J., Markakis, E.: New algorithms for approximate nash equilibria in bimatrix games. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol.\u00a04858, pp. 17\u201329. Springer, Heidelberg (2007)"},{"key":"24_CR5","volume-title":"Convex Optimization","author":"S. Boyd","year":"2009","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization, 7th edn. Cambridge University Press, Cambridge (2009)","edition":"7"},{"key":"24_CR6","first-page":"261","volume-title":"Proc. of 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 47th IEEE Symp. on Found. of Comp. Sci. (FOCS\u00a02006), pp. 261\u2013272. IEEE Comp. Soc. Press, Los Alamitos (2006)"},{"key":"24_CR7","first-page":"603","volume-title":"Proc. of 47th IEEE Symp. on Found. of Comp. Sci. (FOCS\u00a02006)","author":"X. Chen","year":"2006","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Computing nash equilibria: Approximation and smoothed complexity. In: Proc. of 47th IEEE Symp. on Found. of Comp. Sci. (FOCS\u00a02006), pp. 603\u2013612. IEEE Comp. Soc. Press, Los Alamitos (2006)"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/11841036_23","volume-title":"Algorithms \u2013 ESA 2006","author":"B. Codenotti","year":"2006","unstructured":"Codenotti, B., Leoncini, M., Resta, G.: Efficient computation of nash equilibria for very sparse win-lose bimatrix games. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 232\u2013243. Springer, Heidelberg (2006)"},{"key":"24_CR9","first-page":"765","volume-title":"Proc. of 18th Int. Joint Conf. on Art. Intel. (IJCAI\u00a02003)","author":"V. Conitzer","year":"2003","unstructured":"Conitzer, V., Sandholm, T.: Complexity results about nash equilibria. In: Proc. of 18th Int. Joint Conf. on Art. Intel. (IJCAI\u00a02003), pp. 765\u2013771. Morgan Kaufmann, San Francisco (2003)"},{"issue":"1","key":"24_CR10","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 Journal on Computing\u00a039(1), 195\u2013259 (2009); Preliminary version in ACM STOC 2006","journal-title":"SIAM Journal on Computing"},{"key":"24_CR11","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)"},{"doi-asserted-by":"crossref","unstructured":"Daskalakis, C., Mehta, A., Papadimitriou, C.: Progress in approximate nash equilibrium. In: Proc. of 8th ACM Conf. on El. Comm. (EC 2007), pp. 355\u2013358 (2007)","key":"24_CR12","DOI":"10.1145\/1250910.1250962"},{"unstructured":"Daskalakis, C., Papadimitriou, C.: Three player games are hard. Technical Report TR05-139, Electr. Coll. on Comp. Compl., ECCC (2005)","key":"24_CR13"},{"doi-asserted-by":"crossref","unstructured":"Even-Dar, E., Mansour, Y., Nadav, U.: On the convergence of regret minimization dynamics in concave games. In: Proc. of 41st ACM Symp. on Th. of Comp. (STOC 2009), pp. 523\u2013532 (2009)","key":"24_CR14","DOI":"10.1145\/1536414.1536486"},{"key":"24_CR15","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":"24_CR16","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/s00199-009-0436-2","volume":"42","author":"R. Kannan","year":"2010","unstructured":"Kannan, R., Theobald, T.: Games of fixed rank: A hierarchy of bimatrix games. Economic Theory\u00a042, 157\u2013173 (2010); Preliminary version appeared in ACM-SIAM SODA 2007","journal-title":"Economic Theory"},{"key":"24_CR17","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)"},{"doi-asserted-by":"crossref","unstructured":"Kontogiannis, S., Spirakis, P.: Exploiting concavity in bimatrix games: New polynomially tractable subclasses. In: Proc. of 13th W. on Appr. Alg. for Comb. Opt., APPROX\u201910 (2010), http:\/\/www.cs.uoi.gr\/~kontog\/pubs\/approx10paper-full.pdf","key":"24_CR18","DOI":"10.1007\/978-3-642-15369-3_24"},{"key":"24_CR19","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":"24_CR20","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0112033","volume":"12","author":"C. Lemke","year":"1964","unstructured":"Lemke, C., Howson, J.: 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":"24_CR21","first-page":"36","volume-title":"Proc. of 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 4th ACM Conf. on El. Comm (EC\u00a0 2003), pp. 36\u201341. Assoc. of Comp. Mach. (ACM), New York (2003)"},{"issue":"3","key":"24_CR22","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/0022-247X(64)90021-6","volume":"9","author":"O.L. Mangasarian","year":"1964","unstructured":"Mangasarian, O.L., Stone, H.: Two-person nonzero-sum games and quadratic programming. Journal of Mathematical Analysis and Applications\u00a09(3), 348\u2013355 (1964)","journal-title":"Journal of Mathematical Analysis and Applications"},{"volume-title":"The Theory of Games and Economic Behavior","year":"1947","author":"O. Morgenstern","unstructured":"Morgenstern, O., von Neumann, J.: The Theory of Games and Economic Behavior. Princeton University Press, Princeton (1947)","key":"24_CR23"},{"key":"24_CR24","doi-asserted-by":"publisher","first-page":"296","DOI":"10.2307\/1969530","volume":"54","author":"J. Robinson","year":"1951","unstructured":"Robinson, J.: An iterative method of solving a game. Annals of Mathematics\u00a054, 296\u2013301 (1951)","journal-title":"Annals of Mathematics"},{"issue":"3","key":"24_CR25","doi-asserted-by":"publisher","first-page":"520","DOI":"10.2307\/1911749","volume":"33","author":"J. Rosen","year":"1965","unstructured":"Rosen, J.: Existence and uniqueness of equilibrium points for concave n\u2009\u2212person games. Econometrica\u00a033(3), 520\u2013534 (1965)","journal-title":"Econometrica"},{"doi-asserted-by":"crossref","unstructured":"Savani, R., von Stengel, B.: Exponentially many steps for finding a nash equilibrium in a bimatrix game. In: Proc. of 45th IEEE Symp. on Found. of Comp. Sci. (FOCS 2004), pp. 258\u2013267 (2004)","key":"24_CR26","DOI":"10.1109\/FOCS.2004.28"},{"key":"24_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1007\/978-3-540-77105-0_8","volume-title":"Internet and Network Economics","author":"H. Tsaknakis","year":"2007","unstructured":"Tsaknakis, H., Spirakis, P.G.: An optimization approach for approximate nash equilibria. In: Deng, X., Graham, F.C. (eds.) WINE 2007. LNCS, vol.\u00a04858, pp. 42\u201356. Springer, Heidelberg (2007)"},{"unstructured":"Tsaknakis, H., Spirakis, P.G.: A graph spectral approach for computing approximate nash equilibria. Technical report, Electronic Colloquium on Computational Complexity, Report No. 96 (2009)","key":"24_CR28"},{"key":"24_CR29","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF01581085","volume":"57","author":"S. Vavasis","year":"1992","unstructured":"Vavasis, S.: Approximation algorithms for indefinite quadratic programming. Mathematical Programming\u00a057, 279\u2013311 (1992)","journal-title":"Mathematical Programming"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:05:24Z","timestamp":1606187124000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}