# Relaxed core stability in hedonic games

Angelo Fanelli, Gianpiero Monaco, Luca Moscardelli

► To cite this version:

Angelo Fanelli, Gianpiero Monaco, Luca Moscardelli. Relaxed core stability in hedonic games. Artificial Intelligence (AIJ), 2025, 348, pp.104394. 10.1016/j.artint.2025.104394. hal-05368675

HAL Id: hal-05368675

https://hal.science/hal-05368675v1

Submitted on 17 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ELSEVIER

Contents lists available at [ScienceDirect](https://www.sciencedirect.com)

Artificial Intelligence

journal homepage: [www.elsevier.com/locate/artint](https://www.elsevier.com/locate/artint)

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

# Relaxed core stability in hedonic games ☆

Angelo Fanelli<sup>a</sup>, Gianpiero Monaco<sup>b, c</sup>, Luca Moscardelli<sup>b, c</sup>,*

## ARTICLE INFO

**Keywords:**

Coalition formation

Hedonic games

Relaxed core stability

Efficiency of stable solutions

## ABSTRACT

The core is a well-known and fundamental notion of stability in games intended to model coalition formation such as hedonic games: an outcome is core stable if there exists no blocking coalition, i.e., no set of agents that may profit by forming a coalition together. The fact that the cardinality of a blocking coalition, i.e., the number of deviating agents that have to coordinate themselves, can be arbitrarily high, and the fact that agents may benefit only by a tiny amount from their deviation, while they could incur in a higher cost for deviating, suggest that the core is not able to suitably model practical scenarios in large and highly distributed multi-agent systems. For this reason, we consider relaxed core stable outcomes where the notion of permissible deviations is modified along two orthogonal directions: the former takes into account the size *q* of the deviating coalition, and the latter the amount of utility gain, in terms of a multiplicative factor *k*, for each member of the deviating coalition. These changes result in two different notions of stability, namely, the *q*-size core and *k*-improvement core. We consider fractional hedonic games, that is a well-known subclass of hedonic games for which core stable outcomes are not guaranteed to exist and it is computationally hard to decide non-emptiness of the core; we investigate these relaxed concepts of stability with respect to their existence, computability and performance in terms of price of anarchy and price of stability, by providing in many cases tight or almost tight bounds. Interestingly, the considered relaxed notions of core also possess the appealing property of recovering, in some notable cases, the convergence, the existence and the possibility of computing stable solutions in polynomial time.

## 1. Introduction

Group or coalition formation is an important and widely investigated issue in computer science research. In fact, in many economic, social and political settings, individuals carry out activities in groups rather than by themselves. Hedonic games (also known as a hedonic coalition formation games), introduced by Drèze and Greenber [23], are among the most important game-theoretic approaches to the study of coalition formation problems. They represent a major research challenge in the AI field of multi-agent systems. An outcome for these games is a coalition structure, which is a partition of the agents into coalitions, over which the agents have valuations. The utility that an agent gets in a coalition structure only depends on the coalition she belongs to. Hedonic games belong to the family of cooperative non-transferable utility games in which, in contrast to other transferable utility cooperative games where agents are able to freely redistribute the value of a coalition among themselves, a coalition does not choose how to allocate utilities among its members. Coalition formation was initially studied in the context of cooperative games with transferable utility,

<footnote><sup>a</sup> CNRS, LAMSADE, Université Paris Dauphine-PSL, France</footnote>

<footnote><sup>b</sup> University of Chieti-Pescara, Italy</footnote>

<footnote>☆ A preliminary version of this paper appeared in the proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI) [27].</footnote>

<footnote>* Corresponding author.</footnote>

<footnote>E-mail addresses: angelo.fanelli@cnrs.fr (A. Fanelli), gianpiero.monaco@unich.it (G. Monaco), luca.moscardelli@unich.it (L. Moscardelli).</footnote>
where each coalition has a value that has to be allocated among its members in some fair way.<fnref n="1" /> In these settings, the main focus has been on the question of how the values of smaller coalitions should determine the division of the value of the grand coalition (which is the coalition composed by all the agents) among the agents. In hedonic games, each coalition structure specifies the utility of each agent and the main focus is studying the existence and complexity of stable coalition structures (see the chapter by Aziz and Savani [7] for a more detailed discussion).

In this paper we consider Symmetric Fractional Hedonic Games (S-FHGs), introduced by Aziz et al. [3,2], that embody a natural and succinct graph representation subclass of hedonic games. In S-FHGs, each agent has a value for any other agent, and the utility that an agent gets for a coalition is the sum of the values she assigns to the members of her coalition divided by the size of the coalition. S-FHGs can model natural behavioral dynamics in social environments. Real-world examples include workers organizing themselves in work-teams, social networks in which people organize themselves in groups with the aim of maximizing the fraction of people of the same ethnic or with the same interests, politicians organizing themselves in parties with the goal of maximizing the fraction of like-minded members, countries organizing themselves in international groups, employees forming unions, etc. Moreover, even the specific setting of simple symmetric fractional hedonic games (SS-FHGs), where valuations are symmetric and can only take the values 0 and 1, suitably models a basic economic scenario referred by Aziz et al. [2] as Bakers and Millers. In this latter scenario, it is assumed that there are two types of agents, bakers and millers, where individuals of the same type are competitors, trading with agents of the other type. The valuation between any baker and any miller is 1, while the valuation between any two bakers or any two millers is 0. Both types of agents can freely choose the context in which to set up their enterprises, with this context corresponding to a coalition. Millers want to be situated in a coalition in which the ratio between purchasing bakers and competing millers is as high as possible, so as to achieve a high price for the wheat they produce. On the other hand, bakers aim at maximizing the ratio between the number of millers and the number of bakers, so as to keep the price of wheat low and that of bread up.

Among other solution concepts, core stability plays a central rule in hedonic games. An outcome is core stable if there is no subset of agents *T* whose members all prefer *T* with respect to the coalition they belong to in the outcome (the set of agents *T* is called a blocking coalition for the outcome).

It is worth noticing that the members of a blocking coalition have to coordinate in order to perform a deviation; moreover, as they may have to face some drawbacks due to the deviation, they could require a multiplicative improvement in order to accept the agreement to build a new coalition. For these reasons, in large and highly distributed multi-agent systems (including the above described real-world scenarios such as the one considering workers organizing in work-teams, the one of Backers and Millers, and so on), the core, in which it is assumed that coalitions of any size can potentially be formed and that the members of such coalitions agree to deviate even if they improve their utility by a very tiny amount, may be not able to suitably model many practical processes of coalition structure generation. Furthermore, it is well known that there are games that do not always admit core stable outcomes: even for SS-FHGs, the core may be empty. Finally, it is computationally hard in general to decide non-emptiness of the core [2] and, even in games where the existence of core stable outcomes is guaranteed, these outcomes could be very inefficient or computationally intractable.

## 1.1. Our contribution

Motivated by the downsides of core stability, in this work we propose a new natural direction of investigation, which consists in relaxing the stability constraints along two orthogonal directions, with the effect of enriching the set of admissible solutions. Specifically, our conceptual contributions are the notion of *q*-size core stability, in which the size of a blocking coalition is at most *q*, and the one of *k*-improvement core stability, in which each member of a blocking coalition increases her utility by a factor strictly greater than *k*.

The former is a notion of stability related to the one of *q*-strong Nash stability: an outcome is *q*-strong Nash stable if no subset of at most *q* agents can simultaneously deviate, where the deviating agents are not forced to form a coalition together, so as to induce a new outcome which all the *q* deviating agents prefer. We notice that an outcome which is *q*-strong Nash stable is also *q*-size core stable. *q*-strong Nash stability was considered in the context of fractional hedonic games [10] where it is shown that, for any *q* ≥ 2, *q*-strong Nash stable outcomes are not guaranteed to exist even for SS-FHG.

To the best of our knowledge, the latter notion of *k*-improvement core stability has never been investigated in the context of hedonic (non-transferable utility) games. However, it is worth discussing related notions of stability that have been considered in the context of coalition formation games with transferable utility, in which the valuation of any coalition is not agent-specific and has to be allocated among the agents belonging to the considered coalition in some fair way. Specifically, in coalition formation games with transferable utility an imputation is a distribution of utilities among all the agents such that no agent receives less than what she could get on her own, and the sum of the agents' utilities is equal to the value of the grand coalition. The core is the set of imputations such that no coalition of agents has a value greater than the sum of its members' utilities. We notice that this definition of the core differs from the one that we use in this paper that is informally described above, and here the fact that the considered games are transferable utility games or non-transferable utility games is crucial. Indeed, besides the fact that the agents' utilities are defined differently in transferable utility games and non-transferable utility games, in the former for a blocking coalition it is just required that it has a value greater than the sum of the utilities assigned by the imputation to the agents forming the blocking coalition, while

<footnote n="1">¹ A common assumption in cooperative games with transferable utility is that the valuation function is super-additive, which means that the union of two disjoint coalitions has a value greater than or equal to the sum of the values of the separate coalitions.</footnote>
in the latter in a blocking coalition it is required that each agent strictly improves her utility.<fnref n="2" /> A generalization of the core adopted in coalition formation games with transferable utility is the strong ϵ-core [40] also called ϵ-core [22], which is the set of imputations such that no coalition of agents has a value greater than the sum of its members' utilities minus ϵ. Our notion of k-improvement core stability differs from the one of strong ϵ-core because (i) in the spirit of non-transferable utility games, in the former the requested gain is for the utility of any agent, as opposed to the latter in which, in the spirit of transferable utility games, the gain is for the valuation of the whole blocking coalition and (ii) in the former the gain is given by a multiplicative factor, while in the latter by an additive one.

With respect to the last mentioned difference, we would like to spend some lines for better justifying the choice of considering a multiplicative improving factor. As already mentioned, agents may have to face some drawbacks due to the deviation; this naturally leads to the consideration that they need some incentive for accepting to deviate. In many scenarios, it could happen that it is not possible to provide a direct valuation, in terms of utility, for these drawbacks: consider for instance an agent belonging to a work-team and all the drawbacks that she has to face when changing the team (change of office, adaptation to the new job to be done, etc.). An additive incentive would mean that, regardless of how high is the utility she is experiencing in the original work-team, a fixed additive amount of utility gain would be enough for “convincing” her to deviate, while in a more realistic scenario an agent could require to have a significant utility gain (for instance in terms of percentage improvement) for compensating the above mentioned drawbacks. In other words, an additive fixed utility gain would be not able to compensate the above mentioned drawbacks, potentially not being directly valuable in terms of utility, because it would be independent of the utility the considered agent is experiencing: an improvement of one unit of utility is a big improvement (at least a 50% improvement) for agents whose utility is, say, at most 2, while it would be almost negligible for agents with much bigger utility.

We now present an example with the aim of making the introduced concept clearer.

**Example 1.** Consider the instance of Simple Symmetric Fractional Hedonic Game (SS-FHG) depicted in Fig. 1 by means of an undirected unweighted graph, in which nodes represent agents and an edge connects two nodes if the agents corresponding to its endpoints valuate 1 each other, while the symmetric valuation is 0 between agents not connected by an edge.

We can think of this instance as a model for work-teams: agents are workers and the fact that two agents *i* and *j* valuate 1 each other (we say that *i* and *j* are compatible) means that they are “happy” to work together (e.g., they are friends, or they are able to support each other in their work activities, etc). Every worker aims at maximizing the fraction of compatible workers belonging to her coalition.

We therefore have six agents and a coalition structure $S$ composed by three coalitions: the first coalition contains only agent 1, the second one contains agents 2, 3, 5, and the third one contains agents 4, 6. It can be easily checked that the agents' utilities are as follows: agent 1 (i.e., the worker corresponding to node 1) has utility 0, agents 2, 3 and 5 have utility $\frac{2}{3}$, agents 4 and 6 have utility $\frac{1}{2}$.

Notice that the coalition structure $S$ is not core stable because, for instance, agents 1, 3, 4, 6 can form a new coalition together and strictly improve their utility. However, in this deviation the blocking coalition is composed by four agents and agent 3 improves her utility from $\frac{2}{3}$ to $\frac{3}{4}$, i.e., by a factor equal to $\frac{9}{8}$. This means that these deviations can only occur, in the context of *q*-size core stability, when $q \ge 4$ and, in the context of *k*-improvement core stability, when $k < \frac{9}{8}$, i.e., when the agents do not require to improve their utility by a multiplicative factor greater than $\frac{9}{8}$.

Moreover, on the one hand, it is easily verifiable that $S$ is 2-size core stable: if we assume that at most two agents can coordinate in order to constitute a blocking coalition, then $S$ is stable. On the other hand, $S$ is not 3-size core stable since agents 1, 4, 6 can form a new coalition together and strictly improve their utility.

Finally, on the one hand, it can be verified that $S$ is $\frac{4}{3}$-improvement core stable: if we assume every agent of a blocking coalition has to improve her utility by a multiplicative factor greater than $\frac{4}{3}$ (i.e., by more than 33%), then $S$ is stable. On the other hand, $S$ is not $\frac{4}{3} - \epsilon$-improvement core stable, for any (small) $\epsilon > 0$, since agents 1, 4, 6 can form a new coalition together and improve their utility by a factor at least equal to $\frac{4}{3}$.

We investigate the considered relaxed concepts of core stability in fractional hedonic games; in this context, our results are as follows. We first focus on existential and computational aspects (Section 3), with a special focus on the convergence of relaxed core dynamics starting from any coalition structure. In fact, it is worth remarking that the convergence of such dynamics is a very appealing property in practical scenarios.

We show that, for S-FHGs, a 2-size core stable outcome always exists and can be obtained through a 2-size core dynamics (Theorem 3). However, we also show that *q*-size core dynamics are not convergent for any $q \ge 3$ (Example 6). For SS-FHGs, we strengthen the previous result by extending it to 3-size core stable outcomes, also showing that the 3-size core dynamics has polynomial length (Theorem 4).

<footnote n="2">² A further evidence of the difference between transferable utility games and non-transferable utility games has been discussed by Brânzei and Larson [15]. Specifically, they show that the core in the non-transferable utility additive separable hedonic games (in their paper called affinity games) and the core of the related transferable utility games considered by Deng and Papadimitriou [22] are different. It is worth noticing that for both games the value of a coalition is defined in a very similar way.</footnote>
<figure><img src="image_5.png" /><figcaption>Fig. 1. An instance of SS-FHG with a possible coalition structure.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 2. A 2-size core dynamics for the instance of Example 1.</figcaption></figure>

On the side of *k*-improvement core stability, we show that, for S-FHGs, a *k*-improvement core stable outcome always exists for $k \ge 2$ and can be obtained through a *k*-improvement core dynamics (Theorem 5). Moreover, although we are not able to show that such dynamics has the desirable property of polynomial length, we show that a *k*-improvement core stable outcome can be still computed in polynomial time, for any $k \ge 2(1 - 1/n)$, where *n* is the number of agents, through a simple algorithm (Theorem 6).

For SS-FHGs, we slightly strengthen the previous result by proving that a *k*-improvement core stable outcome can still be computed in polynomial time, for any $k \ge 3/2$ (Corollary 7). This latter result has been proven by showing an intriguing relation between 3-size core stable outcomes and 3/2-improvement core stable outcomes; specifically, we show that every 3-size core stable coalition structure is also 3/2-improvement core stable (Theorem 2). We remark that the reason for considering the settings of $q \le 3$ and $k \ge 3/2$ is twofold. On the one hand, they represent a necessary step for understanding the cases with higher coalition sizes or smaller improvement factor (see Section 6 for a more detailed discussion); on the other hand, they are also practically significant in themselves because, when considering small values of *q*, it is easy to obtain coordination within small-sized coalitions, while the value of $k = 3/2$ is reasonably small.

Coming back to **Example 1**, in Fig. 2 a possible 2-size core dynamics, starting from the coalition structure in which all agents are alone in singletons and ending in a 2-size core stable coalition structure, is depicted.

Moreover, in Fig. 3 a possible 3-size core dynamics, starting from the coalition structure of Fig. 1 and ending in a 3-size core stable coalition structure, is depicted. It is worth noticing that this final state, being 3-size core stable, has to be also 3/2-improvement core stable (by Theorem 2).

Finally, we focus on the efficiency of *k*-improvement core and *q*-size core stable outcomes (Section 4) with respect to the well studied utilitarian social welfare given by the sum of the utilities of all agents, in terms of core price of anarchy and core price of stability, that are the worst and the best case ratio between the social optimum and the social welfare of a core stable outcome, respectively. On the side of *k*-improvement core stability we show that, for any $k \ge 1$, in every S-FHG the core price of anarchy is at most $2k$ (Theorem 8) and that such bound is tight even for SS-FHGs (Theorem 9). Furthermore, on the side of the *q*-size core stability, we are able to prove, in Corollary 10 and Example 7, the following bounds on the core price of anarchy: For any $q \ge 2$, a tight bound equal to 4 (with the upper bound holding for S-FHGs and the lower bound holding even for SS-FHGs); for any $q \ge 3$, a tight bound equal to 3 holding for SS-FHGs. These bounds on the *q*-size core price of anarchy can be obtained as a consequence of Theorem 8 combined with the relation between 3-size core stable outcomes and 3/2-improvement core stable outcomes holding for SS-FHGs (proved in Theorem 2) and a similar relation between 2-size core stable outcomes and 2-improvement core stable outcomes holding for S-FHGs (proved in Theorem 1).

Coming back again to **Example 1**, it can be easily verified that there exist two coalition structures realizing the social optimum. They are depicted in Fig. 4 and the value of the social optimum is 4. In fact, the sum of the agent utilities in the coalition structure of Fig. 4.a all agents have utility 2/3, while in the coalition structure of Fig. 4.b the utility of agents 1, 3, 4 and 6 is 3/4 and the one of agents 2 and 5 is 1/2. Moreover, it is worth noticing that:
<figure><img src="image_7.png" /><figcaption>Fig. 3. A 3-size core dynamics for the instance of Example 1.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 4. Two coalition structures realizing the social optimum for the instance of Example 1.</figcaption></figure>

• the social welfare of the coalition structure depicted in Fig. 1 is $0 + \frac{2}{3} + \frac{2}{3} + \frac{1}{2} + \frac{2}{3} + \frac{1}{2} = 3$;

• the social welfare of the last coalition structure of the 2-core dynamics depicted in Fig. 2 is $\frac{1}{2} + \frac{1}{2} + 0 + 0 + \frac{1}{2} + \frac{1}{2} = 2$ (notice that by the upper bound of 4 to the 2-size core price of anarchy it had to be at least $\frac{4}{3} = 1$);

• the social welfare of the last coalition structure of the 3-core dynamics depicted in Fig. 3 is 4, as this coalition structure is an optimal one (notice that by the upper bound of 3 to the 3-size core price of anarchy it had to be at least $\frac{4}{3}$).

As to the core price of stability, we discuss at the beginning of Section 4.2 the implications of previous results (provided both in this paper and in previous work) on the core price of stability, with a special focus on the determination of suitable upper bounds. For the case of *k*-improvement core stability, it turns out that the core price of stability is 1 for any $k \ge 2$; we therefore focus on the case of $k \in (1, 2)$ and we provide in Theorems 11 and 12 non-trivial lower bounds to the *k*-improvement core price of stability, showing that it is strictly greater than 1. Moreover, we show in Theorem 13 that this is the case also for *q*-size core price of stability, for any $q \ge 3$. Concerning the 2-size core price of stability, even determining whether it is equal to 1 or greater than 1 is a challenging open question.

Our results are summarized in Table 1. We remind that the convergence implies the existence. Moreover, on the one hand, if the convergence and/or the existence is guaranteed for S-FHG then it is also guaranteed for SS-FHG, and, on the other hand, if the convergence and/or the existence is not guaranteed for SS-FHG then it is also not guaranteed for S-FHG. Similarly, an upper bound to the core price of anarchy or stability for S-FHG also holds for SS-FHG and a lower bound to the core price of anarchy or stability for SS-FHG also holds for S-FHG.

Finally, in Section 5, we have performed an experimental evaluation on classical and relaxed core dynamics which is able to show how the introduced notions of stability perform, in terms of the speed of convergence, on random generated instances.

## 1.2. Related work

Hedonic games, which are non-transferable utility games, have been introduced by Drèze and Greenber [23] and then further developed [9,11,18]. Work on hedonic games mainly studies the existence, computation and performance of stable solutions, i.e., solutions where no agent or group of agents has interest in deviating from the outcome (see the book chapter by Aziz and Savani [7] for a nice survey on the topic). In this paper we consider core stability in the setting of fractional hedonic games, i.e., a well studied special class of hedonic games in which every agent valuates a coalition with the average utility she ascribes to its members. In the following, we frame this specific class of games in the more general context of hedonic games, also comparing it with other related classes.
<caption>**Table 1**</caption>

Conv. stands for convergence, Exist. stands for existence, CPoA stands for Core Price of Anarchy and CPoS stands for Core Price of Stability. q-size stands for q-size core stability and k-imp. stands for k-improvement core stability. ✓(resp. X) indicates that the convergence or the existence is guaranteed (resp. not guaranteed). (P) indicates that the number of steps, needed for convergence, in the dynamics or the complexity of computing the corresponding relaxed core stable outcome is polynomial. ε > 0 is an infinitely small positive number.

<table><thead><tr><th></th><th>S-FHG</th><th>SS-FHG</th></tr></thead><tbody><tr><td>Conv.</td><td>✓ 2-size (Theorem 3)<br>X q-size, q ≥ 3 (Ex 6)<br>✓ k-imp., k ≥ 2 (Theorem 5)</td><td>✓ (P) q-size, q ≤ 3 (Theorem 4)</td></tr><tr><td>Exist.</td><td>✓ 2-size (Theorem 3)<br>✓ (P) k-imp., k ≥ (2 - 2/n) (Theorem 6)</td><td>✓ (P) q-size, q ≤ 3 (Theorem 4)<br>✓ (P) k-imp., k ≥ 3/2 (Corollary 7)</td></tr><tr><td>CPoA</td><td>q-size ≤ 4, q ≥ 2 (Corollary 10)<br>k-imp. ≤ 2k, k ≥ 1 (Theorem 8)</td><td>q-size ≥ 4 - ε, q ≥ 2 (Ex 7)<br>q-size ≤ 3, q ≥ 3 (Corollary 10)<br>q-size ≥ 3 - ε, q ≥ 3 (Ex 7)<br>k-imp. ≥ 2k - ε, k ≥ 1 (Theorem 9)</td></tr><tr><td>CPoS</td><td>k-imp. = 1, k ≥ 2 (Theorem 5)</td><td>q-size > 1, q ≥ 3 (Theorem 13)<br>k-imp. = 1, k ≥ 2 (Theorem 5)<br>k-imp. > 1, k ∈ (1, 2) (Theorem 11, 12)</td></tr></tbody></table>

Additively separable hedonic games (ASHGs) constitute a natural and succinctly representable class of hedonic games. They can be represented by a weighted graph, where the set of agents coincides with the set of vertices and the utility that an agent gets in a coalition is simply the sum of the weights of the edges adjacent to the agent in the subgraph induced by the coalition. Properties guaranteeing the existence of stable allocations for ASHGs have been studied in several papers [9,11] as well as computational complexity issues [4,8,31,35,37]. A very recent paper by Brandt, Bullinger and Tappe [13] performs a deep study on dynamical aspects of single agent deviations leading to the formation of stable outcomes.

Fractional hedonic games (FHGs), i.e., the setting considered in this paper, are similar to ASHGs, with the difference that the utility of an agent is divided by the number of agents of the coalition. FHGs have been introduced by Aziz et al. [3,2]. They show that the core can be empty even for the special case of simple and symmetric valuations SS-FHG, but that it is not empty for very specific sub-classes. The authors also show that it is computationally hard in general to decide the non-emptiness of the core. Subsequent work [12] considers various computational results for core and individual stability as well as the convergence of simple dynamics based on individual stability [14]. Local core stability [17] deals with structural constraint on the blocking coalition, that is, the subgraph induced by the blocking coalition must be a clique. Studies on FHGs [10] also analyze the existence, efficiency and computational complexity of Nash and strong Nash equilibria. It is worth mentioning that a q-strong Nash stable outcome is also q-size core stable. However, it is known that [10] for any q ≥ 2, q-strong Nash stable outcomes are not guaranteed to exist even for SS-FHG. Notice that this result gives an additional motivation for studying the existence of 2-size core stable outcomes. Improved results about the Nash price of stability have been performed by Kaklamanis et al. [32]: they consider S-FHGs and show a slightly higher lower bound to the price of stability for general graph and that the price of stability is 1 for graphs of girth at least 5.

Aziz et al. [6] study the computational complexity of computing optimal coalition structures for FHGs. Specifically, they show that maximizing utilitarian social welfare, egalitarian social welfare, or Nash social welfare is NP-hard, even for SS-FHG and provide polynomial time approximation algorithms. Several papers [29,30,41] also deal with strategyproof mechanisms for proper subclass of ASHGs, ASHGs and FHGs. A recent paper by Fioravanti et al. [28] considers a relaxed version (but different than the one we consider in this paper) of the core in SS-FHG which is called ε-fractional core stability where it is allowed that at most an ε fraction of coalitions may core-block it.

Modified fractional hedonic games (MFHGs), introduced by Olsen [36], are very similar to fractional ones. The only difference is that the utility of an agent is averaged over all other members of that coalition, i.e., excluding herself. Despite this apparently small difference, stable outcomes such as Nash, strong Nash, and core stable perform very differently in MFHGs with respect to FHGs [34]. Algorithms for finding Pareto optimal solutions in ASHGs, FHGs and MFHGs are also studied [16] as well as the price of Pareto optimal which is an analogue of the price of anarchy for Nash equilibria, with the worst Nash equilibrium replaced with the worst Pareto optimal outcome [24].

Coalition formation games with transferable utility are also well-studied in the literature [5,19,21,25,38,39]. The following setting of coalition formation games with transferable utility has been introduced by Deng and Papadimitriou [22] and it is the most related one to our setting: they consider a weighted undirected graph where each node is an agent and the value of a coalition is defined as the sum of the weights of edges belonging to the subgraph induced by the members of the coalition. In this setting, an imputation is a distribution or an assignment of utilities among all the agents of the value of the grand coalition (which is the coalition composed by all the agents) and the core is the set of imputations such that no coalition of agents has a value greater than the sum of its members' utilities. Deng and Papadimitriou [22] characterize the core, the ε-core and also other solution concepts from the point of view of computational complexity. We notice that, while in this setting one of the main problems is to decide how to distribute the value of the grand coalition among all the agents in order to get some reasonable fair property (e.g., the non-emptiness of the core), in our setting the utility that an agent gets in a coalition structure only depends on the coalition she belongs to and, in general, for different
coalition structures an agent gets different utilities. The main focus in our setting is studying the existence and complexity of stable
coalition structures (e.g. the core).

**2. Model and preliminaries**

For any $n \in \mathbb{N}$, we denote by $[n]$ the set $\{1, 2, \dots, n\}$.

A Symmetric Fractional Hedonic Game (S-FHG) $G = (N, (v_i)_{i \in N})$ is a game in which each agent $i \in N$, where $N = [n]$, has a valuation $v_i : N \to \mathbb{R}^{\ge 0}$, mapping every agent to a real non-negative value. We assume that the number of agents is $n \ge 2$. We denote with $v_i^{\max}(G) = \max_{j \in N} v_j(j)$ the maximum valuation of agent $i$ for any other agent $j \in N$ in the game $G$. We assume that $v_i(i) = 0$ for every $i \in N$ and that the valuations are symmetric, i.e., $v_i(j) = v_j(i)$ for every $i, j \in N$.

If it holds that $v_i(j) \in \{0, 1\}$ for every $i, j \in N$, we say that the game is a *Simple Symmetric Fractional Hedonic Game* (SS-FHG).

**Graph representation** An S-FHG has a very intuitive graph representation. In fact, it can be expressed by a weighted graph $G = (N, E, w)$, where nodes in $N$ represent the agents, and undirected edges are associated to non-null valuations. Namely, for any $i, j \in N$, if $v_i(j) > 0$, an edge $\{i, j\}$ of weight $w(\{i, j\}) = v_i(j) = v_j(i)$ belongs to $E$. Analogously, an SS-FHG can be expressed by an unweighted graph $G = (N, E)$ in which, for any $i, j \in N$, edge $\{i, j\}$ belongs to $E$ if and only if $v_i(j) = 1$. Given a subset of agents $C \subseteq N$, we denote with $G(C)$ the subgraph of $G$ induced by agents in $C$.

**Coalitions and utilities** A coalition is a non-empty subset of $N$. The set of all agents $N$ is also called the *grand coalition*, and a coalition of size 1 is called a *singleton coalition*. Given a coalition $C$ and any agent $i \in C$, let $\delta_C(i) = \sum_{j \in C} v_i(j)$ be the sum of valuations of agent $i$ for every agent belonging to coalition $C$. In graph-theoretic terms, $\delta_C(i)$ corresponds to the (weighted) degree of node $i$ in graph $G(C)$. The *utility* or *payoff* $\mu_i(C)$ of agent $i$ in coalition $C$ such that $i \in C$ is equal to $\delta_C(i)$ divided by the total number of agents in the coalition, that is $\mu_i(C) = \frac{\delta_C(i)}{|C|}$. Notice that $\mu_i(C) \le \frac{|C|-1}{|C|} v_i^{\max}(G) \le \frac{n-1}{n} v_i^{\max}(G)$ for any agent $i \in N$ and coalition $C$ of a game $G$. An outcome of the game is a *coalition structure* $S = \{C_1, \dots, C_h\}$. $S$ is a partition of the agents into $h$ coalitions, that is, $\cup_{t \in [h]} C_t = N$ and $C_i \cap C_p = \emptyset \ \forall t, p \in [h]$, with $t \ne p$. We denote by $S(i)$ the coalition agent $i$ belongs to in coalition structure $S$. The utility $\mu_i(S(i))$ of an agent $i$ in coalition structure $S$ is also denoted by $\mu_i(S)$.

**Core stability** Given a coalition structure $S$, a *blocking coalition* for $S$ is a set of agents $C \subseteq N$ such that, for every agent $i \in C$, it holds that $\mu_i(C) > \mu_i(S)$. Since $v_i(j) \ge 0$ and $v_i(i) = 0$ for every $i, j \in N$, we have that $|C| \ge 2$. A coalition structure $S$ is *core stable* if it does not admit a blocking coalition. We relax the definition of core stability along two directions: (i) given an integer $q \ge 2$, a *q-size blocking coalition* for $S$ is a blocking coalition in which $|C| \le q$ and (ii) given a real number $k \ge 1$, a *k-improvement blocking coalition* for $S$ is a set of agents $C \subseteq N$ such that, for every agent $i \in C$, it holds that $\mu_i(C) > k\mu_i(S)$. Notice that a blocking coalition is also a 1-improvement blocking coalition and an *n-size blocking coalition*. A coalition structure $S$ is *q-size core stable* (respectively *k-improvement core stable*) if it does not admit a *q-size blocking coalition* (respectively a *k-improvement blocking coalition*). We notice that if a coalition structure is *q-size core stable* then it is *q'-size core stable* for any $q' \le q$. Moreover, if a coalition structure is *k-improvement core stable* then it is *k'-improvement core stable* for any $k' \ge k$.

**Dynamics and convergence** The core (respectively *q-size core* and *k-improvement core*) *dynamics* $D$ of a S-FHG is a sequence (possibly infinite) of coalition structures $\langle S^0, S^1, \dots \rangle$ such that for every consecutive pair $(S^{t-1}, S^t)$, with $t \ge 1$, there exists a blocking coalition (respectively *q-size blocking coalition* and *k-improvement blocking coalition*) $C^t$ for $S^{t-1} = \{C_1, C_2, \dots, C_h\}$ and $S^t = \{C^t, C_1 \setminus C^t, \dots, C_h \setminus C^t\} \setminus \{\emptyset\}$. Roughly speaking, the coalition structure $S^t$ is obtained by letting all agents in $C^t$ form a new coalition together, thus leaving the coalitions they belonged to in $S^{t-1}$. We say that agents in the blocking coalition $C^t$ perform a *deviation* and that a *finite dynamics* $D = \langle S^0, S^1, \dots, S^\ell \rangle$ of length $\ell \ge 1$, leads to coalition structure $S^\ell$ starting from the initial coalition structure $S^0$. A game is core (respectively, *q-size core* and *k-improvement core*) *convergent* if, for any coalition structure $S$, every dynamics starting from $S$ is finite.

**Social welfare** The social welfare of a coalition structure $S = \{C_1, \dots, C_h\}$ is given by the sum of the agent utilities, i.e., $SW(S) = \sum_{i \in N} \mu_i(S)$. By extending the previous definition, given a coalition $C$, we denote by $SW(C)$ the sum of utilities of the agents belonging to $C$. Notice that $SW(S) = \sum_{C \in S} SW(C) = \sum_{C \in S} \sum_{i \in C} \mu_i(C)$.

**Efficiency** Given a game $G$, the *optimal outcome* $S^*(G)$ is the one maximizing the social welfare; let *qSIZE CORE*($G$) and *k-IMPR CORE*($G$) be the set of coalition structures that are *q-size core stable* and *k-improvement core stable*, respectively. We use the widely adopted concepts of price of anarchy [33] and price of stability [1] to measure the efficiency of stable outcomes. The *q-size core price of anarchy* (respectively *k-improvement core price of anarchy*) of a symmetric fractional hedonic game $G$ is defined as the ratio between the social welfare of the optimal outcome $C^*(G)$ and the one of the worst *q-size core stable* (respectively *k-improvement core stable*) outcome. Formally, $\text{qSIZE CPOA}(G) = \max_{C \in \text{qSIZE CORE}(G)} \frac{SW(S^*(G))}{SW(C)}$ (respectively $\text{k-IMPR CPOA}(G) = \max_{C \in \text{k-IMPR CORE}(G)} \frac{SW(S^*(G))}{SW(C)}$). Analogously, the *q-size core price of stability* (respectively *k-improvement core price of stability*) of a symmetric fractional hedonic game $G$ is defined as the ratio between the social welfare of the optimal outcome $C^*(G)$ and the one of the best *q-size core stable* (respectively *k-improvement core stable*) outcome. Formally, $\text{qSIZE CPOS}(G) = \min_{C \in \text{qSIZE CORE}(G)} \frac{SW(S^*(G))}{SW(C)}$ (respectively $\text{k-IMPR CPOS}(G) = \min_{C \in \text{k-IMPR CORE}(G)} \frac{SW(S^*(G))}{SW(C)}$).
<figure><img src="image_9.png" /><figcaption>Fig. 5. The instance $\mathcal{G}$ of S-FHG used in Example 2.</figcaption></figure>

**Example 2.** While in Example 1 we have presented a Simple Symmetric Fractional Hedonic Game (SS-FHG), in this example, with the additional aim of making the reader familiar with the notation, we deal with the more general setting of Symmetric Fractional Hedonic Games (S-FHGs), i.e., we present an hedonic game having as graph representation a weighted symmetric graph.

Consider the instance of S-FHG depicted in Fig. 5.a, in which there are six agents and a coalition structure $S$ composed by two coalitions: the first coalition contains agents 1, 4 and 5, while the second one contains agents 2, 3 and 6. It can be easily checked that the agents' utilities are as follows: for the first coalition we have $\mu_1(S) = \frac{4}{3}$, $\mu_4(S) = 1$, $\mu_5(S) = \frac{5}{3}$ and, for the other coalition, $\mu_3(S) = \frac{2}{3}$ and $\mu_2(S) = \mu_6(S) = \frac{1}{2}$. It follows that $SW(S) = \sum_{i=1}^6 \mu_i(S) = \frac{16}{3}$.

It is worth noticing that $S$ is 2-size core stable, i.e., no couple $\{i, j\}$ of nodes (with $i, j \in [6]$ and $i \neq j$) can form a blocking coalition for $S$: in fact, if $\{i, j\} \notin E$, then, trivially, $i$ and $j$ cannot have an incentive to form a new coalition together, while otherwise it can be verified that, for every edge $\{i, j\} \in E$ it holds that $\mu_i(S) \ge \frac{w((i, j))}{2}$ and/or $\mu_j(S) \ge \frac{w((i, j))}{2}$. Moreover, notice that the coalition structure $S$ is not 3-size core stable because, agents 1, 2 and 5 can form a new coalition together and strictly improve their utility. By considering the same deviation, $S$ is not $\frac{6}{5}-\epsilon$-improvement core stable for any (small) $\epsilon > 0$, given that agents 1, 2, and 5 would improve her utility from $\frac{4}{3}$ to $\frac{5}{3}$, from $\frac{1}{3}$ to $\frac{5}{3}$, and from $\frac{5}{3}$ to 2, respectively (notice that $\frac{2}{3} = \frac{6}{5}$).

Finally, it can be verified that the only optimal coalition structure $S^*$ is the one depicted in Fig. 5.b: $S^* = \{\{1, 2, 4, 5\}, \{3, 6\}\}$ and $SW(S^*) = \frac{13}{2}$, because it holds that $\mu_1(S^*) = \frac{3}{2}$, $\mu_2(S^*) = \frac{5}{4}$, $\mu_4(S^*) = \frac{3}{4}$, $\mu_5(S^*) = 2$ and $\mu_3(S^*) = \mu_6(S^*) = \frac{1}{2}$.

## 2.1. Preliminary results

In this section we present some preliminary results about the relation between $q$-size core stable and $k$-improvement core stable coalition structures. The first result highlights an interesting relation between 2-size core stable and 2-improvement core stable coalition structures. Specifically, we show that, for every S-FHG, any 2-size core stable coalition structure is 2-improvement core stable.

**Theorem 1.** For every S-FHG, any 2-size core stable coalition structure is 2-improvement core stable.

**Proof.** Given an S-FHG $\mathcal{G}$, let us assume that $S$ is a 2-size core stable coalition structure of $\mathcal{G}$. Let us suppose, by contradiction, that $S$ admits a 2-improvement blocking coalition $C$. Let $v_{max}^C = v_i(j)$, for some $i, j \in C$, be the maximum valuation of two agents in $C$, that is, $v_{max}^C = \max_{i \in C} v_i^{max}(\mathcal{G}(C))$ where $\mathcal{G}(C) = (C, (v_i)_{i \in C})$ is the game $\mathcal{G}$ restricted to agents in $C$. We notice that $\mu_i(C) \le \frac{|C|-1}{|C|} v_{max}^C$ and that $\mu_j(C) \le \frac{|C|-1}{|C|} v_{max}^C$. This implies that the utility of agents $i$ and $j$ in $S$ is at most $\frac{1}{2} \frac{|C|-1}{|C|} v_{max}^C$ (because agents $i$ and $j$ belong to the 2-improvement blocking coalition $C$). However, in this case agents $i$ and $j$ represent a 2-size blocking coalition for $S$. In fact, by forming a coalition together, each of them gets utility of $\frac{1}{2} v_{max}^C > \frac{1}{2} \frac{|C|-1}{|C|} v_{max}^C$. This is a contradiction to the fact that $S$ is a 2-size core stable coalition structure of $\mathcal{G}$. $\square$

We now show that the analysis of Theorem 1 is tight even for SS-FHG. To this aim, given any $\epsilon > 0$, in the following example we show an instance of SS-FHG where a 2-size core stable coalition structure is not $k$-improvement core stable for any $k < 2 - \epsilon$.

**Example 3.** Consider the instance of SS-FHG given by an unweighted clique with an even number of nodes $n$. It is easy to see that the coalition structure $S$ induced by a perfect matching (where, for each edge $\{i, j\}$ of the perfect matching, we have a coalition $C = \{i, j\}$), where each agent gets utility of $\frac{1}{2}$, is 2-size core stable. Moreover, in the grand coalition each agent gets utility of $\frac{n-1}{n}$. Thus, for any $n \ge \frac{2}{\epsilon}$, it holds that $k < 2 - \epsilon < 2(1 - 1/n)$, thus implying that the grand coalition is a $k$-improvement blocking coalition for $S$.

We also show that, for every SS-FHG, any 3-size core stable coalition structure is $\frac{3}{2}$-improvement core stable.

**Theorem 2.** For every SS-FHG, any 3-size core stable coalition structure is $\frac{3}{2}$-improvement core stable.
**Proof.** In this proof we exploit the graph representation of simple symmetric fractional hedonic games introduced in Section 2; since we are considering SS-FHG, the related graph $G$ is unweighted. Given an SS-FHG $G$, let us assume that $S$ is a 3-size core stable coalition structure of $G$. Let us suppose, by contradiction, that $S$ admits a $\frac{3}{2}$-improvement blocking coalition $C$. Remind that $\mu_i(C) \le \frac{n-1}{n}$ for any $i \in C$. First notice that, for any $i \in C$, it holds that $\mu_i(S) < \frac{2}{3}$ (because they belong to the $\frac{3}{2}$-improvement blocking coalition $C$ and in any coalition structure each agent gets utility of at most $\frac{n-1}{n}$). It implies that the subgraph $G(C)$ induced by agents in $C$ does not contain a triangle. In fact, if three agents of a triangle form a new coalition together, each of them gets utility of $\frac{2}{3}$ and this is a contradiction to the fact that $S$ is a 3-size core stable coalition structure of $G$.

Consider any edge $\{i, j\}$ in $G(C)$. It holds that either $\mu_i(S) \ge \frac{1}{2}$ or $\mu_j(S) \ge \frac{1}{2}$ because otherwise $i$ and $j$ together form a 2-size blocking coalition for $S$, and this is a contradiction to the fact that $S$ is a 3-size core stable coalition structure of $G$. Without loss of generality, let us assume that $\mu_i(S) \ge \frac{1}{2}$. Then, since $i$ belongs to $C$, we have that $\mu_i(C) > \frac{3}{2} > \frac{1}{2} = \frac{3}{4}$. It implies that agent $i$ has more than three adjacents in $G(C)$. We now show an upper bound to the utility of each agent $j$ adjacent to $i$ in $G(C)$. Given that $G(C)$ does not contain triangles, any pair of adjacents of $i$ is not connected by an edge. Let $x$ be the number of agents connected to $i$ in $G(C)$. We have that $\mu_i(C) = \frac{x}{|C|} > \frac{3}{4}$. Thus, any agent $j$ connected to $i$ in $G(C)$ gets utility of at most $\frac{|C|-x}{|C|} < \frac{1}{4}$. Since $j$ is a member of the $\frac{3}{2}$-improvement blocking coalition $C$, we get that $\mu_j(S) < \frac{1}{6}$.

By summarizing, there must exist two agents $j$ and $z$ that together with $i$ form in $G$ a star of three nodes centered in $i$ such that $\mu_j(S) < \frac{1}{6}$, $\mu_z(S) < \frac{1}{6}$ and $\mu_i(S) < \frac{2}{3}$. Therefore, agents $i, j$ and $z$ together form a 3-size blocking coalition for $S$. This is a contradiction to the fact that $S$ is a 3-size core stable coalition structure of $G$. $\square$

We show that the analysis of Theorem 2 is tight, that is, in the following example, given any $\epsilon > 0$, we show an instance of SS-FHG where a 3-size core stable coalition structure is not $k$-improvement core stable for any $k < 3/2 - \epsilon$.

**Example 4.** Consider the instance of SS-FHG given by an unweighted clique of $n$ nodes such that $n \mod 3 = 0$. It is easy to see that the coalition structure $S$ induced by a partition of the graph into triangles (for each triangle $\{i, j, z\}$ of the partition, we have a coalition $C = \{i, j, z\}$), where each agent gets utility of $\frac{2}{3}$, is 3-size core stable. Moreover, in the grand coalition each agent gets utility of $\frac{n-1}{n}$. Thus, for any $n \ge \frac{3}{2\epsilon}$, it holds that $k < 3/2 - \epsilon < 3/2(1 - 1/n)$, thus implying that the grand coalition is a $k$-improvement blocking coalition for $S$.

We conclude this section by showing that the converses of Theorem 1 and Theorem 2 do not hold. Specifically, in the following example we show a simple instance of SS-FHG admitting a coalition structure $S$ which is $\frac{5}{4}$-improvement core stable but not 2-size core stable. Since it holds that (i) if $S$ is $\frac{5}{4}$-improvement core stable then it is $k$-improvement core stable for any $k \ge \frac{5}{4}$ and (ii) if $S$ is not 2-size core stable then it is not $q$-size core stable for any $q \ge 2$, this example implies that the converses of Theorem 1 and Theorem 2 do not hold.

**Example 5.** Consider the instance of SS-FHG given by an unweighted path $(i_1, i_2, i_3, i_4, i_5)$ of 5 agents. We claim that the grand coalition $S$ is 5/4-improvement core stable. Indeed, in $S$, each of the two “external” agents $i_1$ and $i_5$ gets utility of 1/5, while the other “internal” ones $i_2, i_3$ and $i_4$ get utility of 2/5 each. If there exists a $k$-improvement (for some $k \ge 1$) blocking coalition $C$ for $S$, it must contain an internal agent who gets utility of at most 1/2 in $C$. This implies that $S$ is $k$-improvement core stable for any $k \ge 5/4$. However, any two agents connected by an edge of the path form a $q$-size blocking coalition for $S$ for any $q \ge 2$.

### 3. Existence and computation

In this section, we focus on existence and convergence issues of relaxed core solutions. We start by showing that any 2-size dynamics of every S-FHG converges to a stable solution.

**Theorem 3.** Every S-FHG is 2-size core convergent.

**Proof.** Consider any 2-size core dynamics $D$ starting from any coalition structure $S^0$. We show that $D = \langle S^0, S^1, \dots \rangle$ has finite length, i.e., that a 2-size core stable coalition structure is eventually reached. For any $t \ge 1$, let $C^t$ be the blocking coalition (i.e., the set of two agents) performing the $t$-th 2-size core deviation of the dynamics $D$, leading from coalition structure $S^{t-1}$ to $S^t$, and let $N^t = \bigcup_{p=1}^t C^p$ be the set of all agents involved in some of the first $t$ improvement deviations of $D$. Notice that, for any $t \ge 1$, all agents in $C^t$ will belong to a coalition of cardinality at most 2 in any coalition structure $S^p$ with $p \ge t$. For any $t \ge 0$ and any agent $i \in N$, let

$$ \eta_i^t = \begin{cases} 0 & \text{if } i \notin N^t \\ \mu_i(S^t) & \text{otherwise.} \end{cases} $$

Moreover, for any $t \ge 0$, let $\bar{x}^t$ be the vector obtained by listing $\eta_i^t$ (for all $i \in N$) in non-increasing order. As usual, given two $n$-dimensional vectors $\bar{y}$ and $\bar{y}'$, we say that the first one is smaller than the second one for the lexicographical order (and we write $\bar{y} < \bar{y}'$) if either $y_p$ is a prefix of $y'_p$ or $y_p < y'_p$ for the first component $p$ such that $y_p \ne y'_p$.
<figure><img src="image_10.png" /><figcaption>Fig. 6. The instance considered in Example 6.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Fig. 7. The cycle in the 3-size core dynamics.</figcaption></figure>

It holds, for any $t \ge 1$, that $\vec{x}^{t-1} < \vec{x}^t$, i.e., the considered vector always lexicographically increases after each deviation. In order to prove this property, we have to consider all agents $i \in N$ such that $\eta_i^t \ne \eta_i^{t-1}$. In fact, consider for any $t \ge 1$ any agent $i \in C^t$: clearly, $\eta_i^t > \eta_i^{t-1}$ because either $i \notin N^{t-1}$, and in this case it trivially holds that $\eta_i^t = \mu_i(S^t) > 0 = \eta_i^{t-1}$, or $i \in N^{t-1}$ and also in this case it holds $\eta_i^t = \mu_i(S^t) > \mu_i(S^{t-1}) = \eta_i^{t-1}$ given that every agent in $C^t$ improves her utility. It remains to deal with any $i \in N \setminus C^t$ such that $\eta_i^t \ne \eta_i^{t-1}$: first of all, notice that $i \in N^{t-1}$, because otherwise $\eta_i^t = \eta_i^{t-1} = 0$; furthermore, it is easy to see that agent $i$ is canceling her utility out, i.e., $\mu_i(S^t) = 0 < \mu_i(S^{t-1})$, because $i$ has to belong, in $S^{t-1}$, to a coalition of 2 agents in which with the other node, say $j$, belongs to $C^t$. Even if $\eta_i^t = \mu_i(S^t) = 0 < \mu_i(S^{t-1}) = \eta_i^{t-1}$, it still holds that $\vec{x}^{t-1} < \vec{x}^t$ because there exists node $j$ such that $\eta_j^t > \eta_j^{t-1} = \eta_i^{t-1}$.

We have proven that vectors $\vec{x}^t$, for $t \ge 1$, lexicographically increase after each deviation; since the set of possible vectors is finite, the claim directly follows. $\square$

As shown by the following example, the situation is different for *q*-size core dynamics with $q \ge 3$ in S-FHGs, for which the convergence cannot be guaranteed.

**Example 6.** Consider the instance of S-FHG depicted in Fig. 6, given by a weighted graph with 4 nodes and 4 edges. We claim that there exists a 3-size core dynamics admitting a cycle. The cycle is presented in Fig. 7. The first outcome $S^0$ of the dynamics is the one depicted in Fig. 7a. The second outcome $S^1$ of the dynamics is depicted in Fig. 7b and is obtained from $S^0$ by a deviation of the blocking coalition {2, 4}: in fact, $\mu_2(S^1) = 6 > 5 = \mu_2(S^0)$ and $\mu_4(S^1) = 6 > 4 = \mu_4(S^0)$. The third outcome $S^2$ of the dynamics is depicted in Fig. 7c and is obtained from $S^1$ by considering the blocking coalition {1, 2, 3}: in fact, $\mu_1(S^2) = 3 > 0 = \mu_1(S^1)$, $\mu_2(S^2) = \frac{19}{3} > 6 = \mu_2(S^1)$ and $\mu_3(S^2) = \frac{10}{3} > 0 = \mu_3(S^1)$. Finally, $S^0$ can be obtained from $S^2$ by considering the blocking coalition {1, 4}: in fact, $\mu_1(S^0) = 4 > 3 = \mu_1(S^2)$ and $\mu_4(S^0) = 4 > 0 = \mu_4(S^2)$.

We are also able to provide a similar result holding for 3-size dynamics in the context of simple games (i.e., games with valuations in {0, 1}).

**Theorem 4.** Every SS-FHG is 3-size core convergent within a polynomial number of deviations.

**Proof.** In this proof, it is convenient to exploit the graph representation of simple symmetric fractional hedonic games introduced in Section 2; since we are considering SS-FHGs, the related graphs are unweighted. Consider any 3-size core dynamics $D$ starting from any coalition structure $S^0$. We show that $D = \langle S^0, S^1 \dots \rangle$ has finite length, i.e., that a 3-size core stable coalition structure is eventually reached. For any $t \ge 1$, let $C^t$ be the 3-size blocking coalition for $S^{t-1}$ whose deviation leads to $S^t$. It is worth noticing that, for any $t \ge 1$, $G(C^t)$ is (i) either to a triangle (i.e., a clique of 3 nodes), (ii) a path of 3 nodes, or (iii) a clique of 2 nodes.

Given any coalition structure $S$, let $\alpha(S)$ (respectively $\beta(S)$ and $\gamma(S)$) be the number of coalitions in $S$ being triangles (respectively path of 3 nodes and cliques of 2 nodes).

For any $t \ge 0$, let $N^t \subseteq N$ be the set of all agents not belonging, in coalition structure $S^t$, to coalitions being either a triangle, a path of 3 nodes, or a clique of 2 nodes. Moreover, for any $t \ge 0$, let $\vec{x}^t$ be the triple defined as $(\alpha(S^t), \beta(S^t) + \gamma(S^t), \beta(S^t))$. As usual, given two 3-dimensional vectors $\vec{y}$ and $\vec{y}'$, we say that the first one is smaller than the second one for the lexicographical order (and we write $\vec{y} < \vec{y}'$) if $y_p < y'_p$ for the first component $p$ such that $y_p \ne y'_p$.
<figure><img src="image_12.png" /><figcaption>Fig. 8. Deviation in which $G(C^t)$ is a path of 3 nodes with $i$ being the node of degree 2, and $G(S^{t-1}(i))$ is a clique of 2 nodes.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Fig. 9. Deviation in which $G(C^t)$ is a path of 3 nodes with $i$ being the node of degree 2, and also $G(S^{t-1}(i))$ is a path of 3 nodes.</figcaption></figure>

<figure><img src="image_14.png" /><figcaption>Fig. 10. Deviation in which $G(C^t)$ is a clique of 2 nodes $i$ and $j$, $i \in N^{t-1}$ and $G(S^{t-1}(j))$ is a path of 3 nodes.</figcaption></figure>

It holds, for any $t \ge 0$, that $\vec{x}^{t-1} < \vec{x}^t$, i.e., the considered triple always lexicographically increases after each deviation. In order to prove this property, we consider, for any $t \ge 1$, the following disjoint cases:

• $G(C^t)$ is a triangle, with all nodes corresponding to agents having utility $\frac{2}{3}$ in coalition $C^t$.

In this case, $\alpha(S^t) = \alpha(S^{t-1}) + 1$ and therefore the first component of triple $\vec{x}^t$ is greater than the one of triple $\vec{x}^{t-1}$, thus implying that $\vec{x}^{t-1} < \vec{x}^t$.

• $G(C^t)$ is a path of 3 nodes, with agent $i$ being the one connected to both the other agents $j$ and $j'$. It holds that $\mu_i(C^t) = \frac{2}{3}$ and $\mu_j(C^t) = \mu_{j'}(C^t) = \frac{1}{3}$.

Notice that the utility $\mu_i(S^{t-1})$ of agent $i$ in coalition structure $S^{t-1}$ has to be less than $\frac{2}{3}$ and that $\mu_j(S^{t-1})$ and $\mu_{j'}(S^{t-1})$ have to be less than $\frac{1}{3}$. Therefore, it holds that $j, j' \in N^{t-1}$ and we have to consider the following disjoint subcases depending on the coalition agent $i$ belongs to in $S^{t-1}$.

- $i \in N^{t-1}$. In this case, $\alpha(S^t) = \alpha(S^{t-1})$, $\beta(S^t) = \beta(S^{t-1}) + 1$ and $\gamma(S^t) = \gamma(S^{t-1})$; therefore, the second component of triple $\vec{x}^t$ is greater than the one of triple $\vec{x}^{t-1}$ while the other components are equal, thus implying that $\vec{x}^{t-1} < \vec{x}^t$.

- $G(S^{t-1}(i))$ is a clique of 2 nodes (see Fig. 8). In this case, $\alpha(S^t) = \alpha(S^{t-1})$, $\beta(S^t) = \beta(S^{t-1}) + 1$ and $\gamma(S^t) = \gamma(S^{t-1}) - 1$; therefore, the third component of triple $\vec{x}^t$ is greater than the one of triple $\vec{x}^{t-1}$ while the other components are equal, thus implying that $\vec{x}^{t-1} < \vec{x}^t$.

- $G(S^{t-1}(i))$ is a path of 3 nodes, with $\mu_i(S^{t-1}) = \frac{1}{3}$ (see Fig. 9). In this case, since $G(S^{t-1}(i) \setminus \{i\})$ is a clique of 2 nodes, we obtain that $\alpha(S^t) = \alpha(S^{t-1})$, $\beta(S^t) = \beta(S^{t-1})$ and $\gamma(S^t) = \gamma(S^{t-1}) + 1$; therefore, the second component of triple $\vec{x}^t$ is greater than the one of triple $\vec{x}^{t-1}$ while the other components are equal, thus implying that $\vec{x}^{t-1} < \vec{x}^t$.

• $G(C^t)$ is a clique of 2 nodes $i$ and $j$, with $\mu_i(C^t) = \mu_j(C^t) = \frac{1}{2}$. Notice that the utilities $\mu_i(S^{t-1})$ and $\mu_j(S^{t-1})$ of agents $i$ and $j$ in coalition structure $S^{t-1}$ have to be less than $\frac{1}{2}$. We have to consider the following disjoint subcases.

- $i, j \in N^{t-1}$. In this case, $\alpha(S^t) = \alpha(S^{t-1})$, $\beta(S^t) = \beta(S^{t-1})$ and $\gamma(S^t) = \gamma(S^{t-1}) + 1$; therefore, the second component of triple $\vec{x}^t$ is greater than the one of triple $\vec{x}^{t-1}$ while the other components are equal, thus implying that $\vec{x}^{t-1} < \vec{x}^t$.

- only an agent, say agent $i$, belongs to $N^{t-1}$, while $G(S^{t-1}(j))$ is a path of 3 nodes, with $\mu_j(S^{t-1}) = \frac{1}{3}$ (see Fig. 10).

In this case, since $G(S^{t-1}(j) \setminus \{j\})$ is a clique of 2 nodes, we obtain that $\alpha(S^t) = \alpha(S^{t-1})$, $\beta(S^t) = \beta(S^{t-1}) - 1$ and $\gamma(S^t) = \gamma(S^{t-1}) + 2$; therefore, the second component of triple $\vec{x}^t$ is greater than the one of triple $\vec{x}^{t-1}$ while the first components are equal, thus implying that $\vec{x}^{t-1} < \vec{x}^t$.
<figure><img src="image_15.png" /><figcaption>Fig. 11. Deviation in which $G(C^t)$ is a clique of 2 nodes $i$ and $j$, while $G(S^{t-1}(i))$ and $G(S^{t-1}(j))$ are paths of 3 nodes.</figcaption></figure>

- $G(S^{t-1}(i))$ is a path of 3 nodes, with $\mu_i(S^{t-1}) = \frac{1}{3}$ and also $G(S^{t-1}(j))$ is a path of 3 nodes (see Fig. 11), with $\mu_j(S^{t-1}) = \frac{1}{3}$ and $S^{t-1}(i) \neq S^{t-1}(j)$.

In this case, since $G(S^{t-1}(i) \setminus \{i\})$ and $G(S^{t-1}(j) \setminus \{j\})$ are cliques of 2 nodes, we obtain that $\alpha(S^t) = \alpha(S^{t-1})$, $\beta(S^t) = \beta(S^{t-1}) - 2$ and $\gamma(S^t) = \gamma(S^{t-1}) + 3$; therefore, the second component of triple $\bar{x}^t$ is greater than the one of triple $\bar{x}^{t-1}$ while the first components are equal, thus implying that $\bar{x}^{t-1} < \bar{x}^t$.

We have proven that vectors $\bar{x}^t$, for $t \ge 1$, lexicographically increase after each deviation; since the cardinality of the set of possible triples polynomial in the number of agents, the claim directly follows. □

Our last result concerns the convergence of k-improvement dynamics, for any $k \ge 2$. It is obtained by proving that, in this case, the social welfare is indeed a potential function for the game, i.e., every deviation of a blocking coalition implies an increase of the social welfare.

**Theorem 5.** Every S-FHG is k-improvement core convergent, for every $k \ge 2$.

**Proof.** Given any $k \ge 2$, consider any k-improvement core dynamics $D$ starting from any coalition structure $S^0$. We show that $D = (S^0, S^1, \dots)$ has finite length, i.e., that a k-improvement core stable coalition structure is eventually reached. For any $t \ge 1$, let $C^t$ be the blocking coalition performing the t-th k-improvement core deviation of the dynamics $D$, leading from coalition structure $S^{t-1}$ to $S^t$. Moreover, let $\mathcal{X}^t = \{S^{t-1}(i) | i \in C^t\}$ be the collection of coalitions belonging to $S^{t-1}$ being affected by the t-th deviation of the considered dynamics $D$.

In the following we show that, for any $t \ge 1$, $SW(S^{t-1}) < SW(S^t)$, i.e., the social welfare always increases after each deviation. Since the set of possible coalition structures is finite (as well as the one of possible social welfare values), the claim directly follows.

For any $t \ge 1$, by the definition of $\mathcal{X}^t$, it holds that

$$SW(S^t) = SW(S^{t-1}) + SW(C^t) + \sum_{C \in \mathcal{X}^t} (SW(C \setminus C^t) - SW(C)).$$

In order to show that $SW(S^{t-1}) < SW(S^t)$, it is therefore sufficient to verify that

$$SW(C^t) > \sum_{C \in \mathcal{X}^t} (SW(C) - SW(C \setminus C^t)). \qquad (1)$$

Let us first focus on the right hand side of inequality (1).

$$ 
\begin{aligned}
SW(C \setminus C^t) &= \sum_{i \in C \setminus C^t} \mu_i(C \setminus C^t) \\
&= \frac{1}{|C \setminus C^t|} \sum_{i \in C \setminus C^t} \delta_{C \setminus C^t}(i) \\
&= \frac{2}{|C \setminus C^t|} \sum_{i,j \in C \setminus C^t, i < j} v_i(j) \\
&\ge \frac{2}{|C|} \sum_{i,j \in C \setminus C^t, i < j} v_i(j),
\end{aligned} 
\qquad (2) $$

where equality (2) holds because the valuations are symmetric. Analogously, it is possible to derive the following chain of equalities, starting from $SW(C)$:

$$ 
\begin{aligned}
SW(C) &= \sum_{i \in C} \mu_i(C) = \frac{1}{|C|} \sum_{i \in C} \delta_C(i) \\
&= \frac{2}{|C|} \left( \sum_{i,j \in C \setminus C^t, i < j} v_i(j) + \sum_{i,j \in C \setminus C^t, i < j} v_i(j) + \sum_{i \in C \cap C^t, j \in C \setminus C^t} v_i(j) \right),
\end{aligned} 
\qquad (3) $$
where equality (3) holds because the valuations are symmetric and we are counting in three separate summations the contributions to $\sum_{i \in C} \delta_C(i)$ due to the pair of agents both belonging to $C \cap C^t$, the pair of agents both belonging to $C \setminus C^t$ and the pair of agents with an agent belonging to $C \cap C^t$ and the other one to $C \setminus C^t$. By combining $SW(C \setminus C^t) \geq \frac{2}{|C|} \sum_{i,j \in C \setminus C^t, i < j} v_i(j)$ with equality (3), we obtain

$$ 
\begin{aligned}
SW(C) - SW(C \setminus C^t) & \\
& \leq \frac{2}{|C|} \left( \sum_{i,j \in C \cap C^t, i < j} v_i(j) + \sum_{i \in C \cap C^t, j \in C \setminus C^t} v_i(j) \right) \\
& \leq \frac{2}{|C|} \left( \sum_{i,j \in C \cap C^t} v_i(j) + \sum_{i \in C \cap C^t, j \in C \setminus C^t} v_i(j) \right) \\
& = \frac{2}{|C|} \sum_{i \in C \cap C^t} \delta_C(i) = 2 \sum_{i \in C \cap C^t} \mu_i(C).
\end{aligned}
$$

By summing over all coalitions in $\mathcal{X}^t$, we obtain

$$ 
\begin{aligned}
& \sum_{C \in \mathcal{X}^t} (SW(C) - SW(C \setminus C^t)) \\
& \leq 2 \sum_{C \in \mathcal{X}^t} \sum_{i \in C \cap C^t} \mu_i(C) \\
& = 2 \sum_{C \in \mathcal{X}^t} \sum_{i \in C \cap C^t} \mu_i(S^{t-1}) \\
& = 2 \sum_{i \in C^t} \mu_i(S^{t-1}),
\end{aligned}
\quad (4) \quad (5)
$$

where equality (4) holds by the definition of $\mathcal{X}^t$. Thus, the right hand side of inequality (1) can be bounded from above by $2 \sum_{i \in C^t} \mu_i(S^{t-1})$.

We now focus on the left hand side of inequality (1). Since $C^t$ is a $k$-improvement blocking coalition, it follows that, for every agent $i \in C^t$, $\mu_i(C^t) > k\mu_i(S^{t-1}) \geq 2\mu_i(S^{t-1})$. It follows that

$$ SW(C^t) > 2 \sum_{i \in C^t} \mu_i(S^{t-1}), $$

thus proving inequality (1) and the whole theorem. $\square$

Notice that, by Theorem 5, we directly get that every S-FHG admits a $k$-improvement core stable coalition structure, for every $k \geq 2$, that can be obtained by running a $k$-improvement core dynamics starting from any coalition structure. Analogously, by combining Theorem 1 and Theorem 3, we can obtain, for any given S-FHG, a $k$-improvement core stable coalition structure, for every $k \geq 2$, by running a 2-size core dynamics starting from any coalition structure. However, in both cases, we are not guaranteed that the dynamics is convergent within a polynomial number of deviations. Moreover, by Theorem 5, we have that the social welfare is a potential function which implies that the optimal solution is $k$-improvement core stable for any $k \geq 2$. However, computing the optimal solution is an NP-Hard problem even for SS-FHG [6]. In the following, we show a polynomial time algorithm that, given any instance of S-FHG, computes a coalition structure which is $k$-improvement core stable, for every $k \geq 2(1 - 1/n)$.

**Theorem 6.** Every S-FHG admits a $k$-improvement core stable coalition structure that can be computed in polynomial time, for every $k \geq 2(1 - 1/n)$.

**Proof.** We show a simple algorithm that computes in polynomial time a $2(1 - 1/n)$-improvement core stable coalition structure. We notice that the same algorithm has been used to show the existence of core stable outcomes in modified fractional hedonic games [34].<fnref n="3" /> The algorithm works in phases $t = 1, 2, \dots$. Let $G^0 = G$. For any $t \geq 1$, let $G^t = (N^t, (v_i)_i \in N^t)$ be the resulting sub-game obtained after phase $t$. In any phase $t \geq 1$, a new coalition isomorphic to a clique of size 2 is added to $S$ as follows: Let $v_{max}^{t-1} = v_i(j) = v_j(i)$, for some $i, j \in N^{t-1}$, be the maximum valuation of two agents in $G^t$, that is, $v_{max}^{t-1} = \max_{i \in N^{t-1}} v_i^{max}(G^t)$. We add to $S$ the coalition formed by agents $i$ and $j$, i.e., $S = S \cup \{i, j\}$. Moreover, let $G^t$ such that $N^t = N^{t-1} \setminus \{i, j\}$. The algorithm stops when $|N^t| \leq 1$. In particular, if $|N^t| \mod 2 = 0$ (resp. $|N^t| \mod 2 = 1$), the algorithm ends by returning $S$ (resp. $S \cup \{i\}$ where $N^t = \{i\}$). Since at each

<footnote n="3">³ Modified fractional hedonic games differ from fractional hedonic games (that are considered in this paper) in the definition of the utility of an agent: while in fractional hedonic games the utility of an agent is given by the sum of her valuations for all other agents in the same coalition divided by the cardinality of the coalition, in modified fractional hedonic games the utility of an agent is given by the same quantity divided by the cardinality of the coalition minus one, i.e., the utility is given by the average valuation for all other agents in the coalition.</footnote>
phase (excluding the last) two agents are removed from the sub-game, the algorithm terminates in at most $[|N|/2]$ phases returning a coalition structure with all coalitions of cardinality at most 2.

We now show that the returned outcome $S$ is a $2(1 - 1/n)$-improvement core stable coalition structure of $G$. In $S$, agents $i$ and $j$ selected at phase $t = 1$ get each utility of $\frac{v_{max}^0}{2}$. Remind that $\mu_i(S) \le \frac{n-1}{n}v_{max}^0$ and $\mu_j(S) \le \frac{n-1}{n}v_{max}^0$, for any possible coalition structure $S$. It implies that agents $i$ and $j$ cannot belong to a $k$-improvement blocking coalition for $S$, for any $k \ge 2(1 - 1/n)$. The proof continues by induction as follows. Suppose that all the agents selected until phase $z$, i.e., agents belonging to $N \setminus N^z$, cannot belong to any $k$-improvement blocking coalition for $S$, for any $k \ge 2(1 - 1/n)$, then agents $i_{z+1}$ and $j_{z+1}$ selected in the phase $z+1$ of the algorithm cannot belong to any $k$-improvement blocking coalition for $S$, for any $k \ge 2(1 - 1/n)$, as well. In fact, suppose that such agents have a certain utility in the coalition $S$. For the inductive hypothesis we have that they can create a $k$-improvement blocking coalition for $S$, for any $k \ge 2(1 - 1/n)$, only with agents belonging to $N^z$. However, since they have utility $\frac{v_{max}^z}{2}$ and cannot get utility higher than $\frac{n-1}{n}v_{max}^z$, this is not possible. Finally, it is easy to see that, if there is an agent selected as the last one by the algorithm that is alone in her coalition, she cannot form a blocking coalition, and this finishes the proof. $\square$

Finally, we provide the following theorem holding for the special case of simple games: by combining Theorem 2 with Theorem 4, it directly follows that a $k$-improvement core stable outcome can be computed in polynomial time for every $k \ge 3/2$.

**Corollary 7.** Every SS-FHG admits a $k$-improvement core stable coalition structure that can be computed in polynomial time, for every $k \ge 3/2$.

# 4. Efficiency

## 4.1. Price of anarchy

In this section we study the price of anarchy for the considered relaxed core stable outcomes. We start by showing that, for every S-FHG and $k \ge 1$, the social welfare of an optimal outcome can be at most $2k$ times the social welfare of any $k$-improvement core stable outcome.

**Theorem 8.** For every S-FHG $G$ and $k \ge 1$, $k$-IMPR CPOA($G$) $\le 2k$.

**Proof.** First of all, we need some additional notation and definitions. Let $\delta_C^{>}(i) = \sum_{j \in C, j > i} v_i(j)$ be the sum of valuations of agent $i$ for every agent $j > i$ belonging to coalition $C$. Analogously, let $\mu_i^>(C) = \frac{\delta_C^{>}(i)}{|C|}$ be the part of utility of agent $i$ due to her valuations for every agent $j > i$ belonging to coalition $C$. It is worth noticing that, given the symmetry of the valuations, for any coalition $C$, it holds that

$$SW(C) = 2 \sum_{i \in C} \mu_i^>(C). \qquad (6)$$

Let $S^*(G)$ be an optimal coalition structure and $S$ be any $k$-improvement core stable coalition structure of game $G$. We aim at showing that $\frac{SW(S^*(G))}{SW(S)} \le 2k$.

For any $C^* \in S^*(G)$, consider the following process composed by $|C^*|$ phases:

* Phase 1. Let $C_1^* = C^*$. Since $S$ is $k$-improvement core stable, coalition $C_1^*$ cannot be a $k$-improvement blocking coalition for $S$, thus implying that there exists an agent, say agent $i_1$, such that $\mu_{i_1}(C_1^*) \le k\mu_{i_1}(S)$.

* Phase $t$ ($t = 2, \dots, |C^*|$). Let $C_t^* = C_{t-1}^* \setminus \{i_{t-1}\}$. Since $S$ is $k$-improvement core stable, coalition $C_t^*$ cannot be a $k$-improvement blocking coalition for $S$, thus implying that there exists an agent, say agent $i_t$, such that $\mu_{i_t}(C_t^*) \le k\mu_{i_t}(S)$.

Assume, without loss of generality, that the agents are numbered such that $i_1 < i_2 < \dots < i_{|C^*|}$. Notice that the property of this assumption can be simultaneously obtained for all coalitions of $S^*$, for instance assigning to all agents in a same coalition consecutive numbers that respect the desired ordering. By this assumption, for any $t = 1, \dots, |C^*|$, it holds that

$$\mu_{i_t}(C_t^*) = \frac{\delta_{C^*}^{>}(i_t)}{|C_t^*|} \ge \frac{\delta_{C^*}^{>}(i_t)}{|C^*|} = \mu_{i_t}^>(C^*). \qquad (7)$$

By summing over all agents in coalition $C^*$, we obtain

$$SW(C^*) = 2 \sum_{i \in C^*} \mu_i^>(C^*) \le 2 \sum_{t=1}^{|C^*|} \mu_{i_t}(C_t^*) \\ \le 2k \sum_{i \in C^*} \mu_i(S),$$
<figure><img src="image_16.png" /><figcaption>Fig. 12. The unweighted graph $G_{m,t,d}$ of a balanced game $G_{m,t,d}$.</figcaption></figure>

where the first equality holds by (6), the first inequality holds by (7) and the last inequality holds because, for every $t = 1, \dots, |C^*|$, $i_t$ is selected at phase $t$ of the above described process as an agent in $C_t^*$ such that $\mu_{i_t}(C_t^*) \le k\mu_{i_t}(S)$. By applying the last inequality to every coalition in $S^*(G)$, we finally obtain

$$ 
\begin{aligned}
SW(S^*(G)) &= \sum_{C^* \in S^*(G)} SW(C^*) \le 2k \sum_{C^* \in S^*(G)} \sum_{i \in C^*} \mu_i(S) \\
&= 2k \sum_{i \in N} \mu_i(S) = 2k \cdot SW(S). \quad \square
\end{aligned}
$$

We now introduce a parametric class of games, called balanced games, that will be useful for proving several results in the remainder of this section: For every triple of positive integers $(m, t, d)$ such that $t \le m-1$ and $mt$ is even, we construct an unweighted graph $G_{m,t,d}$ representing a balanced game $G_{m,t,d}$ as follows (see Fig. 12). The set of nodes of $G_{m,t,d}$ is partitioned into subset $M = \{1, 2, \dots, m\}$ of size $m \ge 2$, and $m$ subsets $L_1, L_2, \dots, L_m$, each of size $d$. We assume that $\cup_{j=1}^m L_j$ is an independent set in $G_{m,t,d}$, while the subgraph induced by $M$ is a $t$-regular graph; notice that, by definition of $t$ and $m$, this subgraph is well defined (in fact, as it is well known [26], there always exists a $t$-regular graph on $m$ nodes when $t \le m-1$ and $mt$ is even). Finally, each $i \in M$ is connected to every node in $L_i$.

By exploiting balanced games, we are now ready to show that the analysis of Theorem 8 is essentially tight even for SS-FHGs.

**Theorem 9.** There exists an infinite collection of SS-FHGs such that, for every game $G$ belonging to it, it holds that $1-\text{IMPR CPOA}(G) \ge 2$. Moreover, for every $k > 1$ and $\epsilon \in (0, 1/2]$, there exists an infinite collection of SS-FHGs such that, for every game $G$ belonging to it, it holds that $k-\text{IMPR CPOA}(G) \ge 2k(1 - \epsilon)$.

**Proof.** We first focus on the case $k = 1$. Consider the graph $G_{m,t,d}$ and the corresponding balanced game $G_{m,t,d}$, as defined earlier, with $m = d + 1$ and $t = d$. Notice that the subgraph induced by $M$ is a regular graph, in fact it is a complete graph with $d + 1$ nodes.

We claim that $S$ (the coalition structure made of coalition $M$ and $md$ singleton coalitions) is core stable. In fact, in order for any agent $i \in M$ to gain a utility strictly greater than $\mu_i(S) = d/(d+1)$, $i$ must join a blocking coalition with at least $d+1$ agents, involving both agents in $M \setminus \{i\}$ and $L_i$. But such coalition would be vetoed by the agents in $M \setminus \{i\}$ which are not connected to agents in $L_i$. On the other hand, a blocking coalition could never be a subset of $\cup_{j=1}^m L_j$, since this set is independent. This implies that $S$ is core stable.

Therefore, since the social welfare of $S$ is $\sum_{i \in M} \mu_i(S) = t = d$ and the social welfare of $\bar{S}$ (the coalition structure made of $m$ coalitions, in which each agent $i \in M$ makes a coalition with the corresponding set $L_i$) is $(d+1)\frac{2d}{d+1} = 2d$, we have that $SW(\bar{S})/SW(S) = 2$.

Let us now consider the case $k > 1$. We can prove the claim by exploiting a slightly more complicated construction than the one presented for the case $k = 1$. For every triple $(p, q, d)$ of positive integers, such that $p > q$ and $pq$ is even, we consider the graph $G_{m,t,d}$ and the corresponding balanced game $G_{m,t,d}$, with $m = p(d+1)$ and $t = q(d+1)$ (notice that, by the definition of $p$ and $q$, we have that $t \le m-1$ and $mt$ is even).
Let us consider the coalition structure $\mathcal{S}$ made of coalition $M$ and $md$ singleton coalitions, one for each node in $\bigcup_{j=1}^{m} L_j$. We first show that $\mathcal{S}$ is $p/q$-improvement core stable. For the sake of contradiction, let us assume that there is a $p/q$-improvement blocking coalition $C$. Notice that an agent $i \in M$ cannot belong to $C$. In fact, the utility of $i$ is $\mu_i(S) = \frac{1}{m} = \frac{q(d+1)}{p(d+1)} = \frac{q}{p}$ and a $p/q$-improvement deviation would raise the utility to 1, that is above the maximum achievable. On the other hand, since $\bigcup_{j=1}^{m} L_j$ is an independent set, $C$ cannot be a subset of $\bigcup_{j=1}^{m} L_j$. Hence, a contradiction.

In order to evaluate the efficiency of $\mathcal{S}$, we compare its social welfare with the social welfare of the coalition structure $\bar{S}$, made of $m$ coalitions, in which each agent $i \in M$ makes a coalition with the corresponding set $L_i$. The social welfare of $\bar{S}$ is $m \cdot \frac{2d}{d+1} = 2pd$. On the other hand, the social welfare of $\mathcal{S}$ is $\sum_{i \in M} \mu_i(\mathcal{S}) = t = q(d+1)$. It follows that the $\frac{p}{q}$-improvement price of anarchy of $\mathcal{G}$ is at least $SW(\bar{S})/SW(\mathcal{S}) = \frac{2pd}{q(d+1)} = 2\frac{p}{q}(1 - \frac{1}{d+1})$. The claim follows by observing that for every pair of rational numbers $k > 1$ and $\epsilon \in (0, 1/2]$, there are infinite ways of choosing the triple $(p, q, d)$ such that $k = p/q$ and $\epsilon = \frac{1}{d+1}$. $\square$

We now focus on the $q$-size core price of anarchy, for $q \in \{2, 3\}$. For S-FHGs, by Theorem 1 we get that the social welfare of the worst 2-size core stable outcome is at least the social welfare of the worst 2-improvement core stable outcome. Analogously, for SS-FHGs, by Theorem 2 we get that the social welfare of the worst 3-size core stable outcome is at least the social welfare of the worst $\frac{3}{2}$-improvement core stable outcome. Therefore, the following theorem is an immediate consequence of Theorem 8 and the fact that, for any game $\mathcal{G}$, the $q$-SIZE CPOA($\mathcal{G}$) is monotonically decreasing with respect to $q$.

**Corollary 10.** For any S-FHG $\mathcal{G}$ it holds that $q$-SIZE CPOA($\mathcal{G}$) $\le 4$, for any $q \ge 2$; moreover, for any SS-FHG $\mathcal{G}$, it holds that $q$-SIZE CPOA($\mathcal{G}$) $\le 3$, for any $q \ge 3$.

By exploiting the same ideas of the construction of Theorem 9, it is possible to show that, for any $\epsilon > 0$ and any integer $q \ge 2$, there exists a game $\mathcal{G}$ such that $q$-SIZE CPOA($\mathcal{G}$) $\ge 2\frac{q}{q-1} - \epsilon$, thus proving the tightness of the bounds provided by Corollary 10.

**Example 7.** Consider the balanced game $G_{q,q-1,d}$, being an instance of SS-FHG. It is easy to see that the coalition structure $\mathcal{S}$ made of coalition $M$ and $qd$ singleton coalitions is $q$-size core stable. Notice that the social welfare of $\mathcal{S}$ is $q-1$. Let us consider the coalition structure $\bar{S}$ made of $q$ coalitions where each agent $i \in M$ makes a coalition with the corresponding set of agents $L_i$. Notice that the social welfare of $\bar{S}$ is $2q\frac{d}{d+1}$. Thus, we have that $SW(S^*)/SW(S) \ge SW(\bar{S})/SW(S) = 2\frac{q}{q-1}\frac{d}{d+1}$. By setting $d$ large enough, we obtain that $G_q$ is such that $q$-SIZE CPOA($G_q$) $\ge 2\frac{q}{q-1} - \epsilon$, for any $\epsilon > 0$.

## 4.2. Price of stability

In this subsection, we would like to focus on the $q$-size and $k$-improvement core price of stability. Roughly speaking, a low core price of stability means that there exists a core stable solution that is close, in terms of efficiency, to the social optimum. Interestingly, to this respect, some preliminary results arise as a direct consequence of other theorems provided in this paper.

In particular, for S-FHGs, the $k$-improvement core price of stability is 1 for $k \ge 2$, because, by the proof of Theorem 5, the social welfare is in this case a potential function for the game, thus implying that the optimal solution is $k$-improvement core stable. Moreover, always for S-FHGs, if $k < 2$ we know, by Theorem 8, that the core price of stability is at most $2k$, because the core price of stability of a game is always less than its core price of anarchy. For SS-FHGs, by exploiting the fact that, by Corollary 7, a $\frac{3}{2}$-improvement core stable solution (approximating, by Theorem 8, the optimal solution by a factor of 3) is guaranteed to exist and by observing that a $\frac{3}{2}$-improvement core stable solution is also $k$-improvement core stable for any $k > 3/2$, we obtain an improved upper bound equal to 3 for the $k$-improvement core price of stability, with $k \in [3/2, 2)$.

A lower bound of 2 to the core price of stability is known [17, Theorem 5.1] for core stability in which the blocking coalition has to satisfy the additional structural property of inducing a complete subgraph, thus implying that the (1-improvement) core price of stability is at least 2: a matching lower bound for the case $k = 1$.

We now provide some results concerning the determination of non-trivial lower bounds to the $k$-improvement core price of stability for $k \in (1, 2)$, and to the $q$-size core price of stability. The following technical lemma will be exploited in the proof of Theorem 11.

**Lemma 1.** Consider any balanced game. Given any $\bar{M} \subseteq M$ with $|\bar{M}| \ge 3$ and any $\bar{L} \subseteq N \setminus M$, it holds that $SW(\bar{M}) \ge SW(\bar{M} \cup \bar{L})$.

**Proof.** Since nodes in $\bar{M}$ form a clique, we have that $SW(\bar{M}) = \frac{|\bar{M}|(|\bar{M}|-1)}{|\bar{M}|} = |\bar{M}| - 1 \ge 2$. When considering coalition $\bar{M} \cup \bar{L}$, for every node of $\bar{L}$ we are adding one node and at most one edge to coalition $\bar{M}$. Therefore, we obtain that $SW(\bar{M} \cup \bar{L}) \le \frac{|\bar{M}|(|\bar{M}|-1)+2|\bar{L}|}{|\bar{M}|+|\bar{L}|} \le \frac{|\bar{M}|(|\bar{M}|-1)}{|\bar{M}|} = SW(\bar{M})$ because $\frac{2|\bar{L}|}{|\bar{L}|} = 2 \le \frac{|\bar{M}|(|\bar{M}|-1)}{|\bar{M}|}$. $\square$

**Theorem 11.** Given any small $\epsilon > 0$, any small $\delta > 0$ and any integer $d \ge 2$, there exists a SS-FHG game $\mathcal{G}$ such that $(\frac{d+1}{d} - \epsilon)$-IMPR CPOs($\mathcal{G}$) $\ge \frac{2d}{d+1} - \delta$.
<figure><img src="image_17.png" /><figcaption>Fig. 13. The coalition structure $S^x$ of the balanced game $G_{m,m-1,d}$.</figcaption></figure>

**Proof.** Consider the balanced game $G_{m,m-1,d}$, where $m$ is a parameter that will be defined later. Let $S^* = \{i \in M\} \cup L_i | i = 1, \dots, m\}$ be the coalition structure in which there are $m$ coalitions of size $d+1$; notice that $SW(S^*) = m^{\frac{2d}{d+1}}$.

Let $S^x = \{\{x+1, \dots, m\} \subseteq M\} \cup \{\{i \in M\} \cup L_i | i=1, \dots, x\} \cup \{|j \in L_i| j=x+1, \dots, m\}$ be the coalition structure in which there is a coalition given by a clique of size $m-x$, $x$ coalitions of size $d+1$ (given by stars with $d$ leaves, each formed by a node in $i \in M$ together with the corresponding nodes in $L_i$), and $d(m-x)$ singleton coalitions (see Fig. 13); it holds that $SW(S^x) = m - x - 1 + x \frac{2d}{d+1}$.

Let $\tau$ be the smallest integer such that $\frac{\tau}{\tau+1} \frac{d+1}{d} > \frac{d+1}{d} - \epsilon$. In the following, we aim at showing that there exists no stable coalition structure having social welfare better than the social welfare of $S^\tau$, thus implying that

$$ \left(\frac{d+1}{d} - \epsilon\right) \text{-IMPR CPOs}(G) \geq \frac{m^{\frac{2d}{d+1}}}{m - \tau - 1 + \tau \frac{2d}{d+1}}, $$

that for a sufficiently big value of $m$ (depending on $\delta$) proves the theorem.

Consider any coalition structure $S = \{C_1, \dots, C_\alpha\}$. We want to prove that either $SW(S) \le SW(S^\tau)$, or $S$ is not stable. For any $j=1, \dots, \alpha$, let $C'_j = C_j \cap M$ and $n'_j = |C'_j|$. By the arbitrariness of the coalition order in a coalition structure, without loss of generality we assume that the coalitions are sorted in non-decreasing order with respect to $n'_j$.

We divide the proof in the following cases:

* If there exist $\tau + 1$ coalitions $C_1, \dots, C_{\tau+1} \in S$ such that, for all $j = 1, \dots, \tau + 1$, $n'_j = 1$, then $S$ is not stable because $B = \cup_{j=1}^a C'_j$ is a blocking coalition. In fact, for any node in $i \in B$, it holds that $\mu_i(S) \le \frac{d}{d+1}$, while the utility of $i$ in coalition $B$ would be at least $\frac{\tau}{\tau+1} > \left(\frac{d+1}{d} - \epsilon\right) \frac{d}{d+1}$.

* Otherwise, there are exactly $x \le \tau$ coalitions $C_1, \dots, C_x \in S$ such that, for all $j = 1, \dots, x$, $n'_j = 1$. Without loss of generality, given the symmetry of the considered instance, we assume that $C'_j = \{j \in M\}$ for all $j = 1, \dots, x$. Moreover, for every node $i \in \tilde{N}$, let us define the *special utility* of $i$ in $S$ as $\hat{\mu}_i(S) = \frac{SW(S(i))}{|S(i) \cap M|}$. By this definition, it holds that $SW(C_j) = \sum_{i \in C'_j} \hat{\mu}_i(S)$ and that $SW(S) = \sum_{i \in M} \hat{\mu}_i(S)$.

We now show that $SW(S) \le SW(S^x)$, which implies that $SW(S) \le SW(S^\tau)$, given that $SW(S^x) \le SW(S^\tau)$. In order to prove that $SW(S) \le SW(S^x)$, we show that, for every node $i$ in $M$, $\hat{\mu}_i(S) \le \hat{\mu}_i(S^x)$:

- If $i \in \{1, \dots, x\}$, it holds that $\hat{\mu}_i(S) \le \frac{2d}{d+1}$ (with the equality obtained when $|S(i)| = d+1$) and $\hat{\mu}_i(S^x) = \frac{2d}{d+1}$.

- If $i \in \{x+1, \dots, m\}$, let $h > x$ be such that $i \in C_h$. First of all, notice that $\hat{\mu}_i(S^x) = \frac{m-x-1}{m-x}$.

If $n'_h \ge 3$, by Lemma 1, it holds that $SW(C_h) \le SW(C'_h) = n'_h - 1$ and therefore $\hat{\mu}_i(S) \le \frac{n'_h - 1}{n'_h} \le \frac{m-x-1}{m-x}$, where the last inequality holds because $n'_h \le m-x-1$.

Otherwise, i.e., if $n'_h = 2$, let $\delta = |C_h| - 2$ be the nodes connected to a node in $C'_h$. We obtain that $SW(C_h) = \frac{2(\delta+1)}{\delta+2} \le \frac{2(2d+1)}{2d+2}$ because $\delta \le 2d$. It follows that $\hat{\mu}_i(S) \le \frac{1}{2} \frac{2(2d+1)}{2d+2} = \frac{2d+1}{2d+2} \le \frac{m-x-1}{m-x}$, where the last inequality holds by choosing $m \ge 2d+x+2$. $\square$
<figure><img src="image_18.png" /><figcaption>Fig. 14. The case in which there exist two coalitions $C_j$ and $C_{j'}$ such that $|C_j| \in \{3, 4\}$, $|C_{j'}| = 2$, $|C_{j'}| \in \{3, 4\}$ and $|C_{j'}| = 2$.</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>Fig. 15. The case in which there exists only a coalition $C_j$ such that $|C_j| \in \{3, 4\}$ and $|C_{j'}| = 2$.</figcaption></figure>

Both Theorems 11 and 12 provide lower bounds to the k-improvement core price of stability. While Theorem 11 deals with values of k between 1 and 3/2, the following theorem deals with values of k between 8/5 and 2.

**Theorem 12.** For every integer $t \ge 5$, there exists a SS-FHG game $G_t$ such that $k$-IMPR CPOS($G_t$) $\ge \frac{3t}{3t-2}$ for any $k < 2 - \frac{2}{t}$.

*Proof.* We first provide the description of game $G_t$: For any $t \ge 5$, consider the balanced game $G_{t,t-1,1}$. Notice that sets $|L_j| = 1$ for every $j = 1, \dots, t$. We denote by $l_j$ the unique node of $L_j$.

Let $S^* = \{i \in M, l_i\}|i = 1, \dots, t\}$ be the coalition structure in which there are $t$ coalitions of size 2; notice that $SW(S^*) = t$. For any $i = 1, \dots, t$ and any coalition structure $S$, we also define the special utility $\hat{\mu}_i(S) = \mu_i(S) + \mu_{i'}(S)$.

In the following, we exploit a useful property.

**Property 1.** Given any coalition structure $S$, for every $i = 1, \dots, t$, it holds that $\hat{\mu}_i(S) \le 1$.

This property holds because $\mu_i(S) \le \frac{|S(i)|-1}{|S(i)|}$ and $\mu_{i'}(S) \le \frac{1}{|S(i)|}$. It follows that $\hat{\mu}_i(S) = \mu_i(S) + \mu_{i'}(S) \le 1$.

Let $S^{\text{stable}} = \{\{1, l_1, 2\}, \{l_2\}\} \cup \{\{i, l_i\}|i = 3, \dots, t\}$ be the coalition structure being very similar to $S^*$, with the difference that node 2 is in the same coalition of nodes 1 and $l_1$; it holds that $SW(S^{\text{stable}}) = t - 2 + \frac{4}{3} = t - \frac{2}{3}$. In the following, we aim at showing that there exists no stable coalition structure having social welfare better than the social welfare of $S^{\text{stable}}$, thus implying that $k$-IMPR CPOS($G_t$) $\ge \frac{3t}{3t-2}$ for any $k < 2 - \frac{2}{t}$.

Consider any coalition structure $S = \{C_1, \dots, C_\alpha\}$. We want to prove that either $SW(S) \le SW(S^{\text{stable}})$, or $S$ is not stable. For any $j = 1, \dots, \alpha$, let $C'_j = C_j \cap M$. If $|C'_j| \ge 3$, by Lemma 1, it holds that $SW(C_j) \le SW(C'_j) = |C'_j| - 1$. Therefore, given that (i) by Property 1 the special utility of all agents belonging to $M \setminus C_j$ is at most 1 and that (ii) $SW(S) = \sum_{i=1}^t \hat{\mu}_i(S)$, the following holds: if there exists $j$ such that $|C'_j| \ge 3$, then $SW(S) \le t - 1 \le SW(S^{\text{stable}})$. We can therefore assume that, for every $j = 1, \dots, \alpha$, $|C'_j| \le 2$. We now divide the proof in the following cases:

* If there exist two coalitions $C_j$ and $C_{j'}$ such that $|C_j| \in \{3, 4\}$, $|C_{j'}| = 2$, $|C_{j'}| \in \{3, 4\}$ and $|C_{j'}| = 2$ (see Fig. 14), given that (i) by Property 1 the special utility of all agents belonging to $M \setminus C_j$ is at most 1 and that (ii) $SW(S) = \sum_{i=1}^t \hat{\mu}_i(S)$, we obtain that $SW(S) \le t - 4 + 2 \cdot \frac{3}{2} = t - 1 < SW(S^{\text{stable}})$.

* If there exists only a coalition $C_j$ such that $|C_j| \in \{3, 4\}$ and $|C_{j'}| = 2$ (see Fig. 15), it holds that, for all nodes $i \in M \setminus C_j$, $\mu_i(S) \le \frac{1}{2}$. We consider two subcases:

If $|C_j| = 4$, also the two nodes in $M \cap C_j$ have utility $\frac{1}{2}$ in $S$ and $S$ is not stable because $M$ is a blocking coalition.

Otherwise, i.e., $|C_j| = 3$, given that (i) by Property 1 the special utility of all agents belonging to $M \setminus C_j$ is at most 1 and that (ii) $SW(S) = \sum_{i=1}^t \hat{\mu}_i(S)$, we obtain that $SW(S) \le t - 2 + \frac{4}{3} = SW(S^{\text{stable}})$.
<figure><img src="image_20.png" /><figcaption>Fig. 16. The case in which $q=3$, there exists $u \in M$ such that $\alpha_u \ge 2$ and, for all $i \in S(u) \cap M$, $\beta_i \ge 1$.</figcaption></figure>

Therefore, for $t \ge 5$, there exists no stable coalition structure having social welfare better than the social welfare of $S^{\text{stable}}$ and the $k$-IMPR CPOS($G_t$) $\ge \frac{3t}{3t-2}$ for any $k < 2 - \frac{2}{t}$. $\square$

Finally, we provide a lower bound to the $q$-size core price of stability. Before proving Theorem 13, we need a technical lemma.

**Lemma 2.** *Consider the balanced game $G_{q,q-1,q-2}$. In any $q$-size core stable coalition structure $S$, for any node $i \in M$ it holds that $\mu_i(S) \ge \frac{q-2}{q}$.*

**Proof.** Consider any node $i \in M$ and let $B_i \subseteq L_i$ be the set containing all and only the nodes $j \in L_i$ such that $S(j) = S(i)$; similarly, let $\bar{B}_i \subseteq L_i$ be the set containing all and only the nodes $j \in L_i$ such that $C(j) \neq C(i)$; moreover, let $\beta_i = |B_i|$ and $q-2-\beta_i = |\bar{B}_i|$. If $\mu_i(S) \ge \frac{q-2}{q}$, the property holds and we are done. Otherwise, by way of contradiction, assume that $\mu_i(S) < \frac{q-2}{q}$.

If $\beta_i \ge \frac{q-2}{2}$, notice first of all that, since $\mu_i(S) < \frac{q-2}{q}$, other agents (not connected to $i$) have to belong to coalition $S(i)$, i.e., $|S(i)| > \beta_i + 1$. All nodes in $T = \{i\} \cup B_i$ strictly prefer coalition $T$ to their current one: a contradiction. In fact, $\frac{\delta_T(i)}{|T|} = \frac{\beta_i}{\beta_i+1} \ge \frac{\frac{q-2}{2}}{\frac{q-2}{2}+1} = \frac{q-2}{q} > \mu_i(S)$ and, for any $j \in B_i$, $\frac{\delta_T(j)}{|T|} = \frac{1}{\beta_i+1} > \frac{1}{|S(i)|} = \mu_j(S)$.

If $\beta_i < \frac{q-2}{2}$, all nodes in $T = \{i\} \cup \bar{B}_i$ strictly prefer coalition $T$ to their current one: a contradiction. In fact, $\frac{\delta_T(i)}{|T|} = \frac{q-2-\beta_i}{q-1-\beta_i} \ge \frac{q-2}{\frac{q-2}{2}} = \frac{q-2}{q} > \mu_i(S)$ and, for any $j \in \bar{B}_i$, $\frac{\delta_T(j)}{|T|} = \frac{1}{q-1-\beta_i} > 0 = \mu_j(S)$. $\square$

**Theorem 13.** *For every integer $q \ge 3$, there exists a SS-FHG game $G_i$ such that $q$-SIZE CPOS($G_i$) $\ge 2q \frac{q-2}{(q-1)^2}$.*

**Proof.** Consider the balanced game $G_{q,q-1,q-2}$. We first show that any $q$-size core stable coalition structure $S$ is such that $SW(S) \le q-1$.

Let us assume, by way of contradiction, that there exists a $q$-size core stable coalition structure $S$ such that $SW(S) > q-1$. For any $i \in M$, let $A_i = S(i) \cap M$ and $\alpha_i = |A_i|$. Moreover, for any $i \in M$, let $B_i \subseteq L_i$ be the set containing all and only the nodes $j \in L_i$ such that $S(j) = S(i)$, and let $\beta_i = |B_i|$. The proof is now divided into three disjoint cases:

* If, for all $i \in M$, $\alpha_i = 1$, then, for all $i \in M$, $\mu_i(S) = \frac{\beta_i}{\beta_i+1} \le \frac{q-2}{q-3}$, because $\beta_i \le q-2$. Therefore, all nodes in $M$ strictly prefer coalition $M$ to their current one: a contradiction to the stability of $S$. In fact, for any $i \in M$, $\mu_i(S) \le \frac{q-2}{q-1} < \frac{q-1}{q} = \frac{\delta_M(i)}{|T|}$.

* If there exists $u \in M$ such that $\alpha_u \ge 2$ and, for all $i \in S(u) \cap M$, $\beta_i \ge 1$, then let $j \in S(u) \cap M$ be an agent for which $\beta_j = \min_{i \in C(u)} \beta_i$. Notice that $\alpha_j = \alpha_u \ge 2$ because $S(j) = S(u)$.

In the case of $q=3$, if there exists $u \in M$ such that $\alpha_u = 2$, then $M$ is a blocking coalition (see Fig. 16a): a contradiction to the stability of $S$. Otherwise, i.e. if $\alpha_u = 3$ for all $u \in M$ (see Fig. 16b), then $SW(S) = 2 = q-1$: a contradiction to the fact that $SW(S) > q-1$.

In the case of $q=4$, if there exists $u \in M$ such that $\alpha_u = 2$, then $T = \{j\} \cup L_j$ is a blocking coalition (see Fig. 17a): a contradiction to the stability of $S$. In fact, $\mu_j(S) = -\frac{\beta_j+1}{\beta_j+\beta_j+2} \le \frac{\beta_j+1}{2\beta_j+2} = \frac{1}{2}$, while $\frac{\delta_T(j)}{|T|} = \frac{2}{3}$ and it can be easily verified that the utility also improves (from being at most $1/4$ to the new value of $1/3$) for all nodes in $L_j$. Moreover, if there exists $u \in M$ such that $\alpha_u = 3$, then $M$ is a blocking coalition, given that the utility of any agent in $M$ can be at most $4/7$, while in coalition $M$ her utility would be $2/3$ (see Fig. 17b): a contradiction to the stability of $S$. Finally, if $\alpha_u = 4$ for all $u \in M$ (see Fig. 17c), then, by Lemma 1, it holds that $SW(S) = 3 = q-1$: a contradiction to the fact that $SW(S) > q-1$.
<figure><img src="image_21.png" /><figcaption>Fig. 17. The case in which $q=4$, there exists $u \in M$ such that $\alpha_u \ge 2$ and, for all $i \in S(u) \cap M$, $\beta_i \ge 1$.</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>Fig. 18. The case in which $q=3$, there exists $i \in M$ with $\alpha_i \ge 2$ such that (i) there exists $j \in S(i) \cap M$ with $\beta_j = 0$ and (ii) there exists $v \in S(i) \cap M$ with $\beta_v \ge 1$.</figcaption></figure>

In the case of $q \ge 5$, it holds that $\mu_j(S) = \frac{\alpha_j - 1 + \beta_j}{|S(j)|} \le \frac{\alpha_j - 1 + \beta_j}{\alpha_j + \alpha_j \beta_j} \le \frac{1}{2}$, where the last inequality holds because $\alpha_j \ge 2$ and $\beta_j \ge 1$: a contradiction to the fact that, by Lemma 2, it holds that $\mu_j(S) \ge \frac{q-2}{q} \ge \frac{3}{5}$.

• Otherwise, there must exist $i \in M$ such that $\alpha_i \ge 2$ and $j \in S(i) \cap M$ such that $\beta_j = 0$ (notice that $L_j = \bar{B}_j$ and that $\alpha_j = \alpha_i \ge 2$). We have to distinguish among two disjoint subcases:

- If there exists $i \in M$ with $\alpha_i \ge 2$ such that (i) there exists $j \in S(i) \cap M$ with $\beta_j = 0$ and (ii) there exists $v \in S(i) \cap M$ with $\beta_v \ge 1$, then:

When $q \ge 4$, all nodes in $T = \{j\} \cup L_j$ strictly prefer coalition $T$ to their current one: a contradiction to the stability of $S$.

In fact, $\mu_j(S) = \frac{\alpha_j - 1}{|S(i)|} \le \frac{\alpha_j - 1}{\alpha_j + 1} < \frac{q-2}{q-1} = \frac{\delta_T(j)}{|T|}$ (the last inequality holds because $\alpha_j \le q < 2q - 3$ for $q \ge 4$) and, for any $u \in L_j$, $\mu_u(S) = 0 < \frac{1}{q-1} = \frac{\delta_T(u)}{|T|}$.

When $q=3$, if there exists $i \in M$ with $\alpha_i = 2$, then $T = \{j\} \cup L_j$ is a blocking coalition (see Fig. 18a). Moreover, if $\alpha_u = 3$ for all $u \in M$ (see Fig. 18b), then, by Lemma 1, it holds that $SW(S) = 2 = q - 1$: a contradiction to the fact that $SW(S) > q - 1$.

- If, for all $i \in M$ with $\alpha_i \ge 2$, all $j \in S(i) \cap M$ are such that $\beta_j = 0$, then, when $\alpha_i = q$, we obtain that $SW(S) = q - 1$: a contradiction to the fact that $SW(S) > q - 1$. Otherwise, i.e., when $\alpha_i \le q - 1$ for every $i \in M$, we obtain that all nodes in $M$ strictly prefer coalition $M$ to their current one: a contradiction to the stability of $S$. In fact, for all $i \in M$ with $\alpha_i \ge 2$, it holds that $\mu_i(S) = \frac{\alpha_i - 1}{\alpha_i} \le \frac{q-2}{q-1} < \frac{q-1}{q} = \frac{\delta_M(i)}{|M|}$. Finally, for all $i \in M$ with $\alpha_i = 1$, it holds that $\mu_i(S) \le \frac{q-2}{q-1}$, because agent $i$ can be connected in $S$ only to nodes in $L_i$. Thus, $\mu_i(S) \le \frac{q-2}{q-1} < \frac{q-1}{q} = \frac{\delta_M(i)}{|M|}$.

Consider now coalition structure $\bar{C}$ in which each agent $i \in M$ is grouped together with the $q-2$ agents in $L_i$, that is $\bar{C} = \{\{i\} \cup L_i | i = 1, \dots, q\}$. Hence, the social welfare of an optimal coalition structure is $SW(C^*) \ge SW(\bar{C}) = q^{\frac{2(q-2)}{q-1}}$.

Therefore, since for any $q$-size core stable coalition structure $S$ it holds that $SW(S) \le q - 1$, we obtain that the $q$-size core price of stability is at least $\frac{2q(q-2)}{(q-1)^2}$. $\square$
## 5. Experimental evaluation

The experiment process is designed to explore the dynamics of coalitions formation in fractional hedonic games.<fnref n="4" /> By systematically varying parameters and tracking outcomes, the experimental study aims to understand under which conditions stable outcomes emerge, how frequently they emerge and which is the number of deviations needed to reach these stable outcomes. The insights gained from these experiments help in understanding strategic behavior in the considered hedonic games.

The experiment process starts by randomly generating a weighted (or unweighted) graph with $n$ nodes and whose edges are established based on a given probability $p$ (an edge between any pair of nodes is created with probability $p$). This setup allows for the creation of graphs with different values of edge density, depending on the value of $p$. Then an initial partition of agents into coalitions (groups) is defined. The experiment proceeds with a random sequence of profitable deviations starting from the initial partition. The algorithm iteratively checks if there exists a group of agents that can perform a profitable deviation by going through a uniformly sampled sequence of subsets of agents. This random sampling ensures a thorough exploration of possible coalition formations when executing multiple dynamics over the same instance. During the dynamics, the algorithm checks for cycles by keeping track of previously encountered outcomes. The process continues until no further improvements can be made (in this case, the total number of deviations performed is reported) or a cycle is detected.

**Parameters.** The experimental work explores a variety of parameters. The key parameters considered are: $n$ (number of agents), $p$ (edge probability), unweighted (for SS-FHGs) or weighted (for S-FHGs) graph, the initial coalition structure and the type of deviations.

The number of agents $n$ takes values in the set $\{5, 10, 15, 20, 30, 40, 50, 60, 70, 80, 90, 100\}$ (for in $k$-improvement core dynamics, in which the cardinality of the set of possible blocking coalition is exponential in $n$, we limit the number of agents at 20). The probability $p$ that an edge exists between any two agents is considered in the set $\{0.05, 0.1, 0.2, 0.3, 0.5\}$. This parameter determines the density of the graph, influencing the likelihood and number of connections between agents. The experimental evaluation distinguishes between weighted and unweighted graphs. In weighted graphs, edges have random weights selected from the range [1, 100], while in unweighted graphs, all edges are treated equally without specific weights. Two types of initial coalition structures are considered: singleton coalitions and maximal connected components. In the first case, each agent starts in their own coalition, i.e., every agent is a singleton coalition. This setup simulates a scenario where agents do not have any predefined group affiliations. In the second case, agents are grouped into coalitions based on the maximal connected components of the underlying graph. In this case, each coalition consists of all agents who are directly or indirectly connected by a path of edges in the graph; notice that, when the graph is connected, the initial coalition structure contains only the grand coalition (and for this reason this case is referred to as grand coalition in the figures). The choice between these two initial states provides insights into how starting conditions affect the evolution of the dynamics. The experiment examines two types of deviations: $q$-size core deviations, for $q$ in $\{2, 3\}$ and $k$-improvement core deviations for $k$ in $\{1, 3/2, 2\}$ (notice that 1-improvement core deviations correspond to classical core deviations). For every possible combination of the parameters we sample 50 instances and run 50 dynamics for each of them.

**Results.** The obtained results are reported in the graphs and tables below. In every graph there is a plot for every considered value of probability $p$, showing for every considered value of $n$ the average number of deviations before the dynamics reaches a stable outcome, and its standard deviation (denoted by the transparent region around the plot). We say that a cycle is detected in the dynamics when the same coalition structure appears twice during the simulation. When there are instances for which at least a cycle in the dynamics is detected, we also provide a table showing the percentage of these instances, for every considered value of $n$ and $p$. For 2-size core dynamics, results are depicted in Fig. 19 and it is worth noticing the following facts:

* As known by the theoretical results (Theorem 3), all dynamics converge to stable outcomes.

* When starting from singleton coalitions, a stable outcome is reached in about $\frac{n}{2}$ deviations; in fact, agents organize themselves in pairs and, once in a pair, an agent will not perform another deviation.

* When starting from maximal connected components (corresponding to the grand coalition when the graph is connected) and with $p = 0.5$ and simple games, very few deviations are needed before reaching a stable outcome, because it is expected that a lot of agents are already experiencing a utility of about $\frac{1}{5}$, and therefore cannot belong to a blocking coalition of size 2.

* For S-FHGs, the initial state only affects the number of deviations before the dynamics reaches a stable outcome, given that the graphs show similar behaviors for the two considered typologies of initial states.

* Even if for S-FHGs the number of deviations before the dynamics reaches a stable outcome is significantly higher with respect to the one for SS-FHGs, the obtained graphs suggest that the growth in the number of deviations is polynomial in the number of agents.

For 3-size core dynamics, results on the number of deviations needed for convergence are depicted in Fig. 20, while in Table 2 the percentage of instances with (at least) a discovered cyclic dynamics is reported. It is worth remarking that:

<footnote n="4">⁴ Find the Julia code at https://github.com/angelofanelli/RelaxedCore.</footnote>
<figure><img src="image_23.png" /><figcaption>Fig. 19. Convergence of 2-size core dynamics.</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>Fig. 20. Convergence of 3-size core dynamics.</figcaption></figure>

• While, as known by the theoretical results (Theorem 4), all dynamics converge to stable outcomes for SS-FHGs, in the case of S-FHGs there are instances with cyclic dynamics. To this respect, notice that, when for all considered instances a cycle is detected in the dynamics, i.e., when the entry of Table 2 is 100, no value is depicted in the corresponding graph plot of Fig. 20.

• The percentage of instances with (at least) a discovered cyclic dynamics (shown in Table 2) increases as *n* and *p* increase.
<table><caption>**Table 2**
Percentage of instances for which at least a cycle has been detected in 3-size core dynamics.</caption><thead><tr><th colspan="6">S-FHGs from singletons</th><th colspan="6">S-FHGs from grand coalition</th></tr><tr><th>n</th><th>p=0.05</th><th>p=0.1</th><th>p=0.2</th><th>p=0.3</th><th>p=0.5</th><th>n</th><th>p=0.05</th><th>p=0.1</th><th>p=0.2</th><th>p=0.3</th><th>p=0.5</th></tr></thead><tbody><tr><td>10</td><td>0</td><td>2</td><td>2</td><td>12</td><td>30</td><td>10</td><td>0</td><td>0</td><td>10</td><td>8</td><td>24</td></tr><tr><td>20</td><td>2</td><td>6</td><td>20</td><td>62</td><td>94</td><td>20</td><td>0</td><td>4</td><td>26</td><td>60</td><td>96</td></tr><tr><td>30</td><td>0</td><td>12</td><td>74</td><td>90</td><td>100</td><td>30</td><td>0</td><td>10</td><td>68</td><td>92</td><td>100</td></tr><tr><td>40</td><td>2</td><td>24</td><td>96</td><td>100</td><td>100</td><td>40</td><td>4</td><td>32</td><td>96</td><td>100</td><td>100</td></tr><tr><td>50</td><td>16</td><td>62</td><td>100</td><td>100</td><td>100</td><td>50</td><td>10</td><td>56</td><td>100</td><td>100</td><td>100</td></tr><tr><td>60</td><td>20</td><td>82</td><td>100</td><td>100</td><td>100</td><td>60</td><td>32</td><td>78</td><td>100</td><td>100</td><td>100</td></tr><tr><td>70</td><td>36</td><td>80</td><td>100</td><td>100</td><td>100</td><td>70</td><td>36</td><td>94</td><td>100</td><td>100</td><td>100</td></tr><tr><td>80</td><td>54</td><td>100</td><td>100</td><td>100</td><td>100</td><td>80</td><td>34</td><td>92</td><td>100</td><td>100</td><td>100</td></tr><tr><td>90</td><td>56</td><td>98</td><td>100</td><td>100</td><td>100</td><td>90</td><td>54</td><td>100</td><td>100</td><td>100</td><td>100</td></tr><tr><td>100</td><td>62</td><td>100</td><td>100</td><td>100</td><td>100</td><td>100</td><td>70</td><td>100</td><td>100</td><td>100</td><td>100</td></tr></tbody></table>

<figure><img src="image_25.png" /></figure>

<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /></figure>

<figure><img src="image_28.png" /><figcaption>**Fig. 21.** Convergence of 1-improvement core dynamics.</figcaption></figure>

* As in the 2-size core dynamics, even if for S-FHGs the number of deviations before the dynamics reaches a stable outcome (for the instances in which no cycle is detected) is significantly higher with respect to the one for SS-FHGs, the obtained graphs suggest that the growth of the number of deviations is polynomial in the number of agents (for SS-FHGs the dependence seems to be even linear, while for S-FHGs the plot is compatible with a quadratic growth).

For 1-improvement core dynamics, results on the number of deviations needed for convergence are depicted in Fig. 21, while in Table 3 the percentage of instances with (at least) a discovered cyclic dynamics is reported. It is worth remarking that the experiments have been able to detect cyclic dynamics even in the simple setting of SS-FHGs with a small number of agents ($n = 20$). Finally, the odd shape of the plot for S-FHGs from grand coalition with $p = 0.5$ is due to the fact that, as it can be seen from Table 3, in this case and for $n \ge 10$, for a lot of instances a cyclic dynamics is detected (for $n = 20$ even the 95% of the considered instances) and therefore the plotted values refer to a very small set of instances.

For $\frac{3}{2}$-improvement core dynamics, results on the number of deviations needed for convergence are depicted in Fig. 22. Although Corollary 7 guarantees the existence of $\frac{3}{2}$-improvement core stable dynamics in SS-FHGs, nothing is known about the convergence of these dynamics. For the more general case of S-FHGs, even the existence of $\frac{3}{2}$-improvement core stable dynamics is not guaranteed by our theoretical results. It is worth remarking that the experimental evaluation has never detected a cycle in the $\frac{3}{2}$-improvement core dynamics, neither on SS-FHGs nor on S-FHGs, leaving open the possibility of a convergence result in this settings. Moreover, we can notice how the number of deviations before the dynamics reaches a stable outcome decreases in $\frac{3}{2}$-improvement core dynamics with respect to (classical) 1-improvement core dynamics.
<table><caption>**Table 3**
Percentage of instances for which at least a cycle has been detected in 1-improvement core dynamics.</caption><thead><tr><th colspan="6">SS-FHGs from singletons</th><th colspan="6">SS-FHGs from grand coalition</th></tr><tr><th>n</th><th>p=0.05</th><th>p=0.1</th><th>p=0.2</th><th>p=0.3</th><th>p=0.5</th><th>n</th><th>p=0.05</th><th>p=0.1</th><th>p=0.2</th><th>p=0.3</th><th>p=0.5</th></tr></thead><tbody><tr><td>5</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>5</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>10</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>10</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>15</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>15</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>20</td><td>0</td><td>0</td><td>0</td><td>0</td><td>10</td><td>20</td><td>0</td><td>0</td><td>5</td><td>0</td><td>0</td></tr></tbody></table><table><thead><tr><th colspan="6">S-FHGs from singletons</th><th colspan="6">S-FHGs from grand coalition</th></tr><tr><th>n</th><th>p=0.05</th><th>p=0.1</th><th>p=0.2</th><th>p=0.3</th><th>p=0.5</th><th>n</th><th>p=0.05</th><th>p=0.1</th><th>p=0.2</th><th>p=0.3</th><th>p=0.5</th></tr></thead><tbody><tr><td>5</td><td>0</td><td>0</td><td>0</td><td>0</td><td>5</td><td>5</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>10</td><td>0</td><td>0</td><td>10</td><td>25</td><td>20</td><td>10</td><td>0</td><td>0</td><td>0</td><td>5</td><td>30</td></tr><tr><td>15</td><td>0</td><td>0</td><td>5</td><td>35</td><td>55</td><td>15</td><td>0</td><td>0</td><td>5</td><td>30</td><td>45</td></tr><tr><td>20</td><td>0</td><td>0</td><td>20</td><td>45</td><td>95</td><td>20</td><td>0</td><td>5</td><td>20</td><td>60</td><td>95</td></tr></tbody></table>

<figure><img src="image_29.png" /><figcaption>**Fig. 22.** Convergence of 1/2-improvement core dynamics.</figcaption></figure>

For 2-improvement core dynamics, results on the number of deviations needed for convergence are depicted in Fig. 23. As known by Theorem 5, k-improvement core dynamics always converges for $k \ge 2$ and in fact no cycle is detected by our experiments. Finally, the number of deviations before the dynamics reaches a stable outcome further decreases in 2-improvement core dynamics with respect to (classical) 1/2-improvement core dynamics.

## 6. Concluding remarks and open problems

In this paper we have investigated some relaxed variations of core stability in the context of fractional hedonic games. See Section 1.1 for a full description of our results.

It is important to say that a paper by Demeulemeester and Peters [20] that has been published after the preliminary version of this paper [27] confirms two our conjectures: (i) every q-size core stable outcome in an S-FHG is also 1/2-improvement core stable and (ii) the price of anarchy of q-size stability in S-FHG is precisely 2q/q-1.

Several worthwhile research directions arise from this work.
<figure><img src="image_30.png" /><figcaption>Fig. 23. Convergence of 2-improvement core dynamics.</figcaption></figure>

First of all, in a general context, we believe that the investigated relaxed notions of core stability can be of interest for other class of games. For instance, the study of other classes of hedonic games would be a natural extension of our work: On the one hand, for the notion *q*-size core stability, also the most general model of hedonic games, in which every agent has a preference order over all possible coalitions she can belong to, could be studied, at least with respect to the existence and computability of stable solutions. On the other hand, when considering hedonic games in which every agent has a cardinal utility for any possible coalition she can belong to, it makes sense to study also the efficiency of stable solutions (besides their existence and computability) in terms of price of anarchy and price of stability, both for the notion of *q*-size core stability and for the notion of *k*-improvement core stability; to this respect, other notable classes of succinctly representable hedonic games, in which the utility are defined in terms of valuations between couples of agents, are the class of additively separable hedonic games (in which the utility of an agent for a coalition is simply given by the sum of all her valuations towards all other agents in the coalition) and the class of modified fractional hedonic games (in which the utility of an agent for a coalition is given by the sum of all her valuations towards all other agents in the coalition divided by its size minus one, i.e., the utility is the average valuation towards all other agents in the coalition). Some results on this direction have been recently proposed by Demeulemeester and Peters [20].

Furthermore, it is also worth investigating the considered relaxed notions of core stability in combination, i.e., by considering blocking coalitions of bounded cardinality in which every agent has to increase her utility by a given factor, as well as other possible relaxations of stability notions, also with respect to classical notions other than the core stability, with the aim of modeling practical scenarios of multi-agent systems in a more accurate way.

There are also open problems concerning the class of fractional hedonic games that we have considered in this paper. It is worth noticing that Aziz et al. [2] show an instance admitting no core stable outcome is provided. As a direct consequence, it follows that there must exist $\bar{q}$ and $\bar{k}$ such that no *q*-size core stable outcome exists for any $q \ge \bar{q}$ and no *k*-improvement core stable outcome exists for any $k \le \bar{k}$ (in particular, it holds that $\bar{q} = 11$ and $\bar{k} = 100/99$). To this respect, an open problem raised by our work is that of determining the maximum values of *q* and the minimum value of *k* for which *q*-size and *k*-improvement core stable outcomes, respectively, (i) are guaranteed to exist, (ii) can be efficiently computed and (iii) are guaranteed to be reached by any dynamics of the agents.

It would also be interesting to understand if, for $k < 2$, *k*-improvement core dynamics are guaranteed to converge, at least in SS-FHGs, and to study whether 2-size core dynamics (see Theorem 3) and *k*-improvement core dynamics (see Theorem 5) converge after a polynomial number of deviations. Moreover, it would be interesting to derive tight bounds to the *k*-improvement core price of stability for $k \in (1, 2)$, and to the *q*-size core price of stability. In particular, for the 2-size core price of stability, even determining whether it is equal to 1 or greater than 1 is a challenging open question.

Finally, in our experiments we have considered only basic synthetic data (i.e., we have generated the instances uniformly at random). We leave as future work the opportunity to perform experiments under alternative settings (e.g., generating instances using other meaningful probability distributions), as well as to identify a sufficiently large, meaningful, and recent real-world dataset suitable for experimentation.
CRediT authorship contribution statement

**Angelo Fanelli:** Writing – review & editing, Writing – original draft, Visualization, Software, Methodology, Investigation, Funding acquisition, Formal analysis, Data curation, Conceptualization. **Gianpiero Monaco:** Writing – review & editing, Writing – original draft, Visualization, Software, Methodology, Investigation, Funding acquisition, Formal analysis, Data curation, Conceptualization. **Luca Moscardelli:** Writing – review & editing, Writing – original draft, Visualization, Software, Methodology, Investigation, Funding acquisition, Formal analysis, Data curation, Conceptualization.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgement

Gianpiero Monaco and Luca Moscardelli acknowledge support by the PNRR MIUR project FAIR - Future AI Research (PE00000013), Spoke 9 - Green-aware AI, WP 9.2 "Interactions of greenaware agents", cascade sub-project "Existence, Complexity and Efficiency of Stable Solutions in Green-Oriented Games" – ECOGAMES, CUP D23C24000210006, and by the GNCS group of INdAM. Part of the research presented in this manuscript was carried out while Gianpiero Monaco was at Department of Information Engineering, Computer Science and Mathematics of the University of L'Aquila (Italy).

Data availability

A link to the code is available in the manuscript. Data is generated randomly.

References

[1] Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, Tim Roughgarden. The price of stability for network design with fair cost allocation, SIAM J. Comput. 38 (4) (2008) 1602-1623.

[2] Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, Dominik Peters, Fractional hedonic games, ACM Trans. Econ. Comput. 7 (2) (2019) 6:1-6:29.

[3] Haris Aziz, Felix Brandt, Paul Harrenstein, Fractional hedonic games, in: Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems, (AAMAS), 2014, pp. 5–12.

[4] Haris Aziz, Felix Brandt, Hans Georg Seidig, Computing desirable partitions in additively separable hedonic games, Artif. Intell. 195 (2013) 316–334.

[5] Haris Aziz, Bart de Keijzer, Complexity of coalition structure generation, in: Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), IFAAMAS, 2011, pp. 191–198.

[6] Haris Aziz, Serge Gaspers, Joachim Gudmundsson, Julián Mestre, Hanjo Täubig, Welfare maximization in fractional hedonic games, in: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, (IJCAI), 2015, pp. 461–467.

[7] Haris Aziz, Rahul Savani, Hedonic games, in: Handbook of Computational Social Choice, Cambridge University Press, 2016, pp. 356–376.

[8] Coralio Ballester, Np-completeness in hedonic games, Games Econ. Behav. 49 (1) (2004) 1–30.

[9] Suryapratim Banerjee, Hideo Konishi, Tayfun Sönmez, Core in a simple coalition formation game, Soc. Choice Welf. 18 (1) (2001) 135–153.

[10] Vittorio Bilò, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Nash stable outcomes in fractional hedonic games: existence, efficiency and computation, J. Artif. Intell. Res. 62 (2018) 315–371.

[11] Anna Bogomolnaia, Matthew O. Jackson, The stability of hedonic coalition structures, Games Econ. Behav. 38 (2) (2002) 201–230.

[12] Florian Brandl, Felix Brandt, Martin Strobel, Fractional hedonic games: individual and group stability, in: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, (AAMAS), 2015, pp. 1219–1227.

[13] Felix Brandt, Martin Bullinger, Leo Tappe, Stability based on single-agent deviations in additively separable hedonic games, Artif. Intell. 334 (2024) 104160.

[14] Felix Brandt, Martin Bullinger, Anaëlle Wilczynski, Reaching individually stable coalition structures in hedonic games, in: Proceedings of the 35th AAAI Conference on Artificial Intelligence, (AAAI), 2021, pp. 5211–5218.

[15] Simina Brânzei, Kate Larson, Coalitional affinity games and the stability gap, in: Craig Boutilier (Ed.), Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), 2009, pp. 79–84.

[16] Martin Bullinger, Pareto-optimality in cardinal hedonic games, in: Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, (AAMAS), 2020, pp. 213–221.

[17] Raffaello Carosi, Gianpiero Monaco, Luca Moscardelli, Local core stability in simple symmetric fractional hedonic games, in: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, (AAMAS), 2019, pp. 574–582.

[18] Katarína Cechlárová, Antonio Romero-Medina, Stability in coalition formation games, Int. J. Game Theory 29 (4) (2001) 487–494.

[19] Georgios Chalkiadakis, Edith Elkind, Michael Wooldridge, Computational Aspects of Cooperative Game Theory, Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers, 2011.

[20] Tom Demeulemeester, Jannik Peters, Relaxed core stability for hedonic games with size-dependent utilities, in: Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS), in: LIPIcs, vol. 272, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, pp. 41:1–41:14.

[21] Xiaotie Deng, Qizhi Fang, Algorithmic cooperative game theory, in: Altannar Chinchuluun, Panos M. Pardalos, Athanasios Migdalas, Leonidas Pitsoulis (Eds.), Pareto Optimality, Game Theory and Equilibria, in: Springer Optimization and Its Applications, Springer, 2008, pp. 159–185.

[22] Xiaotie Deng, Christos H. Papadimitriou, On the complexity of cooperative solution concepts, Math. Oper. Res. 19 (2) (1994) 257–266.

[23] Jacques Drèze, Joseph Greenberg, Hedonic coalitions: optimality and stability, Econometrica 48 (4) (1980) 987–1003.

[24] Edith Elkind, Angelo Fanelli, Michele Flammini, Price of Pareto optimality in hedonic games, Artif. Intell. 288 (2020) 103357.

[25] Edith Elkind, Talal Rahwan, Nicholas Jennings, Computational Coalition Formation, MIT Press, 2013.

[26] Paul Erdos, Tibor Gallai, Graphs with given degrees of vertices, Mat. Lapok 11 (1960) 264–274.

[27] Angelo Fanelli, Gianpiero Monaco, Luca Moscardelli, Relaxed core stability in fractional hedonic games, in: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, (IJCAI), 2021, pp. 182–188.
[28] Simone Fioravanti, Michele Flammini, Bojana Kodric, Giovanna Varricchio, *e*-fractional core stability in hedonic games, in: Proceedings of the 37th Annual Conference on Neural Information Processing Systems (NeurIPS), 2023.

[29] Michele Flammini, Bojana Kodric, Gianpiero Monaco, Qiang Zhang, Strategyproof mechanisms for additively separable and fractional hedonic games, J. Artif. Intell. Res. 70 (2021) 1253–1279.

[30] Michele Flammini, Bojana Kodric, Giovanna Varricchio, Strategyproof mechanisms for friends and enemies games, Artif. Intell. 302 (2022) 103610.

[31] Martin Gairing, Rahul Savani, Computing stable outcomes in symmetric additively separable hedonic games, Math. Oper. Res. 44 (3) (2019) 1101–1121.

[32] Christos Kaklamanis, Panagiotis Kanellopoulos, Konstantinos Papaioannou, Dimitris Patouchas, On the price of stability of some simple graph-based hedonic games, Theor. Comput. Sci. (2021).

[33] Elias Koutsoupias, Christos Papadimitriou, Worst-case equilibria, in: Proceedings of the 16th Annual Conference on Theoretical Aspects of Computer Science, (STACS), 1999, pp. 404–413.

[34] Gianpiero Monaco, Luca Moscardelli, Yllka Velaj, Stable outcomes in modified fractional hedonic games, Auton. Agents Multi-Agent Syst. 34 (1) (2020) 4.

[35] Martin Olsen, Nash stability in additively separable hedonic games and community structures, Theory Comput. Syst. 45 (4) (2009) 917–925.

[36] Martin Olsen, On defining and computing communities, in: Proceedings of the 18th Conference on Computing: The Australasian Theory Symposium, (CATS), 2012, pp. 97–102.

[37] Dominik Peters, Edith Elkind, Simple causes of complexity in hedonic games, in: Proceedings of the 24th International Joint Conference on Artificial Intelligence, (IJCAI), 2015, pp. 617–623.

[38] Talal Rahwan, Tomasz P. Michalak, Michael J. Wooldridge, Nicholas R. Jennings, Coalition structure generation: a survey, Artif. Intell. 229 (2015) 139–174.

[39] Tuomas Sandholm, Kate Larson, Martin Andersson, Onn Shehory, Fernando Tohmé, Coalition structure generation with worst case guarantees, Artif. Intell. 111 (1–2) (1999) 209–238.

[40] Lloyd Stowell Shapley, Martin Shubik, Quasi-cores in a monetary economy with nonconvex preferences, Econometrica 34 (4) (1966) 805–827.

[41] Mason Wright, Yevgeniy Vorobeychik, Mechanism design for team formation, in: Blai Bonet, Sven Koenig (Eds.), Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, 2015, pp. 1050–1056.