{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T11:32:23Z","timestamp":1768563143938,"version":"3.49.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","license":[{"start":{"date-parts":[[2023,3,31]],"date-time":"2023-03-31T00:00:00Z","timestamp":1680220800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","award":["BR 2312\/11-2 and BR 2312\/12-1"],"award-info":[{"award-number":["BR 2312\/11-2 and BR 2312\/12-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2023,3,31]]},"abstract":"<jats:p>The formal study of coalition formation in multi-agent systems is typically realized in the framework of hedonic games, which originate from economic theory. The main focus of this branch of research has been on the existence and the computational complexity of deciding the existence of coalition structures that satisfy various stability criteria. The actual process of forming coalitions based on individual behavior has received little attention. In this article, we study the convergence of simple dynamics leading to stable partitions in a variety of established classes of hedonic games, including anonymous, dichotomous, fractional, and hedonic diversity games. The dynamics we consider is based on individual stability: an agent will join another coalition if she is better off and no member of the welcoming coalition is worse off.<\/jats:p>\n          <jats:p>Our results are threefold. First, we identify conditions for the (fast) convergence of our dynamics. To this end, we develop new techniques based on the simultaneous usage of multiple intertwined potential functions and establish a reduction uncovering a close relationship between anonymous hedonic games and hedonic diversity games. Second, we provide elaborate counterexamples determining tight boundaries for the existence of individually stable partitions. Third, we study the computational complexity of problems related to the coalition formation dynamics. In particular, we settle open problems suggested by Bogomolnaia and Jackson, Brandl et\u00a0al., and Boehmer and Elkind.<\/jats:p>\n          <jats:p\/>","DOI":"10.1145\/3588753","type":"journal-article","created":{"date-parts":[[2023,3,23]],"date-time":"2023-03-23T12:21:59Z","timestamp":1679574119000},"page":"1-65","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Reaching Individually Stable Coalition Structures"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4179-9897","authenticated-orcid":false,"given":"Felix","family":"Brandt","sequence":"first","affiliation":[{"name":"Technical University of Munich"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4013-1323","authenticated-orcid":false,"given":"Martin","family":"Bullinger","sequence":"additional","affiliation":[{"name":"Technical University of Munich"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0317-6573","authenticated-orcid":false,"given":"Ana\u00eblle","family":"Wilczynski","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Saclay"}]}],"member":"320","published-online":{"date-parts":[[2023,6,24]]},"reference":[{"issue":"1","key":"e_1_3_4_2_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(94)00026-A","article-title":"Paths to marriage stability","author":"Abeledo H.","year":"1995","unstructured":"H. Abeledo and U. G. Rothblum. 1995. Paths to marriage stability. Discrete Applied Mathematics 63, 1 (1995), 1\u201312.","journal-title":"Discrete Applied Mathematics"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3327970"},{"key":"e_1_3_4_4_2","first-page":"166","volume-title":"Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201916)","author":"Aziz H.","unstructured":"H. Aziz, P. Harrenstein, J. Lang, and M. Wooldridge. 2016. Boolean hedonic games. In Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning (KR\u201916). 166\u2013175."},{"key":"e_1_3_4_5_2","volume-title":"Handbook of Computational Social Choice","author":"Aziz H.","unstructured":"H. Aziz and R. Savani. 2016. Hedonic games. In Handbook of Computational Social Choice, F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia (Eds.). Cambridge University Press, 356\u2013376."},{"issue":"1","key":"e_1_3_4_6_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.geb.2003.10.003","article-title":"NP-completeness in hedonic games","author":"Ballester C.","year":"2004","unstructured":"C. Ballester. 2004. NP-completeness in hedonic games. Games and Economic Behavior 49, 1 (2004), 1\u201330.","journal-title":"Games and Economic Behavior"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s003550000067"},{"key":"e_1_3_4_8_2","volume-title":"Approximation Hardness of Short Symmetric Instances of MAX-3SAT","author":"Berman P.","year":"2003","unstructured":"P. Berman, M. Karpinski, and A. Scott. 2003. Approximation Hardness of Short Symmetric Instances of MAX-3SAT. Technical Report TR03-049. Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"e_1_3_4_9_2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1613\/jair.1.11211","article-title":"Nash stable outcomes in fractional hedonic games: Existence, efficiency and computation","author":"Bil\u00f2 V.","year":"2018","unstructured":"V. Bil\u00f2, A. Fanelli, M. Flammini, G. Monaco, and L. Moscardelli. 2018. Nash stable outcomes in fractional hedonic games: Existence, efficiency and computation. Journal of Artificial Intelligence Research 62 (2018), 315\u2013371.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"1","key":"e_1_3_4_10_2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1086\/256633","article-title":"On the rationale of group decision-making","author":"Black D.","year":"1948","unstructured":"D. Black. 1948. On the rationale of group decision-making. Journal of Political Economy 56, 1 (1948), 23\u201334.","journal-title":"Journal of Political Economy"},{"key":"e_1_3_4_11_2","volume-title":"Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI\u201923)","author":"Boehmer N.","year":"2023","unstructured":"N. Boehmer, M. Bullinger, and A. M. Kerkmann. 2023. Causes of stability in dynamic coalition formation. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI\u201923). Forthcoming."},{"key":"e_1_3_4_12_2","first-page":"1822","volume-title":"Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI\u201920)","author":"Boehmer N.","year":"2020","unstructured":"N. Boehmer and E. Elkind. 2020. Individual-based stability in hedonic diversity games. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI\u201920). 1822\u20131829."},{"issue":"2","key":"e_1_3_4_13_2","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1006\/game.2001.0877","article-title":"The stability of hedonic coalition structures","author":"Bogomolnaia A.","year":"2002","unstructured":"A. Bogomolnaia and M. O. Jackson. 2002. The stability of hedonic coalition structures. Games and Economic Behavior 38, 2 (2002), 201\u2013230.","journal-title":"Games and Economic Behavior"},{"key":"e_1_3_4_14_2","first-page":"1219","volume-title":"Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201915)","author":"Brandl F.","year":"2015","unstructured":"F. Brandl, F. Brandt, and M. Strobel. 2015. Fractional hedonic games: Individual and group stability. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS\u201915). 1219\u20131227."},{"key":"e_1_3_4_15_2","first-page":"4867","volume-title":"Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI\u201922)","author":"Brandt F.","year":"2022","unstructured":"F. Brandt, M. Bullinger, and L. Tappe. 2022. Single-agent dynamics in additively separable hedonic games. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI\u201922). 4867\u20134874."},{"key":"e_1_3_4_16_2","first-page":"5211","volume-title":"Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI\u201921)","author":"Brandt F.","year":"2021","unstructured":"F. Brandt, M. Bullinger, and A. Wilczynski. 2021. Reaching individually stable coalition structures in hedonic games. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI\u201921). 5211\u20135218."},{"key":"e_1_3_4_17_2","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1007\/978-3-030-35389-6_8","volume-title":"Proceedings of the 15th International Conference on Web and Internet Economics (WINE\u201919)","author":"Brandt F.","year":"2019","unstructured":"F. Brandt and A. Wilczynski. 2019. On the convergence of swap dynamics to Pareto-optimal matchings. In Proceedings of the 15th International Conference on Web and Internet Economics (WINE\u201919). 100\u2013113."},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/3306127.3331741"},{"key":"e_1_3_4_19_2","volume-title":"Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI\u201923)","author":"Bullinger M.","year":"2023","unstructured":"M. Bullinger and W. Suksompong. 2023. Topological distance games. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI\u201923). Forthcoming."},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.5555\/3306127.3331742"},{"key":"e_1_3_4_21_2","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/978-3-030-17402-6_12","volume-title":"Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC\u201919)","author":"Caskurlu B.","year":"2019","unstructured":"B. Caskurlu and F. E. Kizilkaya. 2019. On hedonic games with common ranking property. In Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC\u201919). 137\u2013148."},{"key":"e_1_3_4_22_2","first-page":"487","article-title":"Stability in coalition formation games","author":"Cechl\u00e1rov\u00e1 K.","year":"2001","unstructured":"K. Cechl\u00e1rov\u00e1 and A. Romero-Medina. 2001. Stability in coalition formation games. International Journal of Game Theory 29 (2001), 487\u2013494.","journal-title":"International Journal of Game Theory"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.2307\/1912943"},{"key":"e_1_3_4_24_2","first-page":"182","volume-title":"Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI\u201921)","author":"Fanelli A.","year":"2021","unstructured":"A. Fanelli, G. Monaco, and L. Moscardelli. 2021. Relaxed core stability in fractional hedonic games. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI\u201921). 182\u2013188."},{"key":"e_1_3_4_25_2","doi-asserted-by":"crossref","first-page":"279","DOI":"10.2307\/1885113","article-title":"Partnerships","author":"Farrell J.","year":"1988","unstructured":"J. Farrell and S. Scotchmer. 1988. Partnerships. Quarterly Journal of Economics 103 (1988), 279\u2013297.","journal-title":"Quarterly Journal of Economics"},{"issue":"3","key":"e_1_3_4_26_2","doi-asserted-by":"crossref","first-page":"1101","DOI":"10.1287\/moor.2018.0960","article-title":"Computing stable outcomes in symmetric additively separable hedonic games","author":"Gairing M.","year":"2019","unstructured":"M. Gairing and R. Savani. 2019. Computing stable outcomes in symmetric additively separable hedonic games. Mathematics of Operations Research 44, 3 (2019), 1101\u20131121.","journal-title":"Mathematics of Operations Research"},{"key":"e_1_3_4_27_2","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/j.artint.2018.06.004","article-title":"Dynamics in matching and coalition formation games with structural constraints","author":"Hoefer M.","year":"2018","unstructured":"M. Hoefer, D. Vaz, and L. Wagner. 2018. Dynamics in matching and coalition formation games with structural constraints. Artificial Intelligence 262 (2018), 222\u2013247.","journal-title":"Artificial Intelligence"},{"key":"e_1_3_4_28_2","first-page":"85","volume-title":"Complexity of Computer Computations","author":"Karp R. M.","unstructured":"R. M. Karp. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (Eds.). Plenum Press, 85\u2013103."},{"key":"e_1_3_4_29_2","first-page":"579","volume-title":"Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI\u201916)","author":"Peters D.","unstructured":"D. Peters. 2016. Complexity of hedonic games with dichotomous preferences. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI\u201916). 579\u2013585."},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.2307\/2938326"},{"key":"e_1_3_4_31_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.mathsocsci.2015.07.004","article-title":"Individual and group stability in neutral restrictions of hedonic games","author":"Suksompong W.","year":"2015","unstructured":"W. Suksompong. 2015. Individual and group stability in neutral restrictions of hedonic games. Mathematical Social Sciences 78 (2015), 1\u20135.","journal-title":"Mathematical Social Sciences"},{"issue":"3","key":"e_1_3_4_32_2","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1016\/j.ejor.2009.09.004","article-title":"Computational complexity in additive hedonic games","author":"Sung S. C.","year":"2010","unstructured":"S. C. Sung and D. Dimitrov. 2010. Computational complexity in additive hedonic games. European Journal of Operational Research203, 3 (2010), 635\u2013639.","journal-title":"European Journal of Operational Research"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588753","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588753","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:36Z","timestamp":1750178856000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588753"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,31]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2023,3,31]]}},"alternative-id":["10.1145\/3588753"],"URL":"https:\/\/doi.org\/10.1145\/3588753","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,31]]},"assertion":[{"value":"2022-04-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-20","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}