# stable_and_envyfree_partitions_in_hedonic_games__85099672.pdf

Stable and Envy-free Partitions in Hedonic Games

Nathana el Barrot1,2 and Makoto Yokoo2,1

1Riken, AIP Center 2Kyushu University nathanaelbarrot@gmail.com, yokoo@inf.kyushu-u.ac.jp

In this paper, we study coalition formation in hedonic games through the fairness criterion of envyfreeness. Since the grand coalition is always envyfree, we focus on the conjunction of envy-freeness with stability notions. We first show that, in symmetric and additively separable hedonic games, an individually stable and justified envy-free partition may not exist and deciding its existence is NPcomplete. Then, we prove that the top responsiveness property guarantees the existence of a Pareto optimal, individually stable, and envy-free partition, but it is not sufficient for the conjunction of core stability and envy-freeness. Finally, under bottom responsiveness, 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 always exists.

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.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

General Symmetric/Mutual

ASHG IS+JEV: NP-c (Prop.1, Th.1) PO+JEV: (Prop.2)

TR PO+IS+EF: P (Th.2) SSNS+EF: (Th.3) CS+EF: (Prop.3)

BR PO+JEF: (Th.5)

SBR IS+EF: NP-c (Prop.4, Th.4) CS/PO+WJEF: (Prop.4/5)

Table 1: Summary of the results. TR, BR, and SBR refer to top, bottom, and strong bottom responsiveness. and means that the desired partition always exists and may not exist. P and NP-c stand for polynomial computation and NP-complete existence problem.

1.2 Related Work

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 7 R such that vi(i) = 0 and for any two coalitions S, T Ni, S i T P j S vi(j) P 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

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

Figure 1: Implications between stability and envy-freeness notions.

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 ?

Figure 2: A symmetric ASHG with no IS and JEF partition.

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

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

Figure 3: Symmetric ASHG obtained by reduction of an X3C instance with s1 = {1, 2, 3}, s2 = {2, 3, 4}, ..., with focus on s1.

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 (yi j)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(yi 1) = vs(yj 1) = vs(yk 1) = 5, and we also set vyi 1(yj 1) = vyj 1(yk 1) = vyk 1 (yi 1) = 1. All other values are equal to 11. Before the main argument, notice that if an agent yi 1 is isolated from agents (yi j)j=2,...,6, then the (partial) partition {{yi 2, yi 3}, {yi 4, yi 5, yi 6}} is the only individually stable and justified envy-free partition for agents (yi j)j=2,...,6. ( ) Assume that there exists a partition S S of Y . Consider partition π = {{s, yi 1, yj 1, yk 1} | s = {i, j, k} S } {{yi 2, yi 3}, {yi 4, yi 5, yi 6}} | i Y } {{s} | s S \ S }. We argue that π is individually stable and justified envy-free. First, for each i Y , agent yi 1 has value 7 in π. Thus, no agent yi 1 has incentive to individually deviate toward another coalition or has envy toward agent yi 3. Hence, each yi 1 is isolated from agents (yi j)j=2,...,6, and, as argued above, each {{yi 2, yi 3}, {yi 4, yi 5, yi 6}} is individually stable and justified envy-free. Lastly, since for all s S and i Y \ s, vs(yi 1)= 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 yi 1 is in coalition {yi 1} or {yi 1, yi 2}, then π is not individually stable and justified envy-free. Hence each agent yi 1 is in coalition with agents from S {yj 1 | j Y }, and thus, each coalition {{yi 2, yi 3}, {yi 4, yi 5, yi 6}} belongs to π. Now, assume that for some i Y , S π(yi 1) = . Since each i Y appears in at most three sets s S, agent yi 1 has value at most 6 in π(yi 1), but then yi 1 has justified envy toward yi 3. Hence for all i Y , S π(yi 1) = . The only individually rational coalitions to which agent yi 1 belongs are {s, yi 1}, {s, yi 1, yj 1}, and {s, yi 1, yj 1, yk 1}, for some s = {i, j, k} S. However, if yi 1 is in coalition {s, yi 1} or {s, yi 1, yj 1}, then yi 1 has value at most 6 and justified envy toward agent yi 3. Therefore, each yi 1 belongs to a coalition {s, yi 1, yj 1, 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),

(2) for all X, Y Ni, ch(i, X) i ch(i, Y ) X i Y ,

(3) for all X, Y Ni, [ch(i, X) = ch(i, Y ) and X Y ] X i Y .

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:

1 : {1} 1 . . . 2 : {1, 2, 3} 2 {1, 2, 3, 4} 2 {1, 2} 2 {2, 3} 2 . . . 3 : {2, 3} 3 {1, 2, 3} 3 {2, 3, 4} 3 . . . 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.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

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:

{k X | j1, . . . , jl X | i X j1 X . . . X jl X k}.

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 \ S 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 \S

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.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

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 Bottom Responsiveness 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 , (2) for all X, Y Ni, [Av(i, X) Av(i, Y ) = and |X| |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: 1 : {1, 2} 1 {1} 1 {1, 2, 3} 1 {1, 3} 2 : {1, 2, 3} 2 {1, 2} 2 {2, 3} 2 {2} 3 : {2, 3} 3 {3} 3 {1, 2, 3} 3 {1, 3}

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 show NP-hardness by reduction from X3C. 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 {yi 1, yi 2} and a clique of seven agents Ki 7 where for all l, l Ki 7, vl(l ) = 1. We set for all l Ki 7, vl(yi 1) = vl(yi 2) = 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(yi 1) = vl(yj 1) = vl(yk 1) = 1, and also vyi 1(yj 1) = vyj 1(yk 1) = vyk 1 (yi 1) = 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 (Ki 7)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 NPNP difficult problems.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)

References [Abdulkadiro glu and S onmez, 2003] Atila Abdulkadiro glu and Tayfun S onmez. School choice: A mechanism design approach. American economic review, 93(3):729 747, 2003. [Alcalde and Revilla, 2004] Jos e Alcalde and Pablo Revilla. Researching with whom? stability and manipulation. Journal of Mathematical Economics, 40(8):869 887, 2004. [Aziz and Brandl, 2012] Haris Aziz and Florian Brandl. Existence of stability in hedonic coalition formation games. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS2012), pages 763 770, 2012. [Aziz and Savani, 2016] Haris Aziz and Rahul Savani. Handbook of Computational Social Choice, chapter Hedonic Games. Cambridge University Press, 2016. [Aziz et al., 2013a] Haris Aziz, Felix Brandt, and Paul Harrenstein. Pareto optimality in coalition formation. Games and Economic Behavior, 82:562 581, 2013. [Aziz et al., 2013b] Haris Aziz, Felix Brandt, and Hans Georg Seedig. Computing desirable partitions in additively separable hedonic games. Artificial Intelligence, 195:316 334, 2013. [Aziz et al., 2014] Haris Aziz, Felix Brandt, and Paul Harrenstein. Fractional hedonic games. In Proceedings of the 13th International Conference on Autonomous Agents and Multi-agent Systems (AAMAS-2014), pages 5 12, 2014. [Ballester, 2004] Coralio Ballester. NP-completeness in hedonic games. Games and Economic Behavior, 49(1):1 30, 2004. [Banerjee et al., 2001] Suryapratim Banerjee, Hideo Konishi, and Tayfun S onmez. Core in a simple coalition formation game. Social Choice and Welfare, 18(1):135 153, 2001. [Bil o et al., 2018] Vittorio Bil o, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, and Luca Moscardelli. Nash stable outcomes in fractional hedonic games: Existence, efficiency and computation. Journal of Artificial Intelligence Research, 62:315 371, 2018. [Bogomolnaia and Jackson, 2002] Anna Bogomolnaia and Matthew O Jackson. The stability of hedonic coalition structures. Games and Economic Behavior, 38(2):201 230, 2002. [Bouveret et al., 2010] Sylvain Bouveret, Ulle Endriss, J erˆome Lang, et al. Fair division under ordinal preferences: Computing envy-free allocations of indivisible goods. In ECAI, pages 387 392, 2010. [Brams and King, 2005] Steven J Brams and Daniel L King. Efficient fair division: Help the worst off or avoid envy? Rationality and Society, 17(4):387 421, 2005. [Brams et al., 2003] Steven J Brams, Paul H Edelman, and Peter C Fishburn. Fair division of indivisible items. Theory and Decision, 55(2):147 180, 2003.

[Brandl et al., 2015] Florian Brandl, Felix Brandt, and Martin Strobel. Fractional hedonic games: Individual and group stability. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2015), pages 1219 1227, 2015. [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. [Chevaleyre et al., 2006] Yann Chevaleyre, Paul E Dunne, Ulle Endriss, J erˆome Lang, Michel Lemaitre, Nicolas Maudet, Julian Padget, Steve Phelps, Juan A Rodriguez Aguilar, and Paulo Sousa. Issues in multiagent resource allocation. Informatica, 30(1), 2006. [Dimitrov and Sung, 2006] Dinko Dimitrov and Shao Chin Sung. Top responsiveness and nash stability in coalition formation games. Kybernetika, 42(4):453 460, 2006. [Dimitrov and Sung, 2007] Dinko Dimitrov and Shao Chin Sung. On top responsiveness and strict core stability. Journal of Mathematical Economics, 43(2):130 134, 2007. [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, 2006. [Elkind et al., 2016] Edith Elkind, Angelo Fanelli, and Michele Flammini. Price of pareto optimality in hedonic games. In Thirtieth AAAI Conference on Artificial Intelligence, 2016. [Foley, 1967] Duncan K Foley. Resource allocation and the public sector. 1967. [Fragiadakis et al., 2016] Daniel Fragiadakis, Atsushi Iwasaki, Peter Troyan, Suguru Ueda, and Makoto Yokoo. Strategyproof matching with minimum quotas. ACM Transactions on Economics and Computation, 4(1):6, 2016. [Garey and Johnson, 2002] Michael R Garey and David S Johnson. Computers and intractability, volume 29. wh freeman New York, 2002. [Monaco et al., 2018] Gianpiero Monaco, Luca Moscardelli, and Yllka Velaj. Stable outcomes in modified fractional hedonic games. ar Xiv preprint ar Xiv:1804.05040, 2018. [Peters and Elkind, 2015] Dominik Peters and Edith Elkind. Simple causes of complexity in hedonic games. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI-2015), pages 617 623, 2015. [Suzuki and Sung, 2010] Koji Suzuki and Shao-Chin Sung. Hedonic coalition formation in conservative societies. Available at SSRN 1700921, 2010. [Ueda, 2018] Suguru Ueda. Envy based fairness in hedonic games. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pages 1852 1853. ACM, 2018.

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19)