Group control for procedural rules: parameterized complexity and consecutive domains

Abstract

We consider GROUP CONTROL BY ADDING INDIVIDUALS (GCAI) in the setting of group identification for two procedural rules—the consensus-start-respecting rule and the liberal-start-respecting rule. It is known that GCAI for both rules are \mathsf{\text{NP}}-hard, but whether they are fixed-parameter tractable with respect to the number of distinguished individuals remained open. We resolve both open problems in the affirmative. In addition, we strengthen the \mathsf{\text{NP}}-hardness of GCAI by showing that, with respect to the natural parameter the number of added individuals, GCAI for both rules are \mathsf{\text{W[2]}}-hard. Notably, the \mathsf{\text{W[2]}}-hardness for the liberal-start-respecting rule holds even when restricted to a very special case where the qualifications of individuals satisfy the so-called consecutive ones property. However, for the consensus-start-respecting rule, the problem becomes polynomial-time solvable in this special case. We also study a dual restriction where the disqualifications of individuals fulfill the consecutive ones property, and show that under this restriction GCAI for both rules turn out to be polynomial-time solvable. Our reductions for showing \mathsf{\text{W[2]}}-hardness also imply several algorithmic lower bounds.

Graphical abstract

Keywords

group control by adding individuals / group identification / parameterized complexity / consecutive ones property / FPT / W[2]-hard

References

[1] Kasher A, Rubinstein A . On the question “Who is a J?”: a social choice approach.. Logique et Analyse, 1997, 40( 160): 385–395

[2] Kasher A. Jewish collective identity. In: Goldberg D T, Krausz M, eds. Jewish Identity. Temple University Press, 1993, 56−78

[3] Dimitrov D. The social choice approach to group identification. In: Herrera-Viedma E, García-Lapresta J L, Kacprzyk J, Fedrizzi M, Nurmi H, Zadrożny S, eds. Consensual Processes. Berlin: Springer, 2011, 123−134

[4] Dimitrov D, Sung S C, Xu Y . Procedural group identification. Mathematical Social Sciences, 2007, 54( 2): 137–146

[5] Nicolas H . “I want to be a J!”: Liberalism in group identification problems. Mathematical Social Sciences, 2007, 54( 1): 59–70

[6] Miller A D . Group identification. Games and Economic Behavior, 2008, 63( 1): 188–202

[7] Samet D, Schmeidler D . Between liberalism and democracy. Journal of Economic Theory, 2003, 110( 2): 213–233

[8] Bartholdi J J, Tovey C A, Trick M A . How hard is it to control an election?. Mathematical and Computer Modelling, 1992, 16( 8−9): 27–40

[9] Yang Y, Dimitrov D . How hard is it to control a group?. Autonomous Agents and Multi-Agent Systems, 2018, 32( 5): 672–692

[10] Erdélyi G, Reger C, Yang Y . The complexity of bribery and control in group identification. Autonomous Agents and Multi-Agent Systems, 2020, 34( 1): 8

[11] Erdélyi G, Reger C, Yang Y. Complexity of group identification with partial information. In: Proceedings of the 5th International Conference on Algorithmic Decision Theory. 2017, 182−196

[12] Erdélyi G, Yang Y. Microbribery in group identification. In: Proceedings of the 19th International Conference on Autonomous Agents and Multi-Agent Systems. 2020, 1840−1842

[13] Boehmer N, Bredereck R, Knop D, Luo J. Fine-grained view on bribery for group identification. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence. 2020, 67−73

[14] Junker E. Broadening the complexity-theoretic analysis of manipulative attacks in group identification. Humboldt Universitat zu Berlin, Dissertation, 2022

[15] Junker E. Manipulative attacks and group identification. 2022, arXiv preprint arXiv: 2203.16151

[16] Blažej V. Complexity of games on graphs. Czech Technical University, Dissertation, 2022

[17] Yang Y, Dimitrov D . Group control for consent rules with consecutive qualifications. Mathematical Social Sciences, 2023, 121: 1–7

[18] Brandt F, Brill M, Hemaspaandra E, Hemaspaandra L A . Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates. Journal of Artificial Intelligence Research, 2015, 53: 439–496

[19] 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. Information and Computation, 2011, 209( 2): 89–107

[20] Peters D. Single-peakedness and total unimodularity: new polynomial-time algorithms for multi-winner elections. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 2018, 1169−1176

[21] Elkind E, Lackner M. Structure in dichotomous preferences. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence. 2015, 2019−2025

[22] Liu H, Guo J. Parameterized complexity of winner determination in minimax committee elections. In: Proceedings of the 15th International Conference on Autonomous Agents and Multi-Agent Systems. 2016, 341−349

[23] Yang Y. On the tree representations of dichotomous preferences. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019, 644−650

[24] Betzler N, Slinko A, Uhlmann J . On the computation of fully proportional representation. Journal of Artificial Intelligence Research, 2013, 47: 475–519

[25] Skowron P, Yu L, Faliszewski P, Elkind E . The complexity of fully proportional representation for single-crossing electorates. Theoretical Computer Science, 2015, 569: 43–57

[26] Elkind E, Lackner M, Peters D. Structured preferences. In: Endriss U, ed. Trends in Computational Social Choice. AI Access, 2017, 187–207

[27] Hemaspaandra E, Hemaspaandra L A, Rothe J. The complexity of manipulative actions in single-peaked societies. In: Rothe J, ed. Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Berlin: Springer, 2016, 327−360

[28] Karpov A V . Structured preferences: A literature survey. Automation and Remote Control, 2022, 83( 9): 1329–1354

[29] Elkind E, Lackner M, Peters D. Preference restrictions in computational social choice: A survey. 2022, arXiv preprint arXiv: 2205.09092

[30] Dom M . Algorithmic aspects of the consecutive-ones property. Bulletin of the European Association for Theoretical Computer Science, 2009, 98: 27–59

[31] Peters D, Lackner M . Preferences single-peaked on a circle. Journal of Artificial Intelligence Research, 2020, 68: 463–502

[32] Booth K S, Lueker G S . Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Journal of Computer and System Sciences, 1976, 13( 3): 335–379

[33] Hsu W L . A simple test for the consecutive ones property. Journal of Algorithms, 2002, 43( 1): 1–16

[34] Cygan M, Fomin F V, Kowalik Ł, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S. Lower bounds based on the exponential-time hypothesis. In: Cygan M, Fomin F V, Kowalik Ł, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S, eds. Parameterized Algorithms. Cham: Springer, 2015, 467−521

[35] Downey R G, Fellows M R. Fundamentals of Parameterized Complexity. London: Springer, 2013

[36] Bang-Jensen J, Gutin G. Digraphs—Theory, Algorithms and Applications. 2nd ed. London: Springer, 2009

[37] West D B. Introduction to Graph Theory. 2nd ed. Prentice Hall, 2001

[38] Dreyfus S E, Wagner R A . The Steiner problem in graphs. Networks, 1971, 1( 3): 195–207

[39] Guo J, Niedermeier R, Suchý O . Parameterized complexity of arc-weighted directed Steiner problems. SIAM Journal on Discrete Mathematics, 2011, 25( 2): 583–599

[40] Ding B, Yu J X, Wang S, Qin L, Zhang X, Lin X. Finding top-k min-cost connected trees in databases. In: Proceedings of the 23rd International Conference on Data Engineering. 2007, 836−845

[41] Björklund A, Husfeldt T, Kaski P, Koivisto M. Fourier meets Möbius: Fast subset convolution. In: Proceedings of the 39th ACM Symposium on Theory of Computing. 2007, 67−74

[42] Fuchs B, Kern W, Molle D, Richter S, Rossmanith P, Wang X . Dynamic programming for minimum Steiner trees. Theory of Computing Systems, 2007, 41( 3): 493–500

[43] Dom M, Lokshtanov D, Saurabh S . Kernelization lower bounds through colors and IDs. ACM Transactions on Algorithms, 2014, 11( 2): 13

[44] Chen J, Huang X, Kanj I A, Xia G . Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences, 2006, 72( 8): 1346–1367

RIGHTS & PERMISSIONS

The Author(s) 2023. This article is published with open access at link.springer.com and journal.hep.com.cn