{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:33:13Z","timestamp":1759638793598,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642339950"},{"type":"electronic","value":"9783642339967"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33996-7_4","type":"book-chapter","created":{"date-parts":[[2012,10,6]],"date-time":"2012-10-06T07:27:01Z","timestamp":1349508421000},"page":"37-48","source":"Crossref","is-referenced-by-count":4,"title":["The Complexity of Decision Problems about Nash Equilibria in Win-Lose Games"],"prefix":"10.1007","author":[{"given":"Vittorio","family":"Bil\u00f2","sequence":"first","affiliation":[]},{"given":"Marios","family":"Mavronicolas","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"crossref","unstructured":"Abbott, T., Kane, D., Valiant, P.: On the Complexity of Two-Player Win-Lose Games. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Sciences, pp. 113\u2013122 (October 2005)","DOI":"10.1109\/SFCS.2005.59"},{"key":"4_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/978-3-642-24829-0_19","volume-title":"Algorithmic Game Theory","author":"V. Bil\u00f2","year":"2011","unstructured":"Bil\u00f2, V., Mavronicolas, M.: Complexity of Rational and Irrational Nash Equilibria. In: Persiano, G. (ed.) SAGT 2011. LNCS, vol.\u00a06982, pp. 200\u2013211. Springer, Heidelberg (2011)"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Chen, X., Deng, X., Teng, S.-H.: Settling the Complexity of Computing Two-Player Nash Equilibria. Journal of the ACM\u00a056(3) (2009)","DOI":"10.1145\/1516512.1516516"},{"key":"4_CR4","unstructured":"Chen, X., Teng, S.-H., Valiant, P.: The Approximation Complexity of Win-Lose Games. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 159\u2013168 (January 2007)"},{"issue":"3","key":"4_CR5","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.ipl.2005.01.010","volume":"94","author":"B. Codenotti","year":"2005","unstructured":"Codenotti, B., Stefanovic, D.: On the Computational Complexity of Nash Equilibria for (0, 1) Bimatrix Games. Information Processing Letters\u00a094(3), 145\u2013150 (2005)","journal-title":"Information Processing Letters"},{"issue":"2","key":"4_CR6","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 and Economic Behavior\u00a063(2), 621\u2013641 (2008)","journal-title":"Games and Economic Behavior"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Daskalakis, C.: On the Complexity of Approximating a Nash Equilibrium. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1498\u20131517 (January 2011)","DOI":"10.1137\/1.9781611973082.117"},{"issue":"1","key":"4_CR8","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)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR9","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability \u2014 A Guide to the Theory of ${\\cal NP}$ -Completeness. W. H. Freeman (1979)"},{"issue":"1","key":"4_CR10","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 and Economic Behavior\u00a01(1), 80\u201393 (1989)","journal-title":"Games and Economic Behavior"},{"issue":"2","key":"4_CR11","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1016\/j.geb.2009.10.003","volume":"68","author":"A. McLennan","year":"2010","unstructured":"McLennan, A., Tourky, R.: Simple Complexity from Imitation Games. Games and Economic Behavior\u00a068(2), 683\u2013688 (2010)","journal-title":"Games and Economic Behavior"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(91)90200-L","volume":"81","author":"N. Megiddo","year":"1991","unstructured":"Megiddo, N., Papadimitriou, C.H.: On Total Functions, Existence Theorems and Computational Complexity. Theoretical Computer Science\u00a081, 317\u2013324 (1991)","journal-title":"Theoretical Computer Science"},{"key":"4_CR13","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1073\/pnas.36.1.48","volume":"36","author":"J.F. Nash","year":"1950","unstructured":"Nash, J.F.: Equilibrium Points in n-Person Games. Proceedings of the National Academy of Sciences of the United States of America\u00a036, 48\u201349 (1950)","journal-title":"Proceedings of the National Academy of Sciences of the United States of America"},{"issue":"2","key":"4_CR14","doi-asserted-by":"publisher","first-page":"286","DOI":"10.2307\/1969529","volume":"54","author":"J.F. Nash","year":"1951","unstructured":"Nash, J.F.: Non-Cooperative Games. Annals of Mathematics\u00a054(2), 286\u2013295 (1951)","journal-title":"Annals of Mathematics"},{"issue":"3","key":"4_CR15","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. Journal of Computer and System Sciences\u00a048(3), 498\u2013532 (1994)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Game Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33996-7_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,10]],"date-time":"2025-04-10T02:04:14Z","timestamp":1744250654000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33996-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642339950","9783642339967"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33996-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}