{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:33:00Z","timestamp":1771036380014,"version":"3.50.1"},"reference-count":37,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2009,7,17]],"date-time":"2009-07-17T00:00:00Z","timestamp":1247788800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["BR 2312\/3-1"],"award-info":[{"award-number":["BR 2312\/3-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["BR 2312\/3-2"],"award-info":[{"award-number":["BR 2312\/3-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Social choice rules are often evaluated and compared by inquiring whether they satisfy certain desirable criteria such as the <jats:italic>Condorcet criterion<\/jats:italic>, which states that an alternative should always be chosen when more than half of the voters prefer it over any other alternative. Many of these criteria can be formulated in terms of choice sets that single out reasonable alternatives based on the preferences of the voters. In this paper, we consider choice sets whose definition merely relies on the pairwise majority relation. These sets include the <jats:italic>Copeland set<\/jats:italic>, the <jats:italic>Smith set<\/jats:italic>, the <jats:italic>Schwartz set<\/jats:italic>, <jats:italic>von Neumann\u2010Morgenstern stable sets<\/jats:italic>, the <jats:italic>Banks set<\/jats:italic>, and the <jats:italic>Slater set<\/jats:italic>. We investigate the relationships between these sets and completely characterize their computational complexity, which allows us to obtain hardness results for entire classes of social choice rules (\u00a9 2009 WILEY\u2010VCH Verlag GmbH &amp; Co. KGaA, Weinheim)<\/jats:p>","DOI":"10.1002\/malq.200810027","type":"journal-article","created":{"date-parts":[[2009,7,18]],"date-time":"2009-07-18T07:49:09Z","timestamp":1247903349000},"page":"444-459","source":"Crossref","is-referenced-by-count":24,"title":["The Computational Complexity of Choice Sets"],"prefix":"10.1002","volume":"55","author":[{"given":"Felix","family":"Brandt","sequence":"first","affiliation":[]},{"given":"Felix","family":"Fischer","sequence":"additional","affiliation":[]},{"given":"Paul","family":"Harrenstein","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2009,7,17]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.2307\/1907651"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.2307\/1907926"},{"key":"e_1_2_1_4_2","unstructured":"M.de Condorcet Essai sur l'application de l'analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix (Imprimerie Royale 1785; facsimile published by Chelsea Publishing Company 1972)."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/0133030"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00303169"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"P.Faliszewski E.Hemaspaandra L.Hemaspaandra andJ.Rothe A richer understanding of the complexity of election systems. In: Fundamental Problems in Computing: Essays in Honor of Professor Daniel J. Rosenkrantz (S. Ravi and S. Shukla eds.) (Springer\u2010Verlag 2009).","DOI":"10.1007\/978-1-4020-9688-4_14"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"J.\u2010F.Laslier Tournament Solutions and Majority Voting (Springer\u2010Verlag 1997).","DOI":"10.1007\/978-3-642-60805-6"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0165-4896(94)00778-7"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00292732"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.2307\/2110736"},{"key":"e_1_2_1_12_2","unstructured":"A. H.Copeland A \u2018reasonable\u2019 social welfare function. Mimeographed University of Michigan Seminar on Applications of Mathematics to the Social Sciences (1951)."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01718625"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.2307\/1914033"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.2307\/2216143"},{"key":"e_1_2_1_16_2","unstructured":"T. N.Tideman Collective Decisions And Voting: The Potential for Public Choice (Ashgate 2006)."},{"key":"e_1_2_1_17_2","unstructured":"J.von Neumann andO.Morgenstern The Theory of Games and Economic Behavior (Princeton University Press 1944)."},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","unstructured":"W. F.Lucas Von Neumann\u2010Morgenstern stable sets. In: Handbook of Game Theory with Economic Applications volume I (R. J. Aumann and S. Hart eds.) pp. 543\u2013590 (North\u2010Holland 1992).","DOI":"10.1016\/S1574-0005(05)80020-7"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(88)90096-8"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00177663"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.2298\/YJOR0401033L"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00649265"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00435496"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/48.3-4.303"},{"key":"e_1_2_1_25_2","first-page":"365","article-title":"Slater's winners of a tournament may not be in the Banks set","volume":"8","author":"Lafiond G.","year":"1991","journal-title":"Social Choice and Welfare"},{"key":"e_1_2_1_26_2","doi-asserted-by":"crossref","unstructured":"D. S.Johnson A catalog of complexity classes. In: Handbook of Theoretical Computer Science volume A. (J. van Leeuwen ed.) pp. 67\u2013161 (Elsevier 1990).","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90038-6"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/0213028"},{"key":"e_1_2_1_29_2","unstructured":"T.Tantau A note on the complexity of the reachability problem for tournaments. ECCC Report TR01\u2010092 Electronic Colloquium on Computational Complexity (2001)."},{"key":"e_1_2_1_30_2","first-page":"143","article-title":"On dominance relations and the structure of animal societies: III","volume":"15","author":"Landau H. G.","year":"1953","journal-title":"The condition for a score structure. Bulletin of Mathematical Biology"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(77)90125-9"},{"key":"e_1_2_1_32_2","unstructured":"V.Chv\u00e1tal On the computational complexity of finding a kernel. Report CRM\u2010300 Centre de Recherches Math\u00e9matiques Universit\u00e9 de Montr\u00e9al (1973)."},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/s003550200197"},{"key":"e_1_2_1_34_2","unstructured":"F.Brandt F.Fischer P.Harrenstein andM.Mair A computational analysis of the tournament equilibrium set. In: Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI) (D. Fox and C. P. Gomes eds.) pp. 38\u201343 (AAAI Press 2008)."},{"key":"e_1_2_1_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-003-0241-y"},{"key":"e_1_2_1_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.08.031"},{"key":"e_1_2_1_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/050623905"},{"key":"e_1_2_1_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2008.04.001"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200810027","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200810027","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.200810027","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T23:18:56Z","timestamp":1699917536000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.200810027"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,17]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1002\/malq.200810027"],"URL":"https:\/\/doi.org\/10.1002\/malq.200810027","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7,17]]}}}