×

Parameterized complexity of control and bribery for \(d\)-approval elections. (English) Zbl 1328.68097

Summary: 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 \in V\), the \(d\)-Approval voting 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^\prime \subseteq U\) such that \(|U^\prime| \leq k\) and \(c\) becomes the winner in \(V \cup U^\prime\). 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 a polynomial-size problem kernel for the standard parameterization of the control by deleting votes problem, the seemingly first non-trivial problem kernel for the control problem of elections.

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
91B12 Voting theory
91B14 Social choice
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arrow, K.; Sen, A.; Suzumura, K., Handbook of Social Choice and Welfare I (2002), North-Holland · Zbl 1307.91009
[2] Arrow, K.; Sen, A.; Suzumura, K., Handbook of Social Choice and Welfare II (2010), North-Holland
[3] Bartholdi, J.; Tovey, C. A.; Trick, M. A., Voting schemes for which it can be difficult to tell who won the election, Soc. Choice Welf., 6, 157-165 (1989) · Zbl 0672.90004
[4] Bartholdi, J.; Tovey, C. A.; Trick, M. A., How hard is it to control an election?, Math. Comput. Modelling, 16, 8/9, 27-40 (1992) · Zbl 0757.90008
[5] Betzler, N.; Bredereck, R.; Chen, J.; Niedermeier, R., Studies in Computational Aspects of Voting - A Parameterized Complexity Perspective, The Multivariate Algorithmic Revolution and Beyond, Lecture Notes in Computer Science, vol. 7370, 318-363 (2012), Springer · Zbl 1358.68118
[6] Bodlaender, H. L., Kernelization: new upper and lower bound techniques, (Proc. 4th IWPEC. Proc. 4th IWPEC, Lecture Notes in Computer Science, vol. 5917 (2009), Springer), 17-37 · Zbl 1273.68158
[7] Conitzer, V.; Sandholm, T.; Lang, J., When are elections with few candidates hard to manipulate?, J. ACM, 54, 3, 1-33 (2007) · Zbl 1292.91062
[8] Downey, R. G.; Fellows, M. R., Parameterized Complexity (1999), Springer · Zbl 0914.68076
[9] Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A., How hard is bribery in elections?, J. Artificial Intelligence Res., 35, 485-532 (2009) · Zbl 1180.91090
[10] Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.; Rothe, J., Llull and Copeland voting computationally resist bribery and constructive control, J. Artificial Intelligence Res., 35, 275-341 (2009) · Zbl 1180.91091
[11] Guo, J.; Niedermeier, R., Invitation to data reduction and problem kernelization, SIGACT News, 38, 1, 31-45 (2007)
[12] Hemaspaandra, E.; Hemaspaandra, L. A.; Rothe, J., Anyone but him: the complexity of precluding an alternative, Artificial Intelligence, 171, 5-6, 255-285 (2007) · Zbl 1168.91346
[13] Jia, W.; Zhang, C.; Chen, J., An efficient parameterized algorithm for \(m\)-set packing, J. Algorithms, 50, 1, 106-117 (2004) · Zbl 1068.68171
[14] Lenstra, H. W., Integer programming with a fixed number of variables, Math. Oper. Res., 8, 538-548 (1983) · Zbl 0524.90067
[15] Lin, A., The complexity of manipulating \(k\)-approval elections, (Proc. 3rd International Conference on Agents and Artificial Intelligence (2) (2011), SciTePress), 212-218
[16] Meir, R.; Procaccia, A.; Rosenschein, J.; Zohar, A., Complexity of strategic behavior in multi-winner elections, J. Artificial Intelligence Res., 33, 149-178 (2008) · Zbl 1165.91361
[17] Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.