Stable and Envy-free Partitions in Hedonic Games

1 Introduction

Coalition formation plays a major role in our social, economic, or politic life. In examples as diverse as academic research or labor unions, individuals (agents) perform activities in groups (coalitions) rather than on their own. In coalition formation with hedonic preferences, or hedonic games, each agent's preference over the set of coalitions only concerns the coalitions that she joins. The outcome of such game is a set of disjoint coalitions of all agents (partition). A natural question is which coalitions are expected to form based on agents' preferences. The main criterion to analyze this question is stability, for which many notions have been discussed in the literature (see handbook chapter Aziz and Savani [2016]).

Introduced by Foley [1967], envy-freeness is a notion of fairness which has a broad range of applicability. This notion has received considerable attention in resource allocation [Chevaleyre et al., 2006]. Since envy-freeness can be trivially achieved (by not allocating any resources), the central issue in resource allocation is the study of envy-free outcomes that additionally satisfy efficiency or feasibility requirements. Contrary to other well-studied fairness notions, e.g. maxmin or proportionality, envy-freeness does not require to compare inter-personnal preferences, and thus, it can be meaningfully expressed in ordinal settings like hedonic games.

In hedonic games, a partition is said to be envy-free if no agent prefers another agent's coalition. Similarly to resource allocation, envy-freeness is always trivially achieved by the grand coalition and the partition of singletons. Since these two partitions are not always relevant, requiring only envyfreeness may not be restrictive enough. Hence, it makes sense to impose additional requirements, like stability or feasibility, in conjunction with envy-freeness. However, only a couple of works have done so in hedonic games, Aziz et al. [2013b] and Ueda [2018], following two different directions: The first paper considers envy-freeness in conjunction with stability and efficiency requirements. The second one restricts the set of feasible partitions and formulates justified envy-freeness, a stronger fairness notion motivated by matching theory.

Following the first direction, we investigate the conjunction of envy-freeness with stability or efficiency notions in three subclass of hedonic games where some level of stability is guaranteed: additively separable hedonic games (ASHG) which form a natural subclass, and top or bottom responsive hedonic games which encompass well-studied hedonic games with realistic interpretations, e.g., friend-enemy oriented hedonic games [Dimitrov et al., 2006] or B-hedonic games [Cechl´arov´a and Romero-Medina, 2001].

1.1 Our Contribution

First, we propose a natural weakening of justified envyfreeness and explore the implications between stability and envy-freeness notions (Figure 1). In symmetric ASHGs, we strengthen results from Aziz et al. [2013b], by proving that an individually stable and justified envy-free partition may not exist and deciding its existence is NP-complete. We also show that a Pareto optimal and justified envy-free partition may not exist. In top responsive hedonic games, we propose the Extended Top Covering Algorithm which returns a Pareto optimal, individually stable, and envy-free partition. In bottom responsive hedonic games, we show that deciding the existence of an individually stable and envy-free partition is NP-complete, but a Pareto optimal and justified envy-free partition is guaranteed. Table 1 summarizes our results.

Note that the partition of singletons is always envy-free and individually rational. Hence, our paper settles the existence of partitions satisfying any conjunction of stability and envyfreeness notions from Figure 1, in the three class at hand.

1.2 RelatedWork

In hedonic games, initiated by Banerjee et al. [2001] and Bogomolnaia and Jackson [2002], the central question is to identify the conditions on preferences that guarantee stability. An important contribution is Aziz and Brandl [2012] which clarified the inclusions between well-studied stability concepts. In fractional hedonic games, introduced by Aziz et al. [2014], Brandl et al. [2015] showed that individually stable outcomes may not exist, Bil `o et al. [2018] extensively studied Nash stability, and Monaco et al. [2018] explored Nash and core stability in a slightly modified setting. Concerning efficiency notions, Aziz et al. [2013a] proposed an algorihm computing Pareto optimal and individually rational partitions, and Elkind et al. [2016] introduced the price of Pareto optimality.

Among many complexity results, Ballester [2004] showed that deciding the existence of individually stable partitions is NP-complete, and Peters and Elkind [2015] developed a framework for proving NP-hardness of existence problems.

Envy-freeness has been extensively studied as a fairness criterion in resource allocation. In ordinal settings, Brams et al. [2003] analyzed conflicts between Pareto optimality and envy-freeness. When the preferences are incomplete, Bouveret et al. [2010] proposed possible and necessary envyfreeness. Justified envy-freeness is motivated in two-sided matching theory, particularly in the school choice setting, where Abdulkadiro˘glu and S¨onmez [2003] argued that it could lead to legal actions, and Fragiadakis et al. [2016] studied its compatibility with efficiency and strategy-proofness.

2 Preliminaries

Let N = {1, . . . , n} denote the set of agents and Ni denote the set of all subsets of N that contain agent i. A coalition X ⊆ N is a subset of agents and Xi denotes the set of all subsets of X that contain agent i. A partition π is a set of disjoint coalitions, containing all agents. Let π(i) denote the coalition to which agent i belongs in π. A hedonic game (N, P ) is defined by a set of agents N and a preference profile P = (≽i)i∈N. Each agent i has a preference, denoted ≽i, which is a weak order on the coalitions to which she belongs; let ≻i and ∼i respectively denote the strict preference and the indifference relation derived from ≽i.

Additively separable hedonic games (ASHG) form a natural class of hedonic game where each agent has a value for any other agent and the utility that an agent derives from a coalition is the sum of the values she has for its members.

Definition 1 (ASHG). A hedonic game (N,≽) is additively separable if for each agent i ∈ N there exists a utility function vi : N ↦→ R such that vi(i) = 0 and for any two coalitions S, T ∈ Ni, S ≽i T ⇔ ∑j∈S vi(j) ≥ ∑j∈T vi(j).

An ASHG is symmetric if any two agents, i, j ∈ N, associate the same value to each other, i.e., vi(j) = vj(i).

Envy-freeness is a notion of fairness in which no agent has envy toward another agent. Informally, a partition is envy-free if no agent prefers another agent's coalition over his own.

Definition 2 (Envy-freeness (EF)). In partition π, agent i has envy toward an agent j with π(i) ̸= π(j), if (π(j) \ {j}) ∪ {i} ≻i π(i). Partition π is envy-free if no agent has envy.

Justified envy-freeness is a stronger notion of fairness, formulated in hedonic games by Ueda [2018]. We propose a natural weakening of justified envy. Agent i has (weakly) justified envy toward agent j if i has envy toward j and each agent in j's coalition is (weakly) in favor of replacing j by i.

Definition 3 (Justified envy-freeness (JEF)). In partition π, i has justified envy toward j with π(i) ̸=π(j), if i has envy toward j and for all j ′ ∈π(j)\{j}, (π(j)\{j})∪{i}≻j ′ π(j). Partition π is justified envy-free if no agent has justified envy.

Definition 4 (Weakly justified envy-freeness (WJEF)). In partition π, agent i has weakly justified envy toward j with π(i)̸=π(j), if i has envy toward j and for all j ′ ∈π(j)\{j}, (π(j) \ {j}) ∪ {i} ≽j ′ π(j). Partition π is weakly justified envy-free if no agent has weakly justified envy.

The following example illustrates these fairness notions. Example 1. Consider a symmetric ASHG with four agents {1, 2, 3, 4} and values v1(2) = v2(3) = v3(1) = 2, v2(4) = v3(4) = x, and v1(4) = -7. In this game, consider partition {{1, 2, 3}, {4}}. If x = 1 then agent 4 has envy toward agent 1, but not weakly justified envy. If x = 2 then 4 has weakly justified envy toward 1, but not justified envy. Finally, if x = 3 then 4 has justified envy toward 1.

By definition, envy-freeness implies weakly justified envyfreeness, which implies justified envy-freeness. Example 1 further shows that the opposite relations do not hold.

Below, we define stability concepts and Pareto optimality. First, we say that partition π′ is reachable from partition π by a set of agents H, denoted π H -→ π′ , if for all i, j ∈ N \ H, i ̸= j : π(i) = π(j) ⇔ π′ (i) = π′ (j).

Definition 5 (Stability/Pareto optimality). For a specific concept X, we say that partition π is X if there exists no X deviation, where an X deviation is defined as follows:

• Individually rational (IR): agent i such that {i} ≻i π(i).
• Individually stable (IS): agent i and coalition X ∈ π ∪ {∅} such that X ∪ {i} ≻i π(i) and for all j ∈ X, X ∪ {i} ≽j X.
• Strong individually stable (SIS): partition π′ and set of agents H such that 1) π H -→ π′ , 2) for all i ∈ H, π′ (i) ≻i π(i), and 3) for all i ∈ H, for all j ∈ π′ (i), π′ (j) ≽j π(j).
• Nash stable (NS): agent i and coalition X ∈ π ∪ {∅} such

that X ∪ {i} ≻i π(i).

• Strong Nash stable (SNS): partition π′ and set of agents H such that 1) π H -→ π′ and 2) for all i ∈ H, π′ (i) ≻i π(i).
• Strict strong Nash stable (SSNS): partition π′ and set of agents H such that 1) π H -→ π′ , 2) for all i ∈ H, π′ (i) ≽i π(i), and 3) there exists i ∈ H such that π′ (i) ≻i π(i).
• Core stable (CS): coalition X ⊆ N such that for all i ∈ X, X ≻i π(i).
• Strict core stable (SCS): coalition X ⊆ N such that for all i ∈ X, X ≽i π(i) and there exists i ∈ X s.t. X ≻i π(i).
• Pareto optimal (PO): partition π′ such that for all i ∈ N, π′ (i) ≽i π(i) and there exists i ∈ N s.t. π′ (i) ≻i π(i).
• Perfect: coalition X⊆N s.t. for some i ∈ X,X≻i π(i).

Let us now describe the implications between envyfreeness and stability notions, summarized in Figure 1.

First, remark that the grand coalition is always envy-free but not always individually rational or Pareto optimal. Thus envy-freeness notions do not imply any of the stability concepts defined in this paper. Notice further that a perfect partition is envy-free, since no agent can improve. Moreover, an agent who has (weakly) justified envy forms a (strict) core deviation with the corresponding coalition. Thus, (strict) core stability implies (weakly) justified envy-freeness.

Finally, strict strong Nash stability does not imply envyfreeness; neither strong Nash stability nor Pareto optimality implies weakly justified envy-freeness; and Nash stability does not imply justified envy-freeness. Indeed, when x equals 1, 2, or 3 in Example 1, partition {{1, 2, 3}, {4}} is respectively strict strong Nash stable, strong Nash stable and Pareto optimal, or Nash stable. Implications between stability notions are taken from Aziz and Brandl [2012].

We assume readers' familiarity with complexity class NP. In our proofs, we use the problem EXACTCOVERBY3SETS, which is NP-complete even when each i ∈ Y appears in at most three sets s ∈ S [Garey and Johnson, 2002].

Definition 6 (EXACTCOVERBY3SETS (X3C)). Consider a set Y = {1, . . . , 3n} and a collection S = {s1, . . . , sm} of subsets of Y such that for all s ∈ S, |s| = 3. Does there exist a subset S′ ⊆ S such that S′ is a partition of Y ?

3 Justified Envy in Symmetric ASHGs

In symmetric ASHGs, it is known that Nash (and thus individually) stable partitions always exist [Bogomolnaia and Jackson, 2002]. However, Aziz et al. [2013b] show that an individually stable and envy-free partition may not exist, and that deciding the existence of such partition is NP-complete. We strengthen both results with Proposition 1 and Theorem 1, showing that they even hold for justified envy-freeness.

Proposition 1. In symmetric ASHGs, an individually stable and justified envy-free partition may not exist.

The proof is based on the following counterexample. Example 2. Consider the symmetric ASHG, illustrated by Figure 2, with six agents {1, . . . , 6} and values v1(2) = 7, v2(3) = 6, v2(4) = 4, v3(4) = 1, v3(5) = 5, v4(5) = v4(6) = 3, and v5(6) = 1. All other values are equal to -9.

Proof. Assume that there exists an individually stable and justified envy-free partition π in Example 2. First, if π contains a coalition where two agents have value -9 for each other, then π is not individually rational for at least one of these agents. Therefore, we limit the following study to coalitions containing no negative values, i.e., cliques in Figure 2.

Assume that coalition {1, 2} belongs to π. If agent 3 is in coalition {3} or coalition {3, 4}, then agent 5 individually deviates toward 3's coalition. Hence coalition {3, 4, 5} belongs to π, but then agent 2 has justified envy toward 5.

Thus, coalition {1, 2} does not belong to π, which implies that agent 1 is in a singleton coalition. If 2 is in coalition {2}, {2, 3}, or {2, 4}, then 2 individually deviates toward {1}. Hence, coalition {2, 3, 4} belongs to π. Now, if agent 5 is in a singleton coalition then 5 deviates toward {6}, and thus {5, 6} belongs to π. It leads to π = {{1}, {2, 3, 4}, {5, 6}}, but then 4 individually deviates toward {5, 6}.

Note that Proposition 1 directly implies that the existence of an {IS, NS} and {JEF, WJEF} partition is not guaranteed. Moreover, Example 2 is minimal in the sense that an individually stable and justified envy-free partition always exists for five agents or less (we omit the case study proof). An interesting question is then the complexity of deciding whether an individually stable and jusified envy-free partition exists.

Theorem 1. Given an ASHG, deciding whether an individually stable and justified envy-free partition exists is NPcomplete, even with symmetric preferences.

Proof. First, the problem is in NP since checking these properties is polynomial. Similarly to Aziz et al. [2013b], we show NP-hardness by reduction from X3C (see Definition 6).

y6

1

Consider (Y, S) an instance of X3C. From (Y, S), we construct a symmetric ASHG as follows, illustrated by Figure 3:

• For each i ∈ Y , we create six agents (yij )j=1,...,6 that form an instance of Example 2.
• For each set s = {i, j, k} ∈ S, we create agent s such that vs(yi1 ) = vs(yj1 ) = vs(yk 1 ) = 5, and we also set vyi1 (yj1 ) = vyj1 (yk 1 ) = vyk 1 (yi1 ) = 1.
• All other values are equal to -11.

Before the main argument, notice that if an agent yi1 is isolated from agents (yij )j=2,...,6, then the (partial) partition {{yi2 , yi3 }, {yi4 , yi5 , yi6 }} is the only individually stable and justified envy-free partition for agents (yij )j=2,...,6.

• (⇒) Assume that there exists a partition S′ ⊆ S of Y . Consider partition π = {{s, yi1 , yj1 , yk 1 } | s = {i, j, k} ∈ S′ }∪{{yi2 , yi3 }, {yi4 , yi5 , yi6 }} | i ∈ Y }∪{{s} | s ∈ S \S′ }. We argue that π is individually stable and justified envy-free. First, for each i ∈ Y , agent yi1 has value 7 in π. Thus, no agent yi1 has incentive to individually deviate toward another coalition or has envy toward agent yi3 . Hence, each yi1 is isolated from agents (yij )j=2,...,6, and, as argued above, each {{yi2 , yi3 }, {yi4 , yi5 , yi6 }} is individually stable and justified envy-free. Lastly, since for all s ∈ S and i ∈ Y \ s, vs(yi1 )=-11, no agent s∈S \S′ has envy toward any s∈S′ .
• (⇐) Assume that there exists an individually stable and justified envy-free partition π. As shown in Example 2, if an agent yi1 is in coalition {yi1 } or {yi1 , yi2 }, then π is not individually stable and justified envy-free. Hence each agent yi1 is in coalition with agents from S ∪ {yj1 | j ∈ Y }, and thus, each coalition {{yi2 , yi3 }, {yi4 , yi5 , yi6 }} belongs to π.

Now, assume that for some i ∈ Y , S ∩ π(yi1 ) = ∅. Since each i ∈Y appears in at most three sets s ∈S, agent yi1 has value at most 6 in π(yi1 ), but then yi1 has justified envy toward yi3 . Hence for all i ∈ Y , S ∩ π(yi1 ) ̸= ∅. The only individually rational coalitions to which agent yi1 belongs are {s, yi1 }, {s, yi1 , yj1 }, and {s, yi1 , yj1 , yk 1 }, for some s = {i, j, k} ∈ S. However, if yi1 is in coalition {s, yi1 } or {s, yi1 , yj1 }, then yi1 has value at most 6 and justified envy toward agent yi3 . Therefore, each yi1 belongs to a coalition {s, yi1 , yj1 , yk 1 } for some s = {i, j, k} ∈ S, which form a partition of Y .

In addition, the reduction holds as it is for any conjunction of {IS, NS} and {JEF, WJEF}.

Finally, Pareto optimal partitions always exist by definition. However, we show that Pareto optimal and justified envy-free partitions may not exist in symmetric ASHGs.

Proposition 2. In symmetric ASHGs, a Pareto optimal and justified envy-free partition may not exist.

We omit the argument of the proof based on Example 3. Example 3. Consider the symmetric ASHG with nine agents {1, . . . , 9} and values v1(2) = 8, v2(3) = 7, v2(4) = 4, v3(4) = 2, v3(5) = 6, v4(5) = 3, v4(6) = 4, v5(6) = 2, v5(7) = v6(7) = 1, and v3(8) = v5(8) = 1. All other values are equal to -10.

4 Top Responsiveness and Envy-freeness

Top responsiveness is a condition on agent's preference, introduced in Alcalde and Revilla [2004]. Intuitively, it requires that an agent's preference over two coalitions is responsive to her best subsets (choice set) in each coalition. Given agent i∈N and coalition X ∈Ni, let Ch(i, X) denote the choice set of i in X, i.e., Ch(i,X) = {Y ∈Xi : ∀ Y ′ ∈ Xi, Y ≽i Y ′ }.

A hedonic game (N,≽) satisfies top responsiveness if for all i ∈ N, the three following conditions are satisfied:

1. for all X ∈ Ni, |Ch(i,X)| = 1, and let ch(i, X) denote the unique element of Ch(i, X),

Further, a top responsive hedonic game is mutual if for all i, j ∈ N and X ∈ Xi ∩ Xj , j ∈ ch(i, X) ⇔ i ∈ ch(j, X).

Dimitrov and Sung [2007] prove that top responsiveness guarantees the existence of the strict core, relying on the Top Covering Algorithm, which outputs a strict core stable partition. Hence, we ask whether top responsiveness guarantees the existence of a (strict) core stable and envy-free partition.

Proposition 3. Top responsiveness does not guarantee the existence of a core stable and envy-free partition.

Example 4. Consider four agents {1, 2, 3, 4} and the following preferences, which can be extended to be top responsive:

• 4 : {3, 4} ≻4 {1, 3, 4} ∼4 {2, 3, 4} ≻4 . . .

Proof. In this example, the only core stable partition is {{1}, {2, 3}, {4}}, however, agent 4 has envy toward 2.

Proposition 3 directly holds for the conjunction of envyfreeness and {SIS, SCS}. Besides, top responsiveness does not guarantee Nash stable partitions [Dimitrov and Sung, 2006]. The remaining questions concern the conjunction of envy-freeness with individual stability or Pareto optimality.

Theorem 2. In top responsive hedonic games, a Pareto optimal, individually stable, and envy-free partition always exists, and can be computed in polynomial time.

Algorithm 1 Extended Top Covering Algorithm

Input: Top responsive hedonic game (N, ≽) Output: π, a partition of N 1: R1 := N, π := ∅ 2: for k = 1 to |N| do 3: Select agent i ∈ Rk such that for all j ∈ Rk |CC (i, Rk )| ≤ |CC (j, Rk )| 4: πk := CC(i,Rk ) 5: if |CC(i,Rk )| ≥ 2 then 6: while ∃ j ∈ Rk \ πk : ch(j,Rk ) ∩ πk ̸= ∅ do 7: πk := πk ∪CC(j,Rk ) 8: end while 9: end if 10: π := π ∪ {πk }, Rk+1 := Rk \πk 11: if Rk+1 = ∅ then 12: return π 13: end if 14: end for 15: return π

Proposition 3 implies that the Top Covering Algorithm does not return an envy-free partition. We propose the Extended Top Covering Algorithm, which returns a Pareto optimal, individually stable, and envy-free partition, when applied to a top responsive hedonic game. To define it, we introduce additional notations taken from Aziz and Brandl [2012].

For a coalition X ⊆ N, let ∽X denote the binary relation on X×X such that i ∽X j if and only if j ∈ ch(i,X). We define the connected component of i with respect to the binary relation ∽X, denoted CC(i,X), as the set:

Informally, CC(i,X) represents the set of agents in X that are "reachable" from i by an iterative use of ch(·, X). We remark that for all i ∈ N and X ∈ Ni, the following inclusions hold: ch(i, X) ⊆ CC (i, X) ⊆ X.

The Extended Top Covering Algorithm is formally defined as Algorithm 1. Let us describe its application on Example 4:

• Step 1 R1 = {1, 2, 3, 4}: CC(1, R1 ) = {1}, CC(2, R1 ) = CC(3, R1 ) = {1, 2, 3}, and CC(4, R1 ) = {1, 2, 3, 4}. Agent 1 is selected and π1 = CC(1, R1 ).

Step 2 R2 = {2, 3, 4}: CC(2, R2 ) = CC(3, R2 ) = {2, 3}, and CC(4,R2 ) = {2, 3, 4}. Agent 2 is selected and π2 = CC (2, R2 ) ∪ CC (4, R2 ) = {2, 3, 4}. Then, R3 = ∅ and the outcome is π = {{1}, {2, 3, 4}}.

Let us state directly that Algorithm 1 runs in polynomial time, returns a partition of N, and at any step k, for all i ∈ πk : (i) ch(i,Rk ) ⊆ πk , and (ii) for all step k′ such that k′ < k and |πk′ | ≥ 2, ch(i, Rk′ )∩πk′ = ∅. To prove Theorem 2, we use the three following lemmas for which we omit the proofs.

Lemma 1. Consider the kth step of Algorithm 1, then for all i ∈ πk , πk ≽i {i}.

Lemma 2. Consider the kth step of Algorithm 1. Let X ⊆ Rk such that πk ⊊ X, then for all i ∈ πk , πk ≻i X.

Lemma 3. Consider the kth step of Algorithm 1. Let X ⊆ Rk such that πk ̸= X and πk ∩X = {i}, then πk ≻i X.

Proof of Theorem 2. Consider a top responsive hedonic game (N, ≽) and let π denote the outcome of Algorithm 1.

• [IS] Toward a contradiction, assume first that agent i ∈ πk individually deviates toward πk′ , i.e., πk′ ∪ {i} ≻i πk and for all j ∈ πk′ , πk′ ∪ {i} ≽j πk′ . Remark first that Lemma 1 implies that πk ≽i {i}, and thus πk′ ̸= ∅.
• If k < k′ , then πk′ ⊆ Rk and πk ∩ (πk′ ∪ {i}) = {i}. By Lemma 3 [for πk ← πk , X ← πk′ ∪ {i}], we get that πk ≻i πk′ ∪ {i}, which is a contradiction.
• If k′ < k, then πk′ ⊊ πk′ ∪ {i} ⊆ Rk′ . By Lemma 2 [for πk ← πk′ , X ← πk′ ∪ {i}], we get that for all j ∈ πk′ , πk′ ≻j πk′ ∪ {i}, which is a contradiction.
• [PO] Assume now that π is not Pareto optimal, i.e., there exists partition π′ such that for all i ∈ N, π′ (i) ≽i π(i) and there exists i ∈ N such that π′ (i) ≻i π(i). Consider the set A = {i ∈ N | π(i) ̸= π′ (i)}, i.e., the set of agents who are in different coalitions in π and π′ . Let k denote the first step of Algorithm 1 such that πk ∩A ̸= ∅, and consider agent i ∈ πk . · If πk ⊆ π′ (i), then by Lemma 2 [for πk ← πk , X ←
• π′ (i)], we get that πk ≻i π′ (i), which is a contradiction.
• If πk ⊈ π′ (i), then there exists j ∈ πk (maybe j = i) such that ch(j,Rk ) ⊈ π′ (j). In addition, by definition of step k, π′ (j) ⊆ Rk , and thus ch(j,Rk ) ≻j ch(j, π′ (j)). Furthermore, since ch(j,Rk ) ⊆ πk , ch(j, πk ) = ch(j,Rk ). Hence, ch(j, πk ) ≻j ch(j, π′ (j)), and top responsiveness implies πk ≻j π′ (j), which is a contradiction.
• [EF] Finally, assume that agent i ∈ πk has envy toward agent j ∈ πk′ , i.e., (πk′ \ {j}) ∪ {i} ≻i πk . First, Lemma 1 implies πk ≽i {i}, and thus (πk′ \ {j}) ̸= ∅.
• If k < k′ , then (πk′ \ {j}) ⊆ Rk and πk ∩ ((πk′ \ {j}) ∪ {i}) = {i}. By Lemma 3 [for πk ← πk , X ← (πk′ \ {j}) ∪
• {i}], we get that πk ≻i (πk′ \ {j}) ∪ {i}, a contradiction.
• If k′ < k, we start by showing that for all step k′′ such that k′ ≤ k′′ , |πk′′ | ≥ 2. First, since πk′ \ {j} ̸= ∅, |πk′ | ≥ 2. By contradiction, consider the first step k∗ such that k′ < k∗ and |πk∗ | = 1, and denote by l the agent such that πk∗ = {l}. For all k′′ such that k′ ≤ k′′ < k∗ , |πk′′ | ≥ 2, and thus ch(l,Rk′′ ) ∩ πk′′ = ∅. Hence, ch(l,Rk′′ ) = ch(l,Rk′′ \ πk′′ ) holds. In total, we obtain ch(l,Rk′ )=ch(l,Rk′ \ ⋃k′≤k′′<k∗ πk′′ )=ch(l,Rk∗ )={l}. Hence, CC (l, Rk′ ) = {l}, which contradicts |πk′ | ≥ 2.

Therefore, for all k′′ such that k′ ≤ k′′ < k, |πk′′ | ≥ 2, and then ch(i,Rk′′ ) ∩ πk′′ = ∅. It implies that ch(i,Rk′′ ) = ch(i,Rk′′ \ πk′′ ), and in total we obtain ch(i, Rk′ ) = ch(i, Rk′ \⋃k′≤k′′<k πk′′ ) = ch(i, Rk ). Moreover, ch(i,Rk ) ⊆ πk , and then ch(i, πk ) = ch(i,Rk ). Thus ch(i, πk ) = ch(i,Rk′ ). Also, since ch(i,Rk′ ) ∩ πk′ = ∅, ch(i,Rk′ ) ∩ (πk′ \ {j}) = ∅ also holds. By definition of ch(i,Rk′ ), it implies ch(i,Rk′ ) ≻i ch(i, (πk′ \ {j}) ∪ {i}). Hence we obtain ch(i, πk ) ≻i ch(i, (πk′ \ {j}) ∪ {i}), and then top responsiveness implies πk ≻i (πk′ \ {j}) ∪ {i}, which is a contradiction.

Finally, when a top responsive hedonic game satisfies mutuality, Aziz and Brandl [2012] show that the outcome of the Top Covering Algorithm is strict strong Nash stable. We further show that its outcome is envy-free.

Theorem 3. Top responsiveness and mutuality guarantee the existence of strict strong Nash stable and envy-free partitions.

Proof. Consider a top responsive and mutual hedonic game (N, ≽) and let π be the outcome of the Top Cover Algorithm. By Theorem 3 and Lemma 1 in Aziz and Brandl [2012] respectively, π is strict strong Nash stable, and for all i ∈ N, ch(i, N) ⊆ π(i). Toward a contradiction, assume that agent i has envy toward agent j in π, i.e., (π(j)\{j})∪{i} ≻i π(i).

First assume π(i) = {i}. It implies (π(j) \ {j}) ̸= ∅, and then {i} ⊊ (π(j) \ {j}) ∪ {i}. Since ch(i,N) ⊆ π(i), it holds that ch(i,N) = {i}. Hence, by definition of ch(i,N), {i} = ch(i, {i}) = ch(i, (π(j) \ {j}) ∪ {i}). With {i} ⊊ (π(j) \ {j}) ∪ {i}, top responsiveness implies {i} = π(i) ≻i (π(j) \ {j}) ∪ {i}, which is contradiction.

Thus π(i) ̸= {i}. Since π is individually rational, it implies ch(i,N) ̸= {i}, and thus ch(i,N) ⊈ (π(j) \ {j}) ∪ {i}. By definition of ch(i,N), for all S ∈ Ni and S ̸= ch(i,N), ch(i,N) ≻i S. Hence, for all S ⊆ (π(j) \ {j}) ∪ {i}, ch(i,N) ≻i S, and thus ch(i,N) ≻i ch(i, (π(j) \ {j}) ∪ {i}). Moreover, since ch(i, N) ⊆ π(i), we obtain ch(i, π(i)) = ch(i,N), and thus ch(i, π(i)) ≻i ch(i, (π(j) \ {j}) ∪ {i}). Hence, top responsiveness implies π(i) ≻i (π(j) \ {j}) ∪ {i}, which is a contradiction.

5 BottomResponsiveness and Envy-freeness

In opposition to top responsiveness, bottom responsiveness [Suzuki and Sung, 2010] is based on the notion of avoid set. Given agent i ∈ N and coalition X ∈ Ni, the avoid set of i in X is Av(i,X) = {Y ∈ Xi : ∀ Y ′ ∈ Xi, Y ′ ≽i Y }. In other words, Av(i,X) denotes the worst subsets in X for agent i. A hedonic game (N, ≽) satisfies bottom responsiveness if for

all i ∈ N, the two following conditions are satisfied:

1. for all X, Y ∈ Ni, [for all X′ ∈ Av(i,X) and Y ′ ∈ Av(i, Y ),X′ ≻i Y ′ ] ⇒X ≻i Y ,

A bottom responsive hedonic game is strongly bottom responsive if for all i ∈ N and X ∈ Xi, |Av(i,X)| = 1, and it satisfies mutuality if for all i, j ∈ N and X ∈ Xi ∩ Xj, j ∈ Av(i, X) ⇔ i ∈ Av(j, X).

Aziz and Brandl [2012] show that bottom responsiveness guarantees a strong individually stable partition, and that strong bottom responsiveness together with mutuality guarantee a strong Nash stable partition. Yet, we show that even the latter one does not guarantee the existence of a weakly justified envy-free and individually or core stable partition.

Proposition 4. In a strong bottom responsive hedonic game, a weakly justified envy-free and individually or core stable partition may not exist, even with mutual preferences.

Example 5. Consider three agents {1, 2, 3} with preferences:

Proof. In Example 5, partitions {{1, 2, 3}} and {{1, 3}, {2}} are not individually rational for agents 1 and 3. Also, partition {{1}, {2}, {3}} is not core or individually stable, since {1, 2} is a deviation. For partitions {{1, 2}, {3}} and {{1}, {2, 3}}, agent 3 has weakly justified envy toward agent 1 in the former, and 1 has weakly justified envy toward 3 in the latter. Preferences are strong bottom responsive and mutual.

Proposition 4 directly holds for the conjunction of {WJEF, EF} and {NS, SIS, SNS}. An interesting question is then the complexity of deciding the existence of such partitions.

Theorem 4. Given a strong bottom responsive hedonic game, deciding whether an individually stable and envy-free partition exists is NP-complete, even with mutual preferences.

Proof sketch. We showNP-hardness by reduction fromX3C. Consider (Y, S) an instance of X3C with Y = {1, . . . , 3n} and S = {s1, . . . , sm}. We construct a symmetric and strong bottom responsive ASHG, as follows:

• For each i ∈ Y , we create two agents {yi1 , yi2 } and a "clique" of seven agents Ki7 where for all l, l′ ∈ Ki7 , vl(l′ ) = 1. We set for all l ∈ Ki7 , vl(yi1 ) = vl(yi2 ) = 1.
• For each set s = {i, j, k} ∈ S, we create a "clique" of five agents Ks 5 where for all l, l′ ∈ Ks 5 , vl(l′ ) = 1. We set for all l ∈ Ks 5 , vl(yi1 ) = vl(yj1 ) = vl(yk 1 ) = 1, and also vyi1 (yj1 ) = vyj1 (yk 1 ) = vyk 1 (yi1 ) = 1.
• All other values are equal to -|N| = -(3n · 9 +m · 5).

The constructed ASHG is both strong bottom responsive and mutual (indeed, it is a symmetric enemy aversion hedonic game [Dimitrov et al., 2006]). Notice that, in individually stable partitions, agents in each "clique" (Ki7 )i∈Y and (Ks 5 )s∈S are in the same coalition. The main argument is then similar to the proof of Theorem 1 and we omit it.

The reduction also holds for the conjunction of {IS, NS} and {WJEF, EF}. A direct corollary is that deciding the existence of an individually stable and envy-free partition is NPcomplete in symmetric ASHGs with only two different values, and thus it strengthens Theorem 13 in Aziz et al. [2013b],

Finally, we state two results on envy-freeness and Pareto optimality under bottom responsiveness, omitting the proofs.

Proposition 5. In a strong bottom responsive hedonic game, a Pareto optimal and weakly justified envy-free partition may not exist, even with mutual preferences.

Theorem 5. In a bottom responsive hedonic game, a Pareto optimal and justified envy-free partition always exists.

6 Conclusion

We settled the existence of partitions satisfying the conjunction of stability and envy-freeness requirements in three important class of hedonic games. Our main positive result, the Extended Top Cover Algorithm, may not adapt well to weaker notion of top responsiveness. In ASHGs and bottom responsive hedonic games, we show that deciding the existence of an individually stable and envy-free partition is NP-complete. Future works include the study of complexity issues related to core stability and Pareto optimality, leading probably to NP NP difficult problems.