[CH03, CH04, ABH13] to investigating the related problems in terms of their computational complexity [Bal04, SD07,
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 Braˆnzei and Larson [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 noncooperative game theory, various notions of altruism have been studied by, e.g., Hoefer and Skopalik [HS09], Chen et al. [CBKS11], Apt and Scha¨fer [AS12], and Rahn and Scha¨fer [RS13].
Hedonic games are formally defined as follows. Let N = f1; : : : ; ng be a set of players and let 2Ni = fC N j i 2 Cg be the set of all coalitions of N containing player i 2 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 G of N into k coalitions, and G(i) denotes the unique coalition in G containing player i 2 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 2 N, let N n fig = 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 2 Fj if and only if j 2 Fi for all i; j 2 N, i 6= j. For A 2 2Ni , we define the friend-oriented utility of player i by viF (A) = njA \ Fij jA \ Eij, and the friend-oriented preferences iF of player i are given by A iF B () viF (A) viF (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; ffi; jg N j i 2 Fjg) 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 iF B () (jA \ Fij > jB \ Fij) or (jA \ Fij = jB \ Fij and jA \ Eij jB \ Eij).
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 2 N and a constant M n3: 1. Using the utility function viminSF (A) = M(njA \ Fij jA \ Eij) + min fnjA \ Faj jA \ Eajg, define the minimuma2A\Fi selfish-first preferences by A iminSF B () viminSF (A) viminSF (B). 2. Using the utility function viminEQ(A) = ences by A iminEQ B () viminEQ(A)
min a2(A\Fi)[fig viminEQ(B).
fnjA \ Faj jA \ Eajg, define the minimum-equal-treatment prefer3. Using the utility function viminAL(A) = njA \ Fij jA \ Eij + M min fnjA \ Faj jA \ Eajg, define the minimuma2A\Fi altruistic-treatment preferences by A iminAL B () viminAL(A) viminAL(B).
Nguyen et al. [NRR+16], are denoted by viSF , viEQ, viAL and iSF , iEQ, iAL.
hedonic games whenever M n5, we can prove Proposition 1 for any choice of M n3. The proof, similar to that of
vSF 1 22M + 16 22M + 19 vminSF 1 22M + 13 22M + 4
n3, the following two implications hold for each i 2 N and for all two coalitions A; B 2 2Ni : iminSF B and a2mAi\nFifvaF (A)g > a2mBi\nFifvaF (B)g =) A iminAL B.
Example 1. Let N = f1; : : : ; 8g be the set of players with the network of friends displayed in Figure 1 (left).
A direct calculation for the coalitions A = f1; 2; 3; 4; 5; 8g and B = f1; 2; 3; 4; 6; 7g 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
Definition 1. Let (N; ) be a hedonic game. A coalition structure G is said to be: 1. Nash stable if for all players i 2 N and every coalition C 2 G [ f0/ g, player i weakly prefers her own coalition to joining C: (8i 2 N)(8C 2 G [ f0/ g) [G(i) i C [ fig]; 2. individually stable if for all players i 2 N and every coalition C 2 G [ f g 0/ , player i weakly prefers her own coalition to joining C, or there is a player in C who objects i joining his coalition: (8i 2 N)(8C 2 G [ f0/ g) [G(i) i C [ fig _ (9 j 2 C) [C j C [ fig]]; 3. contractually individually stable if for all players i 2 N and every coalition C 2 G [ f0/ g, 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 G(i) who is against i leaving G(i): (8i 2 N)(8C 2 G [ f0/ g) [G(i) i C [ fig _ (9 j 2 C) [C j C [ fig] _ (9k 2 G(i)) [G(i) k G(i) n fig]].
individual stability. The following example illustrates these concepts for minEQ-preferences.
Example 2. Let N = f1; : : : ; 8g be the set of players with the friendship relations as depicted in Figure 2 (left). We take a look at the coalition structure G = fA; B;Cg, 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 G. So to check the three stability concepts we defined above, there is only player 1 left to consider: 1. 1 prefers C [ f1g to G(1) = A, so G is not Nash stable. 2. Now, 1 preferring to join C cannot be used to show that G is not individually stable because the happiness of 8 worsens after 1 joins. However, 1 prefers B [ f1g to A as well and no player in B objects. Thus the coalition structure G 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 G is contractually individually stable.
Under minSF and minAL, we obtain similar results. For happiness by joining another coalition in G.
minAL, though, 1 is not the only player that can improve her
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: 4 B 5 6 C 1 8 7 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
all players i 2 C; and C weakly blocks G if C i G(i) for all players i 2 C and there exists a player j 2 C with C is core stable if no nonempty C N blocks G; and G is strictly core stable if no C N weakly blocks G. i G(i) for j G( j). G
Proposition 3. For
minSF -preferences, there always exists a strictly core stable coalition structure.
minAL-preferences. minEQ- and Example 3. Let N = f1; 2; 3; 4; 5g 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 = f1; 2; 3g. (2) The unique, most preferred coalition of players 4 and 5 is B = f3; 4; 5g. (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 G does not contain A, the coalition A weakly blocks G. 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
structures D 6= G it holds that jfi 2 N j G(i) i D(i)gj > jfi 2 N j D(i) i G(i)gj.
complexity of the following problems. In -VERIFICATION-STRICT-POPULARITY, we are given a hedonic game (N; ) by its network of friends and a coalition structure G and we ask whether G is strictly popular under . In -EXISTENCE
a strictly popular coalition structure under .
tence problem is coNP-hard. We will show the same two results even for all three degrees of minimum-based altruism. Theorem 4. Under
minAL, the verification problem for strict popularity is coNP-complete.
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 EXACT-COVER-BY-THREE-SETS (X3C) [GJ79] to our verification problem. The idea behind this reduction is inpired by, but different from, the idea used by
itself is inspired by methods of Sung and Dimitrov [SD10].
Let (B; S ) with B = f1; :::; 3kg and S = fS1; :::; Smg 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 = fbb j b 2 Bg [ fzS;l j S 2 S ; 1 l 3kg [ fhS; j j S 2 S ; 1 j 3g with the following network of friends: (1) All players in fbb j b 2 Bg are friends with each other. (2) Each bb, b 2 B, is friends with all zS;l , 1 l 3k, with b 2 S. (3) For all S 2 S , the players in QS = fzS;l ; hS; j j 1 l 3k; 1 j 3g are friends with each other.
We consider the coalition structure G defined by G = ffb1; :::; b3kg; QS1 ; :::; QSm g and have thus constructed an instance ((N; minEQ); G) of our verification problem.
be so that jS 0j = k and SS2S 0 S = B. Consider the coalition structure D given by D = ffbb j b 2 Sg [ fzS;l j 1 l 3kg j S 2 S 0g [ ffhS;1; hS;2; hS;3g j S 2 S 0g [ fQS j S 2 S n S 0g. It holds that: 1. The players in QS, S 2 S n S 0, are in the same coalition in G and D, so they are indifferent between G and D.
3k, the players zS;l are indifferent as well, because their coalitions in G and D are (3k + 3)-cliques 2. For S 2 S 0, 1 3. For S 2 S 0, 1 l j and thus vzmSi;nlEQ(G) = n(3k + 2) = vzmSi;nlEQ(D).
3, the players hS; j prefer G since vhmSin;jEQ(G) = n(3k + 2) > 2n = vhmSin;jEQ(D). 4. The players bb, b 2 B, prefer D since vbmbinEQ(G) = n(3k 1) < n(3k + 2) = vbmbinEQ(D).
In total, it follows that jfi 2 N j G(i) iminEQ D(i)gj = jfhS; j j S 2 S 0; j 2 f1; 2; 3ggj = 3jfS j S 2 S 0gj = 3k = jfbb j b 2 Bgj = jfi 2 N j D(i) iminEQ G(i)gj, and thus the coalition structure G is not strictly popular.
popular then there exists a coalition structure D 6= G with jfi 2 N j D(i) iminEQ G(i)gj jfi 2 N j G(i) iminEQ D(i)gj. We state the following three claims (whose proofs are omitted here).
Case 1: For all i 2 N, D(i) iminEQ G(i). By Claim 5, D(hS; j) = QS and thus D(zS;l ) = QS for all S 2 S , 1 l 3k, and 1 j 3. The remaining bb can only form coalitions among themselves in D. Since all bb, b 2 B, are friends, deviating from fbb j b 2 Bg by forming smaller coalitions will make them unhappier. It follows that D(bb) = fbb j b 2 Bg. Thus D = G, a contradiction.
Case 2: There is an i 2 N such that D(i) iminEQ G(i). Because of Claims 5 and 6 this i has to be of the form i = bb for some b 2 B. To prefer its coalition in D, there has to be at least one additional friend of bb in D(bb) which is not in fba j a 2 Bg, because G(i) forms a clique. So one can conclude that there is a zS;l with b 2 S in D(bb).
We will show that D(bb) = fba j a 2 Sg [ fzS;l j 1 l 3kg. By assuming otherwise, we can conclude by using Claim 7 that all zS;l , 1 l 3k, prefer G. In addition, Claim 5 yields that hS;1, hS;2, and hS;3 are unhappier with D as well. Thus we have jfi 2 N j G(i) iminEQ D(i)gj 3k + 3. However, because of the preceding claims, there are at most 3k players who are able to prefer D, which is a contradiction. So it holds that D(bb) = fba j a 2 Sg [ fzS;l j 1 l 3kg. By forming this coalition, we can conclude that: (a) There are 3k players who are indifferent: fzS;l j 1 l 3kg; (b) there are three players who prefer D: fba j a 2 Sg; and (c) there are three players who prefer G: fhS; j j 1 j 3g.
preferring G than players who prefer D. So by inductively arguing as above, for each bb, b 2 B, there exists a set S 2 S so that D(bb) = fba j a 2 Sg [ fzS;l j 1 l 3kg. We write S 0 S for the subset containing these S 2 S . Because of the uniqueness of the coalitions in D, we have S \ S0 = 0/ for all S; S0 2 S 0 with S 6= S0. For every b 2 B, there is a S 2 S 0 so that b 2 S. So by definition, S 0 is an exact cover of B. This completes the proof for minEQ-preferences.
correctness one has to consider different arguments. The proof is omitted due to space limitations.
Corollary 8. Under minAL, the existence problem for strict popularity is coNP-hard. 6
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.
-VERIFICATION-MOST-PREFERRED
Question: Does A i B hold for all B 2 2Ni (i.e. is A a most preferred coalition for player i) ?
nondeterministically guessing a coalition which the player likes better. Thus the problem above is in coNP.
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:
b2mFa[infagfdegG(b)g
Data: Network of friends G = (N; A) and a 2 N
Result: kmin 1 kmin 2 while kmin < degG(a) do 3 Nmin fb 2 Fa j degG(b) kming 4 G (N n Nmin; fe 2 A j e \ Nmin = 0/ g) 5 ktemp min fdegG(b)g
b2Fa[fag 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.
at most linear in jNj. 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) < vaminEQ(Ca) nkmin.
considered when computing the values kmin and ktemp. In addition, the condition for the while loop to terminate has to be altered. 7
more appropriate in situations where the entire group of agents crucially suffers from their unhappiest member.
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
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.
[ABH13] [BL11]
tional Journal of Game Theory, 31(3):353–364, 2003.