Hedonic Games with Social Context Gianpiero Monaco1 , Luca Moscardelli2 , and Yllka Velaj3 1 University of L’Aquila, L’Aquila 67100, Italy, gianpiero.monaco@univaq.it 2 University of Chieti-Pescara, Pescara 65127, Italy, luca.moscardelli@unich.it 3 CWI, Amsterdam 1098 XG, Netherlands, yllka.velaj@cwi.nl Abstract. Hedonic games are coalition formation games in which coali- tions are created as a result of the strategic interaction of independent players. To this day, the literature on non-cooperative hedonic games has considered totally selfish players; our aim is that of defining and study- ing 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 hedonic games (SCHGs). We consider Nash equilibria of SCHGs, and study their existence, convergence and performance with respect to the classical notions of price of anarchy and price of stability. In particular, we provide an exact potential function for SCHGs implying the existence and convergence to Nash equilibria, and we prove tight or asymptotically tight bounds on the price of anarchy and the price of stability of SCHGs. Keywords: Coalition Formation; Hedonic Games; Nash Equilibrium; Price of Anarchy; Price of Stability; Social Context 1 Introduction An important issue in computer science is that of investigating the dynamics that regulates clustering and coalition formation. Hedonic games, introduced by Dréze and Greenberg [15], represent a framework for studying the formal aspects of the formation of player coalitions. In these games, players have preferences over the set of all possible player coalitions, and the utility of a player depends on the composition of the coalition she belongs to. Hedonic games are of great interest because they model natural behavioral dynamics in social environments: in economic, social and political situation, in fact, individuals carry out activities in groups rather than by themselves. Politicians, for example, may want to be in a party that maximizes like-minded members or, more in general, people may want to be with people of the same ethnic or social group. While the standard model of 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. We call these games Social Context Hedonic Games (SCHGs); we believe that they provide a more realistic model for hedonic games, because they capture the fact that the behavior of players also depends on the happiness of their friends. To this aim, we consider 2 G. Monaco et al. 2 4 2 4 (i, j) vi,j 5 5 (1,3) 1 (2,5) 3 (1,5) 2 1 3 1 3 (3,4) 1 Fig. 1. A social network G, a coalition structure C and the non-null valuations vi,j . an underlying social network represented by a graph, whose nodes are players and in which an edge connecting two players expresses friendship between them. Arguably, as a first step in the study of SCHGs, it is more natural to consider symmetric friendship relations and therefore we focus on undirected graphs. In SCHGs, valuations are additive and each player has a valuation v for any other player, but differently from the classical hedonic games, the utility of a coalition to a particular player is given not only by the sum of the valuations she assigns to the members of her coalition, but also depends on the sum of the valuations her friends assign to the members of their own coalitions (the latter contribution is multiplied by a given parameter α ∈ [0, 1]). In particular, for α = 0 we model classical hedonic games in the totally selfish setting and when α = 1 we can model a fully altruistic setting. 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 α. Our aim is to study the existence and performance of natural stable outcomes for SCHGs. 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 SCHGs by means of the widely used notions of price of anarchy and price of stability, which are defined as the ratio between the social optimal value and the social value of the worst (resp. best) stable outcome. 1.1 Our Results By providing an exact potential function for the SCHGs, we show that these games always posses a pure Nash equilibrium and also that the convergence to such stable outcomes is guaranteed. 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 α). 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; Hedonic Games with Social Context 3 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 we prove that the price of anarchy is Θ(n), while the price of stability is 1. 1.2 Related Work Social context games are introduced in [2]. These games are defined by an un- derlying game in strategic form, and a social context consisting of an undi- rected graph and an aggregation function. The authors consider resource selec- tion games as the underlying game and they study the existence of pure strategy Nash equilibrium. Building on this model, Bilò et al. [8] 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. [1] study the effects of the altruistic behaviour 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 modelled and studied by Hoefer and Skopalik [19]: they focus on the existence and complexity of pure Nash equilibria with altruistic agents in atomic congestion games. Chen et al. [13] 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 [25] study social choice with empathetic preferences and their local empathetic model is related to the model presented in [21]. Finally, Brânzei and Larson [11] study social distance games. In these games a players opinion on her friends (players of distance one) has the highest weight while her opinion on players farther away counts less. Several papers are devoted to the study of hedonic games. They are intro- duced by Dréze and Greenberg [15], who analyze hedonic games under a coop- erative perspective. Properties guaranteeing the existence of core allocations for games with additively separable utility have been studied by Banerjee, Konishi and Sönmez [7], while Bogomolnaia and Jackson [10] deal with several forms of stable outcomes like the core, Nash and individual stability. Ballester [4] consid- ers computational complexity issues related to hedonic games, and shows that the core and the Nash stable outcomes have corresponding NP-complete decision problems for a variety of situations, while Aziz et al. [3] study the computational complexity of stable coalitions in additively separable hedonic games. Moreover, Olsen [22] proves that the problem of deciding whether a Nash stable coalitions exists in an additively separable hedonic game is NP-complete, as well as the one of deciding whether a non-trivial Nash stable coalitions exists in an ad- ditively separable hedonic game with non-negative and symmetric preferences 4 G. Monaco et al. (i.e., unweighted undirected graphs). Feldman et al. [16] investigate some in- teresting subclasses of hedonic games from a non-cooperative point of view, by characterizing Nash equilibria and providing upper and lower bounds on both the price of stability and the price of anarchy. In their model the agents lie in a metric space with a distance function modeling their distance or ”similarity”. Peters [23] considers “graphical” hedonic games where agents form the vertices of an undirected graph, and each agent’s utility function only depends on the actions taken by her neighbors (with general value functions). Moreover, hedonic games have also been considered by Charikar et al. [12] and by Demaine et al. [14] from a classical optimization point of view (i.e, without requiring stability for the solutions) and by Flammini et al. in an online setting [17]. Peters et al. [24] 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. From a different perspec- tive, strategyproof mechanisms for additively separable hedonic and fractional hedonic games have been proposed in [18], while stable outcomes for these games and for modified fractional hedonic games are presented in [9] and [20]. Finally, hedonic games are being widely investigated also under different utility defini- tions. For instance, in [5, 6], coalition formation games in which agent utilities are proportional to their harmonic centralities in the respective coalitions are considered. To the best of our knowledge, few papers deal with the notion of altruism in hedonic games. Nguyen et al. [21] 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 ones friends decide first. They study both the axiomatic properties of these games and the computational complexity of problems related to common stability concepts. In [26], 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. The paper is organized as follows. In Section 2 we formally define the hedo- nic games with social context. The technical contributions of the paper are then presented in Sections 3, 4 and 5 which address the existence of Nash outcomes, the results on the price of anarchy and those on the price of stability, respec- tively. Finally, in Section 6 we list some interesting open problems. Due to space limitations, some proofs are omitted. 2 Model For an integer k > 0, denote with [k] the set {1, . . . , k}. We model a Social Context Hedonic Game by means of a valuation function v, an undirected graph G = (N, E) and a given parameter α ∈ [0, 1]. We denote Hedonic Games with Social Context 5 with n = |N | the number of nodes of G and with E the set of edges between the nodes, that represent the friendship relation. v : N × N → R is the symmetric valuation function. For the sake of convenience, we adopt the notation (i, j) and vi,j to denote the pair {i, j} ∈ N × N and 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 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 of player i is an integer j ∈ [n], meaning that player i is selecting candidate coalition Cj . A coalition structure (also called outcome) is a partition of the set of playersS into n coalitions C = {C1 , C2 , . . . , Cn } such that Cj ⊆ N for each j ∈ [n], j∈[n] Cj = N and Ci ∩ Cj = ∅ for any i, j ∈ [n] with i 6= j. Notice that, since the number of candidate coalitions is equal to the number of players (nodes), some coalition may be empty. 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 i is a member. In an outcome C, the utility of player i is defined as X ui (C) = ui (C) + α · uj (C), (i,j)∈E P 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 a move) 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 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 moves, while a best-response dynamics is a sequence of best-responses. A game has the finite improvement path prop- erty 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 ofPa coalition structure C is the summation of the players’ utilities, i.e., SW(C) = i∈N ui (C). P We define also a second social welfare function SW(C) = i∈N ui (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, α)) (re- spectively C ∗ (G(G, v, α))) is one that maximizes the social welfare SW (re- 6 G. Monaco et al. spectively SW) of G(G, v, α). The price of anarchy of a social context hedo- nic game G(G, v, α) is defined as the worst-case ratio between the social wel- fare of a social optimum outcome and that of a Nash equilibrium. Formally, ∗ for any k = 1, . . . , n, PoA(G(G, v, α)) = maxC∈N(G(G,v,α)) SW(C SW(C) (G(G,v,α))) and ∗ PoA(G(G, v, α)) = maxC∈N(G(G,v,α)) SW(C SW(C) (G(G,v,α))) . Analogously, the price of stability of G(G, v, α) is defined as the best-case ratio between the social wel- fare of a social optimum outcome and that of a Nash equilibrium. Formally, ∗ for any k = 1, . . . , n, PoS(G(G, v, α)) = minC∈N(G(G,v,α)) SW(C SW(C) (G(G,v,α))) and ∗ PoS(G(G, v, α)) = minC∈N(G(G,v,α)) SW(C SW(C) (G(G,v,α))) . 3 Nash Stable Outcomes In this section we consider Nash stable outcomes. We show that a stable outcome is guaranteed to exist and also that the finite improvement path property holds for SCHGs, because these games admit the potential function 1X Φ(C) = ûi (C), 2 i∈N 0 0 P with ûi (C) = j∈C(i) vi,j , where, for each pair of players (i, j), we define vi,j = 0 vi,j · (1 + α) if (i, j) ∈ E and vi,j = vi,j if (i, j) 6∈ E. Thus, we can rewrite the potential function Φ(C) as X X Φ(C) = vi,j + α · vi,j . j∈C(i) j∈C(i),(i,j)∈E In the following theorem, we prove that Φ(C) is an exact potential function for our game. Theorem 1. Φ is a potential function for SCHGs. Proof. Given two stable outcomes C and C 0 where C 0 is obtained form C after a player i performs a move, we prove that the following holds: Φ(C 0 ) − Φ(C) = ui (C 0 ) − ui (C). (1) For the left hand side of Equation (1), by applying the definition of Φ, we obtain that: ! 0 1 X 0 X 1X Φ(C ) − Φ(C) = ûi (C ) − ûi (C) = (ûi (C 0 ) − ûi (C)) 2 2 i∈N i∈N i∈N   1 X 0 X 0  = · 2 vi,j − vi,j 2 j∈C 0 (i) j∈C(i) X X X X = vi,j + α vi,j − vi,j − α vi,j . j∈C 0 (i) j∈C 0 (i),(i,j)∈E j∈C(i) j∈C(i),(i,j)∈E Hedonic Games with Social Context 7 In the right hand side we obtain that: X X ui (C 0 ) − ui (C) = ūi (C 0 ) + α ūj (C 0 ) − ūi (C) − α ūj (C) (i,j)∈E (i,j)∈E X 0 0 = ūi (C ) − ūi (C) + α (ūj (C ) − ūj (C)) (i,j)∈E X X X X = vi,j + α vi,j − vi,j − α vi,j . j∈C 0 (i) j∈C 0 (i),(i,j)∈E j∈C(i) j∈C(i),(i,j)∈E Hence, the proof follows. t u 4 Price of Anarchy In this section we evaluate the performance of Nash stable outcomes with respect to the notion of price of anarchy. We first show that the price of anarchy is unbounded for general valuations. The following result holds for both the social welfare functions SW and SW, even when the social graph has no edges. Theorem 2. For any α ∈ [0, 1], there exists a function v (also admitting nega- tive valuations), such that PoA(G(G, v, α)) and PoA(G(G, v, α)) are unbounded, where G = (N, ∅). 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 6, there exists a SCHG 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 3. 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 ∗ ) > 0 while SW(C) < 0 for a Nash stable outcome C of G(G, v, α). Given these negative results, in what follows we focus on the case in which the valuation function does not assume negative values, i.e., vi,j ≥ 0 for any i, j ∈ [n] with i 6= j. In order to prove the upper bounds to PoA and PoA, we need some ad- ditional notation and definitions. Given any outcome C, let δi (C) be the sum of P the valuations of player i toward her ¯friends P belonging to C(i), i.e δi (C) = j∈C(i):(i,j)∈E v i,j , and, analogously, let δ i (C) = j∈C(i):(i,j)6∈E vi,j be the sum of the valuations of player i toward players belonging to C(i) and not being her friends. Finally, we denote by δimax the maximum valuation of player i, i.e. δimax = maxj∈N vi,j . The following theorems provide asymptotically matching upper and lower bounds to PoA and PoA. 8 G. Monaco et al. Theorem 4. For any α ∈ [0, 1], any graph G and any function v not admitting negative valuations, PoA(G(G, v, α)) ≤ (n − 1)(1 + α) and PoA(G(G, v, α)) ≤ (n − 1)(1 + α). Proof. Given a Nash stable outcome C, for every player i ∈ [n] it holds that δi (C) + δ¯i (C) + αδi (C) ≥ δimax . P In fact, recall that ui (C) = ui (C) + α · (i,j)∈E uj (C), where, for every i ∈ [n], ui (C) = j∈C(i) vi,j . By the definitions of δi (C) and δ¯i (C), ui (C) = δi (C) + δ¯i (C). P P Moreover, let βi (C) = (i,j)∈E uj (C) − δi (C): it follows that ui (C) = δi (C) + δ¯i (C) + α · (βi (C) + δi (C)). Notice that if player i changes her strategy by joining the coalition containing player j such that vi,j = δimax , inducing in this way a new coalition structure C 0 , we obtain ui (C 0 ) ≥ δimax + αβi (C), because the contributions βi (C) of the friends of i not connected to player i in C(i) remain unchanged in C 0 . Therefore, if δimax + αβi (C) > δi (C) + δ¯i (C) + α · (βi (C) + δi (C)) player i would increase her utility by changing her strategy: a contradiction to the fact that C is Nash stable. Moreover, it trivially holds that in all coalition structures, including the opti- mal outcomes C ∗ and C ∗ , ui is at most (n−1)·δimax . Thus, ui (C ∗ ) ≤ (n−1)·δimax and ui (C ∗ ) ≤ (n − 1) · δimax . Therefore, (n − 1) · i∈N δimax P SW(C ∗ ) ≤ P . SW(C) i∈N ui (C) max δi Since ui (C) = δi (C) + δ¯i (C) ≥ (1+α) , we obtain that (n − 1) · i∈N δimax P SW(C ∗ ) ≤ P max = (n − 1)(1 + α). SW(C) i∈N δi 1+α Analogously, for the social welfare function SW, since ui (C ∗ ) ≤ (n − 1) · δimax δimax and ui (C ∗ ) ≥ (1+α) , by recalling the definition of ui , we obtain that   (n − 1)δimax + α j∈N :(i,j)∈E (n − 1)δjmax P P SW(C ∗ ) i∈N ≤  max  1 + α j∈N :(i,j)∈E δjmax 1+α P P SW(C) i∈N δi   (n − 1) i∈N δimax + α j∈N :(i,j)∈E δjmax P P = P  max  1 + α j∈N :(i,j)∈E δjmax 1+α P i∈N δi ≤ (n − 1)(1 + α), thus proving the claim. t u We now focus on the lower bound to PoA and PoA. Theorem 5. For every even positive integer n and every α ∈ [0, 1], there exist a graph G with n vertices and a valuation function v such that PoA(G(G, v, α)) ≥ (1 + α) n2 − α and PoA(G(G, v, α)) ≥ (1 + α) n2 − α. Hedonic Games with Social Context 9 n−1 n n−3 n−2 A .. .. B . . 3 4 1 2 Fig. 2. The bipartite graph G. Proof. Consider the bipartite graph G = (A ∪ B, E) with n vertices depicted in Figure 2 (note that A = {1, 3, . . . , n − 1} and B = {2, 4, . . . , n}), and let v the valuation function in which 1 – vi,j = vj,i = 1+α for every (i, j) ∈ E; – vi,j = vj,i = 1 for all pairs (i, j) 6∈ E such that i ∈ A and j ∈ B; – vi,j = 0 for all remaining pairs. On the one hand, as it can be easily checked, the grand coalition C o is such that, for every i ∈ [n], ui (C o ) = n2 − 1 + 1+α 1 . Therefore, the optimal outcome C is such that SW(C ) ≥ n 2 − 1 + 1+α and the optimal outcome C ∗ is such n 1  ∗ ∗ that SW(C ∗ ) ≥ n(1 + α) n2 − 1 + 1+α 1  . On the other hand, the coalition structure C in which there are n2 non-empty coalitions {i, i + 1} for i = 1, 3, . . . , n − 1 is a Nash stable outcome; in fact, for 1 1 1 every i ∈ A, ui (C) = 1+α and ui (C) = 1+α + α · 1+α = 1, while a deviation of player i to another non-empty candidate coalition would induce a new coalition structure C 0 such that ui (C 0 ) = 1 + α · 0 = 1, because for player i + 1 connected in G to player i it holds ui+1 (C 0 ) = 0. Moreover, a deviation of player i to an empty candidate coalition would induce a new coalition structure C 00 such that ui (C 00 ) = 0, again because for player i + 1 connected in G to player i it holds ui+1 (C 00 ) = 0. A completely symmetric argument holds for every player i ∈ B. It follows that n n2 − 1 + 1+α 1  SW(C ∗ ) n ≥ 1  = (1 + α) − α. SW(C) n 1+α 2 Analogously, for the social welfare function SW, it holds that n n2 − 1 + 1+α 1  SW(C ∗ ) (1 + α) n ≥   = (1 + α) − α. SW(C) n 1 + α 2 1+α 1+α t u 10 G. Monaco et al. 5 Price of Stability In this section we present our results on the price of stability. First of all, notice that, if all valuations are non-negative, with respect to both social welfare func- tions SW and SW, the grand coalition is at the same time an optimal solution and a Nash stable outcome, thus implying that PoS = PoS = 1. Therefore, in the following we deal with the case of general valuations, i.e., we allow the valuation function to assume negative values. We first show that, for the social welfare function SW, there exists a SCHG in which every Nash equilibrium C is such that SW(C) is negative, while SW(C ∗ ) is positive. Theorem 6. For any α ∈ (0, 1], there exists a graph G and a function v (admit- ting also negative valuations) inducing G(G, v, α), such that SW(C ∗ ) > 0 while SW(C) < 0 for every Nash stable outcome C of G(G, v, α). Proof. Let us consider the graph G depicted in Figure 3 and the valuation func- tion v whose non-null values are listed in Figure 3, and in which  < α is an arbitrary positive parameter. Now we want to show that in every Nash stable outcome C players 1, 2 and 3 belong to the same coalition. First of all, notice that, for any i ≥ 4, vi,j = 0 for any j ∈ [n]; it follows that it is possible to discard players 4, . . . , n in the following discussion. The outcome in which players 1, 2 and 3 belong to three different coalitions is not Nash stable because, for instance, player 1 would increase her utility from 0 to 1 + α by joining the coalition of player 2. The outcome in which players 1 and 2 are in a coalition and player 3 in another one is not Nash stable because player 3 would increase her utility from α to 2α −  by joining the coalition of players 1 and 2 (notice that a symmetric argument holds for the outcome in which players 2 and 3 are in a coalition and player 1 in another one). Finally, the outcome in which players 1 and 3 are in a coalition and player 2 in another one is not Nash stable because, for instance, player 1 would increase her utility from −1 −  to 0 by forming alone a new coalition. It follows that in any Nash equilibrium C (recall that by Theorem 1 a Nash equilibrium always exists) players 1, 2 and 3 belong to the same coalition. It can be easily verified that u1 (C) = u3 (C) = 2α −  and u2 (C) = 2 − 2α. Moreover, since u3 (C) = −, it follows that for any i ≥ 4, ui (C) = −α. 3 n−3 .. (i, j) vi,j . 2 (1,2) 1 (1,3) −1 −  1 (2,3) 1 Fig. 3. Graph G and valuations vi,j . Hedonic Games with Social Context 11 Therefore, SW(C) = 2(2α − ) + 2 − 2α − (n − 3)α < 0 for n going to infinite. In order to complete the proof, it is sufficient to note that there exists a coalition structure (for instance the one in which players 1 and 2 belong to the same coalition and all other players are alone in different coalitions) with positive social welfare. t u Now we focus our attention on the SW social welfare function and we show that PoS is unbounded for α tending to 1. Theorem 7. Given any M > 0, there exist a value of α, a graph G and a function v (admitting also negative valuations) such that PoS(G(G, v, α)) > M . 6 Open Problems Our work leads to many future research directions. It would be interesting to analyze if it is possible to decrease the price of anarchy by restricting to par- ticular classes of graphs, as well as to study different stability notions such as strong Nash outcomes and core stable outcomes. Moreover, the problem in which valuations can be different from zero only between players i, j for which edge (i, j) ∈ E (and not for all pair of players) is worth studying. Finally, it would be interesting to study the fractional version of hedonic games, in which the utility of a player is divided by the number of players in the coalition she belongs to. References 1. A. Anagnostopoulos, L. Becchetti, B. de Keijzer, and G. Schäfer. Inefficiency of games with social context. Theory of Computing Systems, 57(3):782–804, 2015. 2. I. Ashlagi, P. Krysta, and M. Tennenholtz. Social context games. In Internet and Network Economics, pages 675–683, 2008. 3. H. Aziz, F. Brandt, and H. G. Seedig. Stable partitions in additively separable hedonic games. In Proc. 10th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS), pages 183–190, 2011. 4. C. Ballester. Np-completeness in hedonic games. Games and Economic Behavior, 49(1):1–30, 2004. 5. A. Balliu, M. Flammini, G. Melideo, and D. Olivetti. Nash stability in social distance games. In Proc. 31st AAAI Conf. on Artificial Intelligence (AAAI), pages 342–348, 2017. 6. A. Balliu, M. Flammini, and D. Olivetti. On pareto optimality in social distance games. In Proc. 31st AAAI Conf. on Artificial Intelligence (AAAI), pages 349–355, 2017. 7. S. Banerjee, H. Konishi, and T. Sönmez. Core in a simple coalition formation game. Social Choice and Welfare, 18:135–153, 2001. 8. V. Bilò, A. Celi, M. Flammini, and V. Gallotti. Social context congestion games. In Structural Information and Communication Complexity, pages 282–293, 2011. 12 G. Monaco et al. 9. V. Bilò, A. Fanelli, M. Flammini, G. Monaco, and L. Moscardelli. Nash stable out- comes in fractional hedonic games: Existence, efficiency and computation. Journal of Artificial Intelligence Research, 62:315–371, 2018. 10. A. Bogomolnaia and M. O. Jackson. The stability of hedonic coalition structures. Games and Economic Behavior, 38:201–230, 2002. 11. S. Brânzei and K. Larson. Social distance games. In The 10th Int. Conf. on Autonomous Agents and Multiagent Systems - Volume 3, AAMAS, pages 1281– 1282, 2011. 12. M. Charikar, V. Guruswami, and A. Wirth. Clustering with qualitative informa- tion. Journal of Computer and System Sciences, 71(3):360–383, 2005. 13. P.-A. Chen, B. de Keijzer, D. Kempe, and G. Schäfer. The robust price of anarchy of altruistic games. In Proc. 7th Int. Conf. on Internet and Network Economics, WINE’11, pages 383–390, 2011. 14. E. D. Demaine, D. Emanuel, A. Fiat, and N. Immorlica. Correlation clustering in general weighted graphs. Theoretical Computer Science, 361(2-3):172–187, 2006. 15. J. H. Dréze and J. Greenberg. Hedonic coalitions: optimality and stability. Econo- metrica, 48:987–1003, 1980. 16. M. Feldman, L. Lewin-Eytan, and J. S. Naor. Hedonic clustering games. ACM Transactions on Parallel Computing, 2(1):4:1–4:48, 2015. 17. M. Flammini, G. Monaco, L. Moscardelli, M. Shalom, and S. Zaks. Online coalition structure generation in graph games. In Proc. 17th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS), pages 1353–1361, 2018. 18. M. Flammini, G. Monaco, and Q. Zhang. Strategyproof mechanisms for additively separable hedonic games and fractional hedonic games. In Proc. 15th Workshop on Approximation and Online Algorithms (WAOA), pages 301–316, 2017. 19. M. Hoefer and A. Skopalik. Altruism in atomic congestion games. ACM Trans. Econ. Comput., 1(4):21:1–21:21, 2013. 20. G. Monaco, L. Moscardelli, and Y. Velaj. Stable outcomes in modified fractional hedonic games. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS, pages 937–945, 2018. 21. N.-T. Nguyen, A. Rey, L. Rey, J. Rothe, and L. Schend. Altruistic hedonic games. In Proc. 15th Int. Conf. on Autonomous Agents and Multiagent Systems, AAMAS, pages 251–259, 2016. 22. M. Olsen. Nash stability in additively separable hedonic games and community structures. Theory of Computing Systems, 45(4):917–925, 2009. 23. D. Peters. Graphical hedonic games of bounded treewidth. In Proc. of The 30th AAAI Conf. on Artificial Intelligence (AAAI), pages 586–593, 2016. 24. D. Peters and E. Elkind. Simple causes of complexity in hedonic games. In Proc. 24th Int. Joint Conf. on Artificial Intelligence (IJCAI), pages 617–623, 2015. 25. A. Salehi-Abari and C. Boutilier. Empathetic social choice on social networks. In Proc. 13th Int. Conf. on Autonomous Agents and Multi-agent Systems, AAMAS, pages 693–700, 2014. 26. R. Umar and W. Mesbah. Throughput-efficient coalition formation of self- ish/altruistic nodes in ad hoc networks: A hedonic game approach. Telecommun. Syst., 67(1):95–111, Jan. 2018.