# altruism_in_coalition_formation_games__767ebb3b.pdf

Altruism in Coalition Formation Games

Anna Maria Kerkmann and J org Rothe Institut f ur Informatik, Heinrich-Heine-Universit at D usseldorf, Germany {anna.kerkmann, rothe}@uni-duesseldorf.de

Nguyen et al. [2016] introduced altruistic hedonic games in which agents utilities depend not only on their own preferences but also on those of their friends in the same coalition. We propose to extend their model to coalition formation games in general, considering also the friends in other coalitions. Comparing the two models, we argue that excluding some friends from the altruistic behavior of an agent is a major disadvantage that comes with the restriction to hedonic games. After introducing our model, we additionally study some common stability notions and provide a computational analysis of the associated veriﬁcation and existence problems.

1 Introduction We consider coalition formation games where agents have to form coalitions based on their preferences. For hedonic coalition formation games, Dimitrov et al. [2006] proposed the friends-and-enemies encoding with friend-oriented preferences which involves a network of friends, a (simple) graph whose vertices are the players and where two players are connected by an edge exactly if they are friends of each other. Players not connected by an edge consider each other as enemies. Under friend-oriented preferences, player i prefers a coalition C to a coalition D if C contains more of her friends than D, or C and D contain equally many friends but C contains fewer enemies than D. This is a special case of the additive encoding [Aziz et al., 2013]. For more background on these two compact representations, see Section 2 and the book chapter by Aziz and Savani [2016]. Based on friend-oriented preferences, Nguyen et al. [2016] introduced altruistic hedonic games where agents gain utility not only from their own satisfaction but also from their friends satisfaction. However, Nguyen et al. [2016] specifically considered hedonic games only, which require that an agent s utility only depends on her own coalition. In their interpretation of altruism, the utility of an agent is composed of the agent s own valuation of her coalition and the valuations of all this agent s friends in this coalition. Inspired by the idea of altruism, we extend their model to coalition formation games in general. However, we propose a model where agents behave altruistically to all their friends,

Figure 1: A network of friends

not only to the friends in the same coalition. Not restricting to hedonic games, we aim to capture a more natural notion of altruism where none of an agent s friends is excluded from her altruistic behavior. To become acquainted with this idea of altruism, consider the following coalition formation game, represented by the network of friends in Figure 1. Considering coalition structures Γ = {{1, 2, 3}, {4}} and = {{1, 2, 4}, {3}}, it becomes clear that player 1 is indifferent between coalitions {1, 2, 3} and {1, 2, 4} under friendoriented preferences as both coalitions contain one of her friends and one of her enemies. Under altruistic hedonic preferences [Nguyen et al., 2016], however, player 1 behaves altruistically to her friend 2 (who is friends with 3 but not with 4) and therefore prefers {1, 2, 3} to {1, 2, 4}. Now, consider Γ = {{1}, {2, 3}, {4}} and = {{1}, {2, 4}, {3}}. Intuitively, one would still expect 1 to behave altruistically to her friend 2. However, it becomes obvious that under any hedonic preference (which requires that player 1 s preference only depends on her own coalition), player 1 would be indifferent between Γ and . To model a global level of altruism, we release the restriction to hedonic games and introduce altruistic coalition formation where agents behave altruistically to all their friends, independently of their current coalition.

Related Work. Coalition formation games, as considered here, are closely related to the subclass of hedonic games which has been broadly studied in the literature, addressing the issue of compactly representing preferences (some representations are listed in Section 2), conducting axiomatic analyses, dealing with different notions of stability, and investigating the computational complexity of the associated problems (see, e.g., the book chapter by Aziz and Savani [2016]). Previously, altruism in games and social contexts of games have been considered mainly for noncooperative games. Most prominently, Ashlagi et al. [2008] introduced social context games where a strategic game is embedded in a social context that is modeled by a graph of neighborhood. Examples include ranking games [Brandt et al., 2009] and coalitional congestion games [Hayrapetyan et al., 2006; Kuniavsky and Smorodinsky, 2014]. In particular, in the so-

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

cial context that Ashlagi et al. [2008] call surplus collaboration, players seek to maximize the average payoff of themselves and their friends. Still, their model differs from ours in that they consider noncooperative games. Other work studying altruism in noncooperative games is due to Hoefer and Skopalik [2009], Chen et al. [2011], Apt and Sch afer [2014], and Rahn and Sch afer [2013]. Based on altruistic hedonic games [Nguyen et al., 2016], Schlueter and Goldsmith [2018] deﬁned super altruistic hedonic games, related to social distance games due to Brˆanzei and Larson [2011], where friends have a different impact on an agent based on their distances in the underlying network of friends. Monaco et al. [2018; 2019] studied hedonic games with social context and modiﬁed the fractional hedonic games of Aziz et al. [2019] based on egalitarian social welfare. While in their models players care also about their friends happiness, they focus on Nash equilibria, the price of anarchy, and the price of stability. Our Contribution. Conceptually, we extend the model of altruism proposed by Nguyen et al. [2016] from hedonic games to general coalition formation games. We argue how this captures a more global notion of altruism. Technically, we study the common stability concepts in this model and analyze the associated veriﬁcation and existence problems in terms of their computational complexity.

2 The Model Coalition Formation Games. Let N = {1, . . . , n} be a set of agents (or players). Each subset of N is called coalition. A coalition structure Γ is a partition of N and we denote the set of all possible coalition structures by CN. For a player i N and a coalition structure Γ CN, Γ(i) denotes the coalition in Γ containing i. The objective of a coalition formation game is to form a coalition structure based on the agents preferences. Hence, a coalition formation game is a pair (N, ), where N = {1, . . . , n} is a set of agents, = ( 1, . . . , n) is a proﬁle of preferences, and every preference i CN CN is a complete weak order over all possible coalition structures. Note that hedonic games are a special case of coalition formation games where an agent s preference relation only depends on the coalitions containing herself. In a hedonic game (N, ), agent i N is indifferent between any two coalition structures Γ and as long as her coalition is the same, i.e., Γ(i) = (i) = Γ i . Therefore, the preference of agent i N is usually represented by a complete weak order over the set of coalitions containing i. The Friends and Enemies Encoding. Since |CN|, the number of all possible coalition structures, is exponential in the number of agents, it is not reasonable to ask every agent for her complete preference over CN. Instead, we are looking for a way to compactly represent the agents preferences. In the literature, many such representations have been proposed for hedonic games such as the additive encoding [Sung and Dimitrov, 2010; Aziz et al., 2013; Woeginger, 2013], the singleton encoding due to Cechl arov a and Romero-Medina [2001] and further studied by Cechl arov a and Hajdukov a [2003], the friends and enemies encoding due to Dimitrov et al. [2006], and FEN-hedonic games due to Lang et al. [2015] and also used by Kerkmann et al. [2020;

2019] and Rothe et al. [2018]. Here, we use the friend-andenemy encoding due to Dimitrov et al. [2006]. We focus on their friend-oriented model and will later adapt it to our altruistic model. In the friend-oriented model, the preferences of the agents in N are given by a network of friends, i.e., a (simple) graph G = (N, A) whose vertices are the players and where two players i, j N are connected by an edge {i, j} A exactly if they are each other s friends. Agents not connected by an edge consider each other as enemies. For an agent i N, we denote the set of i s friends by Fi = {j N | {i, j} A} and the set of i s enemies by Ei = N \ (Fi {i}). Under friend-oriented preferences as deﬁned by Dimitrov et al. [2006], players prefer coalitions with more friends to those with fewer friends and, if there are equally many friends they prefer the coalition with fewer enemies: C F i D |C Fi| > |D Fi| or (|C Fi| = |D Fi| and |C Ei| |D Ei|). This can also be represented additively. Assigning a value of n to each friend and a value of 1 to each enemy, agent i N values coalition C, containing herself, with vi(C) = n|C Fi| |C Ei|. Note that (n 1) vi(C) n(n 1), and vi(C) > 0 if and only if there is at least one friend of i s in C. For a given coalition structure Γ CN, we also write vi(Γ) for player i s value of Γ(i). We, furthermore, denote the sum of the values of i s friends by sum F i (Γ) = P f Fi vf(Γ).

The Altruistic Model. Based on this friend-oriented model, we will deﬁne altruistic coalition formation games, while considering three degrees of altruism as deﬁned by Nguyen et al. [2016]. However, we adapt them to our model, extending the agents altruism to all their friends.

Selﬁsh First (SF): Agents rank different coalition structures mainly based on their own valuations. Only in the case of a tie between two coalition structures, their friends valuations are considered as well.

Equal Treatment (EQ): Agents treat themselves and their friends the same. That means that an agent i N and all of i s friends have the same impact on i s utility.

Altruistic Treatment (AL): Agents rank coalition structures based on their friends valuations. They only consider their own valuations in the case of a tie.

Formally, for an agent i N and a coalition structure Γ CN, we denote i s utility for Γ under selﬁsh-ﬁrst preferences by u SF i (Γ), under equal treatment by u EQ i (Γ), and under altruistic treatment by u AL i (Γ). They are deﬁned as

u SF i (Γ) = M vi(Γ) + sum F i (Γ) with M n3,

u EQ i (Γ) = vi(Γ) + sum F i (Γ), and

u AL i (Γ) = vi(Γ) + M sum F i (Γ) with M n2.

For any coalition structures Γ, CN, agent i s selﬁsh-ﬁrst preference is then deﬁned by Γ SF i u SF i (Γ) u SF i ( ). Her equaland altruistic-treatment preferences ( EQ i ; AL i ) are deﬁned analogously, using u EQ i and u AL i . The factor M, which is used for the selﬁsh-ﬁrst model and for altruistic treatment, ensures that an agent s utility is ﬁrst determined by the agent s own valuation in the selﬁsh-ﬁrst

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

Figure 2: Network of friends for Example 1

vi(Γ) 1 2 3 4 5 sum F 1 (Γ)

Γ1 15 3 9 9 0 21

Γ2 5 5 10 10 10 25

Table 1: Comparison of two coalition structures in Example 1

model and by the friends valuations in the altruistic model. Similarly as Nguyen et al. [2016] prove the corresponding properties in hedonic games, we can show that for M n3, vi(Γ) > vi( ) implies Γ SF i , and for M n2, sum F i (Γ) > sum F i ( ) implies Γ AL i . An altruistic coalition formation game (ACFG) is a coalition formation game where the agents preferences were obtained by a network of friends via one of these three cases of altruism. For any ACFG, the players utilities can obviously be computed in polynomial time.

Comparison to Altruism in Hedonic Games. Nguyen et al. [2016] focus on altruism in hedonic games where an agent s utility only depends on her own coalition. As we have already seen from the example in the introduction, there are some aspects of altruistic behavior that cannot be realized by hedonic games. The following example shows that our model crucially differs from the model due to Nguyen et al. [2016].

Example 1 Consider an ACFG with ﬁve agents, N = {1, 2, 3, 4, 5}, and the network of friends in Figure 2. Table 1 shows the values vi(Γ), 1 i 5, and the sum of the values of player 1 s friends for coalition structures Γ1 = {{1, 2, 3, 4}, {5}} and Γ2 = {{1, 2}, {3, 4, 5}}. Under the selﬁsh-ﬁrst model, agent 1 prefers Γ1 to Γ2 (Γ1 SF 1 Γ2) because in Γ1 she is together with all her friends while in Γ2 she is only together with one friend. Under altruistic treatment, however, she prefers Γ2 to Γ1 (Γ2 AL 1 Γ1). She would rather form a coalition with only 2 than being with all her friends because 2 doesn t like 3 and 4, and 3 and 4 don t like 2. Since 1 is altruistic to all her friends, she prefers the coalition structure that is valued higher by her friends. Actually, all of agent 1 s friends have a higher valuation for Γ2. Not paying attention to this fact, the altruistictreatment model of Nguyen et al. [2016] crucially differs. In their model, agents only consider friends in their own coalition. Thus, under their model of altruistic treatment, 1 prefers Γ1 to Γ2. She would rather be with 2, 3, and 4 because the average valuation of her friends in her coalition would then be 21

3 = 7 instead of 5

1 = 5 when being alone with 2.

Considering Example 1, an agent does not really seem to act altruistically if she prefers a coalition structure that makes all her friends worse off. To avoid this kind of behavior, we focus on general coalition formation games. In fact, all preferences that were obtained by one of the three degrees of al-

truism, fulﬁll friend-oriented unanimity: For coalition structures Γ, CN, we say i is friend-orientedly unanimous if va(Γ) > va( ) for each a Fi {i} implies Γ i . Comparing coalition structures by concentrating only on the coalitions that the considered agent is part of, the equaland altruistic-treatment models by Nguyen et al. [2016] are not friend-orientedly unanimous.1

3 Stability in ACFGs

The main question in coalition formation games is which coalition structures might form. There are several stability concepts that are well-studied for hedonic games, each indicating whether a given coalition structure would be accepted by the agents or if there are other coalition structures that are more likely to form. Although we consider more general coalition formation games, we can easily adapt these deﬁnitions to our framework.

Stability Notions. Let (N, ) be an ACFG with agents N = {1, . . . , n} and preferences = ( 1, . . . , n) obtained from a network of friends via one of the three degrees of altruism. A coalition structure Γ is said to be

Nash stable if no player prefers moving to another coalition; formally: ( i N)( C Γ { })[Γ i Γi C], where Γi C denotes the coalition structure that arises from Γ when moving i to C, i.e., Γi C = Γ \ {Γ(i), C} {Γ(i) \ {i}, C {i}};

individually rational if no player would prefer being alone: ( i N)[Γ i Γi ];

individually stable if no player prefers moving to another coalition and could deviate to it without harming any player in that coalition: ( i N)( C Γ { }) Γ i Γi C ( j C)[Γ j Γi C] ;

contractually individually stable if no player prefers another coalition and could deviate to it without harming any player in the new or the old coalition: ( i N)( C Γ { }) Γ i Γi C ( j C)[Γ j Γi C] ( k Γ(i))[Γ k Γi C] ;

totally individually stable if no player prefers another coalition and could deviate to it without harming any other player: ( i N)( C Γ { }) Γ i Γi C ( l N \ {i})[Γ l Γi C] ;

core stable if no nonempty coalition blocks Γ: ( C N, C = )( i C)[Γ i ΓC ], where ΓC denotes the coalition structure arising from Γ when all players in C leave their coalitions to form the new coalition C, i.e., ΓC = Γ \ {Γ(j)|j C} {Γ(j) \ C|j C} {C};

strictly core stable if no coalition weakly blocks Γ: ( C N)( i C)[Γ i ΓC ] ( i C)[Γ i ΓC ];

popular if for every other coalition structure , at least as many players prefer Γ to as there are players who

1Note that they deﬁne a restricted version of friend-oriented unanimity that only considers the agents own coalitions.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

stability notion VERIFICATION EXISTENCE

ind. rationality in P1 trivial: YES1

Nash stability in P1 trivial: YES1

ind. stability in P1 trivial: YES1

core stability co NP-compl.2,3 trivial: YES str. core stability in co NP1 trivial: YES

popularity co NP-compl.2,3 not trivial1

str. popularity co NP-compl.2,3 co NP-hard

perfectness in P2,3 in P2

1 This result also holds for EQ and AL. 2 In co NP for EQ. 3 In co NP for AL.

Table 2: Results for α-VERIFICATION and α-EXISTENCE

prefer to Γ: ( CN, = Γ) |{i N | Γ(i) i (i)}| |{i N | (i) i Γ(i)}| ;

strictly popular if for every other coalition structure , more players prefer Γ to than there are players who prefer to Γ: ( CN, = Γ) |{i N | Γ(i) i (i)}| > |{i N | (i) i Γ(i)}| ; and

perfect if there is no player who prefers any coalition structure to Γ: ( i N)( CN)[Γ i ].

Note that totally individual stability is a new notion which we introduce here. It strengthens the notion of contractually individual stability and makes sense in the context of coalition formation games because players preferences may also be inﬂuenced by coalitions they are not part of.

4 How Hard are Veriﬁcation and Existence?

We now study the associated veriﬁcation and existence problems and conduct a computational analysis for them. Given a stability concept α, these problems are deﬁned as follows.

α-VERIFICATION: Given an ACFG (N, ) and a coalition structure Γ CN, does Γ satisfy α?

α-EXISTENCE: Given an ACFG (N, ), does there exist a coalition structure Γ CN that satisﬁes α?

Table 2 summarizes the results for these problems under SF. We will also give results for EQ and AL in this section. In Table 2, however, we only mark if the results for EQ and AL match those for SF.

Individual Rationality. Verifying individual rationality is easy: We just need to iterate over all agents and compare two coalition structures in each iteration. Since players utilities can be computed in polynomial time, individual rationality can be veriﬁed in time polynomial in the number of agents. The existence problem is trivial, since Γ = {{1}, . . . , {n}} is always individually rational. Furthermore, we give the following characterization for all three degrees of altruism, omitting the proof due to space constraints.

Theorem 2 Let (N, ) be an ACFG and let Γ be a coalition structure. Γ is individually rational if and only if it holds for

1 2 3 4 5 6 7 8 9 10

Figure 3: Network of friends for Example 4

all players i N that Γ(i) contains a friend of i s or i is alone, formally: ( i N)[Γ(i) Fi = Γ(i) = {i}].

Nash Stability. Since there are at most n coalitions in a coalition structure Γ CN, we can verify Nash stability in polynomial time: We just iterate over all agents i N (|N| = n) and all coalitions C Γ { } (at most n + 1) and check whether Γ i Γi C. Since we can check a player s preference over two coalition structures in polynomial time and since we have at most a quadratic number of iterations (n (n + 1)), veriﬁcation is in P for Nash stability. Existence is trivially in P for Nash stability; indeed, the same example that Nguyen et al. [2016] gave for altruistic hedonic games works here as well. Speciﬁcally, for C = {i N | Fi = } = {c1, . . . , ck} the coalition structure {{c1}, . . . , {ck}, N \ C} is Nash stable.

Individual Stability. For individual stability, contractually individual stability, and totally individual stability, existence is trivially in P. Nash stability implies all these three concepts, hence, the Nash stable coalition structure from above is also (contractually; totally) individually stable. Veriﬁcation is also in P for these concepts. Similarly to Nash stability, we iterate over all players and all coalitions and check the particular conditions in polynomial time.

Core Stability and Strict Core Stability. We now show that the existence problem is trivial for (strict) core stability if the preferences are obtained via the selﬁsh-ﬁrst model, again omitting the proof due to space constraints.

Theorem 3 Let (N, SF ) be an ACFG where the preferences SF were obtained from a network of friends G via the selﬁsh-ﬁrst model. Let further C1, . . . , Ck be the vertex sets of the connected components of G. Then Γ = {C1, . . . , Ck} is strictly core stable (and thus core stable).

However, the coalition structure from Theorem 3 is not always core stable under equal treatment or altruistic treatment.

Example 4 Let N = {1, . . . , 10} and let the preferences be given by the network of friends G shown in Figure 3. Consider the coalition structure consisting of the connected components of G, i.e., Γ = {{1, . . . , 10}}, and the coalition C = {8, 9, 10}. C blocks Γ under equal and altruistic treatment. To see this, consider how players 7 to 10 value Γ and ΓC and compute the utilities for players 8, 9, and 10. Omitting the details, for all i C = {8, 9, 10} we have u EQ i (Γ) < u EQ i (ΓC ), which implies Γ EQ i ΓC , and that sum F i (Γ) < sum F i (ΓC ), which implies Γ AL i ΓC . Hence, C blocks Γ for equal and altruistic treatment.

Theorem 5 (Strict) core stability veriﬁcation can be done in co NP for all three degrees of altruism. For the selﬁsh-ﬁrst model, core stability veriﬁcation is even co NP-complete.

The proof of Theorem 5 is omitted due to space constraints.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

Figure 4: Network of friends for Example 6

Popularity and Strict Popularity. Under all three degrees of altruism, there does not always exist a (strictly) popular coalition structure.

Example 6 Let N = {1, . . . , 7} and let the preferences be given by the network of friends shown in Figure 4. Then there is no (strictly) popular coalition structure for any of the three degrees of altruism. Since perfectness implies popularity, there is also no perfect coalition structure. Note that there are 877 possible coalition structures for this game2 and that we tested this example using brute force.

We now show that under the selﬁsh-ﬁrst model it is hard to verify if a given coalition structure is (strictly) popular and it is also hard to decide whether there exists a strictly popular coalition structure for a given ACFG.

Theorem 7 Under the selﬁsh-ﬁrst model, strict popularity veriﬁcation is co NP-complete, strict popularity existence is co NP-hard, and popularity veriﬁcation is co NP-complete.

Proof. Recall that a coalition structure Γ CN is not strictly popular in an ACFG (N, ) (given by a network of friends G) if and only if there is a coalition structure CN, = Γ, such that |{i N | Γ(i) i (i)}| |{i N | (i) i Γ(i)}|. We can nondeterministically guess a coalition structure and verify the above condition in polynomial time, so strict popularity veriﬁcation is in co NP. To show co NP-hardness of strict popularity veriﬁcation, we use a restricted version of EXACT COVER BY 3-SETS (X3C), which we denote by RX3C and which is shown to remain NP-complete by Gonzalez [1985]. We provide a polynomial-time many-one reduction from RX3C to the complement of strict popularity veriﬁcation. An instance (B, S ) of RX3C consists of a set B = {1, . . . , 3k} and a collection S = {S1, . . . , S3k} of 3-element subsets of B (Si B and |Si| = 3 for 1 i 3k). The instance is restricted such that each element of B occurs in exactly three sets in S . Given this instance, the question is whether S contains an exact cover for B, i.e., a subset S S such that every element of B occurs in exactly one set in S . Given an instance (B, S ) of RX3C, we construct the following ACFG. The set of players is given by N = {α1, . . . , α5k} {βb | b B} {ζS, ηS | S S }. Let Alpha = {α1, . . . , α5k}, Beta = {βb | b B}, and QS = {ζS, ηS} for each S S . The network of friends is given in Figure 5, where a dashed circle around a group of players means that all these players are friends of each other:

All players in Alpha Beta are friends of each other.

For every S S , ζS and ηS are friends.

For every S S , ζS is friend with every βb with b S.

2The number of possible partitions of a set with n elements equals the nth Bell number [Bell, 1938; Rota, 1964].

Figure 5: Network of friends in the proof of Theorem 7.

Furthermore, consider the coalition structure Γ = {Alpha Beta, QS1, . . . , QS3k}. We show that S contains an exact cover for B if and only if Γ is not strictly popular. Only if: Assume that there is an exact cover S S for B. Since every set in S contains three elements of B, we have |S | = k. Consider the coalition structure = {Alpha Beta S S S QS} {QS|S S \ S }. All βb, b B prefer to Γ since they have 8k 1 friends in Γ(βb) but 8k friends in (βb). All αl, 1 l 5k prefer Γ to because they have the same number of friends in both coalition structures but no enemies in Γ(αl) and 2k enemies in (αl). All ζS with S S prefer to Γ because they have one friend in Γ(ζS) but four friends in (ζS). For all ζS with S S \ S , it holds that (ζS) = Γ(ζS). Hence, they decide their preferences according to their friends valuations. They are friends with ηS who values Γ and the same and friends with three βb, b S, who all value better than Γ. Hence, ζS prefers to Γ. All ηS with S S prefer Γ to because they have the same number of friends in Γ(ηS) and (ηS) but less enemies in Γ(ηS). However, all ηS with S S \ S are indifferent between Γ and because (ηS) = Γ(ηS) and their only friend ζS values Γ and the same. We then have # Γ = |{i N | (i) i Γ(i)}| = |{β1, . . . , β3k, ζS1, . . . , ζS3k}| = 6k and #Γ = |{i N | Γ(i) i (i)}| = |{α1, . . . , α5k} {ηS|S S }| = 5k + k = 6k. Since # Γ = #Γ , Γ is not strictly popular. If: Assume that Γ is not strictly popular, i.e., that there is a coalition structure CN, = Γ with #Γ # Γ.

For every αl, 1 l 5k, Alpha Beta is her best valued coalition since she is together with all her friends and none of her enemies. Every other coalition is valued worse. Hence, αl prefers Γ to every coalition structure where she is not in Alpha Beta. Furthermore, she is indifferent between Γ and if (αl) = Alpha Beta.

If Alpha Beta were a coalition in then some of the players from QS1, . . . , QS3k would be partitioned in a different way than in Γ. However, this would not cause any player to be happier. There would be at least two players who prefer Γ to but no player who prefers to Γ. This is a contradiction to the assumption.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

Hence, Alpha Beta is not a coalition in and all 5k αplayers prefer Γ to . (But we will show that Alpha Beta is subset of a coalition in .) Furthermore, for every ηS, S S it holds that QS is her best valued coalition. Again, ηS prefers Γ to if (ηS) = QS and is indifferent between Γ and if (ηS) = QS. Let k be the number QS-sets that are not a coalition in , i.e., k = |{S S | QS / }|. Then k is also the number of η-players who prefer Γ to . The other 3k k η-players are indifferent between Γ and . First, observe that k k: For a contradiction, assume that k > k. Then 5k α-players and at least k + 1 η-players prefer Γ to , so #Γ 6k + 1. However, this is a contradiction to #Γ # Γ because there are at most 6k players who prefer to Γ, namely 3k β-players and 3k ζ-players. Next, observe that k k: For a contradiction, assume that k < k. There are k ζS-players with (ζS) = QS. Since every ζS-player is friends with exactly three β-players, these k ζS-players are friends with at most 3k different β-players. For the other (at least) 3k 3k β-players it holds that they have none of their ζ-friends in (β). That means, that they have at most 8k 1 friends in (β) (all other αand βplayers). And if they have exactly 8k 1 friends in (β), then they also have an enemy in (β) because Alpha Beta is not a coalition in . Hence, all these 3k 3k β-players prefer Γ to . We then have #Γ 5k + k + (3k 3k ) = 8k 2k > 8k 2k = 6k. This is a contradiction to #Γ # Γ and # Γ 6k. Hence, k = k and 5k α-players plus k η-players prefer Γ to . Then, because of #Γ # Γ, all βand ζ-players prefer to Γ. This is only possible if each of the 3k β-players has all αand β-players and a ζ-player as friend in (β). Since there are k = k ζS-players with (ζS) = QS, each of these ζS-players is friends with three different β-players. Hence, {S S |QS / } is an exact cover for B. The results for strict popularity existence and popularity veriﬁcation can be shown by slightly changing the above reduction. The details are omitted here. K

Perfectness. Turning now to perfectness, we start with the selﬁsh-ﬁrst model.

Theorem 8 Let G be a network of friends on a set of agents N. A coalition structure Γ CN is perfect under the selﬁsh-ﬁrst model if and only if it consists of the connected components of G and all of them are cliques.

Proof. From left to right, assume that the coalition structure Γ CN is perfect. It then holds for all agents i N and all coalition structures CN, = Γ, that i weakly prefers Γ to (Γ SF i ). It follows that vi(Γ) vi( ) for all CN, = Γ and i N. Hence, every agent i N has the maximal valuation vi(Γ) = n |Fi| and is together with all of her friends and none of her enemies. This implies that each coalition in Γ is a connected component and a clique. The implication from right to left is obvious. K

Since it is easy to check this characterization, perfect coalition structures can be veriﬁed in polynomial time for the selﬁsh-ﬁrst model. It follows directly from Theorem 8 that the corresponding existence problem is also in P:

2 3 4 5 9 7 8 6

Figure 6: Network of friends for Example 11

Corollary 9 Let N be a set of agents and G a network of friends on N. There exists a perfect coalition structure under the selﬁsh-ﬁrst model if and only if all connected components of G are cliques.

Proposition 10 Perfectness veriﬁcation can be done in co NP for all three degrees of altruism. For equal treatment, perfectness existence is in co NP.

We again omit the proof of Proposition 10. We only mention that membership of perfectness existence in co NP for equal treatment follows from the following observations. If a coalition structure Γ CN is perfect under equal treatment then (a) each agent is together with all her friends (i.e., ( i N)[Fi Γ(i)]) and (b) each coalition in Γ has a diameter of at most 2. Combining (a) and (b), Γ consists of the connected components of G and all these components have diameters of at most 2. However, this not an equivalence. The converse does not hold as the following example shows.

Example 11 Let N = {1, . . . , 9} and let the network of friends G be given by Figure 6. Γ = {{1, . . . , 9}} consists of the only connected component of G, which has a diameter of 2. However, Γ is not perfect under equal treatment because agent 1 prefers = {{1, . . . , 6}, {7, 8, 9}} to Γ: Omitting the details, we can show that u EQ 1 ( ) = 113 > 112 = u EQ 1 (Γ).

5 Conclusions and Open Problems We have proposed to extend the model of altruistic hedonic games due to Nguyen et al. [2016] to coalition formation games in general. We have compared this more general model to altruism in hedonic games and have motivated our work by solving some crucial disadvantages that come with the restriction to hedonic games. We have studied the common stability notions and have initiated a computational analysis of the associated veriﬁcation and existence problems (see Table 2 for an overview of our results). We also gave characterizations for some of the stability notions, using graph-theoretical properties of the underlying network of friends. For future work, we propose to complete this analysis and get a full characterization for all stability notions. Furthermore, it would be interesting to see if those problems for which we could only show co NP upper bounds are also co NP-complete. Another interesting research topic could be the consideration of altruism for other representations of the players preferences such as the friends-and-enemies encoding with enemy-oriented preferences [Dimitrov et al., 2006].

Acknowledgements We thank the reviewers for helpful comments. This work was supported in part by DFG grants RO 1202/14-2 and RO 1202/21-1 and the NRW project Online Participation.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)

References [Apt and Sch afer, 2014] Krzysztof Apt and Guido Sch afer. Selﬁshness level of strategic games. Journal of Artiﬁcial Intelligence Research, 49:207 240, February 2014. [Ashlagi et al., 2008] Itai Ashlagi, Piotr Krysta, and Moshe Tennenholtz. Social context games. In Proc. WINE 08, pages 675 683. Springer-Verlag LNCS #5385, December 2008. [Aziz and Savani, 2016] Haris Aziz and Rahul Savani. Hedonic games. In Felix Brandt, Vincent Conitzer, Ulle Endriss, J erˆome Lang, and Ariel Procaccia, editors, Handbook of Computational Social Choice, chapter 15, pages 356 376. Cambridge University Press, 2016. [Aziz et al., 2013] Haris Aziz, Felix Brandt, and Hans Georg Seedig. Computing desirable partitions in additively separable hedonic games. Artiﬁcial Intelligence, 195:316 334, February 2013. [Aziz et al., 2019] Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, and Dominik Peters. Fractional hedonic games. ACM Transactions on Economics and Computation, 7(2):Article 6, June 2019. [Bell, 1938] Eric Temple Bell. The iterated exponential integers. Annals of Mathematics, pages 539 557, July 1938. [Brandt et al., 2009] Felix Brandt, Felix Fischer, Paul Harrenstein, and Yoav Shoham. Ranking games. Artiﬁcial Intelligence, 173(2):221 239, February 2009. [Brˆanzei and Larson, 2011] Simina Brˆanzei and Kate Larson. Social distance games. In Proc. IJCAI 11, pages 91 96. AAAI Press/IJCAI, July 2011. [Cechl arov a and Romero-Medina, 2001] Katar ına Cechl arov a and Antonio Romero-Medina. Stability in coalition formation games. International Journal of Game Theory, 29(4):487 494, 2001. [Cechl arov a and Hajdukov a, 2003] Katar ına Cechl arov a and Jana Hajdukov a. Computational complexity of stable partitions with B-preferences. International Journal of Game Theory, 31(3):353 364, June 2003. [Chen et al., 2011] Po-An Chen, Bart de Keijzer, David Kempe, and Guido Sch afer. The robust price of anarchy of altruistic games. In Proc. WINE 11, pages 383 390. Springer-Verlag LNCS #7090, December 2011. [Dimitrov et al., 2006] Dinko Dimitrov, Peter Borm, Ruud Hendrickx, and Shao-Chin Sung. Simple priorities and core stability in hedonic games. Social Choice and Welfare, 26(2):421 433, April 2006. [Gonzalez, 1985] Teoﬁlo Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293 306, 1985. [Hayrapetyan et al., 2006] Ara Hayrapetyan, Eva Tardos, and Tom Wexler. The effect of collusion in congestion games. In Proc. STOC 06, pages 89 98. ACM Press, May 2006. [Hoefer and Skopalik, 2009] Martin Hoefer and Alexander Skopalik. Altruism in atomic congestion games. In Proc.

ESA 09, pages 179 189. Springer-Verlag LNCS #5757, September 2009. [Kerkmann and Rothe, 2019] Anna Maria Kerkmann and J org Rothe. Stability in FEN-hedonic games for singleplayer deviations. In Proc. AAMAS 19, pages 891 899. IFAAMAS, May 2019. [Kerkmann et al., 2020] Anna Maria Kerkmann, J erˆome Lang, Anja Rey, J org Rothe, Hilmar Schadrack, and Lena Schend. Hedonic games with ordinal preferences and thresholds. Journal of Artiﬁcial Intelligence Research, 67:705 756, April 2020. [Kuniavsky and Smorodinsky, 2014] Sergey Kuniavsky and Rann Smorodinsky. Equilibrium and potential in coalitional congestion games. Theory and Decision, 76:69 79, January 2014. [Lang et al., 2015] J erˆome Lang, Anja Rey, J org Rothe, Hilmar Schadrack, and Lena Schend. Representing and solving hedonic games with ordinal preferences and thresholds. In Proc. AAMAS 15, pages 1229 1237, May 2015. [Monaco et al., 2018] Gianpiero Monaco, Luca Moscardelli, and Yllka Velaj. Hedonic games with social context. In Proc. ICTCS 18, volume 2234, pages 24 35. CEURWS.org, September 2018. [Monaco et al., 2019] Gianpiero Monaco, Luca Moscardelli, and Yllka Velaj. On the performance of stable outcomes in modiﬁed fractional hedonic games with egalitarian social welfare. In Proc. AAMAS 19, pages 873 881. IFAAMAS, May 2019. [Nguyen et al., 2016] Nhan-Tam Nguyen, Anja Rey, Lisa Rey, J org Rothe, and Lena Schend. Altruistic hedonic games. In Proc. AAMAS 16, pages 251 259. IFAAMAS, May 2016. [Rahn and Sch afer, 2013] Mona Rahn and Guido Sch afer. Bounding the inefﬁciency of altruism through social contribution games. In Proc. WINE 13, pages 391 404. Springer-Verlag LNCS #8289, December 2013. [Rota, 1964] Gian-Carlo Rota. The number of partitions of a set. The American Mathematical Monthly, 71(5):498 504, 1964. [Rothe et al., 2018] J org Rothe, Hilmar Schadrack, and Lena Schend. Borda-induced hedonic games with friends, enemies, and neutral players. Mathematical Social Sciences, 96:21 36, November 2018. [Schlueter and Goldsmith, 2018] Jacob Schlueter and Judy Goldsmith. Super altruistic hedonic games. In Proc. MPREF 18, January 2018. [Sung and Dimitrov, 2010] Shao-Chin Sung and Dinko Dimitrov. Computational complexity in additive hedonic games. European Journal of Operational Research, 203(3):635 639, June 2010. [Woeginger, 2013] Gerhard Woeginger. A hardness result for core stability in additive hedonic games. Mathematical Social Sciences, 65(2):101 104, March 2013.

Proceedings of the Twenty-Ninth International Joint Conference on Artiﬁcial Intelligence (IJCAI-20)