{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T16:41:00Z","timestamp":1775752860659,"version":"3.50.1"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,3,24]],"date-time":"2023-03-24T00:00:00Z","timestamp":1679616000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,3,24]],"date-time":"2023-03-24T00:00:00Z","timestamp":1679616000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/19"],"award-info":[{"award-number":["NI 369\/19"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/19"],"award-info":[{"award-number":["NI 369\/19"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["BR 5207\/1"],"award-info":[{"award-number":["BR 5207\/1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 369\/15"],"award-info":[{"award-number":["NI 369\/15"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"OP VVV MEYS","award":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"],"award-info":[{"award-number":["CZ.02.1.01\/0.0\/0.0\/16_019\/0000765"]}]},{"DOI":"10.13039\/501100018933","name":"Technische Universit\u00e4t Clausthal","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100018933","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a set of agents qualifying or disqualifying each other, group identification is the task of identifying a <jats:italic>socially qualified<\/jats:italic> subgroup of agents. Social qualification depends on the specific rule used to aggregate individual qualifications . The classical bribery problem in this context asks how many agents need to change their qualifications in order to change the outcome in a certain way. Complementing previous results showing polynomial-time solvability or NP-hardness of bribery for various social rules in the constructive (aiming at making specific agents socially qualified) or destructive (aiming at making specific agents socially disqualified) setting, we provide a comprehensive picture of the parameterized computational complexity landscape. Conceptually, we also consider a more fine-grained concept of bribery cost, where we ask how many single qualifications need to be changed, nonunit prices for different bribery actions, and a more general bribery goal that combines the constructive and destructive setting.<\/jats:p>","DOI":"10.1007\/s10458-023-09597-7","type":"journal-article","created":{"date-parts":[[2023,3,24]],"date-time":"2023-03-24T20:03:01Z","timestamp":1679688181000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fine-grained view on bribery for group identification"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5102-449X","authenticated-orcid":false,"given":"Niclas","family":"Boehmer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6303-6276","authenticated-orcid":false,"given":"Robert","family":"Bredereck","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2588-5709","authenticated-orcid":false,"given":"Du\u0161an","family":"Knop","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8892-8863","authenticated-orcid":false,"given":"Junjie","family":"Luo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,3,24]]},"reference":[{"key":"9597_CR1","doi-asserted-by":"crossref","unstructured":"Baumeister, D., Erd\u00e9lyi, G., & Rothe, J. (2011). How hard is it to bribe the judges? A study of the complexity of bribery in judgment aggregation. In Proceedings of the 2nd iternational conference on algorithmic decision theory (ADT \u201911) (pp.  1\u201315).","DOI":"10.1007\/978-3-642-24873-3_1"},{"key":"9597_CR2","doi-asserted-by":"crossref","unstructured":"Boehmer, N., Bredereck, R., Knop, D., & Luo, J. (2020). Fine-grained view on bribery for group identification. In Proceedings of the 29th international joint conference on artificial intelligence (IJCAI \u201920) (pp.  67\u201373).","DOI":"10.24963\/ijcai.2020\/10"},{"key":"9597_CR3","doi-asserted-by":"crossref","unstructured":"Boehmer, N., Bredereck, R., Faliszewski, P., & Niedermeier, R. (2021a). Winner robustness via swap- and shift-bribery: Parameterized counting complexity and experiments. In Proceedings of the 30th Iiternational joint conference on artificial intelligence (IJCAI \u201921) (pp.  52\u201358).","DOI":"10.24963\/ijcai.2021\/8"},{"key":"9597_CR4","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1613\/jair.1.12755","volume":"71","author":"N Boehmer","year":"2021","unstructured":"Boehmer, N., Bredereck, R., Heeger, K., & Niedermeier, R. (2021). Bribery and control in stable marriage. Journal of Artificial Intelligence Research, 71, 993\u20131048.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9597_CR5","unstructured":"Boehmer, N., Bredereck, R., Knop, D., & Luo, J. (2021c). Finding small multi-demand set covers with ubiquitous elements and large sets is fixed-parameter tractable. CoRR arXiv:2104.0124"},{"key":"9597_CR6","doi-asserted-by":"crossref","unstructured":"Bredereck, R., Faliszewski, P., Niedermeier, R., & Talmon, N. (2016). Complexity of shift bribery in committee elections. In Proceedings of the 30th AAAI conference on artificial intelligence (AAAI \u201916), (pp. 2452\u20132458).","DOI":"10.1609\/aaai.v30i1.10132"},{"key":"9597_CR7","unstructured":"Cary, D. (2011). Estimating the margin of victory for instant-runoff voting. In Proceedings of the 2011 electronic voting technology workshop on trustworthy elections (EVT\/WOTE \u201911)."},{"key":"9597_CR8","first-page":"1396","volume":"14","author":"YJ Chu","year":"1965","unstructured":"Chu, Y. J., & Liu, T. H. (1965). On the shortest arborescence of a directed graph. Scientia Sinica, 14, 1396\u20131400.","journal-title":"Scientia Sinica"},{"key":"9597_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F. V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2015). Parameterized Algorithms. Springer."},{"key":"9597_CR10","doi-asserted-by":"crossref","unstructured":"Dimitrov, D. (2011). The social choice approach to group identification. In Consensual processes (pp.  123\u2013134).","DOI":"10.1007\/978-3-642-20533-0_7"},{"issue":"2","key":"9597_CR11","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.mathsocsci.2007.06.001","volume":"54","author":"D Dimitrov","year":"2007","unstructured":"Dimitrov, D., Sung, S. C., & Xu, Y. (2007). Procedural group identification. Mathematical Social Sciences, 54(2), 137\u2013146.","journal-title":"Mathematical Social Sciences"},{"key":"9597_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R. G., & Fellows, M. R. (2013). Fundamentals of Parameterized Complexity. Springer."},{"issue":"2","key":"9597_CR13","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s00355-015-0914-3","volume":"46","author":"C Duddy","year":"2016","unstructured":"Duddy, C., Piggins, A., & Zwicker, W. S. (2016). Aggregation of binary evaluations: a Borda-like approach. Social Choice and Welfare, 46(2), 301\u2013333.","journal-title":"Social Choice and Welfare"},{"issue":"4","key":"9597_CR14","doi-asserted-by":"publisher","first-page":"233","DOI":"10.6028\/jres.071B.032","volume":"71","author":"J Edmonds","year":"1967","unstructured":"Edmonds, J. (1967). Optimum branchings. Journal of Research of the National Bureau of Standards B, 71(4), 233\u2013240.","journal-title":"Journal of Research of the National Bureau of Standards B"},{"key":"9597_CR15","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., & Weismantel, R. (2018). Proximity results and faster algorithms for integer programming using the Steinitz lemma. In Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms (SODA \u201918) (pp.  808\u2013816).","DOI":"10.1137\/1.9781611975031.52"},{"key":"9597_CR16","doi-asserted-by":"crossref","unstructured":"Erd\u00e9lyi, G., & Yang, Y. (2020). Microbribery in group identification. In Proceedings of the 19th international conference on autonomous agents and multiagent systems (AAMAS \u201920) (pp.  1840\u20131842).","DOI":"10.1007\/s10458-019-09427-9"},{"issue":"1","key":"9597_CR17","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1007\/s10458-019-09427-9","volume":"34","author":"G Erd\u00e9lyi","year":"2020","unstructured":"Erd\u00e9lyi, G., Reger, C., & Yang, Y. (2020). The complexity of bribery and control in group identification. Autonomous Agents and Multi-Agent Systems, 34(1), 8.","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"key":"9597_CR18","doi-asserted-by":"crossref","unstructured":"Faliszewski, P., & Rothe, J. (2016). Control and bribery in voting. In Handbook of computational social choice (pp.  146\u2013168).","DOI":"10.1017\/CBO9781107446984.008"},{"key":"9597_CR19","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1613\/jair.2676","volume":"35","author":"P Faliszewski","year":"2009","unstructured":"Faliszewski, P., Hemaspaandra, E., & Hemaspaandra, L. A. (2009). How hard is bribery in elections? Journal of Artificial Intelligence Research, 35, 485\u2013532.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9597_CR20","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. (2009). Llull and Copeland voting computationally resist bribery and constructive control. Journal of Artificial Intelligence Research, 35, 275\u2013341.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9597_CR21","unstructured":"Faliszewski, P., Skowron, P., Slinko, A., & Talmon, N. (2017a). Multiwinner voting: A new challenge for social choice theory. In  Trends in computational social choice (pp.  27\u201347)."},{"key":"9597_CR22","unstructured":"Faliszewski, P., Skowron, P., & Talmon, N. (2017b). Bribery as a measure of candidate success: Complexity results for approval-based multiwinner rules. In Proceedings of the 16th conference on autonomous agents and multiagent systems (AAMAS \u201917) (pp.  6\u201314)."},{"key":"9597_CR23","unstructured":"Faliszewski, P., Slinko, A., & Talmon, N. (2020). Multiwinner rules with variable number of winners. In  Proceedings of the 24th European conference on artificial intelligence (ECAI \u201920) (pp.  67\u201374)."},{"key":"9597_CR24","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., & Grohe, M. (2006). Parameterized Complexity Theory. Springer."},{"issue":"2","key":"9597_CR25","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"HN Gabow","year":"1986","unstructured":"Gabow, H. N., Galil, Z., Spencer, T. H., & Tarjan, R. E. (1986). Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, 6(2), 109\u2013122.","journal-title":"Combinatorica"},{"issue":"1","key":"9597_CR26","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.mathsocsci.2007.04.005","volume":"54","author":"N Houy","year":"2007","unstructured":"Houy, N. (2007). \u201ci want to be a J!\u2019\u2019: Liberalism in group identification problems. Mathematical Social Sciences, 54(1), 59\u201370.","journal-title":"Mathematical Social Sciences"},{"key":"9597_CR27","unstructured":"Kasher, A. (1993). Jewish collective identity. In Jewish Identity (pp.  56\u201378)."},{"issue":"160","key":"9597_CR28","first-page":"385","volume":"40","author":"A Kasher","year":"1997","unstructured":"Kasher, A., & Rubinstein, A. (1997). On the question \u201cwho is a j?\u2019\u2019 a social choice approach. Logique et Analyse, 40(160), 385\u2013395.","journal-title":"Logique et Analyse"},{"issue":"2","key":"9597_CR29","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s11238-016-9535-2","volume":"81","author":"DM Kilgour","year":"2016","unstructured":"Kilgour, D. M. (2016). Approval elections with a variable number of winners. Theory and Decision, 81(2), 199\u2013211.","journal-title":"Theory and Decision"},{"key":"9597_CR30","unstructured":"Lackner, M., & Maly, J. (2021). Approval-based shortlisting. In Proceedings of the 20th international conference on autonomous agents and multiagent systems (AAMAS \u201921) (pp. 737\u2013745)."},{"key":"9597_CR31","unstructured":"Magrino, T.R., Rivest, R.L., & Shen, E. (2011). Computing the margin of victory in IRV elections. In Proceedings of the 2011 electronic voting technology workshop \/ workshop on trustworthy elections (EVT\/WOTE \u201911)."},{"key":"9597_CR32","volume-title":"Invitation to Discrete Mathematics","author":"J Matou\u0161ek","year":"2009","unstructured":"Matou\u0161ek, J., & Ne\u0161et\u0159il, J. (2009). Invitation to Discrete Mathematics (2nd ed.). Oxford University Press.","edition":"2"},{"issue":"1","key":"9597_CR33","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. (2008). Group identification. Games and Economic Behavior, 63(1), 188\u2013202.","journal-title":"Games and Economic Behavior"},{"key":"9597_CR34","doi-asserted-by":"crossref","unstructured":"Nederlof J (2009) Fast polynomial-space algorithms using M\u00f6bius inversion: Improving on Steiner tree and related problems. In Proceedings of the 36th international colloquium on automata, languages and programming (ICALP\u00a0\u201909) (pp. 713\u2013725).","DOI":"10.1007\/978-3-642-02927-1_59"},{"key":"9597_CR35","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R. (2006). Invitation to Fixed-Parameter Algorithms. Oxford University Press."},{"key":"9597_CR36","doi-asserted-by":"crossref","unstructured":"Orlin, J.B. (2013). Max flows in O(nm) time, or better. In  Proceedings of the 45th annual ACM symposium on theory of computing (STOC \u201915) (pp. 765\u2013774).","DOI":"10.1145\/2488608.2488705"},{"issue":"2","key":"9597_CR37","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. (2003). Between liberalism and democracy. Journal of Economic Theory, 110(2), 213\u2013233.","journal-title":"Journal of Economic Theory"},{"key":"9597_CR38","doi-asserted-by":"crossref","unstructured":"Xia, L. (2012). Computing the margin of victory for various voting rules. In Proceedings of the 13th ACM conference on electronic commerce  (EC \u201912) (pp. 982\u2013999).","DOI":"10.1145\/2229012.2229086"},{"issue":"5","key":"9597_CR39","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. (2018). How hard is it to control a group? Autonomous Agents and Multi-Agent Systems, 32(5), 672\u2013692.","journal-title":"Autonomous Agents and Multi-Agent Systems"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-023-09597-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-023-09597-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-023-09597-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T07:43:30Z","timestamp":1683791010000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-023-09597-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,24]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["9597"],"URL":"https:\/\/doi.org\/10.1007\/s10458-023-09597-7","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,24]]},"assertion":[{"value":"4 January 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"21"}}