Document Open Access Logo

Voting and Bribing in Single-Exponential Time

Authors Dusan Knop, Martin Koutecký, Matthias Mnich

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.46.pdf
  • Filesize: 0.61 MB
  • 14 pages

Document Identifiers

Author Details

Dusan Knop
Martin Koutecký
Matthias Mnich

Cite As Get BibTex

Dusan Knop, Martin Koutecký, and Matthias Mnich. Voting and Bribing in Single-Exponential Time. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.46

Abstract

We introduce a general problem about bribery in voting systems. In the R-Multi-Bribery problem, the goal is to bribe a set of voters at minimum cost such that a desired candidate wins the manipulated election under the voting rule R. 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 for a candidate.
  
As our main result, we show that R-Multi-Bribery is fixed-parameter tractable parameterized by the number of candidates for many natural voting rules R, including Kemeny rule, all scoring protocols, maximin rule, Bucklin rule, fallback rule, SP-AV, and any C1 rule. In particular, our result resolves the parameterized of R-Swap Bribery for all those voting rules, thereby solving a long-standing open problem and "Challenge #2" of the 9 Challenges in computational social choice by Bredereck et al.
  
Further, our algorithm runs in single-exponential time for arbitrary cost; it thus improves the earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the unit-cost case for all scoring protocols, the maximin rule, and Bucklin rule.

Subject Classification

Keywords
  • Parameterized algorithm
  • swap bribery
  • n-fold integer programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. John J. Bartholdi III, Craig A. Tovey, and Michael A. Trick. Voting schemes for which it can be difficult to tell who won the election. Soc. Choice Welfare, 6(2):157-165, 1989. Google Scholar
  2. Dorothea Baumeister, Piotr Faliszewski, Jérôme Lang, and Jörg Rothe. Campaigns for lazy voters: truncated ballots. In Proc. AAMAS 2012, pages 577-584, 2012. Google Scholar
  3. Dorothea Baumeister and Jörg Rothe. Preference aggregation by voting. In Jörg Rothe, editor, Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division., pages 197-326. Springer, 2016. Google Scholar
  4. Nadja Betzler, Susanne Hemmann, and Rolf Niedermeier. A multivariate complexity analysis of determining possible winners given incomplete votes. In Proc. IJCAI 2009, pages 53-58, 2009. Google Scholar
  5. Steven J. Brams and Peter C. Fishburn. Voting procedures. In Katora Suzumura Kenneth J. Arrow, Armatya K. Sen, editor, Handbook of Social Choice and Welfare, volume 19 of Handbooks in Economics, pages 173-236. Elsevier, 2002. Google Scholar
  6. Robert Bredereck, Jiehua Chen, Piotr Faliszewski, Jiong Guo, Rolf Niedermeier, and Gerhard J. Woeginger. Parameterized algorithmics for computational social choice: Nine research challenges. Tsinghua Sci. Tech., 19(4):358-373, 2014. Google Scholar
  7. Robert Bredereck, Jiehua Chen, Piotr Faliszewski, André Nichterlein, and Rolf Niedermeier. Prices matter for the parameterized complexity of shift bribery. In Proc. AAAI 2014, pages 552-558, 2014. Google Scholar
  8. Robert Bredereck, Jiehua Chen, Sepp Hartung, Stefan Kratsch, Rolf Niedermeier, Ondrey Suchý, and Gerhard J. Woeginger. A multivariate complexity analysis of lobbying in multiple referenda. J. Artificial Intelligence Res., 50:409-446, 2014. Google Scholar
  9. Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, Piotr Skowron, and Nimrod Talmon. Elections with few candidates: Prices, weights, and covering problems. In Proc. ADT 2015, volume 9346 of Lecture Notes Comput. Sci., pages 414-431, 2015. Google Scholar
  10. Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, Piotr Skowron, and Nimrod Talmon. Complexity of shift bribery in committee elections. In Proc. AAAI 2016, pages 2452-2458, 2016. Google Scholar
  11. Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, and Nimrod Talmon. Large-scale election campaigns: Combinatorial shift bribery. J. Artificial Intelligence Res., 55:603-652, 2016. Google Scholar
  12. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform. and Comput., 85(1):12-75, 1990. Google Scholar
  13. Britta Dorn and Ildikó Schlotter. Multivariate complexity analysis of swap bribery. Algorithmica, 64(1):126-151, 2012. Google Scholar
  14. Edith Elkind, Piotr Faliszewski, and Arkadii Slinko. Swap bribery. In Proc. SAGT 2009, volume 5814 of Lecture Notes Comput. Sci., pages 299-310, 2009. Google Scholar
  15. Edith Elkind, Piotr Faliszewski, and Arkadii Slinko. Swap bribery, 2009. URL: https://arxiv.org/abs/0905.3885.
  16. Herbert B. Enderton. A Mathematical Introduction to Logic. Academic Press, 1972. Google Scholar
  17. Piotr Faliszewski. Nonuniform bribery. In Proc. AAMAS 2008, pages 1569-1572, 2008. Google Scholar
  18. Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra. How hard is bribery in elections? J. Artificial Intelligence Res., 40:485-532, 2009. Google Scholar
  19. Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra. Multimode control attacks on elections. J. Artificial Intelligence Res., 40:305-351, 2011. Google Scholar
  20. Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. Llull and copeland voting computationally resist bribery and constructive control. J. Artificial Intelligence Res., 35:275-341, 2009. Google Scholar
  21. Robert Ganian and Sebastian Ordyniak. The complexity landscape of decompositional parameters for ILP. In Proc. AAAI 2016, pages 710-716, 2016. Google Scholar
  22. Raymond Hemmecke, Shmuel Onn, and Lyubov Romanchuk. n-fold integer programming in cubic time. Math. Program., 137(1-2, Ser. A):325-341, 2013. Google Scholar
  23. Hendrik W. Lenstra, Jr. Integer programming with a fixed number of variables. Math. Oper. Res., 8(4):538-548, 1983. Google Scholar
  24. Jesus A. De Loera, Raymond Hemmecke, and Matthias Köppe. Algebraic and Geometric Ideas in the Theory of Discrete Optimization, volume 14 of MOS-SIAM Series on Optimization. SIAM, 2013. Google Scholar
  25. Shmuel Onn. Nonlinear discrete optimization. Zurich Lectures in Advanced Mathematics, European Mathematical Society, 2010. Google Scholar
  26. Ildikó Schlotter, Piotr Faliszewski, and Edith Elkind. Campaign management under approval-driven voting rules. In Proc. AAAI 2011, pages 726-731, 2011. Google Scholar
  27. Hobart P. Young. Extending Condorcet’s rule. J. Econ. Theory, 16:335-353, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact