×

zbMATH — the first resource for mathematics

On the computational complexity of variants of combinatorial voter control in elections. (English) Zbl 06721529
Gopal, T. V. (ed.) et al., Theory and applications of models of computation. 14th annual conference, TAMC 2017, Bern, Switzerland, April 20–22, 2017. Proceedings. Cham: Springer (ISBN 978-3-319-55910-0/pbk; 978-3-319-55911-7/ebook). Lecture Notes in Computer Science 10185, 348-361 (2017).
Summary: Voter control problems model situations in which an external agent tries to affect the result of an election by adding or deleting the fewest number of voters. The goal of the agent is to make a specific candidate either win (constructive control) or lose (destructive control) the election. We study the constructive and destructive voter control problems when adding and deleting voters have a combinatorial flavor: if we add (resp. delete) a voter \(v\), we also add (resp. delete) a bundle \(\kappa (v)\) of voters that are associated with \(v\). While the bundle \(\kappa (v)\) may have more than one voter, a voter may also be associated with more than one voter. We analyze the computational complexity of the four voter control problems for the Plurality rule.
We obtain that, in general, making a candidate lose is computationally easier than making her win. In particular, if the bundling relation is symmetric (i.e. \(\forall w:w \in \kappa (v) \Leftrightarrow v \in \kappa (w)\)), and if each voter has at most two voters associated with him, then destructive control is polynomial-time solvable while the constructive variant remains \(\mathsf {NP}\)-hard. Even if the bundles are disjoint (i.e. \(\forall w:w \in \kappa (v) \Leftrightarrow \kappa (v) = \kappa (w)\)), the constructive problem variants remain intractable. Finally, the minimization variant of constructive control by adding voters does not admit an efficient approximation algorithm, unless \(\mathsf {P}= \mathsf {NP}\).
For the entire collection see [Zbl 1360.68012].

MSC:
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anstee, R.P.: An algorithmic proof of Tutte’s \[ f \] -factor theorem. J. Algorithms 6(1), 112–131 (1985) · Zbl 0562.05038 · doi:10.1016/0196-6774(85)90022-7
[2] Anstee, R.P.: Minimum vertex weighted deficiency of \[ (g, f) \] -factors: a greedy algorithm. Discrete Appl. Math. 44(1–3), 247–260 (1993) · Zbl 0797.05065 · doi:10.1016/0166-218X(93)90235-G
[3] Bartholdi, J.J., Tovey, C.A., Trick, M.A.: How hard is it to control an election? Math. Comput. Model. 16(8–9), 27–40 (1992) · Zbl 0757.90008 · doi:10.1016/0895-7177(92)90085-Y
[4] Betzler, N., Uhlmann, J.: Parameterized complexity of candidate control in elections and related digraph problems. Theor. Comput. Sci. 410(52), 43–53 (2009) · Zbl 1176.68138 · doi:10.1016/j.tcs.2009.05.029
[5] Betzler, N., Bredereck, R., Chen, J., Niedermeier, R.: Studies in computational aspects of voting. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) The Multivariate Algorithmic Revolution and Beyond. LNCS, vol. 7370, pp. 318–363. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-30891-8_16 · Zbl 1358.68118 · doi:10.1007/978-3-642-30891-8_16
[6] Bredereck, R., Chen, J., Faliszewski, P., Guo, J., Niedermeier, R., Woeginger, G.J.: Parameterized algorithmics for computational social choice: nine research challenges. Tsinghua Sci. Technol. 19(4), 358–373 (2014) · doi:10.1109/TST.2014.6867518
[7] Bredereck, R., Faliszewski, P., Niedermeier, R., Talmon, N.: Large-scale election campaigns: combinatorial shift bribery. J. Artif. Intell. Res. 55, 603–652 (2016) · Zbl 1352.68094
[8] Bulteau, L., Chen, J., Faliszewski, P., Niedermeier, R., Talmon, N.: Combinatorial voter control in elections. Theor. Comput. Sci. 589, 99–120 (2015) · Zbl 1318.91057 · doi:10.1016/j.tcs.2015.04.023
[9] Chen, J.: Exploiting structure in computationally hard voting problems. Ph.D. thesis, Technische Universität Berlin (2016)
[10] Chen, J., Faliszewski, P., Niedermeier, R., Talmon, N.: Elections with few voters: Candidate control can be easy. In: AAAI 2015, pp. 2045–2051 (2015) · Zbl 1426.91092
[11] Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach, vol. 168. Cambridge University Press, New York (2012) · Zbl 1257.68006 · doi:10.1017/CBO9780511977619
[12] Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, London (2013) · Zbl 1358.68006 · doi:10.1007/978-1-4471-5559-1
[13] Erdélyi, G., Fellows, M.R., Rothe, J., Schend, L.: Control complexity in Bucklin and fallback voting: a theoretical analysis. J. Comput. Syst. Sci. 81(4), 632–660 (2015) · Zbl 1320.91055 · doi:10.1016/j.jcss.2014.11.002
[14] Faliszewski, P., Rothe, J.: Control and bribery in voting. In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A.D. (eds.) Handbook of Computational Social Choice, Chap. 7. Cambridge University Press, Cambridge (2016) · doi:10.1017/CBO9781107446984.008
[15] Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L., Rothe, J.: Llull and Copeland voting computationally resist bribery and constructive control. J. Artif. Intell. Res. 35, 275–341 (2009) · Zbl 1180.91091
[16] Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.: Multimode control attacks on elections. J. Artif. Intell. Res. 40, 305–351 (2011) · Zbl 1242.91055
[17] Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A.: Weighted electoral control. J. Artif. Intell. Res. 52, 507–542 (2015) · Zbl 1328.91068
[18] Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)
[19] Hemaspaandra, E., Hemaspaandra, L.A., Rothe, J.: Anyone but him: the complexity of precluding an alternative. Artif. Intell. 171(5), 255–285 (2007) · Zbl 1168.91346 · doi:10.1016/j.artint.2007.01.005
[20] Hemaspaandra, L.A., Lavaee, R., Menton, C.: Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control. Ann. Math. Artif. Intell. 77(3–4), 191–223 (2016) · Zbl 1346.91072
[21] Kellerhals, L., Korenwein, V., Zschoche, P., Bredereck, R., Chen, J.: On the computational complexity of variants of combinatorial voter control in elections. Technical report arXiv:1701.05108 [cs.MA]. arXiv.org , January 2017 · Zbl 06721529
[22] Liu, H., Zhu, D.: Parameterized complexity of control problems in Maximin election. Inf. Process. Lett. 110(10), 383–388 (2010) · Zbl 1229.68045 · doi:10.1016/j.ipl.2010.03.006
[23] Liu, H., Feng, H., Zhu, D., Luan, J.: Parameterized computational complexity of control problems in voting systems. Theor. Comput. Sci. 410(27–29), 2746–2753 (2009) · Zbl 1164.91004 · doi:10.1016/j.tcs.2009.04.004
[24] Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006) · Zbl 1095.68038 · doi:10.1093/acprof:oso/9780198566076.001.0001
[25] Procaccia, A.D., Rosenschein, J.S., Zohar, A.: Multi-winner elections: Complexity of manipulation, control and winner-determination. In: IJCAI 2007, pp. 1476–1481 (2007)
[26] Rothe, J., Schend, L.: Challenges to complexity shields that are supposed to protect elections against manipulation and control: A survey. Ann. Math. Artif. Intell. 68(1–3), 161–193 (2013) · Zbl 1286.68207 · doi:10.1007/s10472-013-9359-5
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.