{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T22:30:19Z","timestamp":1717194619734},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,2,26]],"date-time":"2022-02-26T00:00:00Z","timestamp":1645833600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,26]],"date-time":"2022-02-26T00:00:00Z","timestamp":1645833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Ministry of Education","award":["Tier-1 grant 2018-T1-001-118"]},{"DOI":"10.13039\/501100001475","name":"Nanyang Technological University","doi-asserted-by":"crossref","award":["SUG M4081985"],"id":[{"id":"10.13039\/501100001475","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100007251","name":"National Research University Higher School of Economics","doi-asserted-by":"crossref","award":["Basic Research Program"],"id":[{"id":"10.13039\/501100007251","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s10458-022-09549-7","type":"journal-article","created":{"date-parts":[[2022,2,26]],"date-time":"2022-02-26T02:02:41Z","timestamp":1645840961000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The complexity of election problems with group-separable preferences"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-0332-4364","authenticated-orcid":false,"given":"Piotr","family":"Faliszewski","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Karpov","sequence":"additional","affiliation":[]},{"given":"Svetlana","family":"Obraztsova","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,26]]},"reference":[{"key":"9549_CR1","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/BF02522824","volume":"17","author":"L Alonso","year":"1997","unstructured":"Alonso, L., R\u00e9my, J.-L., & Schott, R. (1997). A linear time algorithm for the generation of trees. Algorithmica, 17, 162\u2013182.","journal-title":"Algorithmica"},{"key":"9549_CR2","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/S0020-0190(97)00174-9","volume":"64","author":"L Alonso","year":"1997","unstructured":"Alonso, L., R\u00e9my, J.-L., & Schott, R. (1997). Uniform generation of a Schr\u00f6der tree. Information Processing Letters, 64, 305\u2013308.","journal-title":"Information Processing Letters"},{"key":"9549_CR3","unstructured":"Aziz, H., Gaspers, S., Gudmundsson, J., Mackenzie, S., Mattei, N., & Walsh, T. (2015). Computational aspects of multi-winner approval voting. In Proceedings of the 14th international conference on autonomous agents and multiagent systems (AAMAS-15) (pp.107\u2013115)."},{"issue":"2","key":"9549_CR4","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s00355-010-0476-3","volume":"36","author":"M Ballester","year":"2011","unstructured":"Ballester, M., & Haeringer, G. (2011). A characterization of the single-peaked domain. Social Choice and Welfare, 36(2), 305\u2013322.","journal-title":"Social Choice and Welfare"},{"issue":"8\/9","key":"9549_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0895-7177(92)90085-Y","volume":"16","author":"J Bartholdi III","year":"1992","unstructured":"Bartholdi, J., III., Tovey, C., & Trick, M. (1992). How hard is it to control an election? Mathematical and Computer Modeling, 16(8\/9), 27\u201340.","journal-title":"Mathematical and Computer Modeling"},{"key":"9549_CR6","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1613\/jair.3896","volume":"47","author":"N Betzler","year":"2013","unstructured":"Betzler, N., Slinko, A., & Uhlmann, J. (2013). On the computation of fully proportional representation. Journal of Artificial Intelligence Research, 47, 475\u2013519.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9549_CR7","volume-title":"The Theory of Committees and Elections","author":"D Black","year":"1958","unstructured":"Black, D. (1958). The theory of committees and elections. Cambridge University Press."},{"issue":"3","key":"9549_CR8","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K Booth","year":"1976","unstructured":"Booth, K., & Lueker, G. (1976). Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 13(3), 335\u2013379.","journal-title":"Journal of Computer and System Sciences"},{"key":"9549_CR9","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1613\/jair.4647","volume":"53","author":"F Brandt","year":"2015","unstructured":"Brandt, F., Brill, M., Hemaspaandra, E., & Hemaspaandra, L. (2015). Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates. Journal of Artificial Intelligence Research, 53, 439\u2013496.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"4","key":"9549_CR10","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1007\/s00355-012-0717-8","volume":"41","author":"R Bredereck","year":"2013","unstructured":"Bredereck, R., Chen, J., & Woeginger, G. (2013). A characterization of the single-crossing domain. Social Choice and Welfare, 41(4), 989\u2013998.","journal-title":"Social Choice and Welfare"},{"key":"9549_CR11","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.mathsocsci.2015.11.002","volume":"79","author":"R Bredereck","year":"2016","unstructured":"Bredereck, R., Chen, J., & Woeginger, G. (2016). Are there any nicely structured preference profiles nearby? Mathematical Social Sciences, 79, 61\u201373.","journal-title":"Mathematical Social Sciences"},{"key":"9549_CR12","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1017\/CBO9781107446984.006","volume-title":"Handbook of Computational Social Choice","author":"I Caragiannis","year":"2016","unstructured":"Caragiannis, I., Hemaspaandra, E., & Hemaspaandra, L. (2016). Dodgson\u2019s rule and Young\u2019s rule. Handbook of Computational Social Choice (pp. 103\u2013126). Cambridge University Press."},{"issue":"3","key":"9549_CR13","doi-asserted-by":"publisher","first-page":"718","DOI":"10.2307\/1957270","volume":"77","author":"B Chamberlin","year":"1983","unstructured":"Chamberlin, B., & Courant, P. (1983). Representative deliberations and representative decisions: Proportional representation and the Borda rule. American Political Science Review, 77(3), 718\u2013733.","journal-title":"American Political Science Review"},{"key":"9549_CR14","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1613\/jair.2606","volume":"35","author":"V Conitzer","year":"2009","unstructured":"Conitzer, V. (2009). Eliciting single-peaked preferences using comparison queries. Journal of Artificial Intelligence Research, 35, 161\u2013191.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9549_CR15","unstructured":"Cornaz, D., Galand, L., & Spanjaard, O. (2012). Bounded single-peaked width and proportional representation. In Proceedings of the 20th European conference on artificial intelligence (pp. 270\u2013275)."},{"key":"9549_CR16","unstructured":"Cornaz, D., Galand, L., & Spanjaard, O. (2013). Kemeny elections with bounded single-peaked or single-crossing width. In Proceedings of the 23rd international joint conference on artificial Iitelligence (IJCAI-13) (pp. 76\u201382)."},{"key":"9549_CR17","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F., Kowalik, \u0141., \u00a0Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2015). Parameterized algorithms. Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"9549_CR18","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., & Weismantel, R. (2018). Proximity results and faster algorithms for integer programming using the Steinitz lemma. In Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms (SODA-18) (pp. 808\u2013816).","DOI":"10.1137\/1.9781611975031.52"},{"key":"9549_CR19","doi-asserted-by":"crossref","unstructured":"Elkind, E., Faliszewski, P., & Slinko, A. (2012). Clone structures in voters\u2019 preferences. In Proceedings of the 13th ACM conference on electronic commerce (EC-12) (pp. 496\u2013513).","DOI":"10.1145\/2229012.2229050"},{"key":"9549_CR20","unstructured":"Elkind, E., Lackner, M., & Peters, D. (2016). Preference restrictions in computational social choice: Recent progress. In Proceedings of the 25th international joint conference on artificial intelligence (IJCAI-16) (pp. 4062\u20134065)."},{"issue":"2","key":"9549_CR21","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.ic.2010.09.001","volume":"209","author":"P Faliszewski","year":"2011","unstructured":"Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L., & Rothe, J. (2011). The shield that never was: Societies with single-peaked preferences are more open to manipulation and control. Information and Computation, 209(2), 89\u2013107.","journal-title":"Information and Computation"},{"key":"9549_CR22","doi-asserted-by":"publisher","unstructured":"Ferrari, L. (2020). Enhancing the connections between patterns in permutations and forbidden configurations in restricted elections. Journal of Discrete Mathematical Sciences and Cryptography. https:\/\/doi.org\/10.1080\/09720529.2020.1776932.","DOI":"10.1080\/09720529.2020.1776932"},{"key":"9549_CR23","doi-asserted-by":"crossref","unstructured":"Gaven\u010diak, T., Knop, D., & Kouteck\u00fd, M. (2021). Integer programming in parameterized complexity: Five miniatures. Discrete Optimization, 100596.","DOI":"10.1016\/j.disopt.2020.100596"},{"key":"9549_CR24","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T Gonzalez","year":"1985","unstructured":"Gonzalez, T. (1985). Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38, 293\u2013306.","journal-title":"Theoretical Computer Science"},{"issue":"32","key":"9549_CR25","doi-asserted-by":"publisher","first-page":"525","DOI":"10.2307\/1910176","volume":"32","author":"K Inada","year":"1964","unstructured":"Inada, K. (1964). A note on the simple majority decision rule. Econometrica, 32(32), 525\u2013531.","journal-title":"Econometrica"},{"issue":"3","key":"9549_CR26","doi-asserted-by":"publisher","first-page":"490","DOI":"10.2307\/1912796","volume":"37","author":"K Inada","year":"1969","unstructured":"Inada, K. (1969). The simple majority decision rule. Econometrica, 37(3), 490\u2013506.","journal-title":"Econometrica"},{"key":"9549_CR27","doi-asserted-by":"crossref","unstructured":"Karp, R. (1972). Reducibilities among combinatorial problems. In R.\u00a0Miller and J.\u00a0Thatcher, editors, Complexity of Computer Computations (pp. 85\u2013103).","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"3","key":"9549_CR28","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/s10726-019-09621-w","volume":"28","author":"A Karpov","year":"2019","unstructured":"Karpov, A. (2019). On the number of group-separable preference profiles. Group Decision and Negotiation, 28(3), 501\u2013517.","journal-title":"Group Decision and Negotiation"},{"key":"9549_CR29","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1016\/j.geb.2019.05.006","volume":"121","author":"P Liu","year":"2020","unstructured":"Liu, P. (2020). Random assignments on sequentially dichotomous domains. Games and Economic Behavior, 121, 565\u2013584.","journal-title":"Games and Economic Behavior"},{"key":"9549_CR30","unstructured":"Lu, T., & Boutilier, C. (2011). Budgeted social choice: From consensus to personalized decision making. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI-11), pages 280\u2013286."},{"issue":"3","key":"9549_CR31","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1007\/s10458-016-9339-3","volume":"31","author":"K Magiera","year":"2017","unstructured":"Magiera, K., & Faliszewski, P. (2017). How hard is control in single-crossing elections? Autonomous Agents and Multiagent Systems, 31(3), 606\u2013627.","journal-title":"Autonomous Agents and Multiagent Systems"},{"key":"9549_CR32","doi-asserted-by":"publisher","first-page":"175","DOI":"10.2307\/2296779","volume":"38","author":"J Mirrlees","year":"1971","unstructured":"Mirrlees, J. (1971). An exploration in the theory of optimal income taxation. Review of Economic Studies, 38, 175\u2013208.","journal-title":"Review of Economic Studies"},{"key":"9549_CR33","unstructured":"Obraztsova, S., & Elkind, E. (2011). On the complexity of voting manipulation under randomized tie-breaking. In Proceedings of the 22nd international joint conference on artificial intelligence (IJCAI-11) (pp. 319\u2013324)."},{"key":"9549_CR34","unstructured":"Obraztsova, S., Elkind, E., & Hazon, N. (2011). Ties matter: Complexity of voting manipulation revisited. In Proceedings of the 10th international conference on autonomous agents and multiagent systems (AAMAS-11) (pp. 71\u201378)."},{"key":"9549_CR35","doi-asserted-by":"crossref","unstructured":"Peters, D., & Elkind, E. (2016). Preferences single-peaked on nice trees. In Proceedings of the 30th AAAI conference on artificial intelligence (AAAI-16) (pp. 594\u2013600).","DOI":"10.1609\/aaai.v30i1.10049"},{"key":"9549_CR36","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1613\/jair.1.11732","volume":"68","author":"D Peters","year":"2020","unstructured":"Peters, D., & Lackner, M. (2020). Preferences single-peaked on a circle. Journal of Artificial Intelligence Research, 68, 463\u2013502.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"3","key":"9549_CR37","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s00355-007-0235-2","volume":"30","author":"A Procaccia","year":"2008","unstructured":"Procaccia, A., Rosenschein, J., & Zohar, A. (2008). On the complexity of achieving proportional representation. Social Choice and Welfare, 30(3), 353\u2013362.","journal-title":"Social Choice and Welfare"},{"issue":"3","key":"9549_CR38","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0047-2727(77)90005-6","volume":"8","author":"K Roberts","year":"1977","unstructured":"Roberts, K. (1977). Voting over income tax schedules. Journal of Public Economics, 8(3), 329\u2013340.","journal-title":"Journal of Public Economics"},{"issue":"4","key":"9549_CR39","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/s00224-002-1093-z","volume":"36","author":"J Rothe","year":"2003","unstructured":"Rothe, J., Spakowski, H., & Vogel, J. (2003). Exact complexity of the winner problem for Young elections. Theory of Computing Systems, 36(4), 375\u2013386.","journal-title":"Theory of Computing Systems"},{"issue":"2","key":"9549_CR40","doi-asserted-by":"publisher","first-page":"491","DOI":"10.2307\/1909947","volume":"34","author":"A Sen","year":"1966","unstructured":"Sen, A. (1966). A possibility theorem on majority decisions. Econometrica, 34(2), 491\u2013499.","journal-title":"Econometrica"},{"key":"9549_CR41","first-page":"191","volume":"241","author":"P Skowron","year":"2016","unstructured":"Skowron, P., Faliszewski, P., & Lang, J. (2016). Finding a collective set of items: From proportional multirepresentation to group recommendation. Artificial Intelligence, 241, 191\u2013216.","journal-title":"J. Lang. Finding a collective set of items: From proportional multirepresentation to group recommendation. Artificial Intelligence"},{"key":"9549_CR42","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.artint.2015.01.003","volume":"222","author":"P Skowron","year":"2015","unstructured":"Skowron, P., Faliszewski, P., & Slinko, A. (2015). Achieving fully proportional representation: Approximability result. Artificial Intelligence, 222, 67\u2013103.","journal-title":"Artificial Intelligence"},{"key":"9549_CR43","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.tcs.2014.12.012","volume":"569","author":"P Skowron","year":"2015","unstructured":"Skowron, P., Yu, L., Faliszewski, P., & Elkind, E. (2015). The complexity of fully proportional representation for single-crossing electorates. Theoretical Computer Science, 569, 43\u201357.","journal-title":"Theoretical Computer Science"},{"key":"9549_CR44","unstructured":"Szufa, S., Faliszewski, P., Skowron, P., Slinko, A., & Talmon, N. (2020). Drawing a map of elections in the space of statistical cultures. In Proceedings of the 19th international conference on autonomous agents and multiagent systems (AAMAS-20) (pp. 1341\u20131349)."},{"key":"9549_CR45","unstructured":"Thiele, T. (1895). Om flerfoldsvalg. In Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhandlinger (pp. 415\u2013441)."},{"key":"9549_CR46","unstructured":"Walsh, T. (2015). Generating single peaked votes. Technical Report arXiv:1503.02766 [cs.GT], arXiv.org, March."},{"key":"9549_CR47","unstructured":"Yang, Y. (2015). Manipulation with bounded single-peaked width: A parameterized study. In Proceedings of the 14th international conference on autonomous agents and multiagent systems (AAMAS-15) (pp. 77\u201385)."},{"key":"9549_CR48","unstructured":"Yang, Y., & Guo, J. (2014). Controlling elections with bounded single-peaked width. In Proceedings of the 13th International conference on autonomous agents and multiagent systems (pp. 629\u2013636)."},{"issue":"2","key":"9549_CR49","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/0022-0531(77)90012-6","volume":"16","author":"H Young","year":"1977","unstructured":"Young, H. (1977). Extending condorcet\u2019s rule. Journal of Economic Theory, 16(2), 335\u2013353.","journal-title":"Journal of Economic Theory"},{"key":"9549_CR50","unstructured":"Yu, L., Chan, H., & Elkind, E. (2013). Multiwinner elections under preferences that are single-peaked on a tree. In Proceedings of the 23rd international joint conference on artificial intelligence (IJCAI-13) (Vol.\u00a013, pp. 425\u2013431)."}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-022-09549-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-022-09549-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-022-09549-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T23:15:57Z","timestamp":1674861357000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-022-09549-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,26]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["9549"],"URL":"https:\/\/doi.org\/10.1007\/s10458-022-09549-7","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,26]]},"assertion":[{"value":"7 February 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 February 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"18"}}