nach oben

Theory of Computing Systems

Erschienen in:

18.01.2018

Parameterized Complexity of Voter Control in Multi-Peaked Elections

verfasst von: Yongjie Yang, Jiong Guo

Erschienen in: Theory of Computing Systems | Ausgabe 8/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We study the parameterized complexity of voter control problems in κ-peaked elections, where κ is a positive integer. In particular, we focus on the constructive/destructive control by adding/deleting votes for Condorcet, Maximin and Copeland^α. It is known that in general elections all these problems are NP-hard, except for the destructive control by adding/deleting votes for Condorcet which is polynomial-time solvable. We strengthen these results by showing that, when restricted to κ-peaked elections where κ = 3,4, the above NP-hard problems not only remain NP-hard but also are W[1]-hard with respect to the number of added/deleted votes.

Vorheriger Artikel Set Cover Problems with Small Neighborhood Covers

Nächster Artikel Reasoning About XML Constraints Based on XML-to-Relational Mappings

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

A voting correspondence is weakCondorcet consistent if whenever weak Condorcet winners exist the correspondence selects exactly all weak Condorcet winners as winners. There are several variants of weakCondorcet consistent (see, e.g., [27]). The one we mentioned here is the notion used by Brandt et al. [7] to establish their polynomial-time solvability results.

The reduction is still correct without the candidate y (i.e., simply removing y from \(\mathcal {C}\) and all constructed votes does not affect the correctness). However, the subsequent reduction for DCAV-Copeland⁰-UNI needs the candidate y and is obtained from the reduction for DCAV-Copeland⁰-NON by creating polynomially many dummy candidates. Hence, for ease of exposition of the reduction for DCAV-Copeland⁰-UNI, we keep the candidate y in the reduction.

Arrow, K.J.: A difficulty in the concept of social welfare. J. Polit. Econ. 58 (4), 328–346 (1950)CrossRef

Ballester, M.A., Haeringer, G.: A characterization of the single-peaked domain. Soc. Choice Welf. 36(2), 305–322 (2011)MathSciNetCrossRefMATH

Bartholdi, J. J., III, Tovey, C.A., Trick, M.A.: How hard is it to control an election? Math. Comput. Model. 16(8-9), 27–40 (1992)MathSciNetCrossRefMATH

Betzler, N., Slinko, A., Uhlmann, J.: On the computation of fully propotional representation. J. Artif. Intell. Res. 47, 475–519 (2013)CrossRefMATH

Betzler, N., Uhlmann, J.: Parameterized complexity of candidate control in elections and related digraph problems. Theor. Comput. Sci. 410(52), 5425–5442 (2009)MathSciNetCrossRefMATH

Black, D.: On the rationale of group decision-making. J. Polit. Econ. 56(1), 23–34 (1948)CrossRef

Brandt, F., Brill, M., Hemaspaandra, E., Hemaspaandra, L.A.: Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates. J. Artif. Intell. Res. 53, 439–496 (2015)MathSciNetCrossRefMATH

Bredereck, R., Chen, J., Woeginger, G.J.: Are there any nicely structured preference profiles nearby. Math. Soc. Sci. 79, 61–73 (2016)MathSciNetCrossRefMATH

Bulteau, L., Chen, J., Faliszewski, P., Niedermeier, R., Talmon, N.: Combinatorial voter control in elections. Theor. Comput. Sci. 589, 99–120 (2015)MathSciNetCrossRefMATH

10.

Conitzer, V.: Making decisions based on the preferences of multiple agents. Commun. ACM 53(3), 84–94 (2010)MathSciNetCrossRef

11.

Cornaz, D., Galand, L., Spanjaard, O.: Kemeny elections with bounded single-peaked or single-crossing width. In: IJCAI, pp. 76–82 (2013)

12.

Demange, G.: Single-peaked orders on a tree. Math. Soc. Sci. 3(3), 389–396 (1983)MathSciNetMATH

13.

Doignon, J.P., Falmagne, J.C.: A polynomial time algorithm for unidimensional unfolding representations. J. Algorithm. 16(2), 218–233 (1994)MathSciNetCrossRefMATH

14.

Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity texts in computer science. Springer, Berlin (2013)

15.

Egan, P.J.: Do something politics and double-peaked policy preferences. J. Polit. 76(2), 333–349 (2014)CrossRef

16.

Erdėlyi, G., Hemaspaandra, E., Hemaspaandra, L.A.: More natural models of electoral control by partition. In: ADT, pp. 396–413 (2015)

17.

Erdélyi, G., Lackner, M., Pfandler, A.: Computational aspects of nearly single-peaked electorates. J. Artif. Intell. Res. 58, 297–337 (2017)MathSciNetCrossRefMATH

18.

Erdélyi, G., Nowak, M., Rothe, J.: Sincere-strategy preference-based approval voting fully resists constructive control and broadly resists destructive control. Math. Log. Q. 55(4), 425–443 (2009)MathSciNetCrossRefMATH

19.

Erdélyi, G., Reger, C., Yang, Y.: The complexity of bribery and control in group identification. In: AAMAS, pp. 1142–1150 (2017)

20.

Escoffier, B., Lang, J., Öztürk, M.: Single-peaked consistency and its complexity. In: ECAI, pp. 366–370 (2008)

21.

Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A.: Multimode control attacks on elections. J. Artif. Intell. Res. 40, 305–351 (2011)MathSciNetCrossRefMATH

22.

Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A.: The complexity of manipulative attacks in nearly single-peaked electorates. Artif. Intell. 207, 69–99 (2014)MathSciNetCrossRefMATH

23.

Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A., Rothe, J.: Llull and Copeland voting computationally resist bribery and constructive control. J. Artif. Intell. Res. 35, 275–341 (2009)MathSciNetCrossRefMATH

24.

Faliszewski, P., Hemaspaandra, E., Hemaspaandra, L.A., Rothe, J.: The shield that never was: Societies with single-peaked preferences are more open to manipulation and control. Inf. Comput. 209(2), 89–107 (2011)MathSciNetCrossRefMATH

25.

Faliszewski, P., Rothe, J.: Control and bribery in voting. In: Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A. (eds.) Handbook of Computational Social Choice, chapter 7, pp 146–168. Cambridge University Press (2016)

26.

Fellows, M.R., Hermelin, D., Rosamond, F.A., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53–61 (2009)MathSciNetCrossRefMATH

27.

Felsenthal, D.S., Tideman, N.: Weak Condorcet winner(s) revisited. Public Choice 160(3), 313–326 (2014)CrossRef

28.

Gupta, U.I., Lee, D.T., Leung, J. Y. -T.: Efficient algorithms for interval graphs and circular-arc graphs. Networks 12(4), 459–467 (1982)MathSciNetCrossRefMATH

29.

Hemaspaandra, E., Hemaspaandra, L.A., Rothe, J.: Anyone but him: The complexity of precluding an alternative. Artif. Intell. 171(5-6), 255–285 (2007)MathSciNetCrossRefMATH

30.

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)MathSciNetCrossRefMATH

31.

Liu, H., Zhu, D.: Parameterized complexity of control problems in Maximin election. Inf. Process. Lett. 110(10), 383–388 (2010)MathSciNetCrossRefMATH

32.

Liu, H., Zhu, D.: Parameterized complexity of control by voter selection in Maximin, Copeland, Borda, Bucklin, and Approval election systems. Theor. Comput. Sci. 498, 115–123 (2013)MathSciNetCrossRefMATH

33.

Russell, N.F.: Complexity of control of Borda count elections. Master’s thesis, Rochester Institute of Technology (2007)

34.

Stiglitz, J.E.: The demand for education in public and private school systems. J. Pubilc Econ. 3, 349–385 (1974)CrossRef

35.

Walsh, T.: Uncertainty in preference elicitation and aggregation. In: AAAI, pp. 3–8 (2007)

36.

Yang, Y.: Election attacks with few candidates. In: ECAI, pp. 1131–1132 (2014)

37.

Yang, Y.: Manipulation with bounded single-peaked width: A parameterized study. In: AAMAS, pp. 77–85 (2015)

38.

Yang, Y.: The complexity of control and bribery in majority judgement. In AAMAS, pp. 1169–1177 (2017)

39.

Yang, Y.: On the complexity of Borda control in single-peaked elections. In: AAMAS, pp. 1178–1186 (2017)

40.

Yang, Y., Guo, J.: Controlling elections with bounded single-peaked width. In: AAMAS, pp. 629–636 (2014)

41.

Yang, Y., Guo, J.: How hard is control in multi-peaked elections: A parameterized study. In: AAMAS, pp. 1729–1730 (2015)

42.

Yang, Y., Guo, J.: The control complexity of r-approval: From the single-peaked case to the general case. J. Comput. Syst. Sci. 89, 432–449 (2017)MathSciNetCrossRefMATH

43.

Yang, Y., Wang, J.: Anyone but them: The complexity challenge for a resolute election controller. In: AAMAS, pp. 1133–1141 (2017)

Titel: Parameterized Complexity of Voter Control in Multi-Peaked Elections
verfasst von: Yongjie Yang
Jiong Guo
Publikationsdatum: 18.01.2018
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 8/2018
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-018-9843-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 8/2018

Parameterised Algorithms for Deletion to Classes of DAGs

Polynomial Kernels for Vertex Cover Parameterized by Small Degree Modulators

Reasoning About XML Constraints Based on XML-to-Relational Mappings

Space Efficient Linear Time Algorithms for BFS, DFS and Applications

Finger Search in Grammar-Compressed Strings

Revisiting Connected Vertex Cover: FPT Algorithms and Lossy Kernels