Relaxed Core Stability in Fractional Hedonic Games

1 Introduction

Hedonic games, introduced in [Drèze and Greenberg, 1980], represent the most important game-theoretic approach to the study of coalition formation problems. 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. Fractional hedonic games (FHGs), introduced in [Aziz et al., 2014] (see also [Aziz et al., 2019]), embody a natural and succinct graph representation subclass of hedonic games. In these games, 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. FHGs can model natural behavioral dynamics in social environments. Real-world examples include 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, simple symmetric fractional hedonic games (SS-FHGs), where symmetric valuations only take the values 0 and 1, suitably model a basic economic scenario referred to in [Aziz et al., 2019] as Bakers and Millers.

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, they could incur a proportional cost for deviating. For these reasons, in large and highly distributed multi-agent systems, the fact that the number of deviating agents can be arbitrarily high, and the fact that agents may benefit only by a tiny amount from their deviation suggest that the core is 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 [Aziz et al., 2019] 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, in order to enrich the set of admissible solutions. Specifically, our conceptual contributions are the notion of qsize 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. While the former is a notion of stability related to the one of q-strong Nash stability (with the notable difference that, in the context of q-strong Nash, the deviating agents are not forced to form a coalition together) and was also considered in the context of hedonic games [Carosi et al., 2019], to the best of our knowledge the latter has never been investigated in the context of noncooperative games. More specifically, it is worth noticing that, in the context of cooperative coalition formation games 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, a related notion is the one of strong ϵ-core [Shapley and Shubik, 1966], in which a blocking coalition has a valuation that is at least the sum of the current allocations of its agents plus ϵ; this definition leads to the one of least-core [Maschler et al., 1969], that is the strong ϵ-core with the smallest value of ϵ that makes the set of stable solutions non-empty. Our notion of k-improvement core stability differs from the one of strong ϵ-core because (i) in the spirit of non-cooperative 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 cooperative games, the gain is for the valuation of the whole blocking coalition and (ii) in the former such a gain is given by a multiplicative factor, while in the latter by an additive one.

As a case study, we investigate the considered relaxed concepts of stability in fractional hedonic games; in this context, we can summarize the results 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 a 2-size core stable outcome always exists and can be obtained through a 2-size core dynamics (Theorem 3). For simple games, 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). On the side of k-improvement core stability, we show that a k-improvement core stable outcome always exists for k ≥ 2 and can be obtained through a k-improvement core dynamics (Theorem 5). 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 ≥ 2(1 - 1/n), where n is the number of agents, through a simple algorithm (Theorem 6). For simple games, 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 ≥ 3/2 (Theorem 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 32 -improvement core stable (Theorem 2). We remark that the reason for considering the settings of q ≤ 3 and k ≥ 32 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 5 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 = 32

is reasonably small.

Finally, we focus on the efficiency of k-improvement core and q-size core stable outcomes (Section 4). We show that, for every k ≥ 1, in every game 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) and that such bound is tight (Theorem 9). We also provide similar analyses for 2-size core and 3-size core stable outcomes.

1.2 RelatedWork

Hedonic games have been introduced in [Drèze and Greenberg, 1980] and then further developed in [Banerjee et al., 2001; Bogomolnaia and Jackson, 2002; Cechlárová and Romero-Medina, 2001] (see [Aziz and Savani, 2016] for a nice survey on the topic).

Fractional hedonic games (FHGs) have been introduced in [Aziz et al., 2014] (see also [Aziz et al., 2019]) where it is shown 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. Various computational results for core and individual stability have been presented in [Brandl et al., 2015]. Local core stability, where there is a structural constraint on the blocking coalition, has been addressed in [Carosi et al., 2019]. [Bilò et al., 2018] study 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, in [Bilò et al., 2018] it is shown that, 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 can be found in [Kaklamanis et al., 2020]. FHGs have been also considered under different perspectives in [Aziz et al., 2015; Flammini et al., 2018; Flammini et al., 2021].

Modified fractional hedonic games (MFHGs), introduced in [Olsen, 2012], are very similar to fractional ones. A comparison between the two classes of games can be found in [Monaco et al., 2020]. The existence and the performance of natural stable outcomes like Nash, strong Nash, and core stable outcomes for MFHGs have been presented in [Monaco et al., 2019; Monaco et al., 2020].

Finally, the price of Pareto optimality for both MFHGs and FHGs has been studied in [Elkind et al., 2020].

2 Model and Preliminaries

For any n ∈ N, we denote by [n] the set {1, 2, . . . , n}.

A Symmetric Fractional Hedonic Game (S-FHG) G = (N, (vi)i∈N) is a game in which each agent i ∈ N, where N = [n], has a valuation vi : N → R≥0 , mapping every agent to a real non-negative value. We assume that the number of agents is n ≥ 2. We denote with vmax i (G) = maxj∈N vi(j) the maximum valuation of agent i for any other agent j ∈ N in the game G. We assume that vi(i) = 0 for every i ∈ N and that the valuations are symmetric, i.e., vi(j) = vj(i) for every i, j ∈ N.

If it holds that vi(j) ∈ {0, 1} for every i, j ∈ 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 nonnull valuations. Namely, for any i, j ∈ N, if vi(j) > 0, an edge {i, j} of weight w({i, j}) = vi(j) = vj(i) belongs to E. Analogously, an SS-FHG can be expressed by an unweighted graph G = (N, E) in which, for any i, j ∈ N, edge {i, j} belongs to E if and only if vi(j) = 1. Given a subset of agents C ⊆ 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 ∈ C, let δC(i) = ∑j∈C vi(j) be the sum of valuations of agent i for every agent belonging to coalition C. The utility or payoff µi(C) of agent i in coalition C such that C ∋ i is equal to δC(i) divided by the total number of agents in the coalition, that is µi(C) = δC(i) |C| . Notice that µi(C) ≤ |C|-1 |C| vmax i (G) ≤ n-1 n vmax i (G) for any agent i ∈ N and coalition C of a game G. An outcome of the game is a coalition structure C = {C1, . . . , Ch}. C is a partition of the agents into h coalitions, that is, ⋃t∈[h] Ct = N and Ct ∩ Cp = ∅ ∀t, p ∈ [h], with t ̸= p. We denote by C(i) the coalition agent i belongs to in coalition structure C. The utility µi(C(i)) of an agent i in coalition structure C is also denoted by µi(C).

Core stability. Given a coalition structure C, a blocking coalition for C is a set of agents C ⊆ N such that, for every agent i ∈ C, it holds that µi(C) > µi(C). Since vi(j) ≥ 0 and vi(i) = 0 for every i, j ∈ N, we have that |C| ≥ 2. A coalition structure C 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 ≥ 2, a q-size blocking coalition for C is a blocking coalition in which |C| ≤ q and (ii) given a real number k ≥ 1, a k-improvement blocking coalition for C is a set of agents C ⊆ N such that, for every agent i ∈ C, it holds that µi(C) > kµi(C). Notice that a blocking coalition is also a 1-improvement blocking coalition and an n-size blocking coalition. A coalition structure C 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′ ≤ q. Moreover, if a coalition structure is k-improvement core stable then it is k′ -improvement core stable for any k′ ≥ 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 〈C 0 , C 1 , . . .〉 such that for every consecutive pair (C t-1 , C t ), with t ≥ 1, there exists a blocking coalition (respectively q-size blocking coalition and k-improvement blocking coalition) C t for C t-1 = {C1, C2, . . . , Ch} whose deviation leads to the coalition structure C t = {C t , C1 \ C t , . . . , Ch \ C t } \ {∅}. Roughly speaking, the coalition structure C t is obtained by letting all agents in C t form a new coalition together, thus leaving the coalitions they belonged to in C t-1 . We say that a finite dynamics D = 〈C 0 , C 1 , . . . , C ℓ 〉 of length ℓ ≥ 1, leads to coalition structure C ℓ starting from the initial coalition structure C 0 . A game is core (respectively, q-size core and k-improvement core) convergent if, for any coalition structure C, every dynamics starting from C is finite.

Social welfare. The social welfare of a coalition structure C = {C1, . . . ,Cℓ} is given by the sum of the agent utilities, i.e., SW(C) = ∑i∈N µi(C). 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(C) = ∑C∈C SW(C) = ∑C∈C ∑i∈C µi(C).

Efficiency. Given a game G, let C ∗ (G) be the outcome maximizing the social welfare, and let q-SIZE 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. 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, q-SIZE CPOA(G) = maxC∈q-SIZE CORE(G) SW(C∗ (G)) SW(C) (respectively k-IMPR CPOA(G) = maxC∈k-IMPR CORE(G) SW(C∗ (G)) SW(C) ).

2.1 Preliminary Results

We first present 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.

It is also possible to show that the analysis of Theorem 1 is tight even for SS-FHG.

We also show that, for every SS-FHG, any 3-size core stable coalition structure is 32 -improvement core stable.

Theorem 2. For every SS-FHG, any 3-size core stable coalition structure is 32 -improvement core stable.

Proof. In this proof we exploit the graph representation 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 C is a 3-size core stable coalition structure of G. Let us suppose, by contradiction, that C admits a 3 2 -improvement blocking coalition C. Remind that µi(C) ≤ n-1 n for any i ∈ C. First notice that, for any i ∈ C, it holds that µi(C) < 2 3 (because they belong to the 3 2 -improvement blocking coalition C and in any coalition structure each agent gets utility of at most 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 2 3 and this is a contradiction to the fact that C is a 3-size core stable coalition structure of G.

Consider any edge {i, j} in G(C). It holds that either µi(C) ≥ 12 or µj(C) ≥ 12 because otherwise i and j together form a 2-size blocking coalition for C, and this is a contradiction to the fact that C is a 3-size core stable coalition structure of G. Without loss of generality, let us assume that µi(C) ≥ 1 2 . Then, since i belongs to C, we have that µi(C) > 3 2 12 = 34 . 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 µi(C) = x |C| > 34 . Thus, any agent j connected to i in G(C) gets utility of at most |C|-x |C| < 14 . Since j is a member of the 3 2 -improvement blocking coalition C, we get that µj(C) < 16 .

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 µj(C) < 1 6 , µz(C) < 16 and µi(C) < 2 3 . Therefore, agents i, j and z together form a 3-size blocking coalition for C. This is a contradiction to the fact that C is a 3-size core stable coalition structure of G.

It is possible to show that the analysis of Theorem 2 is tight. As a last remark, it is possible to show that the converses of Theorems 1 and 2 do not hold.

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.

Sketch of Proof. We exploit a potential function argument. Consider any 2-size core dynamics D starting from any coalition structure C 0 . We show that D = 〈C 0 , C 1 . . .〉 has finite length, i.e., that a 2-size core stable coalition structure is eventually reached. For any t ≥ 0, let ⃗xt be the vector obtained by listing the utilities of all agents involved in some of the first t improvement deviations of D in non-increasing order (notice that these agents belong to a coalition of cardinality at most 2 in any coalition structure C p with p ≥ t). As usual, given two n-dimensional vectors ⃗y and ⃗y′ , the first one is smaller than the second one for the lexicographical order (and we write ⃗y ≺ ⃗y′ ) if either yp is a prefix of y′p or yp < y′p for the first component p such that yp ̸= y′p . It is possible to show that, for any t ≥ 1, ⃗xt-1 ≺ ⃗xt .

We are also able to provide a similar result holding for 3size 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.

Sketch of Proof. In this proof, it is convenient to exploit the graph representation 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 C 0 . We show that D = 〈C 0 , C 1 . . .〉 has finite length, i.e., that a 3-size core stable coalition structure is eventually reached. For any t ≥ 1, let C t be the 3-size blocking coalition for C t-1 whose deviation leads to C t . It is worth noticing that, for any t ≥ 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 C, let α(C) (respectively β(C) and γ(C)) be the number of coalitions in C being triangles (respectively path of 3 nodes and cliques of 2 nodes).

For any t ≥ 0, let ⃗xt be the triple defined as (α(C t ), β(C t ) + γ(C t ), β(C t )). It is possible to show, by performing a case-by-case analysis, that, for any t ≥ 0, ⃗xt-1 ≺ ⃗xt , i.e., the considered triple always lexicographically increases 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 ≥ 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 ≥ 2.

Notice that, by Theorem 5, we directly get that every S-FHG admits a k-improvement core stable coalition structure, for every k ≥ 2, that can be obtained by running a kimprovement 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 ≥ 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. 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 ≥ 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 ≥ 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 [Monaco et al., 2020]. The algorithm works in phases t = 1, 2, . . . . Let G 0 = G. For any t ≥ 1, let G t = (N t , (vi)ti∈N t) be the resulting sub-game obtained after phase t. In any phase t ≥ 1, a new coalition isomorphic to a clique of size 2 is added to C as follows: Let vt-1 max = vi(j) = vj(i), for some i, j ∈ N t-1 , be the maximum valuation of two agents in G t-1 , that is, vt-1 max = maxi∈N t-1 vmax i (G t-1 ). We add to C the coalition formed by agents i and j, i.e., C = C ∪ {i, j}. Moreover, let G t such that N t = N t-1 \ {i, j}. The algorithm stops when |N t | ≤ 1. In particular, if |N| mod 2 = 0 (resp. |N| mod 2 = 1), the algorithm ends by returning C (resp. C ∪{i} where N t = {i}). Since at each 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 C is a 2(1-1/n)- improvement core stable coalition structure of G. In C, agents i and j selected at phase t = 1 get each utility of v0max 2 . Remind that µi(C) ≤ n-1 n v0max and µj(C) ≤ n-1 n v0max , for any possible coalition structure C. It implies that agents i and j cannot belong to a k-improvement blocking coalition for C, for any k ≥ 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 \ N z , cannot belong to any k-improvement blocking coalition for C, for any k ≥ 2(1 - 1/n), then agents iz+1 and jz+1 selected in the phase z + 1 of the algorithm cannot belong to any k-improvement blocking coalition for C, for any k ≥ 2(1 - 1/n), as well. In fact, suppose that such agents have a certain utility in the coalition C. For the inductive hypothesis we have that they can create a k-improvement blocking coalition for C, for any k ≥ 2(1-1/n), only with agents belonging to N z . However, since they have utility vzmax 2 and cannot get utility higher than n-1 n vzmax , 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.

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 ≥ 3/2.

Theorem 7. Every SS-FHG admits a k-improvement core stable coalition structure that can be computed in polynomial time, for every k ≥ 3/2.

4 Efficiency

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 ≥ 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 ≥ 1, k-IMPR CPOA(G) ≤ 2k.

Proof. First of all, we need some additional notation and definitions. Let δ> C (i) = ∑j∈C,j>i vi(j) be the sum of valuations of agent i for every agent j > i belonging to coalition C. Analogously, let µ>i (C) = δ> 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

Let C ∗ (G) be an optimal coalition structure and C be any k-improvement core stable coalition structure of game G. We aim at showing that SW(C∗ (G)) SW(C) ≤ 2k.

For any C ∗ ∈ C ∗ (G), consider the following process composed by |C ∗ | phases:

• Phase 1. Let C ∗ 1 = C ∗ . Since C is k-improvement core stable, coalition C ∗ 1 cannot be a k-improvement blocking coalition for C, thus implying that there exists an agent, say agent i1, such that µi1 (C ∗ 1 ) ≤ kµi1 (C).
• Phase t (t = 2, . . . , |C ∗ |). Let C ∗ t = C ∗ t-1 \ {it-1}. Since C is k-improvement core stable, coalition C ∗ t cannot be a k-improvement blocking coalition for C, thus implying that there exists an agent, say agent it, such that µit (C ∗ t ) ≤ kµit (C).

Assume, without loss of generality, that the agents are numbered such that i1 < i2 < . . . < i|C∗ |. Notice that the property of this assumption can be simultaneously obtained for all coalitions of C ∗ , for instance assigning to all agents in a same coalition consecutive numbers that respect the desired ordering. By this assumption, for any t = 1, . . . , |C ∗ |, it holds that

By summing over all agents in coalition C ∗ , we obtain

where the first equality holds by (1), the first inequality holds by (2) and the last inequality holds because, for every t = 1, . . . , |C ∗ |, it is selected at phase t of the above described process as an agent in C ∗ t such that µit (C ∗ t ) ≤ kµit (C). By applying the last inequality to every coalition in C ∗ (G), we finally obtain

We now 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-IMPR CPOA(G) ≥ 2. Moreover, for every k > 1 and ϵ ∈ (0, 1/2], there exists an infinite collection of SS-FHGs such that, for every game G belonging to it, it holds that k-IMPR CPOA(G) ≥ 2k(1 - ϵ).

Sketch of Proof. We first focus on the case k > 1. For every triple (p, q, d) of positive integers, such that p > q and pq is even, we construct an unweighted graph G representing a game G as follows. The set of nodes of G is partitioned into subset M = {1, 2, . . . ,m} of size m ≥ 2, and m subsets L1,L2, . . . ,Lm, each of size d, with m = p(d + 1). We assume that ⋃mj=1 Lj is an independent set in G, while the subgraph induced by M is a t-regular graph, with t = q(d + 1); notice that, by definition of t and m, this subgraph is well defined (in fact, as it is well known, there always exists a tregular graph on m nodes when m ≥ t + 1 and mt is even). Finally, each i ∈ M is connected to each node in Li.

Let us consider the coalition structure C made of coalition M and md singleton coalitions, one for each node in ⋃mj=1 Lj. It can be proved that C is p/q-improvement core stable. In order to evaluate the efficiency of C, we compare its social welfare with the social welfare of the coalition structure ¯ C, made of m coalitions, in which each agent i ∈ M makes a coalition with the corresponding set Li. The social welfare of ¯ C is m 2d d+1 = 2pd. On the other hand, the social welfare of C is ∑i∈M µi(C) = t = q(d + 1). It follows that the pq -improvement price of anarchy of G is at least SW ( ¯ C )/SW(C) = 2pd q(d+1) = 2 pq (1- 1 d+1 ). The claim follows by observing that for every pair of rational numbers k > 1 and ϵ ∈ (0, 1/2], there are infinite ways of choosing the triple (p, q, d) such that k = p/q and ϵ = 1 d+1 .

For the case k = 1, we can prove the claim by simplifying the construction presented above, in particular by imposing that the subgraph induced by M is a clique.

We now focus on the q-size core price of anarchy, for q ∈ {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 32 -improvement core stable outcome. Therefore, by Theorem 8, the following upper bounds can be directly obtained.

Theorem 10. For any S-FHG G it holds that 2-SIZE CPOA(G) ≤ 4; moreover, for any SS-FHG G, it holds that 3-SIZE CPOA(G) ≤ 3.

By exploiting the same ideas of the construction of Theorem 9, it is possible to show that, for any ϵ > 0 and any integer q ≥ 2, there exists a game G such that q-SIZE CPOA(G) ≥ 2 q q-1 - ϵ, thus proving the tightness of the bounds provided by the last theorem.

5 Concluding Remarks and Open Problems

In this paper we have investigated some relaxed variations of core stability in the context of fractional hedonic games. Several worth investigating research directions arise from this work. 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 and could be also investigated in combination, i.e., by considering blocking coalitions of bounded cardinality in which every agent has to increase her utility by a given factor. Moreover, it would be interesting to study other possible relaxations of stability notions, also with respect to classical notions other than the core stability, that can lead to model practical scenarios of multi-agent systems in a more accurate way.

We now focus on the open problems for the considered class of fractional hedonic games. It is worth noticing that, in [Aziz et al., 2019], an instance admitting no core stable outcome is provided. As a direct consequence, it follows that there must exist ¯ q and ¯ k such that no q-size core stable outcome exists for any q ≥ ¯ q and no k-improvement core stable outcome exists for any k ≤ ¯ k (in particular, it holds that ¯ q = 11 and ¯ 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 kimprovement 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.

Another interesting research direction is that of investigating the relations between q-size and k-improvement core stable outcomes. To this respect, some preliminary results are provided by Theorems 1 and 2. More generally, we conjecture that any q-size core stable coalition structure is q q-1 - improvement core stable.

With respect to the efficiency, it is worth studying the q-size core price of anarchy of SS-FHGs and S-FHGs, in order to provide suitable upper bounds for the cases q ≥ 4 and q ≥ 3, respectively; to this respect, given the lower bound described after Theorem 10, we conjecture that the q-size core price of anarchy of SS-FHGs and S-FHGs is 2q q-1 for any integer q.

Finally, we would like to focus on the q-size and kimprovement core price of stability, that can be naturally defined, similarly to the q-size and k-improvement core price of anarchy, as the ratio between the social optimum and the social welfare of the best stable outcome. 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 the theorems provided in this paper. In particular, for S-FHGs, the k-improvement core price of stability is 1 for k ≥ 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 then its core price of anarchy. For SS-FHGs, by exploiting the fact that, by Theorem 7, a 32 -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 32 -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 ∈ [3/2, 2). A lower bound of 2 to the core price of stability is provided in [Carosi et al., 2019, Theorem 5.1] when considering a notion of core stability in which there is a structural property the blocking coalition has to satisfy, thus implying that the (1-improvement) core price of stability is at least 2: a matching lower bound for the case k = 1. Therefore, it would be very interesting to solve the open problem of deriving tight bounds to the k-improvement core price of stability for k ∈ (1, 2), besides the one of determining the q-size core price of stability.