Additively separable hedonic games with social context

Monaco, Gianpiero; Moscardelli, Luca; Velaj, Yllka Article Additively separable hedonic games with social context Games Provided in Cooperation with: MDPI – Multidisciplinary Digital Publishing Institute, Basel Suggested Citation: Monaco, Gianpiero; Moscardelli, Luca; Velaj, Yllka (2021) : Additively separable hedonic games with social context, Games, ISSN 2073-4336, MDPI, Basel, Vol. 12, Iss. 3, pp. 1-14, https://doi.org/10.3390/g12030071 This Version is available at: https://hdl.handle.net/10419/257553 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by/4.0/ games Article Additively Separable Hedonic Games with Social Context † Gianpiero Monaco 1,*, Luca Moscardelli 2and Yllka Velaj 3   Citation: Monaco, G.; Moscardelli, L.; Velaj, Y. Additively Separable Hedonic Games with Social Context. Games 2021,12, 71. https://doi.org/ 10.3390/g12030071 Academic Editors: Ulrich Berger and Stefano Moretti Received: 26 July 2021 Accepted: 13 September 2021 Published: 18 September 2021 Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations. Copyright: © 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). 1Department of Information Engineering, Computer Science and Mathematics, University of L’Aquila, 67100 L’Aquila, Italy 2Department of Economic Studies, University of Chieti-Pescara, Viale Pindaro 42, 65125 Pescara, Italy; [email protected] 3Faculty of Computer Science, University of Vienna, 1090 Vienna, Austria; [email protected] *Correspondence: gianpier[email protected]; Tel.: +39-0862433142 † Preliminary results about this work have been presented in the 19th Italian Conference on Theoretical Computer Science (ICTCS 18). Monaco, G.; Moscardelli, L.; Velaj, Y. Hedonic Games with Social Context. In Proceedings of the 19th Italian Conference on Theoretical Computer Science (ICTCS), CEUR-WS.org, 2018; pp. 24–35. Abstract: In hedonic games, coalitions are created as a result of the strategic interaction of independent players. In particular, in additively separable hedonic games, every player has valuations for all other ones, and the utility for belonging to a coalition is given by the sum of the valuations for all other players belonging to it. So far, non-cooperative hedonic games have been considered in the literature only with respect to totally selfish players. Starting from the fundamental class of additively separable hedonic games, we define and study a new model in which, given a social graph, players also care about the happiness of their friends: we call this class of games social context additively separable hedonic games ( SCASHG s). We focus on the fundamental stability notion of Nash equilibrium, and study the existence, convergence and performance of stable outcomes (with respect to the classical notions of price of anarchy and price of stability) in SCASHG s. In particular, we show that SCASHG s are potential games, and therefore Nash equilibria always exist and can be reached after a sequence of Nash moves of the players. Finally, we provide tight or asymptotically tight bounds on the price of anarchy and the price of stability of SCASHGs. Keywords: coalition formation; hedonic games; nash equilibrium; price of anarchy; price of stability; social context 1. Introduction In many economic, social and political situations, individuals carry out activities in groups rather than alone and on their own. In these scenarios, understanding the happiness of each member of the group becomes of crucial importance. As examples, the utility of an individual in a group sharing a resource depends both on the consumption level of the resource and on the identity of the members in the group; similarly, the utility for a party belonging to a political coalition depends both on the party trait and on the identity of its members. Moreover, another important issue is that of investigating the dynamics that regulates coalition formation. Dréze and Greenberg [ 1 ] introduced hedonic games, in which players have preferences over the set of all possible player coalitions. In particular, the utility of a player only depends on the composition of the coalition (or group) she belongs to. Hedonic games constitute a framework for formally studying the stability and the evolution of the process of forming player coalitions. Given that they model natural behavioral dynamics of real-life situations, this class of games has received great interest in the literature: in economic, social and political environments, in fact, individuals perform activities in groups rather than by themselves. Consider, for instance, the following scenarios: a company has to assign its employees to different work teams so that they can profitably collaborate; Games 2021,12, 71. https://doi.org/10.3390/g12030071 https://www.mdpi.com/journal/games Games 2021,12, 71 2 of 14 in a social network, users want to form groups in which they can speak of and share common interests. Additively separable hedonic games constitute a natural and succinctly representable class of hedonic games. In these games, each player has a value for any other player, and the utility of a coalition to a particular player is simply the sum of the values she assigns to the members of her coalition. Additive separability satisfies a number of desirable axiomatic properties [ 2 ] and are the non-transferable utility generalization of graph games studied by Deng and Papadimitriou [ 3 ]. While the standard model of additively separable hedonic games assumes that players are totally selfish, in this paper we are interested in analyzing the case in which players take into account also the happiness of their friends, therefore adding to the original model a sort of altruism. Coming back to the above described scenarios, it is likely that, among the corporate employees, several friendship relations exist, not necessarily between people able to profitably collaborate together. Moreover, social network users often include people coming from the same family; even if they are of different ages and therefore are expected to gladly belong to different groups, they are also interested in the happiness of their relatives. We call these games Social Context Additively Separable Hedonic Games ( SCASHG s) and we believe that they are able to model in a more accurate way the phenomenon of coalition formation in many realistic scenarios. In fact, in SCASHG s the behavior of every player also depends on the happiness of her friends, as it is in the above described scenarios. In SCASHG s, valuations are additive and each player i has a valuation vij for any other player j , but there is a crucial difference with respect to the classical additively separable hedonic games: while in the classical model the utility of a coalition to a particular player is simply given by the sum of the valuations she assigns to the members of her coalition, in SCASHGs there is another additive term that contributes to form the utility of a player, that is equal to the sum of the valuations her friends assign to the members of their own coalitions (this contribution is multiplied by a given parameter α∈[ 0, 1 ] ). In particular, for α= 0, SCASHG s are equivalent to the classical additively separable hedonic games (i.e., a totally selfish setting is considered), while for α= 1 a fully altruistic setting can be modeled. In order to model the friendship relations, a SCASHG is also defined by a graph representing an underlying social network: nodes are players and an edge connecting two players expresses friendship between them. Arguably, as a first step in the study of SCASHG s, it is natural to consider symmetric friendship relations and therefore, in this paper, we focus on undirected graphs. In Figure 1, for example, we can see that the utility of player 5 is equal to v1,5 +v2,5 + α(v1,5 +v2,5 +v3,4) = 2 + 3 +α( 2 + 3 + 1 ) , where 2 + 3 is the sum of valuations of the players in her coalition and α( 2 + 3 + 1 ) is the sum of valuations her friends 1, 2 and 3 assign to the members of their own coalitions, multiplied by α. 1 2 3 4 5 1 2 3 4 5 (i,j)vi,j (1,3) 1 (2,5) 3 (1,5) 2 (3,4) 1 Figure 1. A social network G, a coalition structure Cand the non-null valuations vi,j. Our aim is to study the existence and performance of natural stable outcomes for SCASHG s. We will focus on Nash stable outcomes, i.e., outcomes in which no player can improve her utility by unilaterally changing her own coalition. In particular, we evaluate the performance of Nash outcomes for SCASHG s by means of the widely used notions of price of anarchy and price of stability: the former is defined as the ratio between the social optimum value and the social value of the worst stable outcome, while the latter Games 2021,12, 71 3 of 14 is defined as the ratio between the social optimum value and the social value of the best stable outcome. 1.1. Our Results First of all, we provide an exact potential function for SCASHG s, thus proving that these games always possess a pure Nash equilibrium and also that the convergence to Nash equilibria is guaranteed. In order to evaluate the performance of SCASHG s, we consider two social welfare functions. The first social function, SW , is given by the summation, for each player, of the values she assigns to the members of her coalition, while the second social function, denoted by SW , is the summation of the players’ utilities (taking into account, for any player, also the contribution due to the valuations of her friends multiplied by α ). In fact, we evaluate, for both of them, the performance of the Nash outcomes by means of the notions of price of anarchy and price of stability ( PoA and PoA denote the price of anarchy with respect to SW and SW , respectively; analogously PoS and PoS denote the price of stability with respect to SW and SW, respectively). In presence of negative valuations, both PoS and PoS (and therefore also PoA and PoA ) can be unbounded. Furthermore, in some cases we are able to provide instances in which the social value of any equilibrium C is negative while the optimal solution lead to a positive outcome. We subsequently turn our attention to the case of non-negative valuations and prove that the price of anarchy is Θ(n), while the price of stability is 1. 1.2. Related Work Hedonic games have been broadly studied in the literature. They have been first considered by Dréze and Greenberg [ 1 ], who analyze them under a cooperative perspective. Bogomolnaia and Jackson [ 4 ] and Banerjee et al. [ 5 ] then have defined hedonic games in their present form as a simple but very versatile model of coalition formation. Feldman et al. [ 6 ] investigate some interesting subclasses of hedonic games from a noncooperative point of view, by characterizing Nash equilibria and providing upper and lower bounds on both the price of stability and the price of anarchy. Peters and Elkind [ 7 ] consider several classes of hedonic games and identify simple conditions on expressivity that are sufficient for the problem of checking whether a given game admits a stable outcome to be computationally hard. Additively separable hedonic games have been first considered by Bogomolnaia and Jackson [ 4 ] who show that Nash stable outcomes are not guaranteed to exist for games with asymmetric valuations. However, for symmetric valuations, the existence of a Nash stable outcome is guaranteed by potential function argument [4]. Ballester [8] and Sung and Dimitrov [ 9 ] show that the problem of checking whether an instance admit a Nash stable outcome is NP-complete and NP-complete in the strong sense, respectively. Olsen [ 10 ] proves that the problem of deciding whether a non-trivial Nash stable coalition exists in additively separable hedonic games with non-negative and symmetric preferences is NP-complete. Aziz et al. [ 11 ] show that checking the existence of a core stable outcome is NP-hard even for symmetric valuations. Concerning the performance of Nash stable outcomes in additively separable hedonic games with symmetric valuations, it is easy to check that the price of anarchy is unbounded [ 12 ] and that the price of stability is 1 since an optimal outcome is always Nash stable (it can be easily proved by using the potential function). Fractional hedonic games are close to additively separable ones. The difference is that the utility of each player is divided by the size of her coalition. They have been first considered by Aziz et al. [ 13 ] (see also [ 14 ]), who prove that the core can be empty for asymmetric valuations and that it is not empty for some special cases. Brandl et al. [ 15 ] also study the existence of core as well as individual stability in fractional hedonic games. Bilò et al. [ 16 ] consider Nash stable outcomes for fractional hedonic games and study their existence and complexity. Kaklamanis et al. [ 17 ] also consider Nash stable outcomes and provide some improved results on the price of stability. Carosi et al. [ 18 ] consider local core Games 2021,12, 71 4 of 14 stability in fractional hedonic games with binary symmetric valuations and show that any local core dynamics converges, which implies that a local core stable coalition structure always exists. Finally, Aziz et al. [ 19 ] consider the computational complexity of computing welfare maximizing partitions (not necessarily Nash stable) for fractional hedonic games played on undirected graphs. Modified fractional hedonic games are very similar to fractional hedonic ones. The difference is that the utility of each player is averaged over all the other members of that coalition (i.e., excluding herself). Olsen [ 20 ] is the first to consider these games and investigates computational issues about Nash stable outcomes. Monaco et al. [ 21 , 22 ] completely characterize the existence of fundamental stable outcomes and show tight results on their performance. Elkind et al. [ 23 ] study the set of Pareto optimal outcomes for modified fractional hedonic games with symmetric valuations. From a different perspective, strategy proof mechanisms for additively separable hedonic and fractional hedonic games have been proposed in [ 24 , 25 ]. Moreover, Flammini et al. [ 26 ] consider the problem of maximizing the social welfare in additively separable and fractional hedonic games in the online setting. Hedonic games are being widely investigated also under different utility definitions: For instance, in [ 27 , 28 ], coalition formation games, in which player utilities are proportional to their harmonic centralities in the respective coalitions, are considered. In our paper, we deal with selfish players having also a certain degree of altruism. To this respect, our work is related to social context games. These games have been introduced in [ 29 ] and are defined by an underlying game in strategic form, and a social context consisting of an undirected graph and an aggregation function. In [ 29 ], the authors consider resource selection games as the underlying game and they study the existence of pure strategy Nash equilibrium. Building on this model, Bilò et al. [ 30 ] investigate social context games in which the underlying games are linear congestion games and Shapley cost sharing games, while the aggregation functions are min, max and sum. Moreover, Anagnostopoulos et al. [ 31 ] study the effects of the altruistic behavior of players showing that the price of anarchy may increase as the players become more altruistic. They show that this increase is modest for congestion games and min-sum scheduling games, whereas it might be drastic for generalized second price auctions. The interests on altruistic players have been also modeled and studied by Hoefer and Skopalik [ 32 ]: they focus on the existence and complexity of pure Nash equilibria with altruistic players in atomic congestion games. Chen et al. [ 33 ] study the inefficiency of equilibria for several classes of games such as cost-sharing games, utility games and linear congestion games. Salehi-Abari and Boutilier [ 34 ] study social choice with empathetic preferences and their local empathetic model is related to the model presented in [ 35 ]. Finally, Brânzei and Larson [36] study social distance games. In these games a player’s opinion on her friends (players of distance one) has the highest weight while her opinion on players farther away counts less. To the best of our knowledge, few papers deal with the notion of altruism in hedonic games. Nguyen et al. [ 35 ] define altruistic hedonic games where the satisfaction of players’ friends is taken into account according to three degrees of altruism, from being selfish first, over aggregating opinions of a player and her friends equally, to altruistically letting one’s friends decide first. They study both the axiomatic properties of these games and the computational complexity of problems related to common stability concepts. In [ 37 ], Umar and Mesbah model the problem of joint coalition formation and bandwidth allocation in ad hoc radio networks made of selfish/altruistic nodes as a hedonic coalition formation game with non-transferable utility. The authors study the computational complexity and convergence properties of the proposed hedonic algorithm under selfish and altruistic preferences, and present means to guarantee Nash stability. Finally, it is also worth mentioning some related literature on network formation games, in which interestingly the considered games are shown to be potential games as in our paper: in [ 38 ], Badev deals with a setting in which the utility of the players is Games 2021,12, 71 5 of 14 influenced by the friendship relations and vice-versa, while Kinateder and Merlino [ 39 ] study a network creation game in which benefits are shared among neighbors. Mele [ 40 ] proposes an empirical model of social network formation, combining strategic and random connections among players. Bourlès et al. [ 41 ] provide an interesting analysis of altruism in networks: agents are embedded in a fixed network and care about the well-being of their network neighbors, i.e., they may provide financial support to their poorer friends. 1.3. Paper Organization The paper is organized as follows. In Section 2we formally define social context additively separable hedonic games. The technical contributions of the paper are then presented in Sections 3–5which address the existence of Nash outcomes, the results on the price of anarchy and those on the price of stability, respectively. Finally, in Section 6we list some interesting open problems. 2. Model For an integer k>0, denote by [k]the set {1, . . . , k}. We model Social Context Additively Separable Hedonic Games ( SCASHG s) by means of a valuation function v , an undirected graph G= (N , E) and a given parameter α∈[ 0, 1 ] . We denote with n=|N| the number of nodes of G and with E the set of edges between the nodes, which represent the friendship relation. v:N×N→ R is the symmetric valuation function. We do not require any dependence between v and H , thus allowing for two friends to have a mutual negative valuation (as it is in the scenario described in the Introduction, in which, among the corporate employees, several friendship relations may exist, not necessarily between people able to profitably collaborate together). Nevertheless, all obtained results also hold for the special notable case in which the valuations between friends have to be positive: all positive results clearly hold also in this specific setting, while all remaining ones (given in Proposition 1, Theorem 2, Theorem 5and Theorem 6) exploit constructions in which negative valuations exist only between players not connected by an edge in graph G . For the sake of convenience, we adopt the notation (i , j) and vi,j to denote the pair {i,j} ∈ N×Nand its valuation v({i,j}), respectively. Given a symmetric valuation function v , an undirected graph G= (N , E) and a value for α , the Social Context Additively Separable Hedonic Game induced by G , v and α , denoted as G(G , v , α) , is the game in which each node i∈N is associated with a player. We assume that players are numbered from 1 to n and, for every i∈[n] , each player chooses to join a certain coalition among n candidate ones: the strategy σi of player i is an integer j∈[n] , meaning that player iis selecting candidate coalition Cj. A strategy profile (σ1 , . . . , σn) directly induces an outcome C={C1 , C2 , . . . , Cn} , in which, for any j∈[n],Cj={i|σi=j}. In turn, an outcome C={C1,C2, . . . , Cn}naturally induces a coalition structure, i.e., a partition of the set of players into k≤n coalitions Ch1 , . . . , Chk such that, for any j∈[k] , Chj6=∅ (i.e., empty candidate coalitions are excluded from the partition), Sj∈[k]Chj=N and Chi∩Chj=∅ for any i , j∈[k] with i6=j . For the sake of brevity, we denote by C also the coalition structure induced by C . If i∈Cj , we say that player i is a member of the coalition Cj . We denote by C(i) the coalition in C of which player iis a member. In an outcome C, the utility of player iis defined as ui(C) = ui(C) + α·∑ (i,j)∈E uj(C), where, for every i∈[n],ui(C) = ∑j∈C(i)vi,j. Each player chooses the coalition she belongs to with the aim of maximizing her utility. We denote by (C , i , j) , the new coalition structure obtained from C by moving player i from C(i) to Cj ; formally, (C , i , j) = C \ {C(i) , Cj} ∪ {C(i)\ {i} , Cj∪ {i}} . A player deviates if she changes the coalition she belongs to. Given an outcome C , an improving move (or simply amove) for player i is a deviation to any coalition Cj that strictly increases her utility, i.e., ui((C , i , j)) >ui(C) . Moreover, player i performs a best-response in coalition structure C by Games 2021,12, 71 6 of 14 choosing a coalition providing her the highest possible utility (notice that a best-response is also a move when there exists a coalition Cj such that ui((C , i , j)) >ui(C) . A player is stable if she cannot perform a move. An outcome is (pure) Nash stable (or a Nash equilibrium) if every player is stable. An improving dynamics, or simply a dynamics, is a sequence of improving moves, while a best-response dynamics is a sequence of best-responses. A game has the finite improvement path property if it does not admit an improvement dynamics of infinite length. Clearly, a game possessing the finite improvement path property always admits a Nash stable outcome. We denote with N (G(G , v , α)) the set of Nash stable outcomes of G(G , v , α) . The social welfare of a coalition structure C is the summation of the players’ utilities, i.e., SW(C) = ∑i∈Nui(C). We define also a second social welfare function SW(C) = ∑i∈Nui(C) which is given by the summation, for each player, of the valuations she assigns to the members of her coalition (without considering her friends’ utilities). Given a game G(G , v , α) , an optimum coalition structure C∗(G(G , v , α)) (respectively C∗(G(G , v , α)) ) is one that maximizes the social welfare SW (respectively SW) of G(G , v , α) . The price of anarchy of a social context additively separable hedonic game G(G , v , α) is defined as the worst-case ratio between the social welfare of a socially optimum outcome and that of a Nash equilibrium. Formally, PoA(G(G,v,α)) = max C∈N(G(G,v,α)) SW(C∗(G(G,v,α))) SW(C), and PoA(G(G,v,α)) = max C∈N(G(G,v,α)) SW(C∗(G(G,v,α))) SW(C). Analogously, the price of stability of G(G , v , α) is defined as the best-case ratio between the social welfare of a socially optimum outcome and that of a Nash equilibrium. Formally, PoS(G(G,v,α)) = min C∈N(G(G,v,α)) SW(C∗(G(G,v,α))) SW(C), and PoS(G(G,v,α)) = min C∈N(G(G,v,α)) SW(C∗(G(G,v,α))) SW(C). 3. Nash Stable Outcomes In this section we consider Nash stable outcomes. We first show that the social context radically modifies the notion of stability of additively separable hedonic games. To this aim, consider the instance whose graph G and valuations are depicted in Figure 2. On the one hand, the coalition structure { 1, 2 } , { 3 } is Nash stable when α= 0 (i.e., without considering social effects): the utility of players 1, 2, 3 are 3, 3, 0, respectively. Player 1 is earning as much as possible, and therefore has no incentive to deviate; player 2 would obtain a utility of 2 by joining the coalition of player 3, while it would obtain a utility of 0 by going alone; player 3 would obtain a utility of − 6 by joining the coalition of players 1 and 2. On the other hand, the same coalition structure is not Nash stable when α= 1, i.e., when considering the effect of social context. In fact, in this case the utility of player 2 is again 3 + 1 · 0 = 3, while she would obtain a utility of 2 + 1 · 2 = 4 by joining the same coalition of player 3. Interestingly, it is also possible to build an instance in which the converse does not hold: Consider the instance exploited in the proof of Theorem 2. Here, the grand coalition is Nash stable and is such that every player is getting a negative utility. If we do not consider social context effects on the player utilities, the grand coalition would not be Nash stable because every player would clearly prefer to form a new coalition alone, so getting utility 0. Games 2021,12, 71 7 of 14 2 1 3 (i,j)vi,j (1,3) −8 (1,2) 3 (2,3) 2 Figure 2. Graph Gand valuations vi,j. We now show that a stable outcome is guaranteed to exist and also that the finite improvement path property holds for SCASHG s, because these games admit the potential function. Φ(C) = 1 2∑ i∈N ˆ ui(C), with ˆ ui(C) = ∑j∈C(i)v0 i,j , where, for each pair of players (i , j) , we define v0 i,j=vi,j·( 1 +α) if (i,j)∈Eand v0 i,j=vi,jif (i,j)6∈ E. Thus, we can rewrite the potential function Φ(C)as Φ(C) = ∑ j∈C(i) vi,j+α·∑ j∈C(i),(i,j)∈E vi,j. In the following theorem, we prove that Φ(C) is an exact potential function for our game. Theorem 1. Φis a potential function for SCASHGs. Proof. Given two stable outcomes C and C0 where C0 is obtained from C after a player i performs a move, we prove that the following holds: Φ(C0)−Φ(C) = ui(C0)−ui(C). (1) For the left hand side of Equation (1) , by applying the definition of Φ , we obtain that: Φ(C0)−Φ(C) = 1 2 ∑ j∈N ˆ uj(C0)−∑ j∈N ˆ uj(C)!=1 2∑ j∈Nˆ uj(C0)−ˆ uj(C) =1 2·2 ∑ j∈C0(i) v0 i,j−∑ j∈C(i) v0 i,j  =∑ j∈C0(i) vi,j+α∑ j∈C0(i),(i,j)∈E vi,j−∑ j∈C(i) vi,j−α∑ j∈C(i),(i,j)∈E vi,j. In the right hand side we obtain that: ui(C0)−ui(C) = ¯ ui(C0) + α∑ (i,j)∈E ¯ uj(C0)−¯ ui(C)−α∑ (i,j)∈E ¯ uj(C) =¯ ui(C0)−¯ ui(C) + α∑ (i,j)∈E¯ uj(C0)−¯ uj(C) =∑ j∈C0(i) vi,j+α∑ j∈C0(i),(i,j)∈E vi,j−∑ j∈C(i) vi,j−α∑ j∈C(i),(i,j)∈E vi,j. Hence, the proof follows. 4. Price of Anarchy In this section we evaluate the performance of Nash stable outcomes with respect to the notion of price of anarchy. Games 2021,12, 71 8 of 14 We first show that the price of anarchy is unbounded for general valuations. It is already known that the price of anarchy of additively separable hedonic games is unbounded [ 12 ]. The following proposition is an easy extension to our setting with social context. The following result holds for both the social welfare functions SW and SW. Proposition 1. For any α∈[ 0, 1 ] , there exists a function v (also admitting negative valuations), such that PoA(G(G,v,α)) and PoA(G(G,v,α)) are unbounded, where G = (N,∅). Proof. Let vi,j be the players’ valuations as shown in Figure 3, with Me> 0. As E=∅ , we can easily note that the values of the two social welfare functions SW and SW are equal for every coalition structure. On the one hand, there exists outcome C0={{ 1 } , { 2, 3 } , { 4 }} with SW(C0) = SW(C0) = 2 and therefore SW(C∗)≥ 2 and SW(C∗)≥ 2. On the other hand, it can be easily verified that outcome C={{ 1, 2 } , { 3, 4 }} with SW(C) = SW(C) = 4 e is a Nash equilibrium. Therefore, PoA(G(G , v , α)) ≥1 2e and PoA(G(G , v , α)) ≥1 2e , thus proving the claim for etending to 0. 1234(i,j)vi,j (1,2), (3,4) e (1,3), (2,4) −M (2,3) 1 Figure 3. Graph Gand valuations vi,j. For more involved social graphs, we are also able to show a stronger result, holding even for the case of the price of stability (analyzed in Section 5): by Theorem 5, there exists a SCASHG in which every Nash equilibrium C is such that SW(C) is negative, while SW(C∗) is positive. We now prove a similar result for the social welfare function SW. Theorem 2. For any α∈( 0, 1 ] , there exists a graph G and a function v (also admitting negative valuations) inducing G(G , v , α) , such that SW(C∗)> 0while SW(C)< 0for a Nash stable outcome Cof G(G,v,α). Proof. Let G be the social graph depicted in Figure 4and let vi,j be the valuations as represented in Figure 4, with esuch that 0 <e<2α. 1 3 6 5 24 (i,j)vi,j (1,2), (6, 4) 1 (1,3), (5, 6) −1 (2,3), (4, 5) 1 (2,4) −2−e Figure 4. Graph Gand valuations vi,j. On the one hand, coalition structure C0={{ 1, 2, 3 } , { 4, 5, 6 }} is such that SW(C0) = 4, and therefore SW(C∗)≥4. On the other hand, a Nash equilibrium C is the grand coalition, in which all players are in the same coalition and, as can be easily checked, SW(C) = − 2 e . Indeed, players 1, 3, 5 and 6 have all the same utility u1(C) = −αe when they are in the grand coalition while, if any of them deviates, the best she can do is forming a new coalition alone, in which she would have utility −α( 1 +e)<−αe . Moreover, players 2 and 4 have the same utility u2(C) = −e and if any of them deviates forming another coalition, her utility would become −2α<−efor e<2α. The above results can be interpreted as follows: having negative valuations towards some players can preclude the possibility to form a group with other players for which