Hedonic Games with Social Context

Abstract

Hedonic games are coalition formation games in which coalitions 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 sel sh players; our aim is that of de ning and studying 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

-

An important issue in computer science is that of investigating the dynamics that regulates clustering and coalition formation. Hedonic games, introduced by Dreze 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 sel sh, 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 1 5

5 4 3 2 1 4 3 (i; j) vi;j (1,3) 1 (2,5) 3 (1,5) 2 (3,4) 1 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 rst 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 di erently 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 2 [0; 1]). In particular, for = 0 we model classical hedonic games in the totally sel sh 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 de ned as the ratio between the social optimal value and the social value of the worst (resp. best) stable outcome. 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 rst 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; 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 de ned by an underlying game in strategic form, and a social context consisting of an undirected graph and an aggregation function. The authors consider resource selection games as the underlying game and they study the existence of pure strategy Nash equilibrium. Building on this model, Bilo 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 e ects 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 ine ciency 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^anzei 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 introduced by Dreze and Greenberg [ 15 ], who analyze hedonic games under a cooperative perspective. Properties guaranteeing the existence of core allocations for games with additively separable utility have been studied by Banerjee, Konishi and Sonmez [ 7 ], while Bogomolnaia and Jackson [ 10 ] deal with several forms of stable outcomes like the core, Nash and individual stability. Ballester [ 4 ] considers 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 additively separable hedonic game with non-negative and symmetric preferences (i.e., unweighted undirected graphs). Feldman et al. [ 16 ] investigate some interesting 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 su cient for the problem of checking whether a given game admits a stable outcome to be computationally hard. From a di erent perspective, strategyproof mechanisms for additively separable hedonic and fractional hedonic games have been proposed in [ 18 ], while stable outcomes for these games and for modi ed fractional hedonic games are presented in [ 9 ] and [ 20 ]. Finally, hedonic games are being widely investigated also under di erent utility de nitions. 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 ] de ne altruistic hedonic games where the satisfaction of players' friends is taken into account according to three degrees of altruism, from being sel sh rst, over aggregating opinions of a player and her friends equally, to altruistically letting ones friends decide rst. 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 sel sh/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 sel sh and altruistic preferences, and present means to guarantee Nash-stability.

The paper is organized as follows. In Section 2 we formally de ne the hedonic 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, respectively. 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 f1; : : : ; kg.

We model a Social Context Hedonic Game by means of a valuation function v, an undirected graph G = (N; E) and a given parameter 2 [0; 1]. We denote with n = jN j 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 fi; jg 2 N N and its valuation v(fi; jg), 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 2 N is associated with a player. We assume that players are numbered from 1 to n and, for every i 2 [n], each player chooses to join a certain coalition among n candidate ones: the strategy of player i is an integer j 2 [n], meaning that player i is selecting candidate coalition Cj . A coalition structure (also called outcome) is a partition of the set of players into n coalitions C = fC1; C2; : : : ; Cng such that Cj N for each j 2 [n], Sj2[n] Cj = N and Ci \ Cj = ; for any i; j 2 [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 2 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 de ned as ui(C) = ui(C) +

X where, for every i 2 [n], ui(C) = Pj2C(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 n fC(i); Cj g [ fC(i) n fig; Cj [figg. 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 nite improvement path property if it does not admit an improvement dynamics of in nite length. Clearly, a game possessing the nite 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) = Pi2N ui(C).

We de ne also a second social welfare function SW(C) = Pi2N 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; )) (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 hedonic game G(G; v; ) is de ned as the worst-case ratio between the social welfare of a social optimum outcome and that of a Nash equilibrium. Formally, for any k = 1; : : : ; n, PoA(G(G; v; )) = maxC2N(G(G;v; )) SW(C S(WG((GC);v; ))) and PoA(G(G; v; )) = maxC2N(G(G;v; )) SW(C S(WG((GC);v; ))) . Analogously, the price of stability of G(G; v; ) is de ned as the best-case ratio between the social welfare of a social optimum outcome and that of a Nash equilibrium. Formally, for any k = 1; : : : ; n, PoS(G(G; v; )) = minC2N(G(G;v; )) SW(C S(WG((GC);v; ))) and PoS(G(G; v; )) = minC2N(G(G;v; )) SW(C S(WG((GC);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 nite improvement path property holds for SCHGs, because these games admit the potential function (C) = 12 X u^i(C); i2N with u^i(C) = Pj2C(i) vi0;j, where, for each pair of players (i; j), we de ne vi0;j = vi;j (1 + ) if (i; j) 2 E and vi0;j = vi;j if (i; j) 62 E.

Thus, we can rewrite the potential function (C) as (C) = X vi;j +

Proof. Given two stable outcomes C and C0 where C0 is obtained form 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 de nition of , we obtain that: (C0)

1 (C) = 2

X u^i(C0) i2N 0 = j2C0(i) vi0;j

! X u^i(C) = 1 X (u^i(C0)

2 i2N i2N

u^i(C)) X

X

vi;j: j2C(i);(i;j)2E

In the right hand side we obtain that:

(i;j)2E ui(C) +

X (uj(C0) In this section we evaluate the performance of Nash stable outcomes with respect to the notion of price of anarchy.

We rst 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 2 [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; ;).

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 2 (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 2 [n] with i 6= j.

In order to prove the upper bounds to PoA and PoA, we need some additional notation and de nitions. Given any outcome C, let i C ( ) be the sum of the valuations of player i toward her friends belonging to C(i), i.e i C ( ) = Pj2C(i):(i;j)2E vi;j, and, analogously, let i(C) = Pj2C(i):(i;j)62E 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 = maxj2N vi;j.

The following theorems provide asymptotically matching upper and lower bounds to PoA and PoA.

Theorem 4. For any 2 [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 2 [n] it holds that i(C) + i(C) + i(C) imax: In fact, recall that ui(C) = ui(C) + P(i;j)2E uj(C), where, for every i 2 [n], ui(C) = Pj2C(i) vi;j. By the de nitions of i(C) and i(C), ui(C) = i(C) + i(C). Moreover, let i(C) = P(i;j)2E 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 C0, we obtain ui(C0) imax + i(C), because the contributions i C

( ) of the friends of i not connected to player i in C(i) remain unchanged in C0. 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 optimal outcomes C and C , ui is at most (n 1) imax. Thus, ui(C ) (n 1) imax and ui(C ) (n 1) imax.

Therefore, andAunia(Clog)ousl(y1im,+afox)r, tbhye rseoccaialllinwgeltfhaeredfeunncittiioonn SoWfu,is,iwnceeoubit(aCin) tha(tn 1) imax

Theorem 5. For every even positive integer n and every 2 [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 .

tu . . .

n

Proof. Consider the bipartite graph G = (A [ B; E) with n vertices depicted in Figure 2 (note that A = f1; 3; : : : ; n 1g and B = f2; 4; : : : ; ng), and let v the valuation function in which { vi;j = vj;i = 1+1 for every (i; j) 2 E; { vi;j = vj;i = 1 for all pairs (i; j) 62 E such that i 2 A and j 2 B; { vi;j = 0 for all remaining pairs.

On the one hand, as it can be easily checked, the grand coalition Co is such that, for every i 2 [n], ui(Co) = n2 1 + 1+1 . Therefore, the optimal outcome C is such that SW(C ) n n2 1 + 1+1 and the optimal outcome C is such 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 fi; i + 1g for i = 1; 3; : : : ; n 1 is a Nash stable outcome; in fact, for every i 2 A, ui(C) = 1+1 and ui(C) = 1+1 + 1+1 = 1, while a deviation of player i to another non-empty candidate coalition would induce a new coalition structure C0 such that ui(C0) = 1 + 0 = 1, because for player i + 1 connected in G to player i it holds ui+1(C0) = 0. Moreover, a deviation of player i to an empty candidate coalition would induce a new coalition structure C00 such that ui(C00) = 0, again because for player i + 1 connected in G to player i it holds ui+1(C00) = 0. A completely symmetric argument holds for every player i 2 B.

It follows that

SW(C ) SW(C) n n2

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 functions 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 rst 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 2 (0; 1], there exists a graph G and a function v (admitting 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 function 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 2 [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 di erent 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 veri ed 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 1 2 (i; j) vi;j (1,2) 1 (1,3) 1 (2,3) 1 Fig. 3. Graph G and valuations vi;j .

Therefore,

SW(C) = 2(2 ) + 2 2 (n 3) < 0 for n going to in nite.

In order to complete the proof, it is su cient 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 di erent coalitions) with positive social welfare. tu

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 particular classes of graphs, as well as to study di erent stability notions such as strong Nash outcomes and core stable outcomes. Moreover, the problem in which valuations can be di erent from zero only between players i; j for which edge (i; j) 2 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. Schafer. Ine ciency 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 Arti cial 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 Arti cial Intelligence (AAAI) , pages 349 { 355 , 2017 .

7. S. Banerjee , H. Konishi , and T. So nmez. Core in a simple coalition formation game . Social Choice and Welfare , 18 : 135 { 153 , 2001 .

8. V. Bilo , A. Celi , M. Flammini , and V. Gallotti . Social context congestion games . In Structural Information and Communication Complexity , pages 282 { 293 , 2011 .

9. V. Bilo , A. Fanelli , M. Flammini , G. Monaco, and L. Moscardelli . Nash stable outcomes in fractional hedonic games: Existence, e ciency and computation . Journal of Arti cial 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. Bra^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 information . Journal of Computer and System Sciences , 71 ( 3 ): 360 { 383 , 2005 .

13. P. - A. Chen , B. de Keijzer, D. Kempe , and G. Schafer. 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. Dreze and J. Greenberg . Hedonic coalitions: optimality and stability . Econometrica , 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 modi ed 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 Arti cial 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 Arti cial 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-e cient coalition formation of selfish/altruistic nodes in ad hoc networks: A hedonic game approach . Telecommun. Syst., 67 ( 1 ): 95 { 111 , Jan . 2018 .