Robustness against Agent Failure in Hedonic Games

1 Introduction

Coalition formation is everywhere in human activities. Companies group their employers into project teams. Countries form coalitions to promote international trade among them. Individuals interact with each other and form groups in order to achieve objectives they cannot seek for on their own.

Hedonic coalition formation games (for short, hedonic games), introduced by Bogomolnaia and Jackson [2002] and Banerjee et al. [2001], provide an elegant framework to formulate coalition formation. In these games, each player has a preference over the coalitions to which she belongs, and desirable outcomes often correspond to stable partitions. The basic intuition behind stable partitioning is that group structures need to be robust under certain changes within the system; that is, outcomes must be immune to players' coalitional or individual deviations to other coalitions.

In many real-world scenarios, however, groups may encounter unexpected changes and challenges, imposed from the outside of the system. For instance, a certain country can go bankrupt and be enforced to leave a political alliance. In this respect, a group structure that satisfies a standard stability requirement can become immediately unstable due to unexpected circumstances. A case in point is a political coalition of three countries with one intermediate country connecting two other countries who are enemies to each other: if the intermediate player happens to disappear from the coalition, one cannot maintain the stability of the whole system.

In this paper, we propose a novel criterion that redefines stability from robustness aspect. We define an outcome to be robust with respect to a certain stability requirement � if removing any set of at most k players still preserves �. Besides the preceding example of a political alliance, there are several applications of hedonic games, such as project team formation [Okimoto et al., 2015], research team formation [Alcalde and Revilla, 2004], and group activity selection [Darmann et al., 2017], in which unexpected players' non-participation may severely a�ect stability of the system. To the best of our knowledge, however, no attempt has been ever made to connect two important considerations, robustness and stability. Our goal is to make the first step filling this gap.

We focus on friend-oriented games, introduced by Dimitrov et al. [2006], where players' preferences are succinctly encoded via the binary friendship relations. While it is known that such games always guarantee the existence of stable outcomes, we observe that a simple example of one player connecting two enemies shows impossibility in maintaining most of the stability properties, such as core stability, Nash stability, individual stability, and contractual individual stability. Not surprisingly, this negative result holds even under a very small change of the system, i.e., only a single player can disappear.

Given these non-existence results, we investigate the computational complexity of deciding the existence of a robust outcome in a symmetric friend-oriented game. Specifically, we show that we can e�ciently decide the existence of an outcome that is robust with respect to Nash stability, irrespective of the number of players leaving the game. We then prove that any symmetric friend-oriented game admits a polynomial time algorithm that finds a robust outcome with respect to contractual individual stability in case of removing a single player. To this end, we obtain a non-trivial characterization of games whose corresponding robust outcomes are non-empty. Moreover, we complement this result by showing that the problem becomes NP-hard when k = 2. We also show that the positive results do not extend to individual stability:

we prove that the associated problem for individual stability is NP-hard even when only a single player is allowed to leave.

Finally, we consider the question of whether a minimum stability requirement, individual rationality, can be maintained while ensuring that an outcome of a game itself satisfies stronger stability desiderata. It turns out that when players have symmetric additively separable preferences, an individually stable partition which is robust with respect to individual rationality always exist. Our complexity results are summarized in Table 1.

1.1 RelatedWork

A similar notion of robustness appears in a variety of contexts ranging frommulti-agent systems to graph theory. In particular, the robustness concept adapted in this paper is close to the notion of fault tolerance in the theory of distributed systems. We refer the reader to the work of Fedoruk and Deters [2002] for an overview on fault tolerance. Recent works of Kouvaros and Lomuscio [2017] and Kouvaros et al. [2018] also considered a fault-tolerance problem in the context of temporal epistemic specifications.

In cooperative games with transferable utility, several papers studied robustness against agent failures. Bachrach et al. [2011] proposed the reliability extension of cooperative games, where each agent has an independent failure probability. Okimoto et al. [2015] introduced a similar concept to ours, so-called, k-robustness for team formation problems; under their definition, each team needs to accomplish their task even after k agents fail. Further, we note that our definition of robustness resembles some graph connectivity concepts, such as the k-vertex-connectivity, capturing the robustness of a given network (see, e.g., Schrijver [2003]).

Our work is related to the rich body of the literature on the study of hedonic games [Bogomolnaia and Jackson, 2002; Dimitrov et al., 2006; Aziz et al., 2014; 2017]. The relation between stability and the networks capturing agents' preferences has been fairly well-explored, in which the nodes of a graph represent players and edges correspond to the degree of preference [Bil`o et al., 2014; Peters, 2016; Igarashi and Elkind, 2016].

Full version. The full version of the paper is available on arXiv [Igarashi et al., 2019]. It contains full proofs of Lemma 1, Corollary 1, and Theorems 2, 3, 4, 6, 7, 8.

2 Preliminaries

For a natural number s 2 N, we write [s] = f1; 2; : : : ; sg. A hedonic game is defined as a pair (N; (�i)i2N) where N = [n] is a finite set of players and each �i is a preference over the subsets of N (also referred to as coalitions); specifically for every i 2 N, we let Ni denote the collection of all coalitions containing i; each �i describes a complete and transitive preference over the sets in Ni. Let �i denote the strict preference derived from �i, i.e., S �i T if S �i T, but T �i S . For i 2 N and S; T 2 Ni, we say that player i strictly prefers a coalition S to another coalition T if S �i T; player i weakly prefers S to T if S �i T . We call a coalition S � N individually rational if every player i 2 S weakly prefers S to fig.

A preference profile (�i)i2N is said to be additively separable if there exists a weight function w : N � N ! R such that for each i 2 N and each S; T 2 Ni we have S �i T if and only if P j2S w(i; j) � P j2T w(i; j) [Bogomolnaia and Jackson, 2002]; we will assume that w(i; i) = 0 for each i 2 N. An additively separable preference is said to be symmetric if the weight function w : N � N ! R is symmetric, i.e., w(i; j) = w( j; i) for all i; j 2 N. We use the notation (N; w) to denote an additively separable game with weight function w : N � N ! R. For additively separable games, each player can consider every other player to be either a friend, a neutral player, or an enemy; specifically, for each pair of distinct players i; j 2 N, we say that j is a friend of i if w(i; j) > 0, and j is an enemy of i if w(i; j) < 0.

Dimitrov et al. [2006] introduced a subclass of additively separable preferences, which they called friend-oriented preferences. Under friend-oriented preferences, each player has strong favour towards her friends: w(i; j) 2 fn; �1g for each i; j 2 N with i , j. For a symmetric additively separable game (N; w), let Gw denote the friendship graph where the set of vertices is given by the set of players and two players i; j are adjacent if and only if they are friends; each coalition S is said to have minimum degree t if each player in S has at least t other friends in S .

An outcome of a hedonic game is a partition of players into disjoint coalitions. Given a partition � of N and a player i 2 N, let �(i) denote the unique coalition in � that contains i. Much of the existing literature is concerned with outcomes that satisfy certain stability requirements. A minimum stability property we require is individual rationality. A partition � of N is said to be individually rational (IR) if each player prefers their coalition to staying alone, i.e., all coalitions in � are individually rational. If we extend this to a group deviation, we obtain the definition of the core. Specifically, a coalition S � N strongly blocks a partition � of N if every player i 2 S strictly prefers S to her own coalition �(i). A partition � of N is said to be core stable (CR) if no coalition S � N strongly blocks �. We also consider deviations based on individual movements. Specifically, consider a player i 2 N and a pair of coalitions S < Ni, T 2 Ni. A player j 2 S accepts a deviation of i to S if j weakly prefers S [ fig to S ; a player j 2 T accepts a deviation of i from T if j weakly prefers T n fig to T. A deviation of i from T to S is an NS-deviation if i strictly prefers S [ fig to T, an IS-deviation if it is an NSdeviation and all players in S accept it, and a CIS-deviation if it is an IS-deviation and all players in T accept it. A partition � is called Nash stable (NS) (respectively, individually stable (IS) and contractually individually stable (CIS)) if no player i 2 N has an NS-deviation (respectively, an IS-deviation and a CIS-deviation) from �(i) to another coalition S 2 � or to ;.

Trivially, Nash stability implies individual stability, which also implies contractually individual stability. Usually, core stability does not imply the stability based on individual deviations. However, we note that for a symmetric friend-oriented game, core stability implies individual stability. Also, contractual individual stability implies individual rationality with symmetric friend-oriented preferences.

Lemma 1 Let (N; w) be a symmetric friend-oriented game (N; w). Then core stability implies individual stability. Further, contractually individual stability implies individually rationality.

3 Agent Failure in Hedonic Games

Earlier we defined the robustness informally: A sudden deletion of players upon an outcome should preserve the property it has achieved before. We are now in a position to make the definition more formal. For each S � N and i 2 N, we denote by �i jS the preference relation restricted to Ni \ 2 S .

Definition 1 Given � 2 fCR,NS,IS,CIS, IRg and a natural number k > 0, a partition � is said to be �-robust under deletion of at most k players if � satisfies the property �, and for any S � N with jS j � k, the partition ��S := f S 0 n S j S 0 2 � g still satisfies the property � in the subgame (N nS; (�i jNnS )i2NnS ). When k is clear from the context, we will simply call such partition �-robust.

By definition, if an outcome is �-robust under deletion of k + 1 players, then it is �-robust under deletion of any ' � k players. Also, fixing parameter k, the relations between the above robustness concepts are the same as those among the corresponding stability concepts. Namely, we have the following containment relation among the classes of outcomes: NS-robust � IS-robust � CIS-robust and CR-robust � IR-robust. Also, by Lemma 1, CR-robustness implies ISrobustness and CIS-robustness implies IR-robustness for a symmetric friend-oriented game.

It is known that a stable outcome of a symmetric friendoriented game is guaranteed to exist and can be found in polynomial time: a partition that divides the players into the connected components satisfies the preceding stability requirements. However, the example below illustrates that even when players have symmetric friend-oriented preferences, an �- robust partition under deletion of a single player may not exist for any � 2 fCR; NS; IS;CIS g.

Example 1 Consider a symmetric friend-oriented game (N; w) with three players a, b, and c. The friendship graph Gw forms a star with the center being b (Figure 1).

Suppose that � is CIS-robust under deletion of a single player. First, suppose � = ffa; b; cgg. Then, without b, the coalition is not individually rational, a contradiction. Second, suppose � = ffag; fb; cgg or � = ffa; bg; fcgg. Then, if the player who belongs to the same coalition as b disappears, player b would have a CIS-deviation to the other coalition, a contradiction. Third, if � = ffag; fbg; fcgg, it would not satisfy contractually individual stability, a contradiction. Finally, if � = ffa; cg; fbgg, then � would not be individually rational, a contradiction. We have exhausted all possible cases and hence the game admits no CIS-robust partition. This means that the game does not have an �-robust outcome for any � 2 fCR; NS; IS;CIS g. �

4 NS-robustness

We saw that a symmetric friend-oriented game may not admit an NS-robust outcome. In this section, we show that deciding the existence of an NS-robust outcome remains easy for a symmetric friend-oriented game. We warm up by observing that in order to preserve individual rationality, each coalition must be a clique or have minimum degree at least k + 1.

Lemma 2 For any symmetric friend-oriented game, k > 0, and any IR-robust partition �, each S 2 � is either a clique or has minimum degree at least k + 1.

Proof: Let � be an IR-robust partition. Suppose towards a contradiction that there is a coalition S 2 � such that S does not form a clique and there is a player i 2 S who has at most k friends in S . This means that by IR-robustness, S has size at most k + 1; otherwise, removing all i's friends in S would violate individual rationality for i. Now since S is not a clique, there is a player j who has an enemy in S . Observe that j has at most k � 1 friends in S , since S has size at most k + 1 and at least one of the players is an enemy of j. Hence if all the friends of j in S disappear, this would cause the deviation of j to staying alone, contradicting IR-robustness. �

Observe that if there is a coalition of size at most k + 1 and some player has a friend in other coalitions, the player would have an NS-deviation to the other coalition after removal of k players. Hence, any NS-robust outcome cannot contain such coalitions, which leads to the following characterization of the classes of friend-oriented games whose NS-robust outcomes are non-empty.

Theorem 2 The following conditions are equivalent for any symmetric friend-oriented game (N; w) and any natural number k > 0:

• (i) There exists an NS-robust partition.
• (ii) Each connected component of Gw is either a clique or has minimum degree at least k + 1.

Corollary 1 For a symmetric friend-oriented game (N; w), deciding the existence of NS-robust outcomes can be done in polynomial time.

5 CIS-robustness and IS-robustness

We now turn our attention to a weaker stability concept, contractually individual stability. Usually, such stability requirement is not di�cult to achieve: Gairing and Savani [2010] observed that a CIS partition is guaranteed to exist for any symmetric additively separable game and can be e�ciently computed. As we have seen before, the presence of a star with two leaves complicates the existence of CIS-robust outcomes. In what follows, we will show that by decomposing the friendship graph appropriately, one can determine the existence of CIS-robust outcomes under deletion of a single player. We start by showing that a leaf player and its unique neighbor playing a role of pseudo-center form a pair in a CIS-robust outcome. For a graph G = (V; E) and a subset X � V, we denote by G n X the subgraph of G induced by V n X. We say that a vertex j is a pseudo-center in a graph G if at most one neighbor of j is a non-leaf vertex.

Lemma 3 For a symmetric friend-oriented game (N; w) and k = 1, let � be an arbitrary CIS-robust partition. If j is the unique friend of i, and j is a pseudo-center in Gw, then �(i) = fi; jg.

Proof: By Lemma 2, i's coalition is either the singleton fig or the pair fi; jg. Assume towards a contradiction that �(i) = fig. If j�( j)j = 1, then i has a CIS-deviation to j's coalition, a contradiction. If j�( j)j = 2, then removing the player h , j in �( j) would cause the CIS-deviation of i to j's coalition, a contradiction. If j�( j)j � 3, then this means that j has at least two friends a; b in �( j) by Lemma 2. However, this means that at least one of the players a; b has only one friend j but has at least one enemy in �( j), contradicting Lemma 2. In either case, we obtain a contradiction. �

The above lemma can recursively apply to all such pairs in the following way: as long as there is an edge fi; jg satisfying the property in Lemma 3, we need to put the players into a pair and examine whether such an edge still exists in the remaining instance. This allows us to partially determine the structure of a CIS-robust outcome. Figure 2 illustrates the sequence of pairs of players that need to be formed in a robust outcome. We now formalize the above idea as follows. For a friendship graph Gw, a sequence of edges fit; jtg for t = 1; 2; : : : ; t � is called an outer elimination sequence if the following two hold:

• (E1) jt is the unique friend of it inGt, and jt is a pseudo-center in Gt; or
• (E2) jt is the unique friend of it in Gt, and it is a friend of some player in S t�1 h=1 fih; jhg.

Here Gt = Gw n S t�1 h=1 fih; jhg for each t = 1; 2; : : : ; t � . An outer elimination sequence (fit; jtg)t=1;2;:::;t � is said to be maximal if it cannot be made any longer, i.e., there is no outer elimination sequence (fit; jtg)t=1;2;:::;t � +1.

Lemma 4 For a symmetric friend-oriented game (N; w) and k = 1, let � be an arbitrary CIS-robust partition. If there is an outer elimination sequence fit; jtg for t = 1; 2; : : : ; t � , then we have �(it) = fit; jtg for each t = 1; 2; : : : ; t � .

Proof: We prove the statement by induction on t. When t = 1, the claim holds due to Lemma 3. Suppose that the claim holds for t � d � 1 and we prove it for t = d. Now by the induction hypothesis, �(ih) = fih; jhg for each h = 1; 2; : : : ; t � 1, and thus players it and jt form a coalition within Gt. Now, we have either �(it) = fitg or �(it) = fit; jtg by Lemma 2. Assume towards a contradiction that �(it) = fitg. First suppose that jt is a pseudo-center in Gt. Again, if j�( jt)j � 3, then �( jt) contains at least two friends a; b of jt by Lemma 2 where at least one of the players has only one friend jt in �( jt), contradicting Lemma 2. Thus, jt either stays alone at � or forms a coalition with his another friend in Gt; however, in the former case, it would have a CIS-deviation to jt; and in the latter case, deleting the other friend of jt would cause the CIS-deviation of it to �( jt), a contradiction. Second, suppose that it is a friend of some player i 2 S t�1 h=1 fih; jhg. Then, by removing j 2 �(i) with j , i, player i would have a CIS-deviation to �(it), a contradiction. We thus conclude that �(it) = fit; jtg. �

Given a symmetric friend oriented game (N; w), we say that a pair of players is an elimination pair if it appears in some outer elimination sequence. We denote by Pw the set of players who belong to some elimination pair, by Sw the set of players who belong to N n Pw and have exactly one friend in N n Pw, by Bw the set of players who belong to N n Pw and have at least two friends in N n (Pw [ Sw), and by Rw the set of remaining players, i.e., Rw = N n (Pw [ Sw [ Bw). Before we proceed, we observe the following.

Lemma 5 For a symmetric friend oriented game (N; w), each player in Sw has no friend in Pw.

Proof: Suppose that there is a player i 2 Sw who is a friend of some player in Pw. Let j be the unique friend of i in N n Pw. Then, the pair of players i and j is an elimination pair satisfying the condition (E2), a contradiction. �

Lemma 6 For a symmetric friend oriented game (N; w), let j 2 Rw. Then, j has no friend in N n Pw. Further if there is a CIS-robust outcome, j has no friend in Pw.

Proof: Consider j 2 Rw. Assume towards a contradiction that j has some friend in N n Pw. If j has a friend i 2 Sw, then i together with j is an elimination pair satisfying (E1) and must be included in Pw, a contradiction. If j has exactly one friend in N n (Pw [Sw), then this means that j 2 Sw, a contradiction. If j has at least two friends in N n (Pw [ Sw), then this means that j 2 Bw, a contradiction. Hence j has no friend in N n Pw.

Further assume otherwise that there is a CIS-robust outcome � but there is a player i 2 Pw who is a friend of j. By Lemma 4, i forms a pair, say with player h at �. By Lemma 4 and Lemma 2, j stays alone at �. Thus deleting h would cause the CIS-deviation of i to j, a contradiction. �

Figure 3 illustrates the partition of the player set into Pw; S w; Bw, and Rw. Now, a CIS-robust outcome must include all the elimination pairs, and hence if such outcome exists, there is at most one maximal outer elimination sequence. We can thus completely characterise the class of symmetric friend-oriented games that admit a CIS-robust outcome under deletion of a single player.

Theorem 3 For a symmetric friend-oriented game and k = 1, a CIS-robust outcome exists if and only if the following holds:

• (i) the set of elimination pairs that appear in each maximal elimination sequence is the same; and
• (ii) there are no elimination pairs fi; jg and fu; vg where i is a friend of both u and v; and
• (iii) for each player i 2 Pw and each player j 2 Rw, i and j are enemies to each other; and
• (iv) if there is a player i 2 Pw who is a friend of every player in Bw, then every player j 2 Bw is a friend of exactly one player in Sw and j is an enemy of at least one player in each elimination pair.

Proof Sketch: Suppose that there is a CIS-robust outcome �. To show (i), take any maximal elimination sequences (fit; jtg)t=1;2;:::;t � and (fah; bhg)h=1;2;:::;s � . If there are two elimination pairs fit; jtg and fah; bhg with it = ah and jt , bh, this would imply that �(it) = fit; jtg = fit; bhg by Lemma 4, a contradiction. If the two sequences are disjoint, then one can create a longer elimination sequence by adding edge fa1; b1g to the last position of the other sequence, contradicting maximality. To see (ii), if there are two pairs fi; jg and fu; vg where i is a friend of both u and v, then � has to include both pairs, which however implies that i would have a CIS-deviation to the coalition fu; vg after the removal of player j, a contradiction. The statement (iii) holds due to Lemma 6. To see (iv), assume that some player i 2 Pw is a friend of every player in Bw. Consider any player j 2 Bw. If �( j) � Bw, then by deleting the other friend h , i with h 2 �(i), i would have a CIS-deviation to �( j), a contradiction. Thus we have �( j) * Bw. Further, by Lemma 6, each player in Rw has no friend and hence stays alone at � by Lemma 2. This means �( j) \ Rw = ;, and thus �( j) \ Sw , ;. However, if j has no friend in Sw or multiple friends in Sw, player in Sw who belongs to j's coalition has no friend in �( j) or has at most one friend and at least one enemy in �( j), contradicting Lemma 2. Hence j has exactly one friend s in Sw; by Lemma 2 and by the fact that �( j) \ S w , ;, we have �( j) = f j; sg. If there is an elimination pair fu; vg where both of them are adjacent to j, then j would have a CIS-deviation to the coalition fu; vg after removal of s. Hence, j is an enemy of at least one player in each elimination pair.

Conversely, suppose that all the properties (i) ��(iv) hold. Let Pw = S t � t=1 fit; jtg where fit; jtgt=1;2;:::;t � is a maximal outer elimination sequence. We note that Pw is empty if there is no elimination pair. We define the partition � as follows: First, for each t = 1; 2; : : : ; t � , we set �(it) = fit; jtg. Second, for each player i 2 Rw, we set �(i) = fig. Finally, we partition the players in Bw and Sw as follows.

• � If there is a player i 2 Pw who is a friend of every player in Bw, we put each j 2 Bw and the unique friend of j in Sw into a pair.
• � Otherwise, all players in Bw form a coalition and put each player in Sw into a singleton.

It can be verified that � is CIS-robust when k = 1. �

Building on the above characterization, it is easy to see that we can decide in polynomial time whether a symmetric friend-oriented game admits a CIS-robut outcome under deletion of a single player. The proof employs a simple procedure, which iteratively expands an outer elimination sequence and eventually decompose the player set into Pw, S w, Bw, and Rw.

Theorem 4 For a symmetric friend-oriented game and k = 1, deciding the existence of a CIS-robust outcome can be done in polynomial time.

The above result turns out to be tight in several aspects. We first show that for k = 2, finding a CIS-robust outcome of a symmetric friend-oriented game is NP-hard.

Theorem 5 For a symmetric friend-oriented game (N; w), it is NP-complete to decide the existence of a CIS-robust outcome even for k = 2.

Proof Sketch: CIS-robustness can be verified in polynomial time: for each set X � N of size at most two, one can check in polynomial time whether ��X is contractually individually stable. So our problem is in NP. To show hardness, we give a reduction from Exact-3-Cover (X3C). Recall that an instance of X3C is given by a set of elements V = fv1; v2; : : : ; v3rg and a family S of three-element subsets of V; it is a 'yes'-instance if and only if there is an exact cover S 0 � S with jS 0 j = r and S S2S 0 S = V.

Construction: Given an instance (V; S) of X3C, we construct an instance of a friend-oriented game as follows. For each v 2 V, we create a vertex player v. For each vertex v 2 V, we create a vertex gadget Gv, which enforces the corresponding vertex player v to have at least two friends in his robust coalition. Specifically, Gv consists of vertex player v, two friends f 1 v and f 2 v of v, and one enemy ev of v. All the three players f 1 v , f 2 v , and ev are friends to each other, f 1 v and f 2 v are enemies of all the vertex players except for v, and the player ev is an enemy of all the vertex players. Figure 4(a)

illustrates Gv. For each S = fu; v; wg 2 S, we create a set gadget GS which consists of its vertex players u; v; w, and cliques fS 1 v ; S 2 v ; S 3 v g for v 2 S . Specifically, S 1 v and S 2 v are a friend of v for each v 2 S ; S 3 u ; S 3 v ; S 3 w form a clique; and the pairs of S 1 u and S 1 v , S 2 u and S 2 w , and S 1 w and S 2 v are friends to each other. See Figure 4(b) for an illustration. Unless specified otherwise, players are enemies to each other. Finally, we set k = 2.

Correctness: Suppose that there is an exact cover S 0 � S. Then, we define � as follows. For each set S 2 S 0 and each v 2 S , we set �(v) = fv; S 1 v ; S 2 v g; the remaining players of the set gadget forms a coalition, i.e., �(S 3 u ) = fS 3 u ; S 3 v ; S 3 w g. For each S < S 0 , the non-vertex players in the set gadget Gs form a coalition, i.e., �(S 1 u ) = f S i v j i = 1; 2; 3 ^ v 2 S g. For each v 2 V, we set �( f 1 v ) = f f 1 v ; f 2 v ; evg. The resulting partition � can be easily verified to be IR-robust. Also, as each player has at least two friends in his coalition and one enemy in the other coalitions, no player has a CIS-deviation to other coalitions even after an arbitrary player disappears.

Conversely, let � be a CIS-robust partition. To maintain robustness within each vertex gadget Gv, for v 2 V, it can be verified that the three players f 1 v ; f 2 v ; ev must form a coalition, which means that each vertex player v must have at least two friends in his coalition. Thus for each v 2 V, we have fv; S 1 v ; S 2 v g for some S 2 S with v 2 S . Further, to maintain robustness within each set gadget, if �(v) = fv; S 1 v ; S 2 v g, then each vertex player u 2 S also selects S , i.e., �(u) = fu; S 1 u ; S 2 u g. Now let S 0 = S v2Vf S 2 S j �(v) = fv; S 1 v ; S 2 v g g. Then it can be easily verified that S 0 is an exact cover. �

A similar proof of Theorem 5 shows that finding an ISrobust outcome is NP-hard even if only a single player is allowed to disappear.

Theorem 6 For a symmetric friend-oriented game (N; w), deciding the existence of an IS-robust outcome is NPcomplete even for k = 1.

We have not been able to identify whether the problem of computing a CR-robust outcome is polynomial-time solvable; we leave this question for future work.

6 IR-robustness

In Example 1, we have seen that an outcome of a hedonic game can fail to preserve some stability properties, even when players' preferences are symmetric friend-oriented. Our next question is the following: is it still possible to guarantee a minimum stability requirement, i.e., individual rationality, under deletion of players, while ensuring desirable property of the original partition? The answer is positive for individual stability when players have symmetric additively separable preferences. In these games, one can guarantee the existence of an individually stable partition that is IR-robust.

Theorem 7 For any symmetric additively separable game (N; w) and any natural number k > 0, there exists an individually stable and IR-robust partition.

In general, finding an individually stable outcome of a symmetric additively separable game is known to be computationally intractable [Gairing and Savani, 2011]. In contrast, we can e�ciently construct an individually stable partition that is IR-robust in symmetric friend-oriented games, in which each weight only takes two values.

Theorem 8 For any symmetric friend-oriented (N; w) and any natural number k > 0, one can compute an individually stable and IR-robust partition in polynomial time.

We note that without symmetry, the set of outcomes that are both individually stable and IR-robust can be empty.

7 Conclusion

We believe that this paper has made a first important step towards a future stream of research, sparked by the chemistry of two concepts, robustness and stability. Below, we list several interesting questions for future work.

Most obviously, while our main focus was on robustness against agents' non-participation, studying other types of robustness would be an important topic of research. For instance, one might want to consider sudden failure of agents' friendship relations, due to individual conflicts (see, e.g., Varma and Yoshida [2019]). We expect to see a di�erent impact on stable outcomes as communication failure has usually less a�ect on the the structure of the underlying network.

Also, our work presents the worst-case analysis for agent failure. That is, our definition requires an outcome to be immune to any possibility of agent failure. However, one might want to consider specific coalitional failure, rather than all of them. For example, our model can be extended to the probabilistic setting where each agent/friendship link may have di�erent probability of failure.

Finally, it would be interesting to extend this line of work to other settings where stability plays an important role. Examples include fractional hedonic games [Aziz et al., 2014; 2017], stable marriage problem [Gale and Shapley, 1962], and group activity selection problem [Darmann et al., 2017; Igarashi et al., 2017].

Acknowledgements

We thank reviewers at AAMAS-19 for helpful feedback. We are also grateful to Ilan Nehama and Nathana¨el Barrot for useful discussions. This work was supported by JSPS KAKENHI (Grant-in-Aid for JSPS Fellows, No. 18J00997; JP17H00761; JP18H03299; JP17KK0008) and partially supported by JST Strategic International Collaborative Research Program, SICORP.