Related Work. Much work has been done on hedonic games in the past years, ranging from representation issues [CRM01, DBHS06, EW09, LRR+ 15, AHLW16, ABB+ 19, RSS18] over studying their properties such as various notions of stability [CH03, CH04, ABH13] to investigating the related problems in terms of their computational complexity [Bal04, SD07, SD10, Woe13b, PE15, Pet16, RRSS16]. Needless to say that most of the papers just listed contribute to more than one of these goals; for example, Dimitrov et al. [DBHS06] both introduce new ways of representing hedonic games and study their stability. The recent book chapters by Aziz and Savani [AS16] and Elkind and Rothe [ER15] as well as the excellent survey by Woeginger [Woe13a] provide more background and literature on the area of hedonic games. Most closely related to our paper is the work of Nguyen et al. [NRR+ 16] who introduced and studied altruistic hedonic games. A more general approach is due to Schlueter and Goldsmith [SG18] who define super altruistic hedonic games by considering the preferences of all players inside a coalition and allowing different treatment based on the distances in the network of friends. Somewhat related to but different from our work are the social distance games due to Brânzei and Lar- son [BL11]. Also, Monaco et al. investigated modified fractional hedonic games with egalitarian social welfare [MMV19] and, in another paper, they studied Nash equilibria, the price of anarchy, and the price of stability in hedonic games that are based on a social graph where players care also about the happiness of their friends [MMV18]. Further away, in non- cooperative game theory, various notions of altruism have been studied by, e.g., Hoefer and Skopalik [HS09], Chen et al. [CBKS11], Apt and Schäfer [AS12], and Rahn and Schäfer [RS13]. 2 Preliminaries Hedonic games are formally defined as follows. Let N = {1, . . . , n} be a set of players and let 2Ni = {C ⊆ N | i ∈ C} be the set of all coalitions of N containing player i ∈ N. A hedonic game is a pair (N, ) consisting of a set of players and a profile  = (1 , . . . , n ) of weak preferences of each player in which i is a reflexive, complete, and transitive binary relation on 2Ni . A coalition structure is a partition Γ of N into k coalitions, and Γ(i) denotes the unique coalition in Γ containing player i ∈ N. In general, representing arbitrary hedonic games requires exponential space in n. To compactly represent hedonic games, we will restrict ourselves to friend-oriented hedonic games, which were introduced by Dimitrov et al. [DBHS06]. In these games, each player partitions the other players into friends and enemies, and each player values the presence of friends higher than the absence of enemies. As is common, we will only consider symmetric friendship relations. Formally, for each i ∈ N, let N \ {i} = Fi ∪ Ei be a partition of the remaining players into a set of i’s friends, Fi , and a set of i’s enemies, Ei , satisfying i ∈ Fj if and only if j ∈ Fi for all i, j ∈ N, i 6= j. For A ∈ 2Ni , we define the friend-oriented utility of player i by vFi (A) = n|A ∩ Fi | − |A ∩ Ei |, and the friend-oriented preferences Fi of player i are given by A Fi B ⇐⇒ vFi (A) ≥ vFi (B). Since the friendship relations are symmetric, they can be represented using an undirected graph in which two vertices are adjacent if and only if the corresponding players are friends. For a hedonic game with friend-oriented preferences, we call the graph G = (N, {{i, j} ⊆ N | i ∈ Fj }) the network of friends, and we will represent each friend-oriented hedonic game by its network of friends. Alternatively, instead of defining the friend-oriented preferences using the utility function above, we could have defined them equivalently as follows: A Fi B ⇐⇒ (|A ∩ Fi | > |B ∩ Fi |) or (|A ∩ Fi | = |B ∩ Fi | and |A ∩ Ei | ≤ |B ∩ Ei |). Nguyen et al. [NRR+ 16] introduced and studied three types of altruistic hedonic games. We modify their definitions by replacing the average with the minimum. This can be more appropriate in situations where the weakest/unhappiest friend drags down the whole group. We introduce these modified definitions for each player i ∈ N and a constant M ≥ n3 : 1. Using the utility function vminSF i (A) = M(n|A ∩ Fi | − |A ∩ Ei |) + min {n|A ∩ Fa | − |A ∩ Ea |}, define the minimum- a∈A∩Fi selfish-first preferences by A minSF i B ⇐⇒ vminSF i (A) ≥ vminSF i (B). 2. Using the utility function vminEQ i (A) = min {n|A ∩ Fa | − |A ∩ Ea |}, define the minimum-equal-treatment prefer- a∈(A∩Fi )∪{i} minEQ minEQ ences by A i B ⇐⇒ vi (A) ≥ vminEQ i (B). 3. Using the utility function vminAL i (A) = n|A ∩ Fi | − |A ∩ Ei | + M min {n|A ∩ Fa | − |A ∩ Ea |}, define the minimum- a∈A∩Fi altruistic-treatment preferences by A minAL i B ⇐⇒ vminAL i (A) ≥ vminAL i (B). The corresponding utility functions and preferences when taking the average instead of the minimum, as introduced by EQ AL EQ Nguyen et al. [NRR+ 16], are denoted by vSF SF i , vi , vi and i , i , i . AL + While Nguyen et al. [NRR 16] showed properties analogous to those in Proposition 1 for their average-based altruistic hedonic games whenever M ≥ n5 , we can prove Proposition 1 for any choice of M ≥ n3 . The proof, similar to that of Nguyen et al. [NRR+ 16], is omitted due to space limitations. 6 5 2 vSF 1 vminSF 1 vEQ 1 vminEQ 1 vAL 1 vminAL 1 A 4 1 A 22M + 16 22M + 13 17.5 13 22 + 16M 22 + 13M 3 B 22M + 19 22M + 4 19.75 4 22 + 19M 22 + 4M 8 B 7 Figure 1: Network of friends and partition Γ (left) and average-versus-minimum values (right) for Example 1 Proposition 1. For M ≥ n3 , the following two implications hold for each i ∈ N and for all two coalitions A, B ∈ 2Ni : vFi (A) > vFi (B) =⇒ A minSF i B and min {vFa (A)} > min {vFa (B)} =⇒ A minAL i B. a∈A∩Fi a∈B∩Fi The following example shows, that these preferences do not equal the preferences gained by taking the average: Example 1. Let N = {1, . . . , 8} be the set of players with the network of friends displayed in Figure 1 (left). A direct calculation for the coalitions A = {1, 2, 3, 4, 5, 8} and B = {1, 2, 3, 4, 6, 7} as in Figure 1 (right) shows that, for all three types of altruism, player 1 prefers A to B when taking the minimum, yet prefers B to A when taking the average. 3 Nash Stability, Individual Stability, and Contractual Individual Stability We now study the common stability concepts in minimum-based altruistic hedonic games. Focusing first on single-player deviations, we consider the following concepts. Definition 1. Let (N, ) be a hedonic game. A coalition structure Γ is said to be: 1. Nash stable if for all players i ∈ N and every coalition C ∈ Γ ∪ {0}, / player i weakly prefers her own coalition to joining C: (∀i ∈ N)(∀C ∈ Γ ∪ {0}) / [Γ(i) i C ∪ {i}]; 2. individually stable if for all players i ∈ N and every coalition C ∈ Γ ∪ {0}, / player i weakly prefers her own coalition to joining C, or there is a player in C who objects i joining his coalition: (∀i ∈ N)(∀C ∈ Γ ∪ {0}) / [Γ(i) i C ∪ {i} ∨ (∃ j ∈ C) [C  j C ∪ {i}]]; 3. contractually individually stable if for all players i ∈ N and every coalition C ∈ Γ ∪ {0},/ player i weakly prefers her own coalition to joining C, or there is a player in C who objects i joining his coalition, or there is a player in Γ(i) who is against i leaving Γ(i): (∀i ∈ N)(∀C ∈ Γ ∪ {0})/ [Γ(i) i C ∪ {i} ∨ (∃ j ∈ C) [C  j C ∪ {i}] ∨ (∃k ∈ Γ(i)) [Γ(i) k Γ(i) \ {i}]]. It immediately follows that Nash stability implies individual stability and that individual stability implies contractual individual stability. The following example illustrates these concepts for minEQ -preferences. Example 2. Let N = {1, . . . , 8} be the set of players with the friendship relations as depicted in Figure 2 (left). We take a look at the coalition structure Γ = {A, B,C}, which is illustrated in the same figure. Under minEQ -preferences, the players 2, . . . , 8 can only worsen their happiness by joining any other coalition in Γ. So to check the three stability concepts we defined above, there is only player 1 left to consider: 1. 1 prefers C ∪ {1} to Γ(1) = A, so Γ is not Nash stable. 2. Now, 1 preferring to join C cannot be used to show that Γ is not individually stable because the happiness of 8 worsens after 1 joins. However, 1 prefers B ∪ {1} to A as well and no player in B objects. Thus the coalition structure Γ is not individually stable. 3. If 1 joins any other coalition, the remaining players’ happiness in A worsens. Since there is no other player that can improve her happiness by joining another coalition, the coalition Γ is contractually individually stable. Under minSF and minAL , we obtain similar results. For minAL , though, 1 is not the only player that can improve her happiness by joining another coalition in Γ. Nguyen et al. [NRR+ 16] proved that, for all three degrees of altruism based on taking the average, there always exists a Nash stable (and, thus, also an individually stable and a contractually individually stable) coalition structure. The same proof (which is omitted here) can be applied to show: 2 4 1 A B 5 3 1 4 6 7 3 C 8 2 5 Figure 2: Network of friends for Example 2 (left, with partition Γ) and Example 3 (right) Proposition 2. For all three degrees of minimum-based altruistic hedonic games, there always exists a Nash stable (and, therefore, also an individually stable and a contractually individually stable) coalition structure. 4 Core Stability and Strict Core Stability Next, we turn to stability concepts preventing that a group of players may wish to deviate from their current coalition. Definition 2. Let (N, ) be a hedonic game and Γ a coalition structure. We say a coalition C ⊆ N blocks Γ if C i Γ(i) for all players i ∈ C; and C weakly blocks Γ if C i Γ(i) for all players i ∈ C and there exists a player j ∈ C with C  j Γ( j). Γ is core stable if no nonempty C ⊆ N blocks Γ; and Γ is strictly core stable if no C ⊆ N weakly blocks Γ. It immediately follows that, for given preferences, every coalition structure that is strictly core stable is also core stable. For SF -preferences, Nguyen et al. [NRR+ 16] proved that there always exists a strictly core stable coalition structure. Their proof (omitted here) can be applied to show: Proposition 3. For minSF -preferences, there always exists a strictly core stable coalition structure. The following example shows that there does not always exist a strictly core stable coalition structure for minEQ - and minAL -preferences. Example 3. Let N = {1, 2, 3, 4, 5} be the set of players with the network of friends in Figure 2 (right). We show that there does not exist a strictly core stable coalition structure under minEQ -preferences. A direct calculation gives the following: (1) The unique, most preferred coalition of players 1 and 2 is A = {1, 2, 3}. (2) The unique, most preferred coalition of players 4 and 5 is B = {3, 4, 5}. (3) Player 3 has exactly two most preferred coalitions: A and B. With these observations, we can directly conclude the following: If a given coalition structure Γ does not contain A, the coalition A weakly blocks Γ. So any strictly core stable coalition structure has to contain A. However, the same holds for B, and since A and B are not disjoint, they cannot both be contained in the same coalition structure. Thus there does not exist a strictly core stable coalition structure under minEQ -preferences. Similar arguments work for minAL . 5 Strictly Popular Coalition Structures We now turn to the concept of strict popularity, which—inspired by the Condorcet principle from voting theory—evaluates the quality of a coalition structure by comparing it to other coalition structures. Definition 3. Let (N, ) be a hedonic game. A coalition structure Γ for N is called strictly popular if for all coalition structures ∆ 6= Γ it holds that |{i ∈ N | Γ(i) i ∆(i)}| > |{i ∈ N | ∆(i) i Γ(i)}|. It is easy to construct examples with and without strictly popular coalition structures, which raises the question about the complexity of the following problems. In -V ERIFICATION -S TRICT-P OPULARITY, we are given a hedonic game (N, ) by its network of friends and a coalition structure Γ and we ask whether Γ is strictly popular under . In -E XISTENCE - S TRICT-P OPULARITY, we are given just a hedonic game (N, ) by its network of friends and we ask whether there exists a strictly popular coalition structure under . Nguyen et al. [NRR+ 16] proved that, under SF -preferences, the verification problem is coNP-complete and the exis- tence problem is coNP-hard. We will show the same two results even for all three degrees of minimum-based altruism. Theorem 4. Under minSF , minEQ , and minAL , the verification problem for strict popularity is coNP-complete. Proof. To see that the problems above are in coNP, consider the complementary problem and note that falsification can be done by nondeterministically guessing a coalition structure which is at least as popular. To prove coNP-hardness for minEQ , we reduce the complement of the well-known NP-complete problem E XACT-C OVER - BY-T HREE -S ETS (X3C) [GJ79] to our verification problem. The idea behind this reduction is inpired by, but different from, the idea used by Nguyen et al. [NRR+ 16] for the proof of coNP-completeness of the verification problem under SF -preferences, which itself is inspired by methods of Sung and Dimitrov [SD10]. Let (B, S ) with B = {1, ..., 3k} and S = {S1 , ..., Sm } be an instance of the problem X3C, so each member of S is a size-3 subset of B and the question is whether there exists an exact cover of B, i.e., a size-k subfamily S 0 of S such that each element of B occurs in exactly one member of S 0 . Consider the set of players N given by N = {βb | b ∈ B} ∪ {ζS,l | S ∈ S , 1 ≤ l ≤ 3k} ∪ {ηS, j | S ∈ S , 1 ≤ j ≤ 3} with the following network of friends: (1) All players in {βb | b ∈ B} are friends with each other. (2) Each βb , b ∈ B, is friends with all ζS,l , 1 ≤ l ≤ 3k, with b ∈ S. (3) For all S ∈ S , the players in QS = {ζS,l , ηS, j | 1 ≤ l ≤ 3k, 1 ≤ j ≤ 3} are friends with each other. We consider the coalition structure Γ defined by Γ = {{β1 , ..., β3k }, QS1 , ..., QSm } and have thus constructed an instance ((N, minEQ ), Γ) of our verification problem. We claim that Γ is a strictly popular coalition structure if and only if there is no exact cover for B in S . Only if: We will show that the existence of an exact cover for B in S implies that Γ is not strictly popular. Let S 0 ⊆ S be so that |S 0 | = k and S∈S 0 S = B. Consider the coalition structure ∆ given by ∆ = {{βb | b ∈ S} ∪ {ζS,l | 1 ≤ l ≤ 3k} | S S ∈ S 0 } ∪ {{ηS,1 , ηS,2 , ηS,3 } | S ∈ S 0 } ∪ {QS | S ∈ S \ S 0 }. It holds that: 1. The players in QS , S ∈ S \ S 0 , are in the same coalition in Γ and ∆, so they are indifferent between Γ and ∆. 2. For S ∈ S 0 , 1 ≤ l ≤ 3k, the players ζS,l are indifferent as well, because their coalitions in Γ and ∆ are (3k + 3)-cliques and thus vminEQ ζ (Γ) = n(3k + 2) = vminEQ ζ (∆). S,l S,l 3. For S ∈ S 0 , 1 ≤ j ≤ 3, the players ηS, j prefer Γ since vminEQ minEQ ηS, j (Γ) = n(3k + 2) > 2n = vηS, j (∆). 4. The players βb , b ∈ B, prefer ∆ since vminEQ β (Γ) = n(3k − 1) < n(3k + 2) = vminEQ β (∆). b b In total, it follows that |{i ∈ N | Γ(i) minEQ i ∆(i)}| = |{ηS, j | S ∈ S 0 , j ∈ {1, 2, 3}}| = 3|{S | S ∈ S 0 }| = 3k = |{βb | b ∈ minEQ B}| = |{i ∈ N | ∆(i) i Γ(i)}|, and thus the coalition structure Γ is not strictly popular. If: We will show that Γ not being strictly popular implies that there exists an exact cover of B in S . If Γ is not strictly popular then there exists a coalition structure ∆ 6= Γ with |{i ∈ N | ∆(i) minEQ i Γ(i)}| ≥ |{i ∈ N | Γ(i) minEQ i ∆(i)}|. We state the following three claims (whose proofs are omitted here). Claim 5. All ηS, j prefer QS to every other coalition. Claim 6. The players ζS,l cannot improve by joining any other coalition. Claim 7. Every player ζS,l has exactly two most preferred coalitions. Now we distinguish the following two cases. Case 1: For all i ∈ N, ∆(i) ∼minEQ i Γ(i). By Claim 5, ∆(ηS, j ) = QS and thus ∆(ζS,l ) = QS for all S ∈ S , 1 ≤ l ≤ 3k, and 1 ≤ j ≤ 3. The remaining βb can only form coalitions among themselves in ∆. Since all βb , b ∈ B, are friends, deviating from {βb | b ∈ B} by forming smaller coalitions will make them unhappier. It follows that ∆(βb ) = {βb | b ∈ B}. Thus ∆ = Γ, a contradiction. Case 2: There is an i ∈ N such that ∆(i) minEQ i Γ(i). Because of Claims 5 and 6 this i has to be of the form i = βb for some b ∈ B. To prefer its coalition in ∆, there has to be at least one additional friend of βb in ∆(βb ) which is not in {βa | a ∈ B}, because Γ(i) forms a clique. So one can conclude that there is a ζS,l with b ∈ S in ∆(βb ). We will show that ∆(βb ) = {βa | a ∈ S} ∪ {ζS,l | 1 ≤ l ≤ 3k}. By assuming otherwise, we can conclude by using Claim 7 that all ζS,l , 1 ≤ l ≤ 3k, prefer Γ. In addition, Claim 5 yields that ηS,1 , ηS,2 , and ηS,3 are unhappier with ∆ as well. Thus we have |{i ∈ N | Γ(i) minEQ i ∆(i)}| ≥ 3k + 3. However, because of the preceding claims, there are at most 3k players who are able to prefer ∆, which is a contradiction. So it holds that ∆(βb ) = {βa | a ∈ S} ∪ {ζS,l | 1 ≤ l ≤ 3k}. By forming this coalition, we can conclude that: (a) There are 3k players who are indifferent: {ζS,l | 1 ≤ l ≤ 3k}; (b) there are three players who prefer ∆: {βa | a ∈ S}; and (c) there are three players who prefer Γ: {ηS, j | 1 ≤ j ≤ 3}. If the remaining βb would stay among themselves, they all would clearly prefer Γ and thus there would be more players preferring Γ than players who prefer ∆. So by inductively arguing as above, for each βb , b ∈ B, there exists a set S ∈ S so that ∆(βb ) = {βa | a ∈ S} ∪ {ζS,l | 1 ≤ l ≤ 3k}. We write S 0 ⊆ S for the subset containing these S ∈ S . Because of the uniqueness of the coalitions in ∆, we have S ∩ S0 = 0/ for all S, S0 ∈ S 0 with S 6= S0 . For every b ∈ B, there is a S ∈ S 0 so that b ∈ S. So by definition, S 0 is an exact cover of B. This completes the proof for minEQ -preferences. For the proof of the coNP-hardness for minAL one can use the same reduction as in the previous case. However, for the correctness one has to consider different arguments. The proof is omitted due to space limitations. Finally, coNP-hardness for minSF can be shown via the same reduction that Nguyen et al. [NRR+ 16] used to prove coNP-hardness for SF (though, again, the proof of correctness is slightly different). q By a slight modification of the reduction used in the proof of Theorem 4, we obtain: Corollary 8. Under minSF , minEQ , and minAL , the existence problem for strict popularity is coNP-hard. 6 Most Preferred Coalitions In the minSF case, it is trivial to see which coalition a player prefers the most: the coalition which contains himself, all his friends and none of his enemies. However, in the remaining two cases this is not so easy: More friends do not always result in an increase of the player’s happiness since unhappy friends will drag it down. We will consider the following decision problem: -V ERIFICATION -M OST-P REFERRED Given: A hedonic game (N, ) by its network of friends, a coalition A and a player i ∈ A. Question: Does A i B hold for all B ∈ 2Ni (i.e. is A a most preferred coalition for player i) ? It is easy to see, that the complementary problems for minEQ and minAL are in NP since falsification can be done by nondeterministically guessing a coalition which the player likes better. Thus the problem above is in coNP. We assume that the two problems above are coNP-complete as well, but are not able to show this at the moment. However, we can show that the difficulty solely depends on the number of enemies of the unhappiest friend, i.e. we show, that computing the number of friends of the unhappiest friend in a most preferred coalition of a player can be done in polynomial time. For minEQ preferences it can be done by using the following algorithm: Algorithm 1: Calculation of the number of friends of the unhappiest friend in a most preferred coalition Data: Network of friends G = (N, A) and a ∈ N Result: kmin 1 kmin ← min {degG (b)} b∈Fa ∪{a} 2 while kmin < degG (a) do 3 Nmin ← {b ∈ Fa | degG (b) ≤ kmin } 4 G ← (N \ Nmin , {e ∈ A | e ∩ Nmin = 0}) / 5 ktemp ← min {degG (b)} b∈Fa ∪{a} 6 if ktemp > kmin then 7 kmin ← ktemp The algorithm works als follows: Starting with the coalition which contains every player, one calculates the number of friends of the player a and all his friends. Then the minimum over these values is taken and saved in kmin and the most unhappiest friends are removed from the coalition. Then again, the number of friends of the player and his remaining friends are calculated and the unhappiest friends are removed. If the new minimum is greater then the previous one, kmin gets updated. This procedure repeats as long as the player a himself is not the one with the least amount of friends. Finally, the output kmin is the number of friends of the unhappiest friend of a (including himself) in a most preferred coalition of player a. The proof of correctness is omitted due to space limitations. Remark 9. 1. Since we take out at least one friend of a’s in every iteration of the while loop, the number of iterations is at most linear in |N|. Every command inside (and outside) the loop can be done in polynomial time. Thus, in total, Algorithm 1 runs in polynomial time. 2. To find a most preferred coalition, one has to minimize the number of enemies of the unhappiest friend (including player a). This can be done by finding the smallest coalition which satisfies that the number of friends of the unhappiest friend (including a) is kmin . 3. If Ca is a most preferred coalition of player a, then it holds that n(kmin − 1) < vminEQ a (Ca ) ≤ nkmin . 4. One can construct a similar algorithm for the minimum-altruistic-treatment case. To achieve this, only Fa should be considered when computing the values kmin and ktemp . In addition, the condition for the while loop to terminate has to be altered. 7 Conclusion and Future Work We have introduced and studied the minimum-based variants of the three degrees of altruistic hedonic games due to Nguyen et al. [NRR+ 16]. While this is only a small definitional change, it yields a fundamental change of view and is more appropriate in situations where the entire group of agents crucially suffers from their unhappiest member. We have shown that some of the results for average-based altruistic hedonic games carry over to their minimum-based variants, but some do not. An interesting open question is whether the coNP-completeness results that we obtained for the problem of verifying strict popularity under all three types of minimum-based preferences in Theorem 4 also hold for EQ - and AL -preferences. Regarding future work, we also propose to extend the notion of minimum-based altruism to coalition formation games in general (i.e., not restricted to hedonic games), just as Kerkmann and Rothe [KR20] do for (average-based) altruism in coalition formation games. Acknowledgements. This work was supported in part by DFG grants RO 1202/14-2 and RO 1202/21-1. References [ABB+ 19] H. Aziz, F. Brandl, F. Brandt, P. Harrenstein, M. Olsen, and D. Peters. Fractional hedonic games. ACM Transactions on Economics and Computation, 7(2):Article 6, 2019. [ABH13] H. Aziz, F. Brandt, and P. Harrenstein. Pareto optimality in coalition formation. Games and Economic Behavior, 82:562–581, 2013. [AHLW16] H. Aziz, P. Harrenstein, J. Lang, and M. Wooldridge. Boolean hedonic games. In Proc. KR’16, pages 166–175. AAAI Press, 2016. [AS12] K. Apt and G. Schäfer. Selfishness level of strategic games. In Proc. SAGT’12, pages 13–24. Springer-Verlag LNCS #7615, 2012. [AS16] H. Aziz and R. Savani. Hedonic games. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, editors, Handbook of Computational Social Choice, pages 356–376. Cambridge University Press, 2016. [Bal04] C. Ballester. NP-completeness in hedonic games. Games and Economic Behavior, 49(1):1–30, 2004. [BJ02] A. Bogomolnaia and M. Jackson. The stability of hedonic coalition structures. Games and Economic Behav- ior, 38(2):201–230, 2002. [BKS01] S. Banerjee, H. Konishi, and T. Sönmez. Core in a simple coalition formation game. Social Choice and Welfare, 18(1):135–153, 2001. [BL11] S. Brânzei and K. Larson. Social distance games. In Proc. IJCAI’11, pages 91–96. AAAI Press/IJCAI, 2011. [CBKS11] P. Chen, B. de Keijzer, D. Kempe, and G. Schäfer. The robust price of anarchy of altruistic games. In Proc. WINE’11, pages 383–390. Springer-Verlag LNCS #7090, 2011. [CH03] K. Cechlárová and J. Hajduková. Computational complexity of stable partitions with B-preferences. Interna- tional Journal of Game Theory, 31(3):353–364, 2003. [CH04] K. Cechlárová and J. Hajduková. Stable partitions with W -preferences. Discrete Applied Mathematics, 138(3):333–347, 2004. [CRM01] K. Cechlárová and A. Romero-Medina. Stability in coalition formation games. International Journal of Game Theory, 29(4):487–494, 2001. [DBHS06] D. Dimitrov, P. Borm, R. Hendrickx, and S. Sung. Simple priorities and core stability in hedonic games. Social Choice and Welfare, 26(2):421–433, 2006. [DG80] J. Drèze and J. Greenberg. Hedonic coalitions: Optimality and stability. Econometrica, 48(4):987–1003, 1980. [ER15] E. Elkind and J. Rothe. Cooperative game theory. In J. Rothe, editor, Economics and Computation, pages 135–193. Springer, 2015. [EW09] E. Elkind and M. Wooldridge. Hedonic coalition nets. In Proc. AAMAS’09, pages 417–424. IFAAMAS, 2009. [GJ79] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979. [HS09] M. Hoefer and A. Skopalik. Altruism in atomic congestion games. In Proc. ESA’09, pages 179–189. Springer- Verlag LNCS #5757, 2009. [KR20] A. Kerkmann and J. Rothe. Altruism in coalition formation games. In Proc. IJCAI’20. ijcai.org, 2020. To appear. [LRR+ 15] J. Lang, A. Rey, J. Rothe, H. Schadrack, and L. Schend. Representing and solving hedonic games with ordinal preferences and thresholds. In Proc. AAMAS’15, pages 1229–1237, 2015. [MMV18] G. Monaco, L. Moscardelli, and Y. Velaj. Hedonic games with social context. In Proc. ICTCS’18, volume 2234, pages 24–35. CEUR-WS.org, 2018. [MMV19] G. Monaco, L. Moscardelli, and Y. Velaj. On the performance of stable outcomes in modified fractional hedonic games with egalitarian socialwelfare. In Proc. AAMAS’19, pages 873–881. IFAAMAS, 2019. [NRR+ 16] N. Nguyen, A. Rey, L. Rey, J. Rothe, and L. Schend. Altruistic hedonic games. In Proc. AAMAS’16, pages 251–259. IFAAMAS, 2016. [PE15] D. Peters and E. Elkind. Simple causes of complexity in hedonic games. In Proceedings of the 24th Interna- tional Joint Conference on Artificial Intelligence, pages 617–623. AAAI Press/IJCAI, July 2015. [Pet16] D. Peters. Complexity of hedonic games with dichotomous preferences. In Proc. AAAI’16, pages 579–585. AAAI Press, 2016. [RRSS16] A. Rey, J. Rothe, H. Schadrack, and L. Schend. Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games. Annals of Mathematics and Artificial Intelligence, 77(3):317–333, 2016. [RS13] M. Rahn and G. Schäfer. Bounding the inefficiency of altruism through social contribution games. In Proc. WINE’13, pages 391–404. Springer-Verlag LNCS #8289, 2013. [RSS18] J. Rothe, H. Schadrack, and L. Schend. Borda-induced hedonic games with friends, enemies, and neutral players. Mathematical Social Sciences, 96:21–36, 2018. [SD07] S. Sung and D. Dimitrov. On core membership testing for hedonic coalition formation games. Operations Research Letters, 35(2):155–158, 2007. [SD10] S. Sung and D. Dimitrov. Computational complexity in additive hedonic games. European Journal of Opera- tional Research, 203(3):635–639, 2010. [SG18] J. Schlueter and J. Goldsmith. Super altruistic hedonic games. In Proc. M-PREF’18, 2018. [Woe13a] G. Woeginger. Core stability in hedonic coalition formation. In Proc. SOFSEM’13, pages 33–50. Springer- Verlag LNCS #7741, January 2013. [Woe13b] G. Woeginger. A hardness result for core stability in additive hedonic games. Mathematical Social Sciences, 65(2):101–104, 2013.