# robustness_against_agent_failure_in_hedonic_games__a85bb36a.pdf

Robustness against Agent Failure in Hedonic Games

Ayumi Igarashi1 , Kazunori Ota2 , Yuko Sakurai3, and Makoto Yokoo2

1University of Tokyo, Tokyo, Japan, 2Kyusu University, Fukuoka, Japan, 3National Institute of Advanced Industrial Science and Technology, Tokyo, Japan igarashi@mist.i.u-tokyo.ac.jp, {ota,yokoo}@inf.kyushu-u.ac.jp, yuko.sakurai@aist.go.jp

We study how stability can be maintained even after any set of at most k players leave their groups, in the context of hedonic games. While stability properties ensure an outcome to be robust against players deviations, it has not been considered how an unexpected change caused by a sudden deletion of players affects stable outcomes. In this paper, we propose a novel criterion that reshapes stability form robustness aspect. We observe that some stability properties can be no longer preserved even when a single agent is removed. However, we obtain positive results by focusing on symmetric friendoriented hedonic games. We prove that we can efficiently decide the existence of robust outcomes with respect to Nash stability under deletion of any number of players or contractual individual stability under deletion of a single player. We also prove that symmetric additively separable games always admit an individual stable outcome that is robust with respect to individual rationality.

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 affect 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 efficiently 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:

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

NS-robustness polytime (Cor. 1) IS-robustness NP-complete (k = 1) (Th. 6) CIS-robustness polytime (k = 1) (Th. 4) NP-complete (k = 2) (Th. 5) IS & IR-robustness exists and polytime (Th. 8)

Table 1: Overview of our complexity results in a symmetric friendoriented game, where k is the maximum number of players who can leave the entire game.

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 Related Work A similar notion of robustness appears in a variety of contexts ranging from multi-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 ar Xiv [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 N, we write [s] = {1, 2, . . . , s}. A hedonic game is defined as a pair (N, ( i)i N) 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 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 N and S, T 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 S weakly prefers S to {i}. A preference profile ( i)i N is said to be additively separable if there exists a weight function w : N N R such that for each i N and each S, T Ni we have S i T if and only if P j S w(i, j) P j T w(i, j) [Bogomolnaia and Jackson, 2002]; we will assume that w(i, i) = 0 for each i 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 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 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) {n, 1} for each i, j 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 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 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 N and a pair of coalitions S < Ni, T Ni. A player j S accepts a deviation of i to S if j weakly prefers S {i} to S ; a player j T accepts a deviation of i from T if j weakly prefers T \ {i} to T. A deviation of i from T to S is an NS-deviation if i strictly prefers S {i} 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 N has an NS-deviation (respectively, an IS-deviation and a CIS-deviation) from π(i) to another coalition S π or to .

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

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 N, we denote by i |S the preference relation restricted to Ni 2S .

Definition 1 Given α {CR,NS,IS,CIS, IR} 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 |S | k, the partition π S := { S \ S | S π } still satisfies the property α in the subgame (N \ S, ( i |N\S )i N\S ). 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 α {CR, NS, IS,CIS }.

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

Figure 1: Non-existence of a CR-robust partition for symmetric friend-oriented games.

Suppose that π is CIS-robust under deletion of a single player. First, suppose π = {{a, b, c}}. Then, without b, the

coalition is not individually rational, a contradiction. Second, suppose π = {{a}, {b, c}} or π = {{a, b}, {c}}. 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 π = {{a}, {b}, {c}}, it would not satisfy contractually individual stability, a contradiction. Finally, if π = {{a, c}, {b}}, 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 α {CR, NS, IS,CIS }.

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 π 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 π such that S does not form a clique and there is a player i 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.

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

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 difficult to achieve: Gairing and Savani [2010] observed that a CIS partition is guaranteed to exist for any symmetric additively separable game and can be efficiently 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 \ X the subgraph of G induced by V \ 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) = {i, j}.

Proof: By Lemma 2, i s coalition is either the singleton {i} or the pair {i, j}. Assume towards a contradiction that π(i) = {i}. If |π(j)| = 1, then i has a CIS-deviation to j s coalition, a contradiction. If |π(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)| 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 {i, j} 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 {it, jt} for t = 1, 2, . . . , t is called an outer elimination sequence if the following two hold:

(E1) jt is the unique friend of it in Gt, 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 St 1 h=1{ih, jh}.

Here Gt = Gw \ St 1 h=1{ih, jh} for each t = 1, 2, . . . , t . An outer elimination sequence ({it, jt})t=1,2,...,t is said to be maximal if it cannot be made any longer, i.e., there is no outer elimination sequence ({it, jt})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 {it, jt} for t = 1, 2, . . . , t , then we have π(it) = {it, jt} for each t = 1, 2, . . . , t .

i1 j1 i2 j2

i1 j1 i2 j2

Figure 2: Examples of maximal outer elimination sequences. Observe that the left friendship graph admits a unique CIS-robust partition that consists of elimination pairs, whereas the right friendship graph admits no CIS-robust partition since deleting i3 would cause the CIS-deviation of j3 to s.

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) = {ih, jh} for each h = 1, 2, . . . , t 1, and thus players it and jt form a coalition within Gt. Now, we have either π(it) = {it} or π(it) = {it, jt} by Lemma 2. Assume towards a contradiction that π(it) = {it}. First suppose that jt is a pseudo-center in Gt. Again, if |π(jt)| 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 St 1 h=1{ih, jh}. Then, by removing j π(i) with j , i, player i would have a CIS-deviation to π(it), a contradiction. We thus conclude that π(it) = {it, jt}.

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 S w the set of players who belong to N \ Pw and have exactly one friend in N \ Pw, by Bw the set of players who belong to N \ Pw and have at least two friends in N \ (Pw S w), and by Rw the set of remaining players, i.e., Rw = N \ (Pw S w Bw). Before we proceed, we observe the following.

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

Proof: Suppose that there is a player i S w who is a friend of some player in Pw. Let j be the unique friend of i in 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 Rw. Then, j has no friend in N \ Pw. Further if there is a CIS-robust outcome, j has no friend in Pw.

Proof: Consider j Rw. Assume towards a contradiction that j has some friend in N \ Pw. If j has a friend i S w, 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 \(Pw S w), then this means that j S w, a contradiction. If j has at least two friends in N \ (Pw S w), then this means that j Bw, a contradiction. Hence j has no friend in N \ Pw.

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

Further assume otherwise that there is a CIS-robust outcome π but there is a player i 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 {i, j} and {u, v} where i is a friend of both u and v; and

(iii) for each player i Pw and each player j Rw, i and j are enemies to each other; and

(iv) if there is a player i Pw who is a friend of every player in Bw, then every player j Bw is a friend of exactly one player in S w 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 ({it, jt})t=1,2,...,t and ({ah, bh})h=1,2,...,s . If there are two elimination pairs {it, jt} and {ah, bh} with it = ah and jt , bh, this would imply that π(it) = {it, jt} = {it, bh} by Lemma 4, a contradiction. If the two sequences are disjoint, then one can create a longer elimination sequence by adding edge {a1, b1} to the last position of the other sequence, contradicting maximality. To see (ii), if there are two pairs {i, j} and {u, v} 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 {u, v} after the removal of player j, a contradiction. The statement (iii) holds due to Lemma 6. To see (iv), assume that some player i Pw is a friend of every player in Bw. Consider any player j Bw. If π(j) Bw, then by deleting the other friend h , i with h π(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) S w , . However, if j has no friend in S w or multiple friends in S w, player in S w 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 S w; by Lemma 2 and by the fact that π(j) S w , , we have π(j) = {j, s}. If there is an elimination pair {u, v} where both of them are adjacent to j, then j would have a CIS-deviation to the coalition {u, v} 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 = St t=1{it, jt} where {it, jt}t=1,2,...,t is a maximal outer

Figure 3: A partition of the player set into Pw, S w, Bw, Rw.

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) = {it, jt}. Second, for each player i Rw, we set π(i) = {i}. Finally, we partition the players in Bw and S w as follows.

If there is a player i Pw who is a friend of every player in Bw, we put each j Bw and the unique friend of j in S w into a pair.

Otherwise, all players in Bw form a coalition and put each player in S w 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 = {v1, v2, . . . , v3r} 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 S with |S | = r and S S S S = V. Construction: Given an instance (V, S) of X3C, we construct an instance of a friend-oriented game as follows. For each v V, we create a vertex player v. For each vertex v 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)

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

f 1 v f 2 v

(a) Vertex gadget Gv

S 1 v S 2 v

S 3 u S 3 w

(b) Set gadget GS for S = {u, v, w}

Figure 4: Gadgets constructed in the proofs of Theorem 5. The grey nodes correspond to vertex players.

illustrates Gv. For each S = {u, v, w} S, we create a set gadget GS which consists of its vertex players u, v, w, and cliques {S 1 v, S 2 v, S 3 v} for v S . Specifically, S 1 v and S 2 v are a friend of v for each v 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 S. Then, we define π as follows. For each set S S and each v S , we set π(v) = {v, S 1 v, S 2 v}; the remaining players of the set gadget forms a coalition, i.e., π(S 3 u) = {S 3 u, S 3 v, S 3 w}. For each S < S , the non-vertex players in the set gadget Gs form a coalition, i.e., π(S 1 u) = { S i v | i = 1, 2, 3 v S }. For each v V, we set π(f 1 v ) = {f 1 v , f 2 v , ev}. 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 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 V, we have {v, S 1 v, S 2 v} for some S S with v S . Further, to maintain robustness within each set gadget, if π(v) = {v, S 1 v, S 2 v}, then each vertex player u S also selects S , i.e., π(u) = {u, S 1 u, S 2 u}. Now let S = S v V{ S S | π(v) = {v, S 1 v, S 2 v} }. Then it can be easily verified that S 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 efficiently 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 different impact on stable outcomes as communication failure has usually less affect 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 different 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.

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

[Alcalde and Revilla, 2004] J. Alcalde and P. Revilla. Researching with whom? stability and manipulation. Journal of Mathematical Economics, 40(8):869 887, 2004.

[Aziz et al., 2014] H. Aziz, F. Brandt, and P. Harrenstein. Fractional hedonic games. In Proceedings of the 13th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), pages 5 12, 2014.

[Aziz et al., 2017] H. Aziz, F. Brandl, F. Brandt, P. Harrenstein, M. Olsen, and D. Peters. Fractional hedonic games. Co RR, abs/1705.10116, 2017.

[Bachrach et al., 2011] Y. Bachrach, R. Meir, M. Feldman, and M. Tennenholtz. Solving cooperative reliability games. In Proceedings of the 27th Annual Conference on Uncertainty in Artificial Intelligence (UAI), pages 27 34, 2011.

[Banerjee et al., 2001] S. Banerjee, H. Konishi, and T. S onmez. Core in a simple coalition formation game. Social Choice and Welfare, 18(1):135 153, 2001.

[Bil o et al., 2014] V. Bil o, A. Fanelli, M. Flammini, G. Monaco, and L. Moscardelli. Nash stability in fractional hedonic games. In Proceedings of the 10th Conference on Web and Internet Economics (WINE), pages 486 491, 2014.

[Bogomolnaia and Jackson, 2002] A. Bogomolnaia and M.O. Jackson. The stability of hedonic coalition structures. Games and Economic Behavior, 38(2):201 230, 2002.

[Darmann et al., 2017] A. Darmann, E. Elkind, S. Kurz, J. Lang, J. Schauer, and G. Woeginger. Group activity selection problem. International Journal of Game Theory, 2017.

[Dimitrov et al., 2006] D. Dimitrov, P. Borm, R. Hendrickx, and S. C. Sung. Simple priorities and core stability in hedonic games. Social Choice and Welfare, 26(2):421 433, 2006.

[Fedoruk and Deters, 2002] A. Fedoruk and R. Deters. Improving fault-tolerance by replicating agents. In Proceedings of the 1st International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 737 744, 2002.

[Gairing and Savani, 2010] M. Gairing and R. Savani. Computing stable outcomes in hedonic games. In Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT), pages 174 185, 2010.

[Gairing and Savani, 2011] M. Gairing and R. Savani. Computing stable outcomes in hedonic games with votingbased deviations. In Proceedings of the 10th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 559 566, 2011.

[Gale and Shapley, 1962] D. Gale and L.S. Shapley. College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69:9 15, 1962.

[Igarashi and Elkind, 2016] A. Igarashi and E. Elkind. Hedonic games with graph-restricted communication. In Proceedings of the 15th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 242 250, 2016. [Igarashi et al., 2017] A. Igarashi, D. Peters, and E. Elkind. Group activity selection on social networks. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pages 565 571, 2017. Extended version available as ar Xiv:1611.04524 [cs.GT]. [Igarashi et al., 2019] A. Igarashi, K. Ota, Y. Sakurai, and M. Yokoo. Robustness agains agent failure in hedonic games. Co RR, abs/1903.05534, 2019. [Kouvaros and Lomuscio, 2017] Panagiotis Kouvaros and Alessio Lomuscio. Verifying fault-tolerance in parameterised multi-agent systems. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI), pages 288 294, 2017. [Kouvaros et al., 2018] P. Kouvaros, A. Lomuscio, and E. Pirovano. Symbolic synthesis of fault-tolerance ratios in parameterised multi-agent systems. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI), pages 324 330, 2018. [Okimoto et al., 2015] T. Okimoto, N. Schwind, M. Clement, T. Ribeiro, K. Inoue, and P. Marquis. How to form a task-oriented robust team. In Proceedings of the 14th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 395 403, 2015. [Peters, 2016] D. Peters. Graphical hedonic games of bounded treewidth. In Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pages 586 593, 2016. [Schrijver, 2003] A. Schrijver. Combinatorial Optimization Polyhedra and Efficiency, volume 24. Springer-Verlag Berlin Heidelberg, 2003. [Varma and Yoshida, 2019] N. Varma and Y. Yoshida. Average sensitivity of graph algorithms. Co RR, abs/1904.03248, 2019.

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