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 -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 -hardness of GCAI by showing that, with respect to the natural parameter the number of added individuals, GCAI for both rules are -hard. Notably, the -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 -hardness also imply several algorithmic lower bounds.
A, Kasher A Rubinstein . 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
D Dimitrov . 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
D, Dimitrov S C, Sung Y Xu . Procedural group identification. Mathematical Social Sciences, 2007, 54( 2): 137–146
5
H Nicolas . “I want to be a J!”: Liberalism in group identification problems. Mathematical Social Sciences, 2007, 54( 1): 59–70
6
A D Miller . Group identification. Games and Economic Behavior, 2008, 63( 1): 188–202
7
D, Samet D Schmeidler . Between liberalism and democracy. Journal of Economic Theory, 2003, 110( 2): 213–233
8
J J, Bartholdi C A, Tovey M A Trick . How hard is it to control an election?. Mathematical and Computer Modelling, 1992, 16( 8−9): 27–40
9
Y, Yang D Dimitrov . How hard is it to control a group?. Autonomous Agents and Multi-Agent Systems, 2018, 32( 5): 672–692
10
G, Erdélyi C, Reger Y Yang . The complexity of bribery and control in group identification. Autonomous Agents and Multi-Agent Systems, 2020, 34( 1): 8
11
G, Erdélyi C, Reger Y Yang . 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
N, Boehmer R, Bredereck D, Knop J Luo . 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
E Junker . 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
Y, Yang D Dimitrov . Group control for consent rules with consecutive qualifications. Mathematical Social Sciences, 2023, 121: 1–7
18
F, Brandt M, Brill E, Hemaspaandra L A Hemaspaandra . Bypassing combinatorial protections: polynomial-time algorithms for single-peaked electorates. Journal of Artificial Intelligence Research, 2015, 53: 439–496
19
P, Faliszewski E, Hemaspaandra L A, Hemaspaandra J Rothe . 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
E, Elkind M Lackner . 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
Y Yang . On the tree representations of dichotomous preferences. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence. 2019, 644−650
24
N, Betzler A, Slinko J Uhlmann . On the computation of fully proportional representation. Journal of Artificial Intelligence Research, 2013, 47: 475–519
25
P, Skowron L, Yu P, Faliszewski E Elkind . 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
E, Hemaspaandra L A, Hemaspaandra J Rothe . 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
A V Karpov . Structured preferences: A literature survey. Automation and Remote Control, 2022, 83( 9): 1329–1354
29
E, Elkind M, Lackner D Peters . Preference restrictions in computational social choice: A survey. 2022, arXiv preprint arXiv: 2205.09092
30
M Dom . Algorithmic aspects of the consecutive-ones property. Bulletin of the European Association for Theoretical Computer Science, 2009, 98: 27–59
31
D, Peters M Lackner . Preferences single-peaked on a circle. Journal of Artificial Intelligence Research, 2020, 68: 463–502
32
K S, Booth G S Lueker . 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
W L Hsu . A simple test for the consecutive ones property. Journal of Algorithms, 2002, 43( 1): 1–16
34
M, Cygan F V, Fomin Ł, Kowalik D, Lokshtanov D, Marx M, Pilipczuk M, Pilipczuk S Saurabh . 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
R G, Downey M R Fellows . Fundamentals of Parameterized Complexity. London: Springer, 2013
36
J, Bang-Jensen G Gutin . Digraphs—Theory, Algorithms and Applications. 2nd ed. London: Springer, 2009
37
West D B. Introduction to Graph Theory. 2nd ed. Prentice Hall, 2001
38
S E, Dreyfus R A Wagner . The Steiner problem in graphs. Networks, 1971, 1( 3): 195–207
39
J, Guo R, Niedermeier O Suchý . Parameterized complexity of arc-weighted directed Steiner problems. SIAM Journal on Discrete Mathematics, 2011, 25( 2): 583–599
40
B, Ding J X, Yu S, Wang L, Qin X, Zhang X Lin . Finding top-k min-cost connected trees in databases. In: Proceedings of the 23rd International Conference on Data Engineering. 2007, 836−845
41
A, Björklund T, Husfeldt P, Kaski M Koivisto . Fourier meets Möbius: Fast subset convolution. In: Proceedings of the 39th ACM Symposium on Theory of Computing. 2007, 67−74
42
B, Fuchs W, Kern D, Molle S, Richter P, Rossmanith X Wang . Dynamic programming for minimum Steiner trees. Theory of Computing Systems, 2007, 41( 3): 493–500
43
M, Dom D, Lokshtanov S Saurabh . Kernelization lower bounds through colors and IDs. ACM Transactions on Algorithms, 2014, 11( 2): 13
44
J, Chen X, Huang I A, Kanj G Xia . Strong computational lower bounds via parameterized complexity. Journal of Computer and System Sciences, 2006, 72( 8): 1346–1367
