Abstract
A d-Approval election consists of a set C of candidates and a set V of votes, where each vote v can be presented as a set of d candidates. For a vote v ∈ V, the protocol assigns one point to each candidate in v. The candidate getting the most points from all votes wins the election. An important aspect of studying election systems is the strategic behavior such as control and bribery problems. The control by deleting votes problem decides whether for a given election (C,V), a specific candidate c, and an integer k, it is possible to delete at most k votes such that c wins the resulting election. In the control by adding votes setting, one has two sets V and U of votes and asks for a subset U′ ⊆ U such that |U′| ≤ k and c becomes the winner in V ∪ U′. The bribery problem has the same input as the vote deleting control problem and asks for changing at most k votes to make c win. All three problems have been shown NP-hard. We initialize the study of the parameterized complexity of these problems and present a collection of tractability and intractability results. In particular, we derive polynomial-size problem kernels for the standard parameterizations of the control by deleting votes and bribery problems, the seemingly first non-trivial problem kernels for the control and bribery problems of elections.
This work is supported by the National Natural Science Foundation of China under Grant (61232001, 61103033, 61173051, 61128006), the DFG Excellence Cluster on Multimodal Computing and Interaction (MMCI).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arrow, K., Sen, A., Suzumura, K.: Handbook of Social Choice and Welfare I. North-Holland (2002)
Arrow, K., Sen, A., Suzumura, K.: Handbook of Social Choice and Welfare II. North-Holland (2010)
Bartholdi III, J., Tovey, C.A., Trick, M.A.: Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare 6, 157–165 (1989)
Bartholdi III, J., Tovey, C.A., Trick, M.A.: How hard is it to control an election? Mathematical and Computer Modelling 16(8/9), 27–40 (1992)
Betzler, N., Bredereck, R., Chen, J., Niedermeier, R.: Studies in Computational Aspects of Voting - A Parameterized Complexity Perspective. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift 2012. LNCS, vol. 7370, pp. 318–363. Springer, Heidelberg (2012)
Bodlaender, H.L.: Kernelization: New Upper and Lower Bound Techniques. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 17–37. Springer, Heidelberg (2009)
Conitzer, V., Sandholm, T., Lang, J.: When are elections with few candidates hard to manipulate? Journal of the ACM 54(3), 1–33 (2007)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A.: How Hard Is Bribery in Elections? J. Artif. Intell. Res (JAIR) 35, 485–532 (2009)
Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A., Rothe, J.: Llull and Copeland Voting Computationally Resist Bribery and Constructive Control. J. Artif. Intell. Res (JAIR) 35, 275–341 (2009)
Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. ACM SIGACT News 38(1), 31–45 (2007)
Hemaspaandra, E., Hemaspaandra, L.A., Rothe, J.: Anyone but him: The complexity of precluding an alternative. Artificial Intelligence 171(5-6), 255–285 (2007)
Jia, W., Zhang, C., Chen, J.: An efficient parameterized algorithm for m-set packing. J. Algorithms 50(1), 106–117 (2004)
Lenstra, H.W.: Integer programming with a fixed number of variables. Mathematics of Operations Research 8, 538–548 (1983)
Lin, A.: The complexity of manipulating k-Approval elections. In: Proc. 3rd International Conference on Agents and Artificial Intelligence, vol. (2), pp. 212–218. SciTe Press (2011)
Meir, R., Procaccia, A., Rosenschein, J., Zohar, A.: Complexity of strategic behavior in multi-winner elections. Journal of Artificial Intelligence Research 33, 149–178 (2008)
Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Wang, J., Yang, M., Guo, J., Feng, Q., Chen, J. (2013). Parameterized Complexity of Control and Bribery for d-Approval Elections. In: Widmayer, P., Xu, Y., Zhu, B. (eds) Combinatorial Optimization and Applications. COCOA 2013. Lecture Notes in Computer Science, vol 8287. Springer, Cham. https://doi.org/10.1007/978-3-319-03780-6_23
Download citation
DOI: https://doi.org/10.1007/978-3-319-03780-6_23
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03779-0
Online ISBN: 978-3-319-03780-6
eBook Packages: Computer ScienceComputer Science (R0)