{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T09:25:37Z","timestamp":1770888337905,"version":"3.50.1"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,9,30]],"date-time":"2021-09-30T00:00:00Z","timestamp":1632960000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NCN","award":["DEC-2012\/06\/M\/ST1\/00358"],"award-info":[{"award-number":["DEC-2012\/06\/M\/ST1\/00358"]}]},{"name":"ISF","award":["630\/19"],"award-info":[{"award-number":["630\/19"]}]},{"name":"Alexander-von-Humboldt Foundation","award":["Friedrich Wilhelm Bessel Research Award"],"award-info":[{"award-number":["Friedrich Wilhelm Bessel Research Award"]}]},{"name":"DFG","award":["PAWS (NI 369\/10); Research Training GroupMethods for Discrete Structures (GRK 1408)"],"award-info":[{"award-number":["PAWS (NI 369\/10); Research Training GroupMethods for Discrete Structures (GRK 1408)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>\n            Given an election, a preferred candidate\u00a0\n            <jats:italic>p<\/jats:italic>\n            , and a budget, the S\n            <jats:sc>HIFT<\/jats:sc>\n            B\n            <jats:sc>RIBERY<\/jats:sc>\n            problem asks whether\u00a0\n            <jats:italic>p<\/jats:italic>\n            can win the election after shifting\u00a0\n            <jats:italic>p<\/jats:italic>\n            higher in some voters\u2019 preference orders. Of course, shifting comes at a price (depending on the voter and on the extent of the shift) and one must not exceed the given budget. We study the (parameterized) computational complexity of S\n            <jats:sc>HIFT<\/jats:sc>\n            B\n            <jats:sc>RIBERY<\/jats:sc>\n            for multiwinner voting rules where winning the election means to be part of some winning committee. We focus on the well-established SNTV, Bloc,\n            <jats:italic>k<\/jats:italic>\n            -Borda, and Chamberlin-Courant rules, as well as on approximate variants of the Chamberlin-Courant rule. We show that S\n            <jats:sc>HIFT<\/jats:sc>\n            B\n            <jats:sc>RIBERY<\/jats:sc>\n            tends to be harder in the multiwinner setting than in the single-winner one by showing settings where S\n            <jats:sc>HIFT<\/jats:sc>\n            B\n            <jats:sc>RIBERY<\/jats:sc>\n            is computationally easy in the single-winner cases, but is hard (and hard to approximate) in the multiwinner ones.\n          <\/jats:p>","DOI":"10.1145\/3470647","type":"journal-article","created":{"date-parts":[[2021,12,23]],"date-time":"2021-12-23T17:35:03Z","timestamp":1640280903000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Complexity of Shift Bribery in Committee Elections"],"prefix":"10.1145","volume":"13","author":[{"given":"Robert","family":"Bredereck","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}]},{"given":"Piotr","family":"Faliszewski","sequence":"additional","affiliation":[{"name":"AGH University, Krakow, Poland"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Berlin, Berlin, Germany"}]},{"given":"Nimrod","family":"Talmon","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Ben-Gurion Boulevard, Israel"}]}],"member":"320","published-online":{"date-parts":[[2021,12,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-016-1019-3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3171642.3171656"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2772879.2772896"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2343776.2343779"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/2566972.2566985"},{"key":"e_1_2_1_6_1","volume-title":"Voting Power and Procedures: Essays in Honour of Dan Felsenthal and Mosh\u00e9 Machover","author":"Brams Steven J.","unstructured":"Steven J. Brams and D. Marc Kilgour . 2014. Satisfaction approval voting . In Voting Power and Procedures: Essays in Honour of Dan Felsenthal and Mosh\u00e9 Machover , R. Fara, D. Leech, and M. Salles (Eds.). Springer , 323\u2013346. Steven J. Brams and D. Marc Kilgour. 2014. Satisfaction approval voting. In Voting Power and Procedures: Essays in Honour of Dan Felsenthal and Mosh\u00e9 Machover, R. Fara, D. Leech, and M. Salles (Eds.). Springer, 323\u2013346."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TST.2014.6867518"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2893873.2894090"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2016.08.003"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66700-3_7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103403"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.01.017"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3016100.3016242"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3013558.3013575"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556950"},{"key":"e_1_2_1_16_1","volume-title":"2011 Electronic Voting Technology Workshop\/Workshop on Trustworthy Elections.","author":"Cary David","year":"2011","unstructured":"David Cary . 2011 . Estimating the Margin of Victory for Instant-Runoff Voting. (2011) . Presented at the 2011 Electronic Voting Technology Workshop\/Workshop on Trustworthy Elections. David Cary. 2011. Estimating the Margin of Victory for Instant-Runoff Voting. (2011). Presented at the 2011 Electronic Voting Technology Workshop\/Workshop on Trustworthy Elections."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.2307\/1957270"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/2815661"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118216.3118278"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2568438"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1940179.1940221"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-017-1026-z"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04645-2_27"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1641503.1641514"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103520"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-014-9277-x"},{"key":"e_1_2_1_27_1","volume-title":"Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang","author":"Faliszewski Piotr","unstructured":"Piotr Faliszewski and J\u00f6rg Rothe . 2016. Control and bribery in voting . In Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang , and Ariel Procaccia (Eds.). Cambridge University Press , Chapter 7, 146\u2013168. Piotr Faliszewski and J\u00f6rg Rothe. 2016. Control and bribery in voting. In Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel Procaccia (Eds.). Cambridge University Press, Chapter 7, 146\u2013168."},{"key":"e_1_2_1_28_1","volume-title":"Trends in Computational Social Choice","author":"Faliszewski Piotr","unstructured":"Piotr Faliszewski , Piotr Skowron , Arkadii Slinko , and Nimrod Talmon . 2017. Multiwinner voting: A new challenge for social choice theory . In Trends in Computational Social Choice , Ulle Endriss (Ed.). AI Access Foundation . Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. 2017. Multiwinner voting: A new challenge for social choice theory. In Trends in Computational Social Choice, Ulle Endriss (Ed.). AI Access Foundation."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/3091125.3091133"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1121738"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0490-y"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-019-09403-3"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/2875343.2875346"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3396855"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2020.105173"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/2283396.2283444"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2028012.2028016"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.02.001"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jal.2015.03.004"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/2343896.2344031"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/3237383.3237933"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-54921-3_19"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622698.1622703"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.2307\/2082518"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_48_1","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier Rolf","unstructured":"Rolf Niedermeier . 2006. Invitation to Fixed-Parameter Algorithms . Oxford University Press . Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-007-0235-2"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0064-0"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/3091125.3091136"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2016.09.003"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2015.01.003"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/3491440.3491453"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229086"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/3367032.3367123"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/3398761.3398943"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/3398761.3398952"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470647","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3470647","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:55Z","timestamp":1750191535000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3470647"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,30]]},"references-count":58,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3470647"],"URL":"https:\/\/doi.org\/10.1145\/3470647","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,30]]},"assertion":[{"value":"2018-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}