Individual Rationality in Constrained Hedonic Games: Additively Separable and Fractional Preferences DOI: 10.1613/jair.1.xxxxx Volume: 4 6 8 Note: An extended abstract of this work has been published in the Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’26 ( Fioravantes et al. 2026 ) .

Foivos Fioravantes, Harmender Gahlawat, Nikolaos Melissinos, Šimon Schierreich · 2026

Read Individual Rationality in Constrained Hedonic Games: Additively Separable and Fractional Preferences DOI: 10.1613/jair.1.xxxxx Volume: 4 6 8 Note: An extended abstract of this work has been published in the Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’26 ( Fioravantes et al. 2026 ) . by Foivos Fioravantes, Harmender Gahlawat, Nikolaos Melissinos, Šimon Schierreich (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-21826.txt.

Introduction

Fioravantes and co-authors study coalition formation when the number and size of groups are fixed in advance. In hedonic games, selfish agents split into coalitions they like. The team requires exactly k coalitions, each within a set size range. They ask when an outcome exists where no agent would rather be alone. That bare stability test turns out to have a rich complexity map. For additively separable and fractional preferences, they chart which cases are tractable and which are hard, using the structure of the preference graph.

Catalog record

CREATORFoivos Fioravantes, Harmender Gahlawat, Nikolaos Melissinos, Šimon Schierreich
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE90943
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.21826

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Individual Rationality in Constrained Hedonic Games: Additively Separable and Fractional Preferences DOI: 10.1613/jair.1.xxxxx Volume: 4 6 8 Note: An extended abstract of this work has been published in the Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’26 ( Fioravantes et al. 2026 ) . Foivos Fioravantes, Harmender Gahlawat, Nikolaos Melissinos, Šimon Schierreich Abstract . Hedonic games are an archetypal problem in coalition formation, where a set of selfish agents want to partition themselves into stable coalitions. In this work, we focus on two natural constraints on the possible outcomes. First, we require that exactly k {{k}} coalitions are created. Then, loosely following the model of Bilò et al. (AAAI 2022), we assume that each of the k {{k}} coalitions is additionally associated with a lower and upper bound on its size. The notion of stability that we study is that of individual rationality (IR), which requires that no agent strictly prefers to be alone compared to being in his or her coalition. Although IR is trivially satisfiable even in the most general models of hedonic games, the complexity picture of deciding whether an IR allocation exists, considering the above constraints, is unexpectedly rich. We reveal that tractable fragments of this computational problem require surprisingly nontrivial arguments, even if we restrict ourselves to additively separable and fractional hedonic games . Our tractability results, achieved by exploiting the structure of the underlying preference graph , are also complemented by their intractability counterparts, painting a fairly complete picture of the tractability landscape of this problem. \JAIRAE Insert JAIR AE Name \JAIRTrack 1. Introduction Organizing a seating arrangement for a banquet may seem straightforward, but quickly becomes complex when interpersonal relationships are considered. For example, placing Janine from HR at the same table as Sheldon from the Physics Department could result in a very unpleasant evening—not just for them, but likely for all the attendees. And it is not only about animosities; seating Sheldon at the table only with strangers can be a similarly explosive choice. In addition, there may be certain restrictions on seating, including the number of available tables and their capacity. The situation introduced above appears naturally in various domains and falls in the area of coalition formation . More formally, the goal here is to partition a set of agents into several groups, called coalitions , so that no agent is motivated to deviate from its coalition to improve their utility. In more game-theoretical terms, we are interested in stable partitions. The prevailing model in this area is that of hedonic games ( Drèze & Greenberg 1980 ; Aziz & Savani 2016 ) , where agents care only about other agents in their own coalition and not about how the additional coalitions are formed. Traditionally, arbitrarily constructed coalition structures are acceptable as long as they meet certain stability criteria. However, in many real-life scenarios, such as the one at the beginning of this section, we have an additional restriction on the outcome. First, as argued by Sless et al. 2018 , in certain situations, it may be necessary to form an exact number of coalitions; see also ( Waxman et al. 2021 ; Barr et al. 2024 ) . We call this model k -hedonic games . A different restriction, motivated by the recently proposed model of Bilò et al. 2022 (see also ( Li et al. 2023 ; Deligkas et al. 2025 ; Agarwal et al. 2025 ) ), asks for k coalitions, each of size between a given lower and upper bound. We call this model hedonic games with size-constrained coalitions . Several of these works study the computational aspects of finding stable outcomes under these two restrictions. However, they are mostly interested in Nash, individual, or core stability, which are all very demanding, rarely satisfiable, and the associated computational problems are often intractable. In our work, we return to the foundational stability notion of individual rationality (IR) ( Roth 1977 ; Ashlagi & Roth 2011 ; Polevoy & Dziubinski 2022 ; Deligkas et al. 2024 ) , which is strictly weaker than the notions mentioned above (see, e.g., ( Aziz & Savani 2016 , Figure 15.1) ). Intuitively, a coalition structure is IR if no agent strictly prefers to be alone compared to being in its current coalition. It is a well-known fact that every hedonic game admits a trivial individually-rational solution; just place each agent in a coalition on its own. Due to this, individual rationality is completely overlooked in the relevant literature. However, as we show, our restrictions turn IR into an unexpectedly interesting solution concept with a very colorful complexity picture. Table 1. Summary of our contributions. We use \operatorname{vc}(G) to denote the vertex cover number of G , and \operatorname{tw}(G) for its treewidth. Problem Restrictions Complexity Reference Both k -ASHGs and ASHGs-SCC for every k\geq 2 , symmetric valuations, G is a split graph with {\mathcal{O}\left(k^{2}\right)} negative edges and \operatorname{vc}(G)=2k NP -complete Theorem 3.2 for every k\geq 2 , symmetric valuations, G is a clique, and the valuations use six different unary encoded values NP -complete Theorem 3.3 symmetric, unary encoded valuations, parameterized by the number of coalitions k , the number of negative edges, and \operatorname{vc}(G) W[1] -hard Theorem 4.2 unary encoded valuations, parameterized by \operatorname{vc}(G) XP Theorem 4.1 for k=2 , symmetric and binary valuations, W[1] -hard Theorem 5.1 parameterized by the treedepth of G Only k -ASHGs parameterized by \operatorname{vc}(G) and the maximum weight {\omega}_{\max} FPT Theorem 4.3 binary valuations, parameterized by \operatorname{tw}(G) XP Theorem 5.2 ASHGs-SCC parameterized by \operatorname{vc}(G) , the number of coalitions {{k}} , and the maximum weight {\omega}_{\max} FPT Proposition 4.4 binary valuations, parameterized by \operatorname{tw}(G) and the number of coalitions {{k}} XP Theorem 5.2 1.1. Our Contribution The main contribution of our work is a detailed algorithmic landscape of the two restrictions of coalition formation introduced above assuming two prominent subclasses of hedonic games. As classical complexity renders the problem very soon intractable, we turn to the finer-grained framework of parameterized complexity 1 1 1 A formal introduction to parameterized complexity is given in Section 2 . . Intuitively, we study the complexity of a computational problem not only with respect to the input size, but also assuming some parameter p additionally restricting the input instance. The ultimate goal of parameterized algorithms is to find (or prove that it is not possible by showing that the problem is W[1] -hard ) an algorithm whose running time is exponential only in the parameter, and its time dependence on the input size is only polynomial in it. Such algorithms are called FPT . Slightly worse are XP algorithms, whose running time is also polynomial in the input size, but the degree of this polynomial depends on the parameter. One can conditionally rule out the existence of an XP algorithm by showing that a problem is NP -hard already for a constant value of p . The two classes of hedonic games we study are additively separable hedonic games (ASHGs) ( Bogomolnaia & Jackson 2002 ) and (modified) fractional hedonic games (MFHGs) ( Aziz et al. 2019 ; Olsen 2012 ) . In these games, each agent i has a specific value

Read the complete text