{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T14:15:14Z","timestamp":1764339314816,"version":"3.46.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>\n                    A variety of constructive manipulation, control, and bribery problems for approval-based multiwinner voting have been extensively studied recently. However, their destructive counterparts seem to be less explored. This article investigates the complexity of several destructive bribery problems under five prestigious approval-based multiwinner voting rules\u2014approval voting, satisfaction approval voting, net-satisfaction approval voting, Chamberlin-Courant approval voting, and proportional approval voting. Broadly, these problems aim to determine if a number of given candidates can be excluded from any winning committees by performing a limited number of modification operations. We offer a complete landscape of the complexity of the problems. For\n                    <jats:sans-serif>NP<\/jats:sans-serif>\n                    -hard problems, we study their parameterized complexity with respect to meaningful parameters.\n                  <\/jats:p>","DOI":"10.1145\/3749377","type":"journal-article","created":{"date-parts":[[2025,7,17]],"date-time":"2025-07-17T11:25:06Z","timestamp":1752751506000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Complexity of Destructive Bribery in Approval-Based Multiwinner Voting"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7731-6818","authenticated-orcid":false,"given":"Yongjie","family":"Yang","sequence":"first","affiliation":[{"name":"Saarland University","place":["Saarbr\u00fccken, Germany"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,11,28]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-016-1019-3"},{"key":"e_1_3_4_3_2","first-page":"107","volume-title":"AAMAS","author":"Aziz H.","year":"2015","unstructured":"H. Aziz, S. Gaspers, J. Gudmundsson, S. Mackenzie, N. Mattei, and T. Walsh. 2015. Computational aspects of multi-winner approval voting. In AAMAS. 107\u2013115. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=2772896"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.04.005"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00183045"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00295861"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0895-7177(92)90085-Y"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33011764"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/2283396.2283407"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.3896"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-43254-5_10"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.5555\/3545946.3598829"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-05158-1_18"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v30i1.10132"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm086"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.2307\/1957270"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5515"},{"key":"e_1_3_4_18_2","first-page":"1925","volume-title":"AAMAS","author":"Dey P.","year":"2019","unstructured":"P. Dey. 2019. Local distance restricted bribery in voting. In AAMAS. 1925\u20131927. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=3331965"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-28332-1_4"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1992.215379"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/2832415.2832529"},{"key":"e_1_3_4_23_2","unstructured":"E. Elkind M. Lackner and D. Peters. 2022. Preference restrictions in computational social choice: A survey. arXiv:2205.09092. Retrieved from https:\/\/arxiv.org\/abs\/2205.09092"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2543629"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2014.11.003"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-019-09427-9"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-20614-6_7"},{"key":"e_1_3_4_28_2","first-page":"6","volume-title":"AAMAS","author":"Faliszewski P.","year":"2017","unstructured":"P. Faliszewski, P. Skowron, and N. Talmon. 2017. Bribery as a measure of candidate success: Complexity results for approval-based multiwinner rules. In AAMAS. 6\u201314. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=3091133"},{"key":"e_1_3_4_29_2","first-page":"485","volume-title":"AAMAS","author":"Fern\u00e1ndez L.","year":"2019","unstructured":"L. Fern\u00e1ndez and J. A. Fisteus. 2019. Monotonicity axioms in approval-based multi-winner voting rules. In AAMAS. 485\u2013493. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=3331731"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/6462.6502"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-31489-7_2"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/S00453-023-01155-7"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1134\/S0005117922090016"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-20441-8_12"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.5555\/3545946.3598831"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_3_4_38_2","first-page":"61","volume-title":"MPREF@AAAI","author":"Loreggia A.","year":"2014","unstructured":"A. Loreggia, N. Narodytska, F. Rossi, K. B. Venable, and T. Walsh. 2014. Controlling elections by replacing candidates: Theoretical and experimental results. In MPREF@AAAI. 61\u201366. Retrieved from http:\/\/www.aaai.org\/ocs\/index.php\/WS\/AAAIW14\/paper\/view\/8758"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41575-3_20"},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2566"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488705"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.5555\/3504035.3504178"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.5555\/3298239.3298338"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5628"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2015.01.003"},{"key":"e_1_3_4_46_2","first-page":"415","volume-title":"Oversigt Over Det Kongelige Danske Videnskabernes Selskabs Forhandlinger","author":"Thiele T. N.","year":"1895","unstructured":"T. N. Thiele. 1895. Om flerfoldsvalg. In Oversigt Over Det Kongelige Danske Videnskabernes Selskabs Forhandlinger. 415\u2013441. Retrieved from http:\/\/publ.royalacademy.dk\/books\/355\/2284?lang=da"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1287\/inte.32.3.30.39"},{"key":"e_1_3_4_48_2","volume-title":"Introduction to Graph Theory","author":"West D. B.","year":"2000","unstructured":"D. B. West. 2000. Introduction to Graph Theory. Prentice-Hall. Retrieved from https:\/\/ia801204.us.archive.org\/35\/items\/igt_west\/igt_west_text.pdf"},{"key":"e_1_3_4_49_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/90"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/91"},{"key":"e_1_3_4_51_2","doi-asserted-by":"publisher","DOI":"10.5555\/3398761.3398943"},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-018-9392-1"},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.08.013"},{"key":"e_1_3_4_54_2","first-page":"1133","volume-title":"AAMAS","author":"Yang Y.","year":"2017","unstructured":"Y. Yang and J. Wang. 2017. Anyone but them: The complexity challenge for a resolute election controller. In AAMAS. 1133\u20131141. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=3091284"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-023-09610-z"},{"key":"e_1_3_4_56_2","first-page":"503","volume-title":"AAMAS","author":"Zhou A.","year":"2019","unstructured":"A. Zhou, Y. Yang, and J. Guo. 2019. Parameterized complexity of committee elections with dichotomous and trichotomous votes. In AAMAS. 503\u2013510. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=3331733"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3749377","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T14:10:27Z","timestamp":1764339027000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3749377"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,28]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3749377"],"URL":"https:\/\/doi.org\/10.1145\/3749377","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2025,11,28]]},"assertion":[{"value":"2023-12-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-20","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}