{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:16:03Z","timestamp":1740122163518,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T00:00:00Z","timestamp":1625702400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T00:00:00Z","timestamp":1625702400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["BR 5207\/2","BR 5207\/1"],"award-info":[{"award-number":["BR 5207\/2","BR 5207\/1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/15"],"award-info":[{"award-number":["NI 369\/15"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006211","name":"Humboldt-Universit\u00e4t zu Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006211","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":[[2021,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Shortlisting of candidates\u2014selecting a group of\u00a0\u201cbest\u201d candidates\u2014is a special case of multiwinner elections. We provide the first in-depth study of the computational complexity of strategic voting for shortlisting based on the perhaps most basic voting rule in this scenario,<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u2113<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>-Bloc (every voter approves<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\ell $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>\u2113<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>\u00a0candidates). In particular, we investigate the influence of several different group evaluation functions (e.g., egalitarian versus utilitarian) and tie-breaking mechanisms modeling pessimistic and optimistic manipulators. Among other things, we conclude that in an egalitarian setting strategic voting may indeed be computationally intractable regardless of the tie-breaking rule. Altogether, we\u00a0provide a\u00a0fairly comprehensive picture of the computational complexity landscape of this scenario.<\/jats:p>","DOI":"10.1007\/s10458-021-09507-9","type":"journal-article","created":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T10:03:12Z","timestamp":1625738592000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On coalitional manipulation for multiwinner elections: shortlisting"],"prefix":"10.1007","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6303-6276","authenticated-orcid":false,"given":"Robert","family":"Bredereck","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1401-0157","authenticated-orcid":false,"given":"Andrzej","family":"Kaczmarczyk","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1703-1236","authenticated-orcid":false,"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,8]]},"reference":[{"key":"9507_CR1","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 \u201915 (pp. 107\u2013115)."},{"issue":"2","key":"9507_CR2","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00355-016-1019-3","volume":"48","author":"H Aziz","year":"2017","unstructured":"Aziz, H., Brill, M., Conitzer, V., Elkind, E., Freeman, R., & Walsh, T. (2017a). Justified representation in approval-based committee voting. Social Choice and Welfare, 48(2), 461\u2013485.","journal-title":"Social Choice and Welfare"},{"key":"9507_CR3","doi-asserted-by":"crossref","unstructured":"Aziz, H., Elkind, E., Faliszewski, P., Lackner, M., & Skowron, P. (2017b). The Condorcet principle for multiwinner elections: from shortlisting to proportionality. In Proceedings of the 26th international conference on artificial intelligence, IJCAI \u201917 (pp. 84\u201390).","DOI":"10.24963\/ijcai.2017\/13"},{"issue":"1","key":"9507_CR4","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00355-007-0268-6","volume":"31","author":"S Barber\u00e0","year":"2008","unstructured":"Barber\u00e0, S., & Coelho, D. (2008). How to choose a non-controversial list with $$k$$ names. Social Choice and Welfare, 31(1), 79\u201396.","journal-title":"Social Choice and Welfare"},{"issue":"1","key":"9507_CR5","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.geb.2009.03.008","volume":"70","author":"S Barber\u00e0","year":"2010","unstructured":"Barber\u00e0, S., & Coelho, D. (2010). On the rule of $$k$$ names. Games and Economic Behavior, 70(1), 44\u201361.","journal-title":"Games and Economic Behavior"},{"issue":"3","key":"9507_CR6","doi-asserted-by":"publisher","first-page":"595","DOI":"10.2307\/2938220","volume":"59","author":"S Barber\u00e0","year":"1991","unstructured":"Barber\u00e0, S., Sonnenschein, H., & Zhou, L. (1991). Voting by committees. Econometrica, 59(3), 595\u2013609.","journal-title":"Econometrica"},{"key":"9507_CR7","doi-asserted-by":"crossref","unstructured":"Barrot, N., Gourv\u00e8s, L., Lang, J., Monnot, J., & Ries, B. (2013). Possible winners in approval voting. In Proceedings of the 3rd international conference on algorithmic decision theory, ADT \u201913 (pp. 57\u201370).","DOI":"10.1007\/978-3-642-41575-3_5"},{"issue":"3","key":"9507_CR8","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/BF00295861","volume":"6","author":"JJ Bartholdi III","year":"1989","unstructured":"Bartholdi, J. J., III., Tovey, C. A., & Trick, M. A. (1989). The computational difficulty of manipulating an election. Social Choice and Welfare, 6(3), 227\u2013241.","journal-title":"Social Choice and Welfare"},{"key":"9507_CR9","first-page":"197","volume-title":"Economics and computation: An introduction to algorithmic game theory, computational social choice, and fair division","author":"D Baumeister","year":"2015","unstructured":"Baumeister, D., & Rothe, J. (2015). Preference aggregation by voting, chap\u00a04. In J. Rothe (Ed.), Economics and computation: An introduction to algorithmic game theory, computational social choice, and fair division (pp. 197\u2013325). Berlin: Springer."},{"key":"9507_CR10","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"},{"volume-title":"Handbook of computational social choice","year":"2016","key":"9507_CR11","unstructured":"Brandt, F., Conitzer, V., Endriss, U., Lang, J., & Procaccia, A. D. (Eds.). (2016). Handbook of computational social choice. Cambridge: Cambridge University Press."},{"key":"9507_CR12","doi-asserted-by":"crossref","unstructured":"Bredereck, R., Kaczmarczyk, A., & Niedermeier, R. (2017). On coalitional manipulation for multiwinner elections: Shortlisting. In Proceedings of the 26th international joint conference on artificial intelligence, IJCAI \u201917 (pp. 887\u2013893).","DOI":"10.24963\/ijcai.2017\/123"},{"key":"9507_CR13","doi-asserted-by":"crossref","unstructured":"Caragiannis, I., Kalaitzis, D., & Markakis, E. (2010). Approximation algorithms and mechanism design for minimax approval voting. In Proceedings of the 24th AAAI conference on artificial intelligence (AAAI \u201910) (pp. 737\u2013742). AAAI Press.","DOI":"10.1609\/aaai.v24i1.7615"},{"issue":"3","key":"9507_CR14","doi-asserted-by":"publisher","first-page":"718","DOI":"10.2307\/1957270","volume":"77","author":"JR Chamberlin","year":"1983","unstructured":"Chamberlin, J. R., & Courant, P. N. (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":"9507_CR15","unstructured":"Coleman, T., & Teague, V. (2007). On the complexity of manipulating elections. In Proceedings of computing: The 13th Australasian theory symposium (pp. 25\u201333)."},{"key":"9507_CR16","first-page":"126","volume-title":"Handbook of computational social choice","author":"V Conitzer","year":"2016","unstructured":"Conitzer, V., & Walsh, T. (2016). Barriers to manipulation in voting, chap\u00a06. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. D. Procaccia (Eds.), Handbook of computational social choice (pp. 126\u2013145). Cambridge: Cambridge University Press."},{"issue":"3","key":"9507_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1236457.1236461","volume":"54","author":"V Conitzer","year":"2007","unstructured":"Conitzer, V., Sandholm, T., & Lang, J. (2007). When are elections with few candidates hard to manipulate? Journal of the ACM, 54(3), 1\u201333.","journal-title":"Journal of the ACM"},{"key":"9507_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., et al. (2015). Parameterized algorithms. Berlin: Springer."},{"key":"9507_CR19","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/j.artint.2014.07.005","volume":"217","author":"J Davies","year":"2014","unstructured":"Davies, J., Katsirelos, G., Narodytska, N., Walsh, T., & Xia, L. (2014). Complexity of and algorithms for the manipulation of Borda, Nanson\u2019s and Baldwin\u2019s voting rules. Artificial Intelligence, 217, 20\u201342.","journal-title":"Artificial Intelligence"},{"issue":"4","key":"9507_CR20","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/BF00182574","volume":"9","author":"B Debord","year":"1992","unstructured":"Debord, B. (1992). An axiomatic characterization of Borda\u2019s k-choice function. Social Choice and Welfare, 9(4), 337\u2013343.","journal-title":"Social Choice and Welfare"},{"key":"9507_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R. G., & Fellows, M. R. (2013). Fundamentals of parameterized complexity. Berlin: Springer."},{"key":"9507_CR22","first-page":"135","volume-title":"Economics and computation: an introduction to algorithmic game theory, computational social choice, and fair division","author":"E Elkind","year":"2015","unstructured":"Elkind, E., & Rothe, J. (2015). Cooperative game theory, chap\u00a03. In J. Rothe (Ed.), Economics and computation: an introduction to algorithmic game theory, computational social choice, and fair division (pp. 135\u2013193). Berlin: Springer."},{"issue":"3","key":"9507_CR23","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1007\/s00355-017-1026-z","volume":"48","author":"E Elkind","year":"2017","unstructured":"Elkind, E., Faliszewski, P., Skowron, P., & Slinko, A. M. (2017). Properties of multiwinner voting rules. Social Choice and Welfare, 48(3), 599\u2013632.","journal-title":"Social Choice and Welfare"},{"issue":"4","key":"9507_CR24","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1016\/j.jcss.2014.11.003","volume":"81","author":"G Erd\u00e9lyi","year":"2015","unstructured":"Erd\u00e9lyi, G., Fellows, M. R., Rothe, J., & Schend, L. (2015). Control complexity in Bucklin and fallback voting: An experimental analysis. Journal of Computer and System Sciences, 81(4), 661\u2013670.","journal-title":"Journal of Computer and System Sciences"},{"key":"9507_CR25","doi-asserted-by":"crossref","unstructured":"Faliszewski, P., Skowron, P., Slinko, A. M., & Talmon, N. (2016). Multiwinner analogues of the plurality rule: Axiomatic and algorithmic perspectives. In Proceedings of the 30th AAAI conference on artificial intelligence, AAAI \u201916 (pp. 482\u2013488).","DOI":"10.1609\/aaai.v30i1.10031"},{"key":"9507_CR26","first-page":"27","volume-title":"Trends in computational social choice","author":"P Faliszewski","year":"2017","unstructured":"Faliszewski, P., Skowron, P., Slinko, A. M., & Talmon, N. (2017a). Multiwinner voting: A new challenge for social choice theory, chap\u00a02. In U. Endriss (Ed.), Trends in computational social choice (pp. 27\u201347). New York: AI Access."},{"key":"9507_CR27","unstructured":"Faliszewski, P., Skowron, P., & Talmon, N. (2017b). Bribery as a measure of candidate success: Complexity results for approval-based multiwinner rules. In Proceedings of the 16th international conference on autonomous agents and multiagent systems, AAMAS \u201917 (pp. 6\u201314)."},{"issue":"1","key":"9507_CR28","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2008.09.065","volume":"410","author":"MR Fellows","year":"2009","unstructured":"Fellows, M. R., Hermelin, D., Rosamond, F., & Vialette, S. (2009). On the parameterized complexity of multiple-interval graph problems. Theoretical Computer Science, 410(1), 53\u201361.","journal-title":"Theoretical Computer Science"},{"key":"9507_CR29","volume-title":"Parameterized complexity theory","author":"J Flum","year":"2006","unstructured":"Flum, J., & Grohe, M. (2006). Parameterized complexity theory. Berlin: Springer."},{"key":"9507_CR30","unstructured":"Kalkbrenner, L. (2019). Coalitional manipulation for multiwinner elections: Algorithms and experiments. Bachelor thesis. http:\/\/fpt.akt.tu-berlin.de\/publications\/theses\/BA-lydia-kalkbrenner.pdf."},{"key":"9507_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., & Pisinger, D. (2004). Knapsack problems. Berlin: Springer."},{"key":"9507_CR32","first-page":"331","volume-title":"Handbook of computational social choice","author":"B Klaus","year":"2016","unstructured":"Klaus, B., Manlove, D. F., Rossi, F., Aziz, H., Savani, R., Chalkiadakis, G., & Wooldridge, M. (2016). Coalitional formation. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. D. Procaccia (Eds.), Handbook of computational social choice (pp. 331\u2013396). Cambridge: Cambridge University Press (chap 14\u201316, part 3)."},{"key":"9507_CR33","doi-asserted-by":"crossref","unstructured":"Lackner, M., & Skowron, P. (2018). Approval-based multi-winner rules and strategic voting. In Proceedings of the 27th international joint conference on artificial intelligence, IJCAI \u201918 (pp. 340\u2013346).","DOI":"10.24963\/ijcai.2018\/47"},{"issue":"4","key":"9507_CR34","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra","year":"1983","unstructured":"Lenstra, H. W. (1983). Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4), 538\u2013548.","journal-title":"Mathematics of Operations Research"},{"key":"9507_CR35","unstructured":"Lin, A. (2011). The complexity of manipulating $$k$$-approval elections. In Proceedings of the 3rd international conference on agents and artificial intelligence, ICAART \u201911 (pp. 212\u2013218)."},{"key":"9507_CR36","unstructured":"Lu, T., Tang, P., Procaccia, A. D., & Boutilier, C. (2012). Bayesian vote manipulation: Optimal strategies and impact on welfare. In Proceedings of the 28th conference on uncertainty in artificial intelligence, UAI \u201912 (pp. 543\u2013553)."},{"key":"9507_CR37","doi-asserted-by":"crossref","unstructured":"Mattei, N., & Walsh, T. (2013). Preflib: A library for preferences. In Proceedings of the 3nd international conference on algorithmic decision theory, ADT \u201913 (pp. 259\u2013270).","DOI":"10.1007\/978-3-642-41575-3_20"},{"issue":"1","key":"9507_CR38","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1613\/jair.2566","volume":"33","author":"R Meir","year":"2008","unstructured":"Meir, R., Procaccia, A. D., Rosenschein, J. S., & Zohar, A. (2008). Complexity of strategic behavior in multi-winner elections. Journal of Artificial Intelligence Research, 33(1), 149\u2013178.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9507_CR39","unstructured":"Ministry of Science and Higher Education of the Republic of Poland. (2019). Informations on the election of The Board of Research Excellence (in Polish). http:\/\/www.bip.nauka.gov.pl\/g2\/oryginal\/2019_03\/c435c5061f0aab7158eba2716553f240.pdf. Accessed July 30, 2019"},{"key":"9507_CR40","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to fixed-parameter algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R. (2006). Invitation to fixed-parameter algorithms. Oxford: Oxford University Press."},{"key":"9507_CR41","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic game theory","author":"N Nisan","year":"2007","unstructured":"Nisan, N., Roughgarden, T., Tardos, \u00c9., & Vazirani, V. V. (2007). Algorithmic game theory. Cambridge: Cambridge University Press."},{"key":"9507_CR42","unstructured":"Obraztsova, S., Zick, Y., & Elkind, E. (2013). On manipulation in multi-winner elections based on scoring rules. In Proceedings of the 12th international conference on autonomous agents and multiagent systems, AAMAS \u201913 (pp. 359\u2013366)."},{"key":"9507_CR43","unstructured":"Scheuerman, J., Harman, J. L., Mattei, N., & Venable, K. B. (2019). Heuristics in multi-winner approval voting. CoRR abs\/1905.12104."},{"key":"9507_CR44","unstructured":"Skowron, P. (2015). What do we elect committees for? A voting committee model for multi-winner rules. In Proceedings of the 24th international conference on artificial intelligence, IJCAI \u201915 (pp. 1141\u20131147)."},{"key":"9507_CR45","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. M. (2015). Achieving fully proportional representation: Approximability results. Artificial Intelligence, 222, 67\u2013103.","journal-title":"Artificial Intelligence"},{"issue":"1\u20132","key":"9507_CR46","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1023\/A:1005082925477","volume":"103","author":"N Tideman","year":"2000","unstructured":"Tideman, N., & Richardson, D. (2000). Better voting methods through technology: The refinement-manageability trade-off in the single transferable vote. Public Choice, 103(1\u20132), 13\u201334.","journal-title":"Public Choice"},{"key":"9507_CR47","first-page":"1","volume":"44","author":"T Walsh","year":"2011","unstructured":"Walsh, T. (2011). Where are the hard manipulation problems? Journal of Artificial Intelligence Research, 44, 1\u201329.","journal-title":"Journal of Artificial Intelligence Research"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-021-09507-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-021-09507-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-021-09507-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T09:52:56Z","timestamp":1672739576000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-021-09507-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,8]]},"references-count":47,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["9507"],"URL":"https:\/\/doi.org\/10.1007\/s10458-021-09507-9","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"type":"print","value":"1387-2532"},{"type":"electronic","value":"1573-7454"}],"subject":[],"published":{"date-parts":[[2021,7,8]]},"assertion":[{"value":"12 May 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"38"}}