{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T06:56:26Z","timestamp":1775717786651,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T00:00:00Z","timestamp":1775692800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T00:00:00Z","timestamp":1775692800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005690","name":"Universit\u00e4t des Saarlandes","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005690","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    This paper studies the complexity of two microbribery problems under the model of group identification. In these problems, we are given a subset of distinguished individuals, and the questions are whether these individuals can be made socially qualified or whether they can be made exactly the socially qualified individuals, respectively, by modifying a limited number of entries in the qualifications-profile. For consent rules, the consensus-start-respecting rule, and the liberal-start-respecting rule, we obtain many NP-hardness results and polynomial-time solvability results. We also study the problems in\n                    <jats:italic>r<\/jats:italic>\n                    -profiles where each individual qualifies exactly\u00a0\n                    <jats:italic>r<\/jats:italic>\n                    individuals.\n                  <\/jats:p>","DOI":"10.1007\/s00224-026-10273-y","type":"journal-article","created":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T06:09:32Z","timestamp":1775714972000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Microbribery in Group Identification"],"prefix":"10.1007","volume":"70","author":[{"given":"G\u00e1bor","family":"Erd\u00e9lyi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongjie","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,9]]},"reference":[{"key":"10273_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Fischer, F.A., Procaccia, A.D., Tennenholtz, M.: Sum of us: Strategyproof selection from the selectors. In: TARK, pp. 101\u2013110 (2011)","DOI":"10.1145\/2000378.2000390"},{"key":"10273_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511804090"},{"key":"10273_CR3","doi-asserted-by":"crossref","unstructured":"Aziz, H., Lev, O., Mattei, N., Rosenschein, J.S., Walsh, T.: Strategyproof peer selection: Mechanisms, analyses, and experiments. In: AAAI, pp. 397\u2013403 (2016)","DOI":"10.1609\/aaai.v30i1.10038"},{"key":"10273_CR4","volume-title":"Digraphs: Theory","author":"J Bang-Jensen","year":"2008","unstructured":"Bang-Jensen, J., Gutin, G.: Digraphs: Theory. Algorithms and Applications. Springer, London (2008)"},{"key":"10273_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.disopt.2013.10.003","volume":"11","author":"D Binkele-Raible","year":"2014","unstructured":"Binkele-Raible, D., Erd\u00e9lyi, G., Fernau, H., Goldsmith, J., Mattei, N., Rothe, J.: The complexity of probabilistic lobbying. Discret. Optim. 11, 1\u201321 (2014)","journal-title":"Discret. Optim."},{"key":"10273_CR6","unstructured":"Bla\u017eej, V.: Complexity of games on graphs. Ph.D. thesis, Czech Technical University (2022)"},{"key":"10273_CR7","doi-asserted-by":"crossref","unstructured":"Boehmer, N., Bredereck, R., Knop, D., Luo, J.: Fine-grained view on bribery for group identification. Auton. Agents Multi Agent Syst. 37(1), Nr.\u00a021 (2023)","DOI":"10.1007\/s10458-023-09597-7"},{"key":"10273_CR8","doi-asserted-by":"crossref","unstructured":"Brandt, F., Conitzer, V., Endriss, U., Lang, J., Procaccia, A. (eds.): Handbook of Computational Social Choice. Cambridge University Press (2016)","DOI":"10.1017\/CBO9781107446984.002"},{"key":"10273_CR9","doi-asserted-by":"crossref","unstructured":"Bredereck, R., Faliszewski, P., Niedermeier, R., Talmon, N.: Complexity of shift bribery in committee elections. In: AAAI, pp. 2452\u20132458 (2016)","DOI":"10.1609\/aaai.v30i1.10132"},{"key":"10273_CR10","doi-asserted-by":"crossref","unstructured":"Bredereck, R., Kaczmarczyk, A., Niedermeier, R.: On coalitional manipulation for multiwinner elections: Shortlisting. In: IJCAI, pp. 887\u2013893 (2017)","DOI":"10.24963\/ijcai.2017\/123"},{"key":"10273_CR11","doi-asserted-by":"crossref","unstructured":"Chen, J., Kaczmarek, J., N\u00fcsken, P., Rothe, J., Schlotter, I., Seeger, T.: Control in Computational Social Choice. IJCAI 10391\u201310399 (2025)","DOI":"10.24963\/ijcai.2025\/1154"},{"key":"10273_CR12","doi-asserted-by":"crossref","unstructured":"Dimitrov, D.: The social choice approach to group identification. In: Consensual Processes, pp. 123\u2013134. Springer (2011)","DOI":"10.1007\/978-3-642-20533-0_7"},{"issue":"2","key":"10273_CR13","first-page":"137","volume":"54","author":"D Dimitrov","year":"2007","unstructured":"Dimitrov, D., Sung, S.C., Xu, Y.: Procedural group identification. Math. Social Sci. 54(2), 137\u2013146 (2007)","journal-title":"Procedural group identification. Math. Social Sci."},{"key":"10273_CR14","unstructured":"Erd\u00e9lyi, G., Reger, C., Yang, Y.: Structure in dichotomous preferences. In: IJCAI, pp. 2019\u20132025 (2015)"},{"key":"10273_CR15","doi-asserted-by":"crossref","unstructured":"Erd\u00e9lyi, G., Reger, C., Yang, Y.: Complexity of group identification with partial information. In: ADT, pp. 182\u2013196 (2017)","DOI":"10.1007\/978-3-319-67504-6_13"},{"key":"10273_CR16","doi-asserted-by":"crossref","unstructured":"Erd\u00e9lyi, G., Reger, C., Yang, Y.: The complexity of bribery and control in group identification. Auton. Agent Multi-Ag. 34(1), Nr.\u00a08 (2020)","DOI":"10.1007\/s10458-019-09427-9"},{"key":"10273_CR17","doi-asserted-by":"crossref","unstructured":"Erd\u00e9lyi, G., Yang, Y.: Microbribery in group identification. In: AAMAS, pp. 1840\u20131842 (2020)","DOI":"10.65109\/JIXJ3071"},{"key":"10273_CR18","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1613\/jair.2697","volume":"35","author":"P Faliszewski","year":"2009","unstructured":"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\u2013341 (2009)","journal-title":"J. Artif. Intell. Res."},{"key":"10273_CR19","doi-asserted-by":"crossref","unstructured":"Faliszewski, P., Skowron, P., Talmon, N.: Bribery as a measure of candidate success: Complexity results for approval-based multiwinner rules. In: AAMAS, pp. 6\u201314 (2017)","DOI":"10.65109\/GVQO7469"},{"key":"10273_CR20","doi-asserted-by":"crossref","unstructured":"Faliszewski, P., Slinko, A., Talmon, N.: Multiwinner rules with variable number of winners. In: ECAI, pp. 67\u201374 (2020)","DOI":"10.3233\/FAIA200077"},{"key":"10273_CR21","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"MR Garey","year":"1980","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco (1980)"},{"key":"10273_CR22","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"10273_CR23","unstructured":"Junker, E.: Broadening the complexity-theoretic analysis of manipulative attacks in group identification. Master\u2019s thesis, Humboldt-Universit\u00e4t zu Berlin (2022)"},{"key":"10273_CR24","unstructured":"Junker, E.: Manipulative attacks and group identification (2022). https:\/\/arxiv.org\/pdf\/2203.16151.pdf"},{"key":"10273_CR25","first-page":"56","volume-title":"Jewish Identity","author":"A Kasher","year":"1993","unstructured":"Kasher, A.: Jewish collective identity. In: Goldberg, D.T., Krausz, M. (eds.) Jewish Identity, pp. 56\u201378. Temple University Press, U.S. (1993)"},{"key":"10273_CR26","unstructured":"Kasher, A., Rubinstein, A.: On the question \u201cWho is a J?\u201d: A social choice approach. Log. Anal. 40(160), 385\u2013395 (1997)"},{"issue":"1","key":"10273_CR27","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1016\/j.geb.2007.08.006","volume":"63","author":"AD Miller","year":"2008","unstructured":"Miller, A.D.: Group identification. Game. Econ. Behav. 63(1), 188\u2013202 (2008)","journal-title":"Group identification. Game. Econ. Behav."},{"key":"10273_CR28","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-60099-9","volume-title":"Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division","author":"J Rothe","year":"2024","unstructured":"Rothe, J.: Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division. Springer, Cham, Switzerland (2024)"},{"issue":"2","key":"10273_CR29","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/S0022-0531(03)00080-2","volume":"110","author":"D Samet","year":"2003","unstructured":"Samet, D., Schmeidler, D.: Between liberalism and democracy. J. Econ. Theory 110(2), 213\u2013233 (2003)","journal-title":"J. Econ. Theory"},{"issue":"2","key":"10273_CR30","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10273_CR31","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1287\/inte.32.3.30.39","volume":"32","author":"CA Tovey","year":"2002","unstructured":"Tovey, C.A.: Tutorial on computational complexity. Interfaces 32(3), 30\u201361 (2002)","journal-title":"Interfaces"},{"key":"10273_CR32","unstructured":"West, D.B.: Introduction to Graph Theory. Prentice-Hall (2000)"},{"key":"10273_CR33","doi-asserted-by":"crossref","unstructured":"Yang, Y.: Complexity of manipulating and controlling approval-based multiwinner voting. In: IJCAI, pp. 637\u2013643 (2019)","DOI":"10.24963\/ijcai.2019\/90"},{"key":"10273_CR34","doi-asserted-by":"crossref","unstructured":"Yang, Y.: On the tree representations of dichotomous preferences. In: IJCAI, pp. 644\u2013650 (2019)","DOI":"10.24963\/ijcai.2019\/91"},{"key":"10273_CR35","doi-asserted-by":"crossref","unstructured":"Yang, Y.: On the complexity of destructive bribery in approval-based multi-winner voting. In: AAMAS, pp. 1584\u20131592 (2020)","DOI":"10.65109\/QHPC9003"},{"issue":"5","key":"10273_CR36","doi-asserted-by":"publisher","first-page":"672","DOI":"10.1007\/s10458-018-9392-1","volume":"32","author":"Y Yang","year":"2018","unstructured":"Yang, Y., Dimitrov, D.: How hard is it to control a group? Auton. Agent Multi-Ag. 32(5), 672\u2013692 (2018)","journal-title":"Auton. Agent Multi-Ag."},{"key":"10273_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.mathsocsci.2022.11.003","volume":"121","author":"Y Yang","year":"2023","unstructured":"Yang, Y., Dimitrov, D.: Group control for consent rules with consecutive qualifications. Math. Soc. Sci. 121, 1\u20137 (2023)","journal-title":"Math. Soc. Sci."},{"key":"10273_CR38","doi-asserted-by":"crossref","unstructured":"Yang, Y., Dimitrov, D.: Group control for procedural rules: parameterized complexity and consecutive domains. Frontiers Comput. Sci. 18(3), Nr.\u00a0183402 (2024)","DOI":"10.1007\/s11704-023-2700-1"},{"key":"10273_CR39","doi-asserted-by":"crossref","unstructured":"Yang, Y., Wang, J.: Multiwinner voting with restricted admissible sets: Complexity and strategyproofness. In: IJCAI, pp. 576\u2013582 (2018)","DOI":"10.24963\/ijcai.2018\/80"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10273-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-026-10273-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-026-10273-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T06:09:39Z","timestamp":1775714979000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-026-10273-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,9]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10273"],"URL":"https:\/\/doi.org\/10.1007\/s00224-026-10273-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,9]]},"assertion":[{"value":"4 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}},{"value":"not applicable","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}}],"article-number":"26"}}