{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:16:39Z","timestamp":1740122199647,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,7,30]],"date-time":"2024-07-30T00:00:00Z","timestamp":1722297600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,30]],"date-time":"2024-07-30T00:00:00Z","timestamp":1722297600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/R513222\/1","EP\/X013618\/1"],"award-info":[{"award-number":["EP\/R513222\/1","EP\/X013618\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["J\u00e1nos Bolyai Research Fellowship"],"award-info":[{"award-number":["J\u00e1nos Bolyai Research Fellowship"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]}],"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 study the problem of fairly partitioning a set of agents into coalitions based on the agents\u2019 additively separable preferences, which can also be viewed as a hedonic game. We study three successively weaker solution concepts, related to envy, weakly justified envy, and justified envy. In a model in which coalitions may have any size, trivial solutions exist for these concepts, which provides a strong motivation for placing restrictions on coalition size. In this paper, we require feasible coalitions to have size three. We study the existence of partitions that are envy-free, weakly justified envy-free, and justified envy-free, and the computational complexity of finding such partitions, if they exist. We impose various restrictions on the agents\u2019 preferences and present a complete complexity classification in terms of these restrictions.<\/jats:p>","DOI":"10.1007\/s10458-024-09657-6","type":"journal-article","created":{"date-parts":[[2024,7,30]],"date-time":"2024-07-30T15:02:28Z","timestamp":1722351748000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Envy-freeness in 3D hedonic games"],"prefix":"10.1007","volume":"38","author":[{"given":"Michael","family":"McKay","sequence":"first","affiliation":[]},{"given":"\u00c1gnes","family":"Cseh","sequence":"additional","affiliation":[]},{"given":"David","family":"Manlove","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,7,30]]},"reference":[{"key":"9657_CR1","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, 135\u2013153.","journal-title":"Social Choice and Welfare"},{"key":"9657_CR2","doi-asserted-by":"crossref","unstructured":"Olsen, M. (2007). Nash stability in additively separable hedonic games is NP-hard. In: Proceedings of CiE \u201907: the 3$$^{{{\\rm rd}}}$$ Conference on Computability in Europe. LNCS, vol. 4497, pp. 598\u2013605. Springer","DOI":"10.1007\/978-3-540-73001-9_62"},{"key":"9657_CR3","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., & Moulin, H. (2016). Hedonic games. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. D. Procaccia (Eds.), Handbook of Computational Social Choice (pp. 356\u2013376). Cambridge University Press."},{"issue":"4","key":"9657_CR4","doi-asserted-by":"publisher","first-page":"987","DOI":"10.2307\/1912943","volume":"48","author":"JH Dr\u00e8ze","year":"1980","unstructured":"Dr\u00e8ze, J. H., & Greenberg, J. (1980). Hedonic coalitions: Optimality and stability. Econometrica, 48(4), 987\u20131003.","journal-title":"Econometrica"},{"key":"9657_CR5","unstructured":"Elkind, E., & Wooldridge, M. (2009). Hedonic coalition nets. In: Proceedings of AAMAS \u201909: the 8$$^{{{\\rm th}}}$$ International Conference on Autonomous Agents and Multiagent Systems, vol. 1, pp. 417\u2013424. International Foundation for Autonomous Agents and Multiagent Systems"},{"key":"9657_CR6","doi-asserted-by":"crossref","unstructured":"Barrot, N., & Yokoo, M. (2019). Stable and envy-free partitions in hedonic games. In: Proceedings of IJCAI \u201919: the 28$$^{{{\\rm th}}}$$ International Joint Conference on Artificial Intelligence, pp. 67\u201373. IJCAI Organization","DOI":"10.24963\/ijcai.2019\/10"},{"key":"9657_CR7","doi-asserted-by":"crossref","unstructured":"Ueda, S. (2018). Envy based fairness in hedonic games. In: Proceedings of GECCO \u201918: the Genetic and Evolutionary Computation Conference, pp. 1852\u20131853. ACM","DOI":"10.1145\/3205651.3208275"},{"key":"9657_CR8","doi-asserted-by":"crossref","unstructured":"Bredereck, R., Heeger, K., Knop, D., & Niedermeier, R. (2020). Multidimensional stable roommates with master list. In: Proceedings of WINE \u201920: the 16$$^{{{\\rm th}}}$$ Conference on Web and Internet Economics. LNCS, vol. 12495, pp. 59\u201373. Springer","DOI":"10.1007\/978-3-030-64946-3_5"},{"key":"9657_CR9","doi-asserted-by":"crossref","unstructured":"Huang, C.-C. (2007). Two\u2019s company, three\u2019s a crowd: Stable family and threesome roommates problems. In: Proceedings of ESA \u201907: the 15$$^{{{\\rm th}}}$$ European Symposium on Algorithms. LNCS, vol. 4698, pp. 558\u2013569. Springer","DOI":"10.1007\/978-3-540-75520-3_50"},{"key":"9657_CR10","unstructured":"Iwama, K., Miyazaki, S., & Okamoto, K. (2007). Stable roommates problem with triple rooms. In: Proceedings of WAAC \u201907: the 10$$^{{{\\rm th}}}$$ Korea-Japan Workshop on Algorithms and Computation, pp. 105\u2013112. Archived as Technical Report COMP2007-41 in the Kyoto University Research Information Repository."},{"key":"9657_CR11","doi-asserted-by":"crossref","unstructured":"McKay, M., & Manlove, D. (2021). The three-dimensional stable roommates problem with additively separable preferences. In: Proceedings of SAGT \u201921: the 14$$^{{{\\rm th}}}$$ International Symposium on Algorithmic Game Theory. LNCS, vol. 12885, pp. 266\u2013280. Springer","DOI":"10.1007\/978-3-030-85947-3_18"},{"issue":"1","key":"9657_CR12","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1137\/0404023","volume":"4","author":"C Ng","year":"1991","unstructured":"Ng, C., & Hirschberg, D. S. (1991). Three-dimensional stable matching problems. SIAM Journal on Discrete Mathematics, 4(1), 245\u2013252.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9657_CR13","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.artint.2018.03.004","volume":"259","author":"L Sless","year":"2018","unstructured":"Sless, L., Hazon, N., Kraus, S., & Wooldridge, M. (2018). Forming $$k$$ coalitions and facilitating relationships in social networks. Artificial Intelligence, 259, 217\u2013245.","journal-title":"Artificial Intelligence"},{"issue":"1","key":"9657_CR14","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1002\/nav.22084","volume":"70","author":"HA Yekta","year":"2023","unstructured":"Yekta, H. A., Bergman, D., & Day, R. (2023). Balancing stability and efficiency in team formation as a generalized roommate problem. Naval Research Logistics, 70(1), 72\u201388.","journal-title":"Naval Research Logistics"},{"key":"9657_CR15","unstructured":"Premier Chess Academy Corporation: Premier Middle East League Schedule (2021). https:\/\/web.archive.org\/web\/20231021151757\/https:\/\/premierchessacademy.com\/2021-premier-middleeast-league\/"},{"key":"9657_CR16","unstructured":"Leeds Chess Association: Rules and Constitution (2023). https:\/\/web.archive.org\/web\/20230322065051\/https:\/\/www.leedschess.org\/rules-and-constitution\/"},{"key":"9657_CR17","unstructured":"International Chess Federation (FIDE) Handbook (2023). https:\/\/web.archive.org\/web\/20231019083209\/https:\/\/handbook.fide.com\/"},{"key":"9657_CR18","doi-asserted-by":"publisher","DOI":"10.1142\/8591","volume-title":"Algorithmics of matching under preferences","author":"DF Manlove","year":"2013","unstructured":"Manlove, D. F. (2013). Algorithmics of matching under preferences. World Scientific."},{"key":"9657_CR19","doi-asserted-by":"crossref","unstructured":"Coutance, B., Maddila, P., & Wilczynski, A. (2023). Rank-Envy-Freeness in roommate matchings. In: Proceedings of ECAI \u201923: the 26$$^{{{\\rm th}}}$$ European Conference on Artificial Intelligence, pp. 493\u2013500. IOS Press","DOI":"10.3233\/FAIA230308"},{"key":"9657_CR20","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. G. (2013). Computing desirable partitions in additively separable hedonic games. Artificial Intelligence, 195, 316\u2013334.","journal-title":"Artificial Intelligence"},{"issue":"4","key":"9657_CR21","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.ipl.2008.10.003","volume":"109","author":"EM Arkin","year":"2009","unstructured":"Arkin, E. M., Bae, S. W., Efrat, A., Mitchell, J. S. B., Okamoto, K., & Polishchuk, V. (2009). Geometric stable roommates. Information Processing Letters, 109(4), 219\u2013224.","journal-title":"Information Processing Letters"},{"key":"9657_CR22","doi-asserted-by":"crossref","unstructured":"Bil\u00f2, V., Monaco, G., & Moscardelli, L. (2022). Hedonic games with fixed-size coalitions. In: Proceedings of AAAI \u201922: the 36$$^{{{\\rm th}}}$$ AAAI Conference on Artificial Intelligence, pp. 9287\u20139295. AAAI Press","DOI":"10.1609\/aaai.v36i9.21156"},{"issue":"2","key":"9657_CR23","doi-asserted-by":"publisher","first-page":"1","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), 1\u201329.","journal-title":"ACM Transactions on Economics and Computation"},{"issue":"3","key":"9657_CR24","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.1287\/moor.2018.0960","volume":"44","author":"M Gairing","year":"2008","unstructured":"Gairing, M., & Savani, R. (2008). Computing stable outcomes in symmetric additively separable hedonic games. Mathematics of Operations Research, 44(3), 1101\u20131121.","journal-title":"Mathematics of Operations Research"},{"issue":"2","key":"9657_CR25","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. O. (2002). The stability of hedonic coalition structures. Games and Economic Behavior, 38(2), 201\u2013230.","journal-title":"Games and Economic Behavior"},{"key":"9657_CR26","doi-asserted-by":"publisher","first-page":"885","DOI":"10.1007\/978-0-387-30162-4_397","volume-title":"The encyclopedia of algorithms","author":"K Cechl\u00e1rov\u00e1","year":"2008","unstructured":"Cechl\u00e1rov\u00e1, K. (2008). Stable partition problem. The encyclopedia of algorithms (pp. 885\u2013888). Springer."},{"key":"9657_CR27","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1613\/jair.1.13470","volume":"74","author":"F Brandt","year":"2022","unstructured":"Brandt, F., & Bullinger, M. (2022). Finding and recognizing popular coalition structures. Journal of Artificial Intelligence Research, 74, 569\u2013626.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9657_CR28","doi-asserted-by":"crossref","unstructured":"Li, L., Micha, E., Nikolov, A., & Shah, N. (2023). Partitioning friends fairly. In: Proceedings of AAAI \u201923: the 37$$^{{{\\rm th}}}$$ AAAI Conference on Artificial Intelligence, pp. 5747\u20135754. AAAI Press","DOI":"10.1609\/aaai.v37i5.25713"},{"key":"9657_CR29","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1613\/jair.1.14863","volume":"77","author":"J Gan","year":"2023","unstructured":"Gan, J., Li, B., & Li, Y. (2023). Your college dorm and dormmates: Fair resource sharing with externalities. Journal of Artificial Intelligence Research, 77, 793\u2013820.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9657_CR30","doi-asserted-by":"crossref","unstructured":"Boehmer, N., & Elkind, E. (2020). Stable roommate problem with diversity preferences. In: Proceedings of IJCAI \u201920: the 29$$^{{{\\rm th}}}$$ International Joint Conference on Artificial Intelligence, pp. 96\u2013102. IJCAI Organization","DOI":"10.24963\/ijcai.2020\/14"},{"issue":"1","key":"9657_CR31","doi-asserted-by":"publisher","first-page":"87","DOI":"10.22574\/jmid.2019.11.003","volume":"4","author":"\u00c1 Cseh","year":"2019","unstructured":"Cseh, \u00c1., Fleiner, T., & Harj\u00e1n, P. (2019). Pareto optimal coalitions of fixed size. Journal of Mechanism and Institution Design, 4(1), 87\u2013108.","journal-title":"Journal of Mechanism and Institution Design"},{"key":"9657_CR32","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/BF02716626","volume":"1","author":"J Alcalde","year":"1995","unstructured":"Alcalde, J. (1995). Exchange-proofness or divorce-proofness? Stability in one-sided matching markets. Economic Design, 1, 275\u2013287.","journal-title":"Economic Design"},{"key":"9657_CR33","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability. Freeman."},{"key":"9657_CR34","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J. (1978). The complexity of satisfiability problems. In: Proceedings of STOC \u201978: the 10$$^{{{\\rm th}}}$$ Annual ACM Symposium on Theory of Computing, pp. 216\u2013226","DOI":"10.1145\/800133.804350"},{"key":"9657_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2013.10.030","volume":"167","author":"S Porschen","year":"2014","unstructured":"Porschen, S., Schmidt, T., Speckenmeyer, E., & Wotzlaw, A. (2014). XSAT and NAE-SAT of linear CNF classes. Discrete Applied Mathematics, 167, 1\u201314.","journal-title":"Discrete Applied Mathematics"},{"key":"9657_CR36","unstructured":"Cechl\u00e1rov\u00e1, K., Fleiner, T., & Manlove, D. (2005). The kidney exchange game. In: Proceedings of SOR \u201905: the 8$$^{{{\\rm th}}}$$ International Symposium on Operations Research in Slovenia, pp. 77\u201383. IM Preprint series A, no. 5\/2005, PJ \u0160af\u00e1rik University, Faculty of Science, Institute of Mathematics"},{"key":"9657_CR37","unstructured":"Bullinger, M. (2021). Single-Agent Dynamics in Hedonic Games. Talk presented on 17$$^{{{\\rm th}}}$$ August 2021 at Dagstuhl Seminar 21331: Coalition Formation Games in Dagstuhl, Germany. http:\/\/web.archive.org\/web\/20220913192100\/https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2021\/15588\/pdf\/dagrep_v011_i007_p001_21331.pdf"},{"issue":"1","key":"9657_CR38","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. American Mathematical Monthly, 69(1), 9\u201315.","journal-title":"American Mathematical Monthly"},{"key":"9657_CR39","doi-asserted-by":"crossref","unstructured":"Ohta, K., Barrot, N., Ismaili, A., Sakurai, Y., & Yokoo, M. (2017). Core stability in hedonic games among friends and enemies: Impact of neutrals. In: Proceedings of IJCAI \u201917: the 26$$^{{{\\rm th}}}$$ International Joint Conference on Artificial Intelligence, pp. 359\u2013365. IJCAI Organization","DOI":"10.24963\/ijcai.2017\/51"},{"key":"9657_CR40","first-page":"353","volume":"31","author":"K Cechl\u00e1rov\u00e1","year":"2002","unstructured":"Cechl\u00e1rov\u00e1, K., & Hajdukov\u00e1, J. (2002). Computational complexity of stable partitions with $${\\mathscr {B}}$$-preferences. International Journal of Game Theory, 31, 353\u2013364.","journal-title":"International Journal of Game Theory"},{"issue":"3","key":"9657_CR41","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/S0166-218X(03)00464-5","volume":"138","author":"K Cechl\u00e1rov\u00e1","year":"2004","unstructured":"Cechl\u00e1rov\u00e1, K., & Hajdukov\u00e1, J. (2004). Stable partitions with $${\\mathscr {W}}$$-preferences. Discrete Applied Mathematics, 138(3), 333\u2013347.","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"9657_CR42","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1142\/S0219198906001144","volume":"8","author":"J Hajdukov\u00e1","year":"2006","unstructured":"Hajdukov\u00e1, J. (2006). Coalition formation games: A survey. International Game Theory Review, 8(4), 613\u2013641.","journal-title":"International Game Theory Review"},{"issue":"1","key":"9657_CR43","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson, N., & Seymour, P. D. (1984). Graph minors. III. Planar tree-width. Journal of Combinatorial Theory, Series B, 36(1), 49\u201364.","journal-title":"Journal of Combinatorial Theory, Series B"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-024-09657-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-024-09657-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-024-09657-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,13]],"date-time":"2024-11-13T15:24:04Z","timestamp":1731511444000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-024-09657-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,30]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["9657"],"URL":"https:\/\/doi.org\/10.1007\/s10458-024-09657-6","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"type":"print","value":"1387-2532"},{"type":"electronic","value":"1573-7454"}],"subject":[],"published":{"date-parts":[[2024,7,30]]},"assertion":[{"value":"10 June 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 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":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"37"}}