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

Yongjie Yang received his PhD degree in computer science from Saarland University, Germany in 2015. He is currently a Postdoc in the Chair of Economic Theory, Saarland University, Germany. His research interests mainly include algorithmic game theory, algorithmic graph theory, and computational social choice

Dinko Dimitrov is Full Professor of Economic Theory at Saarland University, Germany since October 2009. His research centers around topics in microeconomic theory, especially coalition formation, cooperative games and social choice. He is an Associate Editor of Mathematical Social Sciences and SN Business & Economics, a Series Editor of Springer Lecture Notes in Economics and Mathematical Systems, and has published in leading economic journals such as Games and Economic Behavior, Economic Theory, Social Choice and Welfare, Economics Letters, Mathematical Social Sciences, Journal of Mathematical Economics, Theory and Decision

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

Funding note

Open Access funding enabled and organized by Projekt DEAL.

Open Access

This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made.

The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

RIGHTS & PERMISSIONS

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