{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T14:59:39Z","timestamp":1777733979057,"version":"3.51.4"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"AI Programme of The Alan Turing Institute and the Deutsche Forschungsgemeinschaft","award":["BR 2312\/11-2 and BR 2312\/12-1"],"award-info":[{"award-number":["BR 2312\/11-2 and BR 2312\/12-1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2026,1,31]]},"abstract":"<jats:p>\n            Coalition formation explores how to partition a set of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( n \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            agents into disjoint coalitions according to their preferences. We consider a cardinal utility model with an additively separable aggregation of preferences and study the online variant, where agents arrive in sequence. The goal is to achieve competitive social welfare. In the basic model, agents arrive in an arbitrary order and have to be assigned to coalitions immediately and irrevocably. There, the natural greedy algorithm is known to achieve an optimal competitive ratio, which heavily relies on the range of utilities.\n          <\/jats:p>\n          <jats:p>\n            We complement this result by considering two related models. First, we study a model where agents arrive in a random order. We find that the competitive ratio of the greedy algorithm is\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Theta\\left(\\frac{1}{n^{2}}\\right)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . In contrast, an alternative algorithm, which is based on alternating between waiting and greedy phases, can achieve a competitive ratio of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Theta\\left(\\frac{1}{n}\\right)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . Second, we relax the irrevocability of decisions by allowing the dissolution of coalitions into singleton coalitions. We achieve an asymptotically optimal competitive ratio of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Theta\\left(\\frac{1}{n}\\right)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            by drawing a close connection to a general model of online matching. Hence, in both models, we obtain a competitive ratio that removes the unavoidable utility dependencies in the basic model and essentially matches the best possible approximation ratio by polynomial-time algorithms.\n          <\/jats:p>","DOI":"10.1145\/3758324","type":"journal-article","created":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T15:16:47Z","timestamp":1754493407000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Online Coalition Formation under Random Arrival or Coalition Dissolution"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4013-1323","authenticated-orcid":false,"given":"Martin","family":"Bullinger","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, United Kingdom"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6447-7794","authenticated-orcid":false,"given":"Ren\u00e9","family":"Romen","sequence":"additional","affiliation":[{"name":"School of Computation, Information and Technology, Technical University of Munich, Munich, Germany"}]}],"member":"320","published-online":{"date-parts":[[2025,10,7]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3327970"},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1016\/j.artint.2012.09.006","article-title":"Computing desirable partitions in additively separable hedonic games","volume":"195","author":"Aziz Haris","year":"2013","unstructured":"Haris Aziz, Felix Brandt, and Hans Georg Seedig. 2013. Computing desirable partitions in additively separable hedonic games. Artificial Intelligence 195 (2013), 316\u2013334.","journal-title":"Artificial Intelligence"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107446984.016"},{"key":"e_1_3_3_5_2","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/978-3-642-22006-7_32","volume-title":"Proceedings of the 38th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Varadaraja Ashwinkumar Badanidiyuru","year":"2011","unstructured":"Ashwinkumar Badanidiyuru Varadaraja. 2011. Buyback problem\u2014Approximate matroid intersection with cancellation costs. In Proceedings of the 38th International Colloquium on Automata, Languages, and Programming (ICALP), 379\u2013390."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2003.10.003"},{"key":"e_1_3_3_7_2","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/s003550000067","article-title":"Core in a simple coalition formation game","volume":"18","author":"Banerjee Suryapratim","year":"2001","unstructured":"Suryapratim Banerjee, Hideo Konishi, and Tayfun S\u00f6nmez. 2001. Core in a simple coalition formation game. Social Choice and Welfare 18 (2001), 135\u2013153.","journal-title":"Social Choice and Welfare"},{"key":"e_1_3_3_8_2","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","article-title":"Correlation clustering","volume":"56","author":"Bansal Nikhil","year":"2004","unstructured":"Nikhil Bansal, Avrim Blum, and Shuchi Chawla. 2004. Correlation clustering. Machine Learning 56 (2004), 89\u2013113.","journal-title":"Machine Learning"},{"key":"e_1_3_3_9_2","article-title":"On the factorization of the complete uniform hypergraph","author":"Baranyai Zsolt","year":"1973","unstructured":"Zsolt Baranyai. 1973. On the factorization of the complete uniform hypergraph. Infinite and Finite Sets (1973). Retrieved from https:\/\/cir.nii.ac.jp\/crid\/1571417125147391744","journal-title":"Infinite and Finite Sets"},{"key":"e_1_3_3_10_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","volume":"62","author":"Bil\u00f2 Vittorio","year":"2018","unstructured":"Vittorio Bil\u00f2, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, and Luca 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"},{"key":"e_1_3_3_11_2","first-page":"9287","volume-title":"Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI)","author":"Bil\u00f2 Vittorio","year":"2022","unstructured":"Vittorio Bil\u00f2, Gianpiero Monaco, and Luca Moscardelli. 2022. Hedonic games with fixed-size coalitions. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), 9287\u20139295."},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3711671"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1006\/game.2001.0877"},{"key":"e_1_3_3_14_2","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1613\/jair.1.13470","article-title":"Finding and recognizing popular coalition structures","volume":"74","author":"Brandt Felix","year":"2022","unstructured":"Felix Brandt and Martin Bullinger. 2022. Finding and recognizing popular coalition structures. Journal of Artificial Intelligence Research 74 (2022), 569\u2013626.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","first-page":"104160","DOI":"10.1016\/j.artint.2024.104160","article-title":"Stability based on single-agent deviations in additively separable hedonic games","volume":"334","author":"Brandt Felix","year":"2024","unstructured":"Felix Brandt, Martin Bullinger, and Leo Tappe. 2024. Stability based on single-agent deviations in additively separable hedonic games. Artificial Intelligence 334 (2024), 104160.","journal-title":"Artificial Intelligence"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3588753"},{"issue":"3","key":"e_1_3_3_17_2","first-page":"1384","article-title":"Sum the odds to one and stop","volume":"28","author":"Bruss F. Thomas","year":"2000","unstructured":"F. Thomas Bruss. 2000. Sum the odds to one and stop. The Annals of Probability 28, 3 (2000), 1384\u20131391.","journal-title":"The Annals of Probability"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/3398761.3398791"},{"key":"e_1_3_3_19_2","first-page":"618","volume-title":"Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)","author":"Bullinger Martin","year":"2025","unstructured":"Martin Bullinger, Vaggos Chatziafratis, and Parnian Shahkar. 2025. Welfare approximation in additively separable hedonic games. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 618\u2013426."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-60099-9_3"},{"key":"e_1_3_3_21_2","volume-title":"Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI)","author":"Bullinger Martin","year":"2025","unstructured":"Martin Bullinger and Matan Gilboa. 2025. Settling the complexity of popularity in additively separable and fractional hedonic games. In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI)."},{"key":"e_1_3_3_22_2","doi-asserted-by":"crossref","first-page":"2423","DOI":"10.1613\/jair.1.16420","article-title":"Stability in online coalition formation","volume":"82","author":"Bullinger Martin","year":"2025","unstructured":"Martin Bullinger and Ren\u00e9 Romen. 2025. Stability in online coalition formation. Journal of Artificial Intelligence Research 82 (2025), 2423\u20132452.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"e_1_3_3_23_2","unstructured":"Martin Bullinger Ren\u00e9 Romen and Alexander Schlenga. 2025. The Power of Matching for Online Fractional Hedonic Games. Technical Report. Retrieved from https:\/\/arxiv.org\/abs\/2505.06163"},{"key":"e_1_3_3_24_2","doi-asserted-by":"crossref","first-page":"114238","DOI":"10.1016\/j.tcs.2023.114238","article-title":"Topological distance games","volume":"981","author":"Bullinger Martin","year":"2024","unstructured":"Martin Bullinger and Warut Suksompong. 2024. Topological distance games. Theoretical Computer Science 981 (2024), 114238.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/3306127.3331742"},{"key":"e_1_3_3_26_2","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/s001820000053","article-title":"Stability in coalition formation games","volume":"29","author":"Cechl\u00e1rov\u00e1 Katar\u00edna","year":"2001","unstructured":"Katar\u00edna Cechl\u00e1rov\u00e1 and Antonio 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_3_27_2","first-page":"494","volume-title":"Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS)","author":"Cohen Saar","year":"2023","unstructured":"Saar Cohen and Noa Agmon. 2023. Online coalitional skill formation. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 494\u2013503."},{"key":"e_1_3_3_28_2","first-page":"2475","volume-title":"Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)","author":"Cohen Saar","year":"2025","unstructured":"Saar Cohen and Noa Agmon. 2025. Egalitarianism in online coalition formation (extended abstract). In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2475\u20132477."},{"key":"e_1_3_3_29_2","first-page":"4157","volume-title":"Proceedings of the 39th International Conference on Machine Learning (ICML)","author":"Cohen-Addad Vincent","year":"2022","unstructured":"Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, and Nikos Parotsidis. 2022. Online and consistent correlation clustering. In Proceedings of the 39th International Conference on Machine Learning (ICML), 4157\u20134179."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.008"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00355-006-0104-4"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.2307\/1912943"},{"key":"e_1_3_3_33_2","first-page":"627","article-title":"The optimum choice of the instant for stopping a Markov process","volume":"4","author":"Dynkin Evgenii Borisovich","year":"1963","unstructured":"Evgenii Borisovich Dynkin. 1963. The optimum choice of the instant for stopping a Markov process. Soviet Mathematics 4 (1963), 627\u2013629.","journal-title":"Soviet Mathematics"},{"key":"e_1_3_3_34_2","doi-asserted-by":"crossref","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","article-title":"Paths, trees and flowers","volume":"17","author":"Edmonds Jack","year":"1965","unstructured":"Jack Edmonds. 1965. Paths, trees and flowers. Canadian Journal of Mathematics 17 (1965), 449\u2013467.","journal-title":"Canadian Journal of Mathematics"},{"key":"e_1_3_3_35_2","doi-asserted-by":"crossref","first-page":"103357","DOI":"10.1016\/j.artint.2020.103357","article-title":"Price of pareto optimality in hedonic games","volume":"288","author":"Elkind Edith","year":"2020","unstructured":"Edith Elkind, Angelo Fanelli, and Michele Flammini. 2020. Price of pareto optimality in hedonic games. Artificial Intelligence 288 (2020), 103357.","journal-title":"Artificial Intelligence"},{"key":"e_1_3_3_36_2","first-page":"417","volume-title":"Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)","author":"Elkind Edith","year":"2009","unstructured":"Edith Elkind and Michael Wooldridge. 2009. Hedonic coalition nets. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 417\u2013424."},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/100801901"},{"key":"e_1_3_3_38_2","first-page":"389","volume-title":"Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS)","author":"Epstein Leah","year":"2013","unstructured":"Leah Epstein, Asaf Levin, Danny Segev, and Oren Weimann. 2013. Improved bounds for online preemptive matching. In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), 389\u2013399."},{"key":"e_1_3_3_39_2","doi-asserted-by":"crossref","first-page":"1148","DOI":"10.1145\/3490486.3538290","volume-title":"Proceedings of the 22nd ACM Conference on Economics and Computation (ACM-EC)","author":"Ezra Tomer","year":"2022","unstructured":"Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. 2022. General graphs are easier than bipartite graphs: Tight bounds for secretary matching. In Proceedings of the 22nd ACM Conference on Economics and Computation (ACM-EC), 1148\u20131177."},{"key":"e_1_3_3_40_2","first-page":"745","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Feigenbaum Joan","year":"2005","unstructured":"Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. 2005. Graph distances in the streaming model: The value of space. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 745\u2013754."},{"key":"e_1_3_3_41_2","first-page":"206","article-title":"On graph problems in a semi-streaming model","volume":"348","author":"Feigenbaum Joan","year":"2005","unstructured":"Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. 2005. On graph problems in a semi-streaming model. Theoretical Computer Science 348 (2005), 206\u2013216.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_3_42_2","first-page":"374","volume-title":"Proceedings of the 5th International Conference on Web and Internet Economics (WINE)","author":"Feldman Jon","year":"2009","unstructured":"Jon Feldman, Nitish Korula, Vahab Mirrokni, Shanmugavelayutham Muthukrishnan, and Martin P\u00e1l. 2009. Online ad assignment with free disposal. In Proceedings of the 5th International Conference on Web and Internet Economics (WINE), 374\u2013385."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177012493"},{"key":"e_1_3_3_44_2","first-page":"1253","article-title":"Strategyproof mechanisms for additively separable and fractional hedonic games","volume":"70","author":"Flammini Michele","year":"2021","unstructured":"Michele Flammini, Bojana Kodric, Gianpiero Monaco, and Qiang Zhang. 2021. Strategyproof mechanisms for additively separable and fractional hedonic games. Journal of Artificial Intelligence Research 70 (2021), 1253\u20131279.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"e_1_3_3_45_2","doi-asserted-by":"crossref","first-page":"103610","DOI":"10.1016\/j.artint.2021.103610","article-title":"Strategyproof mechanisms for friends and enemies games","volume":"302","author":"Flammini Michele","year":"2022","unstructured":"Michele Flammini, Bojana Kodric, and Giovanna Varricchio. 2022. Strategyproof mechanisms for friends and enemies games. Artificial Intelligence 302 (2022), 103610.","journal-title":"Artificial Intelligence"},{"key":"e_1_3_3_46_2","doi-asserted-by":"crossref","first-page":"1215","DOI":"10.1613\/jair.1.12989","article-title":"On the online coalition structure generation problem","volume":"72","author":"Flammini Michele","year":"2021","unstructured":"Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Mordechai Shalom, and Shmuel Zaks. 2021. On the online coalition structure generation problem. Journal of Artificial Intelligence Research 72 (2021), 1215\u20131250.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2018.0960"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00011"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.5555\/562056"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188858"},{"key":"e_1_3_3_52_2","volume-title":"Online and Matching-Based Market Design","author":"Huang Zhiyi","year":"2023","unstructured":"Zhiyi Huang and Torben Tr\u00f6bst. 2023. Online matching. In Online and Matching-Based Market Design. F. Echenique, N. Immorlica, and V. V. Vazirani (Eds.), Cambridge University Press."},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90033-1"},{"key":"e_1_3_3_54_2","first-page":"587","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC)","author":"Karande Chinmay","year":"2011","unstructured":"Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. 2011. Online bipartite matching with unknown distributions. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), 587\u2013596."},{"key":"e_1_3_3_55_2","first-page":"352","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC)","author":"Karp Richard M.","year":"1990","unstructured":"Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. 1990. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), 352\u2013358."},{"key":"e_1_3_3_56_2","first-page":"589","volume-title":"Proceedings of the 21st European Symposium on Algorithms (ESA)","author":"Kesselheim Thomas","year":"2013","unstructured":"Thomas Kesselheim, Klaus Radke, Andreas T\u00f6nnis, and Berthold V\u00f6cking. 2013. An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In Proceedings of the 21st European Symposium on Algorithms (ESA), 589\u2013600."},{"key":"e_1_3_3_57_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-24488-9","volume-title":"Combinatorial Optimization","author":"Korte Bernhard","year":"2012","unstructured":"Bernhard Korte and Jens Vygen. 2012. Combinatorial Optimization (5th ed.). Springer-Verlag.","edition":"5"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.5555\/3635637.3662968"},{"key":"e_1_3_3_59_2","first-page":"597","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC)","author":"Mahdian Mohammad","year":"2011","unstructured":"Mohammad Mahdian and Qiqi Yan. 2011. Online bipartite matching with random arrivals: An approach based on strongly factor-revealing LPs. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), 597\u2013605."},{"key":"e_1_3_3_60_2","doi-asserted-by":"crossref","unstructured":"Andrew McGregor. 2005. Finding graph matchings in data streams. In Proceedings of the 8th International Workshop on Approximation Algorithms for Compinatorial Optimization Problems and 9th International Workshop on Randomization and Computation (APPROX & RANDOM) 170\u2013181.","DOI":"10.1007\/11538462_15"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000002"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9176-8"},{"key":"e_1_3_3_63_2","first-page":"97","volume-title":"Proceedings of the 18th Computing: The Australasian Theory Symposium (CATS) (Conferences in Research and Practice in Information Technology (CRPIT)","author":"Olsen Martin","year":"2012","unstructured":"Martin Olsen. 2012. On defining and computing communities. In Proceedings of the 18th Computing: The Australasian Theory Symposium (CATS) (Conferences in Research and Practice in Information Technology (CRPIT), 97\u2013102."},{"key":"e_1_3_3_64_2","first-page":"617","volume-title":"Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI)","author":"Peters Dominik","year":"2015","unstructured":"Dominik Peters and Edith Elkind. 2015. Simple causes of complexity in hedonic games. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), 617\u2013623."},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2009.09.004"},{"key":"e_1_3_3_66_2","first-page":"526","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Swamy Chaitanya","year":"2004","unstructured":"Chaitanya Swamy. 2004. Correlation clustering: Maximizing agreements via semidefinite programming. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 526\u2013527."},{"key":"e_1_3_3_67_2","doi-asserted-by":"crossref","first-page":"1070","DOI":"10.1007\/978-3-662-47672-7_87","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Wang Yajun","year":"2015","unstructured":"Yajun Wang, Sam Chiu, and Wai Wong. 2015. Two-sided online bipartite matching and vertex cover: Beating the greedy algorithm. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), 1070\u20131081."},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.mathsocsci.2012.10.001"},{"key":"e_1_3_3_69_2","first-page":"1050","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI)","author":"Wright Mason","year":"2015","unstructured":"Mason Wright and Yevgeniy Vorobeychik. 2015. Mechanism design for team formation. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), 1050\u20131056."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3758324","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T15:05:33Z","timestamp":1759849533000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3758324"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,7]]},"references-count":68,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1,31]]}},"alternative-id":["10.1145\/3758324"],"URL":"https:\/\/doi.org\/10.1145\/3758324","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,7]]},"assertion":[{"value":"2023-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-23","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}