{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T13:22:58Z","timestamp":1792070578105,"version":"4.4.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["MN 59\/4-1"],"award-info":[{"award-number":["MN 59\/4-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"name":"OP VVV MEYS","award":["CZ.02.1.01\/0.0\/0.0\/16 019\/0000765"],"award-info":[{"award-number":["CZ.02.1.01\/0.0\/0.0\/16 019\/0000765"]}]},{"name":"European Research Council","award":["306465"],"award-info":[{"award-number":["306465"]}]},{"name":"Charles University project","award":["UNCE\/SCI\/004"],"award-info":[{"award-number":["UNCE\/SCI\/004"]}]},{"DOI":"10.13039\/501100001824","name":"GA \u010cR","doi-asserted-by":"crossref","award":["19-27871X"],"award-info":[{"award-number":["19-27871X"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100018240","name":"\u201cResearch Center for Informatics\u201d","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100018240","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2020,8,31]]},"abstract":"<jats:p>\n            We introduce a general problem about bribery in voting systems. In the\n            <jats:italic>R<\/jats:italic>\n            -M\n            <jats:sc>ulti<\/jats:sc>\n            -B\n            <jats:sc>ribery<\/jats:sc>\n            problem, the goal is to bribe a set of voters at minimum cost such that a desired candidate is a winner in the perturbed election under the voting rule\n            <jats:italic>R<\/jats:italic>\n            . Voters assign prices for withdrawing their vote, for swapping the positions of two consecutive candidates in their preference order, and for perturbing their approval count to favour candidates.\n          <\/jats:p>\n          <jats:p>\n            As our main result, we show that\n            <jats:italic>R<\/jats:italic>\n            -M\n            <jats:sc>ulti<\/jats:sc>\n            -B\n            <jats:sc>ribery<\/jats:sc>\n            is fixed-parameter tractable parameterized by the number of candidates |\n            <jats:italic>C<\/jats:italic>\n            | with only a single-exponential dependence on |\n            <jats:italic>C<\/jats:italic>\n            |, for many natural voting rules\u00a0\n            <jats:italic>R<\/jats:italic>\n            , including all natural scoring protocols, maximin rule, Bucklin rule, Fallback rule, SP-AV, and any C1 rule. The vast majority of previous work done in the setting of few candidates proceeds by grouping voters into at most |\n            <jats:italic>C<\/jats:italic>\n            |! types by their preference, constructing an integer linear program with |\n            <jats:italic>C<\/jats:italic>\n            |!\n            <jats:sup>2<\/jats:sup>\n            variables, and solving it by Lenstra\u2019s algorithm in time |\n            <jats:italic>C<\/jats:italic>\n            |!\n            <jats:sup>\n              |\n              <jats:italic>C<\/jats:italic>\n              |!\n            <\/jats:sup>\n            <jats:sup>2<\/jats:sup>\n            , hence double-exponential in |\n            <jats:italic>C<\/jats:italic>\n            |. Note that it is not possible to encode a large number of different voter costs in this way and still obtain a fixed-parameter algorithm, as that would increase the number of voter types and hence the dimension. These two obstacles of double-exponential complexity and restricted costs have been formulated as \u201cChallenges #1 and #2\u201d of the \u201cNine Research Challenges in Computational Social Choice\u201d by Bredereck et al.\n          <\/jats:p>\n          <jats:p>\n            Hence, our result resolves the parameterized complexity of\n            <jats:italic>R<\/jats:italic>\n            -S\n            <jats:sc>wap<\/jats:sc>\n            -B\n            <jats:sc>ribery<\/jats:sc>\n            for the aforementioned voting rules plus Kemeny\u2019s rule, and for all rules except Kemeny brings the dependence on |\n            <jats:italic>C<\/jats:italic>\n            | down to single-exponential. The engine behind our progress is the use of a new integer linear programming formulation, using so-called \u201c\n            <jats:italic>n<\/jats:italic>\n            -fold integer programming.\u201d Since its format is quite rigid, we introduce \u201cextended\n            <jats:italic>n<\/jats:italic>\n            -fold IP,\u201d which allows many useful modeling tricks. Then, we model\n            <jats:italic>R<\/jats:italic>\n            -M\n            <jats:sc>ulti<\/jats:sc>\n            -B\n            <jats:sc>ribery<\/jats:sc>\n            as an extended\n            <jats:italic>n<\/jats:italic>\n            -fold IP and apply an algorithm of Hemmecke et al. [Math. Prog. 2013].\n          <\/jats:p>","DOI":"10.1145\/3396855","type":"journal-article","created":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T18:17:45Z","timestamp":1592849865000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Voting and Bribing in Single-Exponential Time"],"prefix":"10.1145","volume":"8","author":[{"given":"Du\u0161an","family":"Knop","sequence":"first","affiliation":[{"name":"Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Kouteck\u00fd","sequence":"additional","affiliation":[{"name":"Charles University, Czech Republic"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthias","family":"Mnich","sequence":"additional","affiliation":[{"name":"TU Hamburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3330137"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00303169"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2015.03.006"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201912)","author":"Baumeister Dorothea","year":"2012"},{"key":"e_1_2_1_5_1","volume-title":"Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, J\u00f6rg Rothe (Ed.)","author":"Baumeister Dorothea"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI\u201909)","author":"Betzler Nadja","year":"2009"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI\u201911)","author":"Betzler Nadja","year":"2011"},{"key":"e_1_2_1_8_1","volume-title":"Fishburn","author":"Brams Steven J.","year":"2002"},{"key":"e_1_2_1_9_1","first-page":"358","article-title":"Parameterized algorithmics for computational social choice: Nine research challenges. Tsinghua Sci","volume":"19","author":"Bredereck Robert","year":"2014","journal-title":"Tech."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Association for the Advancement of Artificial Intelligence (AAAI\u201914)","author":"Bredereck Robert","year":"2014"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2693068.2693079"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66700-3_7"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23114-3_25"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Association for the Advancement of Artificial Intelligence (AAAI\u201916)","author":"Bredereck Robert","year":"2016"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/3013558.3013575"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 2011 Electronic Voting Technology Workshop \/ Workshop on Trustworthy Elections.","author":"Cary David","year":"2011"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_2_1_18_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek"},{"key":"e_1_2_1_19_1","volume-title":"Algebraic and Geometric Ideas in the Theory of Discrete Optimization. MOS-SIAM Series on Optimization","author":"De Loera Jes\u00fas A."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201915)","author":"Dey Palash"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.02.031"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118216.3118278"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17572-5_40"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04645-2_27"},{"key":"e_1_2_1_26_1","volume-title":"A Mathematical Introduction to Logic","author":"Enderton Herbert B.","edition":"2"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201908)","author":"Faliszewski Piotr","year":"2008"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/30"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2676"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2016945.2016954"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2697"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201908)","author":"Faliszewski Piotr","year":"2008"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33011901"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-014-9277-x"},{"key":"e_1_2_1_35_1","volume-title":"Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D","author":"Faliszewski Piotr"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201917)","author":"Faliszewski Piotr","year":"2017"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0133030"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23114-3_7"},{"key":"e_1_2_1_39_1","unstructured":"J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag Berlin.  J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer-Verlag Berlin."},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the Association for the Advancement of Artificial Intelligence (AAAI\u201990)","author":"Freuder Eugene C.","year":"1990"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the Association for the Advancement of Artificial Intelligence (AAAI\u201916)","author":"Ganian Robert","year":"2016"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-31489-7_2"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI\u201913)","author":"Hazon Noam","year":"2013"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0490-y"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.04.004"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-019-09403-3"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808749"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11538"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11335"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201917)","volume":"66","author":"Knop Du\u0161an","year":"2017"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/3237383.3237427"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Dusan Knop Martin Kouteck\u00fd and Matthias Mnich. 2019. Combinatorial n-fold integer programming and applications. Mathematical Programmin. https:\/\/doi.org\/10.1007\/s10107-019-01402-2.  Dusan Knop Martin Kouteck\u00fd and Matthias Mnich. 2019. Combinatorial n -fold integer programming and applications. Mathematical Programmin. https:\/\/doi.org\/10.1007\/s10107-019-01402-2.","DOI":"10.1007\/s10107-019-01402-2"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/2028012.2028016"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/3237383.3237933"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-017-9369-5"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the European Conference on Artificial Intelligence (ECAI\u201914)","volume":"263","author":"Narodytska Nina","year":"2014"},{"key":"e_1_2_1_58_1","volume-title":"Nonlinear Discrete Optimization","author":"Onn Shmuel"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9669-1"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-015-0064-0"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201913)","author":"Shiryaev Dmitry","year":"2013"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229086"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(77)90012-6"},{"key":"e_1_2_1_64_1","volume-title":"Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D","author":"Zwicker William S."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3396855","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3396855","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:06Z","timestamp":1750200066000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3396855"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,8,31]]}},"alternative-id":["10.1145\/3396855"],"URL":"https:\/\/doi.org\/10.1145\/3396855","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2018-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}