Altruism in Coalition Formation Games

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, 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 social 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] defined 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 modified 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 verification and existence problems in terms of their computational complexity.

2 The Model

Coalition FormationGames. 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 profile 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 defined 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 ⪰Fi 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 sumFi (Γ) = ∑f∈Fi vf(Γ).

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

• Selfish 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 selfish-first preferences by uSF i (Γ), under equal treatment by uEQ i (Γ), and under altruistic treatment by uAL i (Γ). They are defined as

For any coalition structures Γ,∆ ∈ CN, agent i's selfish-first preference is then defined by Γ ⪰SF i ∆ ⇐⇒ uSF i (Γ) ≥ uSF i (∆). Her equal- and altruistic-treatment preferences (⪰EQ i ; ⪰AL i ) are defined analogously, using uEQ i and uAL i . The factor M, which is used for the selfish-first model and for altruistic treatment, ensures that an agent's utility is first determined by the agent's own valuation in the selfish-first 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 , sumFi (Γ) > sumFi (∆) 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 five 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 selfish-first 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 51 = 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 altruism, fulfill 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 equal- and 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 definitions 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 prefersmoving 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

1 Note that they define a restricted version of friend-oriented unanimity that only considers the agents' own coalitions.

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

• 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 influenced by coalitions they are not part of.

4 HowHard are Verification and Existence?

We now study the associated verification and existence problems and conduct a computational analysis for them. Given a stability concept α, these problems are defined 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 satisfies α?

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 verified 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

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)), verification 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. Specifically, 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.

Verification 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 selfish-first 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 selfish-first 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 uEQ i (Γ) < uEQ i (ΓC→∅), which implies Γ ≺EQ i ΓC→∅, and that sumFi (Γ) < sumFi (ΓC→∅), which implies Γ ≺AL i ΓC→∅. Hence, C blocks Γ for equal and altruistic treatment.

Theorem 5 (Strict) core stability verification can be done in coNP for all three degrees of altruism. For the selfish-first model, core stability verification is even coNP-complete.

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

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 game 2 and that we tested this example using brute force.

We now show that under the selfish-first 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 selfish-first model, strict popularity verification is coNP-complete, strict popularity existence is coNP-hard, and popularity verification is coNP-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 verification is in coNP.

To show coNP-hardness of strict popularity verification, 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 verification. 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.

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

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 ′ 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.

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 verification can be shown by slightly changing the above reduction. The details are omitted here. q

Perfectness. Turning now to perfectness, we start with the selfish-first model.

Theorem 8 Let G be a network of friends on a set of agents N. A coalition structure Γ ∈ CN is perfect under the selfish-first 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. q

Since it is easy to check this characterization, perfect coalition structures can be verified in polynomial time for the selfish-first model. It follows directly from Theorem 8 that the corresponding existence problem is also in P:

1

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 selfish-first model if and only if all connected components of G are cliques.

Proposition 10 Perfectness verification can be done in coNP for all three degrees of altruism. For equal treatment, perfectness existence is in coNP.

We again omit the proof of Proposition 10. We only mention that membership of perfectness existence in coNP 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 uEQ 1 (∆) = 113 > 112 = uEQ 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 verification 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 coNP upper bounds are also coNP-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."