{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T12:18:33Z","timestamp":1725538713447},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642046445"},{"type":"electronic","value":"9783642046452"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-04645-2_22","type":"book-chapter","created":{"date-parts":[[2009,10,7]],"date-time":"2009-10-07T07:14:23Z","timestamp":1254899663000},"page":"238-249","source":"Crossref","is-referenced-by-count":1,"title":["The Computational Complexity of Weak Saddles"],"prefix":"10.1007","author":[{"given":"Felix","family":"Brandt","sequence":"first","affiliation":[]},{"given":"Markus","family":"Brill","sequence":"additional","affiliation":[]},{"given":"Felix","family":"Fischer","sequence":"additional","affiliation":[]},{"given":"Jan","family":"Hoffmann","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0165-1765(91)90179-O","volume":"36","author":"K. Basu","year":"1991","unstructured":"Basu, K., Weibull, J.: Strategy subsets closed under rational behavior. Economics Letters\u00a036, 141\u2013146 (1991)","journal-title":"Economics Letters"},{"key":"22_CR2","unstructured":"Baumeister, D., Brandt, F., Fischer, F., Hoffmann, J., Rothe, J.: The complexity of computing minimal unidirectional covering sets. Technical report (2009), http:\/\/arxiv.org\/abs\/0901.3692"},{"issue":"4","key":"22_CR3","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.2307\/1911196","volume":"52","author":"B. Bernheim","year":"1984","unstructured":"Bernheim, B.: Rationalizable strategic behavior. Econometrica\u00a052(4), 1007\u20131028 (1984)","journal-title":"Econometrica"},{"issue":"2","key":"22_CR4","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/j.mathsocsci.2008.04.001","volume":"56","author":"F. Brandt","year":"2008","unstructured":"Brandt, F., Fischer, F.: Computing the minimal covering set. Mathematical Social Sciences\u00a056(2), 254\u2013268 (2008)","journal-title":"Mathematical Social Sciences"},{"key":"22_CR5","doi-asserted-by":"crossref","unstructured":"Brandt, F., Brill, M., Fischer, F., Harrenstein, P.: Computational aspects of Shapley\u2019s saddles. In: Proc.\u00a0of 8th AAMAS Conference, pp. 209\u2013216 (2009)","DOI":"10.1145\/1980522.1980525"},{"key":"22_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/978-3-642-04645-2_26","volume-title":"SAGT 2009","author":"F. Brandt","year":"2009","unstructured":"Brandt, F., Brill, M., Fischer, F., Harrenstein, P.: On the complexity of iterated weak dominance in constant-sum games. In: Mavronicolas, M., Papadopoulou, V.G. (eds.) SAGT 2009. LNCS, vol.\u00a05814, pp. 287\u2013298. Springer, Heidelberg (2009)"},{"key":"22_CR7","first-page":"261","volume-title":"Proc.\u00a0of 47th FOCS Symposium","author":"X. Chen","year":"2006","unstructured":"Chen, X., Deng, X.: Settling the complexity of 2-player Nash-equilibrium. In: Proc.\u00a0of 47th FOCS Symposium, pp. 261\u2013272. IEEE Press, Los Alamitos (2006)"},{"key":"22_CR8","first-page":"88","volume-title":"Proc.\u00a0of 6th ACM-EC Conference","author":"V. Conitzer","year":"2005","unstructured":"Conitzer, V., Sandholm, T.: Complexity of (iterated) dominance. In: Proc.\u00a0of 6th ACM-EC Conference, pp. 88\u201397. ACM Press, New York (2005)"},{"key":"22_CR9","first-page":"71","volume-title":"Proc.\u00a0of 38th STOC","author":"C. Daskalakis","year":"2006","unstructured":"Daskalakis, C., Goldberg, P., Papadimitriou, C.: The complexity of computing a Nash equilibrium. In: Proc.\u00a0of 38th STOC, pp. 71\u201378. ACM Press, New York (2006)"},{"key":"22_CR10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1006\/jeth.1996.0085","volume":"70","author":"J. Duggan","year":"1996","unstructured":"Duggan, J., Le Breton, M.: Dutta\u2019s minimal covering set and Shapley\u2019s saddles. Journal of Economic Theory\u00a070, 257\u2013265 (1996)","journal-title":"Journal of Economic Theory"},{"key":"22_CR11","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/0022-0531(88)90096-8","volume":"44","author":"B. Dutta","year":"1988","unstructured":"Dutta, B.: Covering sets and a new Condorcet choice correspondence. Journal of Economic Theory\u00a044, 63\u201380 (1988)","journal-title":"Journal of Economic Theory"},{"issue":"3","key":"22_CR12","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1287\/moor.18.3.553","volume":"18","author":"I. Gilboa","year":"1993","unstructured":"Gilboa, I., Kalai, E., Zemel, E.: The complexity of eliminating dominated strategies. Mathematics of Operations Research\u00a018(3), 553\u2013565 (1993)","journal-title":"Mathematics of Operations Research"},{"issue":"6","key":"22_CR13","doi-asserted-by":"publisher","first-page":"806","DOI":"10.1145\/268999.269002","volume":"44","author":"E. Hemaspaandra","year":"1997","unstructured":"Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Exact analysis of Dodgson elections: Lewis Carroll\u2019s 1876 voting system is complete for parallel access to NP. Journal of the ACM\u00a044(6), 806\u2013825 (1997)","journal-title":"Journal of the ACM"},{"key":"22_CR14","volume-title":"Games and Decisions: Introduction and Critical Survey","author":"R.D. Luce","year":"1957","unstructured":"Luce, R.D., Raiffa, H.: Games and Decisions: Introduction and Critical Survey. John Wiley & Sons Inc., Chichester (1957)"},{"issue":"4","key":"22_CR15","doi-asserted-by":"publisher","first-page":"1172","DOI":"10.2307\/1959383","volume":"70","author":"R.D. McKelvey","year":"1976","unstructured":"McKelvey, R.D., Ordeshook, P.C.: Symmetric spatial games without majority rule equilibria. The American Political Science Review\u00a070(4), 1172\u20131184 (1976)","journal-title":"The American Political Science Review"},{"key":"22_CR16","volume-title":"Game Theory: Analysis of Conflict","author":"R.B. Myerson","year":"1991","unstructured":"Myerson, R.B.: Game Theory: Analysis of Conflict. Harvard University Press, Cambridge (1991)"},{"issue":"2","key":"22_CR17","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"},{"key":"22_CR18","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"issue":"4","key":"22_CR19","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.2307\/1911197","volume":"52","author":"D. Pearce","year":"1984","unstructured":"Pearce, D.: Rationalizable strategic behavior and the problem of perfection. Econometrica\u00a052(4), 1029\u20131050 (1984)","journal-title":"Econometrica"},{"key":"22_CR20","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0899-8256(92)90020-S","volume":"4","author":"L. Samuelson","year":"1992","unstructured":"Samuelson, L.: Dominated strategies and common knowledge. Games and Economic Behavior\u00a04, 284\u2013313 (1992)","journal-title":"Games and Economic Behavior"},{"key":"22_CR21","unstructured":"Shapley, L.: Order matrices. I. Technical Report RM-1142, The RAND Corporation (1953)"},{"key":"22_CR22","unstructured":"Shapley, L.: Order matrices. II. Technical Report RM-1145, The RAND Corporation (1953)"},{"key":"22_CR23","series-title":"Annals of Mathematics Studies","first-page":"1","volume-title":"Advances in Game Theory","author":"L. Shapley","year":"1964","unstructured":"Shapley, L.: Some topics in two-person games. In: Dresher, M., Shapley, L.S., Tucker, A.W. (eds.) Advances in Game Theory. Annals of Mathematics Studies, vol.\u00a052, pp. 1\u201329. Princeton University Press, Princeton (1964)"},{"key":"22_CR24","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01448847","volume":"100","author":"J. Neumann von","year":"1928","unstructured":"von Neumann, J.: Zur Theorie der Gesellschaftspiele. Mathematische Annalen\u00a0100, 295\u2013320 (1928)","journal-title":"Mathematische Annalen"},{"key":"22_CR25","volume-title":"Theory of Games and Economic Behavior","author":"J. Neumann von","year":"1944","unstructured":"von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behavior. Princeton University Press, Princeton (1944)"},{"key":"22_CR26","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0304-3975(87)90049-1","volume":"51","author":"K. Wagner","year":"1987","unstructured":"Wagner, K.: More complicated questions about maxima and minima, and some closures of NP. Theoretical Computer Science\u00a051, 53\u201380 (1987)","journal-title":"Theoretical Computer Science"}],"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-04645-2_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:43:04Z","timestamp":1606167784000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04645-2_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642046445","9783642046452"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04645-2_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}