{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T15:51:55Z","timestamp":1765295515389,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T00:00:00Z","timestamp":1727740800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NRW project \"Online Participation\""},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["RO~1202\/21-1  and -2"],"award-info":[{"award-number":["RO~1202\/21-1  and -2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003484","name":"Heinrich-Heine-Universit\u00e4t D\u00fcsseldorf","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003484","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":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider average- and min-based altruistic hedonic games and study the problem of verifying popular and strictly popular coalition structures. While strict popularity verification has been shown to be coNP-complete in min-based altruistic hedonic games, this problem has been open for equal- and altruistic-treatment average-based altruistic hedonic games. We solve these two open cases of strict popularity verification and then provide the first complexity results for popularity verification in (average- and min-based) altruistic hedonic games, where we cover all three degrees of altruism.<\/jats:p>","DOI":"10.1007\/s10458-024-09679-0","type":"journal-article","created":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T06:01:43Z","timestamp":1727762503000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The complexity of verifying popularity and strict popularity in altruistic hedonic games"],"prefix":"10.1007","volume":"38","author":[{"given":"Anna Maria","family":"Kerkmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00f6rg","family":"Rothe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,10,1]]},"reference":[{"key":"9679_CR1","unstructured":"Kerkmann, A., & Rothe, J. (2022). Popularity and strict popularity in altruistic hedonic games and minimum-based altruistic hedonic games (extended abstract). In Proceedings of the 21th international conference on autonomous agents and multiagent systems, pp 1657\u20131659. IFAAMAS, Auckland, New Zealand, virtual conference"},{"key":"9679_CR2","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/j.artint.2015.08.004","volume":"229","author":"T Rahwan","year":"2015","unstructured":"Rahwan, T., Michalak, T., Wooldridge, M., & Jennings, N. (2015). Coalition structure generation: A survey. Artificial Intelligence, 229, 139\u2013174.","journal-title":"Artificial Intelligence"},{"key":"9679_CR3","unstructured":"Marcolino, S., Jiang, A., & Tambe, M. (2013). Multi-agent team formation: Diversity beats strength? In: Proceedings of the 23rd international joint conference on artificial intelligence, pp 279\u2013285. AAAI Press\/IJCAI, Beijing, China"},{"key":"9679_CR4","doi-asserted-by":"crossref","unstructured":"Mirsky, R., Carlucho, I., Rahman, A., Fosong, E., Macke, W., Sridharan, M., Stone, P., & Albrecht, S. (2022). A survey of ad hoc teamwork research. In: Baumeister, D., Rothe, J. (eds.) Proceedings of the 19th European conference of multi-agent systems, pp 275\u2013293. Springer, D\u00fcsseldorf, Germany","DOI":"10.1007\/978-3-031-20614-6_16"},{"issue":"4","key":"9679_CR5","doi-asserted-by":"publisher","first-page":"987","DOI":"10.2307\/1912943","volume":"48","author":"J Dr\u00e8ze","year":"1980","unstructured":"Dr\u00e8ze, J., & Greenberg, J. (1980). Hedonic coalitions: Optimality and stability. Econometrica, 48(4), 987\u20131003.","journal-title":"Econometrica"},{"issue":"2","key":"9679_CR6","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1006\/game.2001.0877","volume":"38","author":"A Bogomolnaia","year":"2002","unstructured":"Bogomolnaia, A., & Jackson, M. (2002). The stability of hedonic coalition structures. Games and Economic Behavior, 38(2), 201\u2013230.","journal-title":"Games and Economic Behavior"},{"issue":"1","key":"9679_CR7","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s003550000067","volume":"18","author":"S Banerjee","year":"2001","unstructured":"Banerjee, S., Konishi, H., & S\u00f6nmez, T. (2001). Core in a simple coalition formation game. Social Choice and Welfare, 18(1), 135\u2013153.","journal-title":"Social Choice and Welfare"},{"issue":"2","key":"9679_CR8","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/3327970","volume":"7","author":"H Aziz","year":"2019","unstructured":"Aziz, H., Brandl, F., Brandt, F., Harrenstein, P., Olsen, M., & Peters, D. (2019). Fractional hedonic games. ACM Transactions on Economics and Computation, 7(2), 6.","journal-title":"ACM Transactions on Economics and Computation"},{"issue":"2","key":"9679_CR9","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/s00355-006-0104-4","volume":"26","author":"D Dimitrov","year":"2006","unstructured":"Dimitrov, D., Borm, P., Hendrickx, R., & Sung, S. (2006). Simple priorities and core stability in hedonic games. Social Choice and Welfare, 26(2), 421\u2013433.","journal-title":"Social Choice and Welfare"},{"key":"9679_CR10","doi-asserted-by":"crossref","unstructured":"Rothe, J. (2021). Thou shalt love thy neighbor as thyself when thou playest: Altruism in game theory. In Proceedings of the 35th AAAI conference on artificial intelligence, 15070\u201315077. AAAI Press, virtual conference","DOI":"10.1609\/aaai.v35i17.17770"},{"key":"9679_CR11","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1613\/jair.1.13706","volume":"75","author":"A Kerkmann","year":"2022","unstructured":"Kerkmann, A., Nguyen, N., Rey, A., Rey, L., Rothe, J., Schend, L., & Wiechers, A. (2022). Altruistic hedonic games. Journal of Artificial Intelligence Research, 75, 129\u2013169.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9679_CR12","volume-title":"Survival of the Friendliest: Understanding Our Origins and Rediscovering Our Common Humanity","author":"B Hare","year":"2020","unstructured":"Hare, B., & Woods, V. (2020). Survival of the Friendliest: Understanding Our Origins and Rediscovering Our Common Humanity. New York: Penguin Random House."},{"key":"9679_CR13","unstructured":"Nguyen, N., Rey, A., Rey, L., Rothe, J., & Schend, L. (2016). Altruistic hedonic games. In Proceedings of the 15th international conference on autonomous agents and multiagent systems, pp 251\u2013259. IFAAMAS, Singapore"},{"key":"9679_CR14","unstructured":"Wiechers, A., & Rothe, J. (2020). Stability in minimization-based altruistic hedonic games. In Proceedings of the 9th European starting AI researchers\u2019 symposium, vol. 2655. CEUR-WS.org, Santiago de Compostela, Spain"},{"key":"9679_CR15","doi-asserted-by":"crossref","unstructured":"Gaston, M., & Desjardins, M. (2005). Agent-organized networks for dynamic team formation. In Proceedings of the 4th international joint conference on autonomous agents and multiagent systems, pp 230\u2013237. IFAAMAS, Utrecht, The Netherlands","DOI":"10.1145\/1082473.1082508"},{"key":"9679_CR16","doi-asserted-by":"publisher","first-page":"1121","DOI":"10.1016\/j.infsof.2006.11.006","volume":"49","author":"X Guo","year":"2007","unstructured":"Guo, X., & Lim, J. (2007). Negotiation support systems and team negotiations: The coalition formation perspective. Information and Software Technology, 49, 1121\u20131127.","journal-title":"Information and Software Technology"},{"key":"9679_CR17","unstructured":"Barrett, S., Stone, P., & Kraus, S. (2011). Empirical evaluation of ad hoc teamwork in the pursuit domain. In: Proceedings of the 10th international conference on autonomous agents and multiagent systems, pp 567\u2013574. IFAAMAS, Taipei, Taiwan"},{"key":"9679_CR18","unstructured":"Leibo, J., Zambald, V., Lanctot, M., Marecki, J., & Graepel, T. (2017). Multi-agent reinforcement learning in sequential social dilemmas. In: Proceedings of the 16th international conference on autonomous agents and multiagent systems, pp 464\u2013473. IFAAMAS, Sao Paulo, Brazil"},{"key":"9679_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103356","volume":"288","author":"Y Bachrach","year":"2020","unstructured":"Bachrach, Y., Everett, R., Hughes, E., Lazaridou, A., Leibo, J., Lanctot, M., Johanson, M., Czarnecki, W., & Graepel, T. (2020). Negotiating team formation using deep reinforcement learning. Artificial Intelligence, 288, 103356.","journal-title":"Artificial Intelligence"},{"key":"9679_CR20","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1017\/CBO9781107446984.016","volume-title":"Handbook of Computational Social Choice","author":"H Aziz","year":"2016","unstructured":"Aziz, H., & Savani, R. (2016). Hedonic games. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. Procaccia (Eds.), Handbook of Computational Social Choice (pp. 356\u2013376). Cambridge, UK: Cambridge University Press."},{"key":"9679_CR21","doi-asserted-by":"crossref","unstructured":"Bullinger, M., Elkind, E., & Rothe, J. (2024). Cooperative game theory. In: Rothe, J. (ed.) Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, 2nd edn. Classroom Companion: Economics, pp 139\u2013229. Springer, Berlin and Heidelberg, Germany, Chap. 3","DOI":"10.1007\/978-3-031-60099-9_3"},{"key":"9679_CR22","doi-asserted-by":"crossref","unstructured":"Woeginger, G. (2013). Core stability in hedonic coalition formation. In Proceedings of the 39th international conference on current trends in theory and practice of computer science, pp 33\u201350. Springer, Berlin and Heidelberg, Germany","DOI":"10.1007\/978-3-642-35843-2_4"},{"key":"9679_CR23","unstructured":"Schlueter, J., & Goldsmith, J. (2020). Super altruistic hedonic games. In Proceedings of the 33rd international Florida artificial intelligence research society conference, pp 160\u2013165. AAAI Press, North Miami Beach, Florida, USA"},{"key":"9679_CR24","unstructured":"Br\u00e2nzei, S., & Larson, K. (2011). Social distance games. In Proceedings of the 22nd international joint conference on artificial intelligence, pp 91\u201396. AAAI Press\/IJCAI, Barcelona, Spain"},{"key":"9679_CR25","doi-asserted-by":"crossref","unstructured":"Bullinger, M., & Kober, S. (2021). Loyalty in cardinal hedonic games. In Proceedings of the 30th international joint conference on artificial intelligence, pp 66\u201372. ijcai.org, Montr\u00e9al, Canada, virtual conference","DOI":"10.24963\/ijcai.2021\/10"},{"key":"9679_CR26","doi-asserted-by":"crossref","unstructured":"Kerkmann, A., & Rothe, J. (2020). Altruism in coalition formation games. In Proceedings of the 29th international joint conference on artificial intelligence, pp 347\u2013353. ijcai.org, Yokohama, Japan, virtual conference","DOI":"10.24963\/ijcai.2020\/49"},{"issue":"3","key":"9679_CR27","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/s10472-023-09881-y","volume":"92","author":"A Kerkmann","year":"2024","unstructured":"Kerkmann, A., Cramer, S., & Rothe, J. (2024). Altruism in coalition formation games. Annals of Mathematics and Artificial Intelligence, 92(3), 601\u2013629.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"9679_CR28","doi-asserted-by":"crossref","unstructured":"Hoffjan, M., Kerkmann, A., & Rothe, J. (2024). Core stability in altruistic coalition formation games. In Proceedings of the 16th latin American theoretical informatics symposium, pp 320\u2013333. Springer, Berlin and Heidelberg, Germany","DOI":"10.1007\/978-3-031-55601-2_21"},{"issue":"3","key":"9679_CR29","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/bs.3830200304","volume":"20","author":"P G\u00e4rdenfors","year":"1975","unstructured":"G\u00e4rdenfors, P. (1975). Match making: Assignments based on bilateral preferences. Behavioral Science, 20(3), 166\u2013173.","journal-title":"Behavioral Science"},{"key":"9679_CR30","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1016\/j.artint.2012.09.006","volume":"195","author":"H Aziz","year":"2013","unstructured":"Aziz, H., Brandt, F., & Seedig, H. (2013). Computing desirable partitions in additively separable hedonic games. Artificial Intelligence, 195, 316\u2013334.","journal-title":"Artificial Intelligence"},{"key":"9679_CR31","unstructured":"Brandt, F., & Bullinger, M. (2020). Finding and recognizing popular coalition structures. In Proceedings of the 19th International conference on autonomous agents and multiagent systems, pp 195\u2013203. IFAAMAS, Auckland, New Zealand, virtual conference ."},{"key":"9679_CR32","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1613\/jair.1.11531","volume":"67","author":"A Kerkmann","year":"2020","unstructured":"Kerkmann, A., Lang, J., Rey, A., Rothe, J., Schadrack, H., & Schend, L. (2020). Hedonic games with ordinal preferences and thresholds. Journal of Artificial Intelligence Research, 67, 705\u2013756.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9679_CR33","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M Garey","year":"1976","unstructured":"Garey, M., Johnson, D., & Stockmeyer, L. (1976). Some simplified NP-complete graph problems. Theoretical Computer Science, 1, 237\u2013267.","journal-title":"Theoretical Computer Science"},{"key":"9679_CR34","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T Gonzalez","year":"1985","unstructured":"Gonzalez, T. (1985). Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38, 293\u2013306.","journal-title":"Theoretical Computer Science"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-024-09679-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-024-09679-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-024-09679-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,13]],"date-time":"2024-11-13T15:24:49Z","timestamp":1731511489000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-024-09679-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,1]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["9679"],"URL":"https:\/\/doi.org\/10.1007\/s10458-024-09679-0","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"type":"print","value":"1387-2532"},{"type":"electronic","value":"1573-7454"}],"subject":[],"published":{"date-parts":[[2024,10,1]]},"assertion":[{"value":"11 September 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 October 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"While conducting this work, the second author has been on the following editorial boards of scientific journals: <i>Annals of Mathematics and Artificial Intelligence<\/i> (AMAI), Associate Editor, since 01\/2020, <i>Journal of Artificial Intelligence Research<\/i> (JAIR), Associate Editor, 09\/2017\u201308\/2023, and <i>Journal of Universal Computer Science<\/i> (J.UCS), Editorial Board, since 01\/2005.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"47"}}