--- title: "Core Stability in Hedonic Games among Friends and Enemies: Impact of Neutrals" authors: - "Kazunori Ohta" - "Nathanaël Barrot" - "Anisse Ismaili" - "Yuko Sakurai" - "Makoto Yokoo" doi: "10.24963/ijcai.2017/51" url: "https://ijcai.org/proceedings/2017/51" pdf: "https://ijcai.org/proceedings/2017/0051.pdf" venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence" year: 2017 pages: "359-365" track: "Main track" keywords: - "Agent-based and Multi-agent Systems: Cooperative Games" - "Agent-based and Multi-agent Systems: Social Choice Theory" --- # Core Stability in Hedonic Games among Friends and Enemies: Impact of Neutrals Kazunori Ohta, Nathanaël Barrot, Anisse Ismaili, Yuko Sakurai, Makoto Yokoo *Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 359-365. DOI: [10.24963/ijcai.2017/51](https://doi.org/10.24963/ijcai.2017/51) ## Abstract We investigate hedonic games under enemies aversion and friends appreciation, where every agent considers other agents as either a friend or an enemy. We extend these simple preferences by allowing each agent to also consider other agents to be neutral. Neutrals have no impact on her preference, as in a graphical hedonic game.Surprisingly, we discover that neutral agents do not simplify matters, but cause complexity. We prove that the core can be empty under enemies aversion and the strict core can be empty under friends appreciation. Furthermore, we show that under both preferences, deciding whether the strict core is non-empty, is NP^NP-complete. This complexity extends to the core under enemies aversion. We also show that under friends appreciation, we can always find a core stable coalition structure in polynomial time. ## Full text ## 1 Introduction Coalitions are a central part of economics, political, and social life. A natural question is whether a coalition structure (which is a partition of the set of agents) exists that is stable. In coalition formation games with hedonic preferences, each agent only cares about her own coalition. Since the number of coalitions that she can join is exponential, various compact classes of hedonic games have been proposed. In particular, Dimitrov et al. [2006] developed games in which each agent divides the other agents into friends or enemies. They propose two alternative preferences. One is enemies aversion, where each agent prefers coalitions with fewer enemies and in case of a tie, with more friends. The other is friends appreciation, where each agent prefers coalitions with more friends and in case of a tie, with fewer enemies. Under enemies aversion, there always exists a core stable coalition structure that is NP-hard to find; and under friends appreciation, there always exists a strict core stable coalition structure, which can be found in polynomial-time. In this paper, we examine a slight extension of this model where each agent divides the others into three groups, friends, enemies, and neutrals, who do not impact her preference, in the fashion of graphical hedonic games [Peters, 2016]. Indeed, in practice, agents commonly only care about a subset of other agents; the rest are neutral. One might think that adding such a graphical assumption would simplify the computational problems or that since neutral agents do not impact preferences, the previous results in Dimitrov et al. [2006] would still hold in this extended model. Table 1: Summary of results: new ones marked with ∗ . | | Enemies aversion | Friends appreciation | |-------------|--------------------------------------------------------------------------|---------------------------------------------------------------------------| | Core | May be empty (Th. 1)∗ VERIF is coNP-c (Th. 5) EXIST is NP NP -c (Th. 6)∗ | Non-empty (Th. 9)∗ CONSTRUCTION takes polynomial time (Th. 9)∗ | | Strict core | May be empty (Ex. 1) VERIF is coNP-c (Th. 3)∗ EXIST is NP NP -c (Th. 4)∗ | May be empty (Th. 2)∗ VERIF is coNP-c (Th. 7)∗ EXIST is NP NP -c (Th. 8)∗ | It turns out that under enemies aversion, a core stable coalition structure might not exist, and it might not exist under friends appreciation for the strict core either. Then, we investigate the complexity of (VERIF) to verify whether a given coalition structure is (strict) core stable and (EXIST) whether the (strict) core is non-empty. Our findings are in Table 1. Related work Lang et al. [2015] proposed friendsneutrals-enemies hedonic games using the generalized Bossong-Schweigert extension principle. Peters [2016] considered graphical hedonic games. If the agent graph has a bounded treewidth and a bounded degree, deciding the core's existence is polynomial-time tractable. Aziz and Brandl [2012] clarified the inclusions between stability concepts such as core and Nash stability, and provided some existence results. Aziz et al. [2014] proposed conditions that guarantee a core stable outcome in fractional hedonic games. Aziz et al. [2016] proposed Boolean hedonic games where an agent partitions a set of other agents into satisfactory and unsatisfactory groups and showed core non-emptiness. Sung and Dimitrov [2007] showed that the verification problem for the core is coNP-complete in additive hedonic games. Woeginger [2013] showed that the existence problem for the core is NP NP -complete in additively separable hedonic games (ASHG). Peters [2015] proved that the existence problem for the strict core is NP NP -complete in ASHGs. Rey et al. [2016] show that under enemy-aversion, deciding the existence of the strict-core is DP-hard. Peters and Elkind [2015] developed a framework to prove the NP-hardness of existence problems, which widely applies to various hedonic games such as individually rational coalition lists [Ballester, 2004] and hedonic coalition nets [Elkind and Wooldridge, 2009]. ## 2 Model Let N = {1, . . . , n} denote the set of agents. A coalition C ⊆ N is a subset of agents. A coalition structure π is a partition of set N. Let π(i) denote the coalition to which agent i belongs in π. Let C N denote the set of coalition structures. For every agent i, her preference ≿i is based on the coalitions to which she belongs; let ≻i (respectively ∼i) denote the preference's asymmetric (respectively symmetric) part. A hedonic game (N, P) is defined by set of agents N and preference profile P = (≿i)i∈N . Coalition structure π ∈ C N admits blocking coalition ∅ ̸= X ⊆ N iff for every i ∈ X, X ≻i π(i) holds. The core is the set of coalition structures that do not admit any blocking coalition. Similarly, coalition structure π ∈ C N admits weakly blocking coalition X ⊆ N iff for every i ∈ X, X ≿i π(i), and there exists j ∈ X such that X ≻j π(j). The strict core is the set of coalition structures that do not admit any weakly blocking coalition. 1 Coalition C is acceptable for agent i if and only if C ≿i {i} holds. 2 In this paper, we consider the following simple (and compact) preferences. For each agent i, set N is partitioned into {Fi,Ei,⊥i}. Agents Fi are her friends, Ei are her enemies, and ⊥i are neutral agents (i ∈⊥i). Under enemies aversion, she first compares the number of enemies. Hence, without loss of generality, any coalition that contains an enemy is unacceptable. Within acceptable coalitions, she prefers coalitions with more friends, i.e., for two acceptable coalitions, C ≻i D holds iff |C ∩ Fi| > |D ∩ Fi|. Under friends appreciation, she prefers coalitions with more friends, and in case of a tie, she prefers the one with fewer enemies: C ≻i D holds iff (a) |C ∩ Fi| > |D ∩ Fi|, or (b) |C ∩Fi| = |D∩Fi| and |C ∩Ei| < |D∩Ei|. In both preferences, C ∼i D holds iff |C ∩Ei| = |D∩Ei| and |C ∩ Fi| = |D ∩ Fi|. The set of preference profiles under enemies aversion (respectively friends appreciation) is denoted by P E (respectively by P F ). In P E there is additive separability on weights {1, 0, -n}, and in P F on {n, 0, -1}. Definition 1 (HG/E and HG/F). An HG/E is a hedonic game (N, (≿i)i∈N) such that each ≿i is in P E . Similarly, an HG/F is a hedonic game (N, (≿i)i∈N) such that each ≿i is in P F . Such hedonic games can be represented by a labeled digraph GEF⊥ = (N, AE ∪ AF ∪ A⊥) where each vertex represents an agent, and arc (i, j) in set AE labeled by E (respectively by F,⊥) indicates that for agent i, agent j is an enemy (respectively friend, neutral). 3 Example 1. [Dimitrov et al., 2006] Under enemies aversion, in this three-agent HG/E, the following preferences hold: ![Image](https://ijcai.org/proceedings/2017/fulltext/51/image_000000_f9ff8081887f14368c89be2cacabdc8c525785ef25e6ef4a61398ec3585e117c.png) The coalition structures that do not admit a blocking coalition, are set { {{1, 2}, {3}} , {{1}, {2, 3}} }. However, there are weak deviations from these coalition structures, respectively {2, 3} and {1, 2}, and thus, the strict core is empty. 1 The strict core is more demanding, thus contained in the core. 2 If π(i) is unacceptable, π cannot be a member of the core. 3 The size of this representation is Θ(n2 ). Depending on the context, we sometimes omit one of the three sets AE, AF or A⊥, since it can be deduced from the two others. For instance, omitting set A⊥, graph GEF = (N,AE ∪ AF ) shows a graphical hedonic game [Peters, 2016]. The following remark is also useful: Remark 1. Under enemies aversion, consider an HG/E and graph GF⊥ = (N, AF ∪A⊥), where only friendly and neutral arcs are represented, and enemy arcs omitted. Given coalition C, if arc (i, j) is missing in subgraph GF⊥[C], then agent j is an enemy of i, and C is unacceptable to her. Thus, (i) if π is a member of the (strict) core, for each C ∈ π, subgraph GF⊥[C] is necessarily a clique 4 , and (ii) given π where every coalition C ∈ π induces clique GF⊥[C], a (weakly) blocking coalition X ⊆ N necessarily induces clique GF⊥[X]. ## 3 Stable Coalitions May Not Exist. In this section, we discuss the existence of a (strict) core stable coalition structure. Under enemies aversion, considering only friends and enemies (no neutrals), the possible nonexistence of a strict core stable coalition structure was shown in Example 1 [Dimitrov et al., 2006] and implies that the strict core can be empty, when neutral agents are also allowed. This example does not extend to the (non strict) core in the friends-and-enemies model and indeed a core stable coalition structure always exists under enemies aversion [Dimitrov et al., 2006]. However, when we add neutral agents to the friends-and-enemies model, the following theorem holds. ## Theorem 1. In an HG/E, the core can be empty. To prove this theorem, we utilize the following example. Example 2. Assume 15 agents who are divided into a cycle of five groups, C0, . . . , C4, each of which contains three agents. Ci+k (resp. Ci-k) denotes Ci+k mod 5 (resp. Ci-k mod 5). The sets of friends, neutrals and enemies are as follows: - Agents in the same group are friends. - Agents in Cj consider agents in Cj±2 enemies. - Agents in Cj consider agents in Cj+1 friends. - Agents in Cj consider one agent in Cj-1 a neutral and the other two agents to be friends. We illustrate these preferences with a partial representation of graph GF⊥ by focusing on group C0: ![Image](https://ijcai.org/proceedings/2017/fulltext/51/image_000001_bbdd253014670511ea5da603702c43e8a54c1698905ab8321b38df7a46768231.png) Proof of Theorem 1. Assume π is core stable in Example 2. From Remark 1, only the agents in adjoining groups can form a coalition. Also, note that if coalition Ci ∪ Ci+1 is formed, each member in Ci is with 5 friends and each member in Ci+1 is with 4 friends. First, we show that the agents in a same group cannot be separated. For the sake of contradiction, assume agent i ∈ C0 is separated from the other members in C0. There are three cases to study: 4 A digraph G = (W, B) is a clique iff ∀(i, j) ∈ W 2 , (i, j) ∈ B. - When π(i) ∩ C1 ̸= ∅: i is with at most 3 friends, and j ∈ C0 (j ̸= i) is with at most 3 friends. Each member in C4 is also with at most 4 friends (since they are not with i). Then C4 ∪ C0 is a deviation. - When π(i) ∩ C4 ̸= ∅: each member of C4 is with at most 3 friends. Also, each member of C3 is with at most 4 friends. Then, C3 ∪ C4 is a deviation. - When π(i) = {i}: the only case for which C0 ∪ C1 (or C0∪C4) is not a deviation is when (C0 \{i})∪C1 forms a coalition (such that at least one member in C1 does not strictly prefer C0 ∪ C1). Here, each member in C1 is with at most 4 friends. Then, consider the members of C2. The only way that a member of C2 is with 4 or more than 4 friends is to form a coalition with 2 or 3 members of C3. However, in such a case, each member of C3 is with at most 4 friends and each member in C4 is with at most 3 friends, and therefore, C3 ∪ C4 becomes a deviation. Thus, each member in C2 is with at most 3 friends, but then C1 ∪C2 is a deviation. Using a similar argument, we can prove that all the members in the same group must be in the same coalition in π. Also, it is not possible that two adjoining groups, Cj and Cj+1, are isolated, i.e., Cj ∈ π and Cj+1 ∈ π, since Cj∪Cj+1 becomes a deviation. Therefore, consider coalition structure π where no two consecutive groups are alone, which implies that exactly one Cj is alone. Without loss of generality, we assume that just C0 is alone. Then the only coalition structure that is not discarded by Remark 1 is π = {C0, C1 ∪ C2, C3 ∪ C4}. Then each member in C0 is with 2 friends and each member in C4 is with 4 friends, and thus, C4 ∪ C0 is a deviation. Therefore, no core stable coalition structure exists. Under friends appreciation and considering only friends and enemies, both the core and the strict core always exist [Dimitrov et al., 2006]. However, if we add neutral agents, then we have the following: Theorem 2. In an HG/F, the strict core can be empty. To prove this theorem, we utilize the following example. Example 3. Consider N = {1, 2, 3} under friends appreciation based on partitions F1 = {1, 2}, E1 = {3}, F2 = {2}, ⊥2= {1, 3}, F3 = {2, 3} and E3 = {1}. Proof of Theorem 2. The core contains all of the coalition structures except {{2}, {1, 3}}. However, there is a weak deviation from all coalition structures in the core, either {1, 2} or {2, 3}, and thus, the strict core is empty. ## 4 Problems and Complexity The previous section showed that in an HG/E, both the strict core and the core may be empty, and in an HG/F, the strict core may be empty. These observations bring to surface the following decision problems to decide the non-emptiness of the strict core and the core for an HG/E as well as the non-emptiness of the strict core for an HG/E: (i) HG/E/SC/EXIST, (ii) HG/E/C/EXIST, and (iii) HG/F/SC/EXIST. To examine whether they belong to class NP, we also study the problem of verifying whether a given coalition structure π is in the core or the strict core for a given game: i.e., (a) HG/E/SC/VERIF, (b) HG/E/C/VERIF, and (c) HG/F/SC/VERIF. We address the complexity of these problems in the next sections. Class NP corresponds to the set of decision problems where 'yes'-instances allow a polynomially-sized certificate verifiable in polynomial-time. For instance, in a further proof, we utilize problem MAXCLIQUE, which is among the computationally most intractable problems in class NP. Indeed, it is NP-complete: it is in NP and NP-hard. 5 Definition 2 (Problem MAXCLIQUE). Given graph G = (V,A) and lower threshold k ∈ N, does a subset of k vertices W ⊆ V exist such that subgraph G[W] is a clique? Complementation consists in transposing the 'yes' and 'no' answers. Consequently, class coNP is symmetric to class NP and corresponds to the set of decision problems where 'no'-instances allow a polynomially-sized certificate verifiable in polynomial-time. For instance, the problem of verifying that a given coalition structure is core stable belongs to class coNP, since we can certify 'no'-instances with a blocking coalition. One can show that a problem is coNP-complete by proving that it is in coNP and that it is the complement of an NP-hard problem, by symmetry of NP and coNP. A decision problem may also neither allow a yes or a no verification in polynomial-time, falling outside of NP and coNP. Class NP NP corresponds 6 to the decision problems for which 'yes'-instances allow a polynomially-sized certificate that is verifiable in polynomial-time using a constant-time NP-oracle. 7 Class coNP NP is its complement. 8 Typically, a problem in NP NP is extremely hard, since it consists in a coNP problem nested into an NP problem. Problem MINMAXCLIQUE is typical for this second level of the polynomial hierarchy. Definition 3 (Problem MINMAXCLIQUE). Given graph G = (V, A), two sets I, J that partition set V into {Vi,j | i ∈ I, j ∈ J}, and lower threshold k ∈ N, does, for every function t : I → J, subgraph G[∪i∈IVi,t(i)], contain a k-sized clique? Intuitively, V is partitioned into |I|·|J| subsets Vi,j. According to function t, |I| subsets are chosen (for each i ∈ I, set Vi,t(i)). Then for the union of these subsets, we consider MAXCLIQUE. There are |J||I| variations of function t. Problem MINMAXCLIQUE lies in class coNP NP , since by inferring the correct function t : I → J (a 'no' certificate), the NPoracle can solve the MAXCLIQUE problem on G[∪i∈IVi,t(i)] and verify the 'no' answer. Completeness is defined in a standard manner with polynomial-time reductions, and we know: Lemma 1. [Ko and Lin, 1995] ProblemMINMAXCLIQUE is coNP NP -complete. (Their proof even holds when J = {0, 1} and |Vi,0| = |Vi,1| for every i ∈ I.) 5 Any problem from class NP can be reduced to MAXCLIQUE in polynomial-time; so that solving it efficiently would solve P vs NP. 6 Class ΣP2 in the second level of the Polynomial Hierarchy. 7 A blackbox that solves any (co)NP problem in constant-time. 8 Class ΠP2 in the second level of the Polynomial Hierarchy. ## 5 Enemies Aversion and the Strict Core In this section, under enemies aversion, we first address the complexity of verifying that a given coalition structure is in the strict core. Second, we address the complexity of deciding whether the strict core is non-empty. We show the following: Hence the existence problem does not allow a classical verification procedure in polynomial-time. Indeed, it is not in NP or coNP, since we show that: Theorem 4. Problem HG/E/SC/EXIST is NP NP -complete. Therefore, since this problem is at least as intractable as all the problems that nest a coNP problem into an NP problem, it is extremely intractable, despite the utter simplicity of enemies aversion as a preference. ## 5.1 Proving Complexity of Verification Proof of Theorem 3. Problem HG/E/SC/VERIF is in coNP, since 'no'-instances can be certified with a weakly blocking coalition. For coNP-hardness, we reduce problem MAXCLIQUE to the complement of problem HG/E/SC/VERIF. Let graph G = (V,A) and threshold k ∈ N define an instance of MAXCLIQUE. From it, we construct an HG/E/SC/VERIF instance with vertex-agents V ≡ V, k - 1 weight-agents in set K, and one fulcrum-agent ϕ; therefore with set of agents N = V ∪ {ϕ} ∪ K. Bearing Remark 1 in mind, we depict graph GF⊥ in Fig. 1, and all other arcs are enemies. Concerning set V , for every edge {i, j} in graph G = (V,A) we construct neutral arcs (i, j) and (j, i). In set K, all k - 1 agents are mutual friends. Between sets V and K, fulcrum-agent ϕ shares a mutual friendship with everyone. Finally, in given coalition structure π, every vertexagent i ∈ V is in singleton {i}, and the fulcrum-agent forms a coalition with the k - 1 weight agents. In coalition structure π, there is a (weakly) blocking coalition if and only if the fulcrum-agent can improve (from k -1 to at least k friends) with a k-sized clique in set V , and hence if and only if a k-sized clique exists in graph G. ## 5.2 Proving Complexity of Existence Proof of Theorem 4. Problem HG/E/SC/EXIST is in NP NP . For 'yes'-instances, a coalition structure π in the strict core is a certificate that can be verified using an NP-oracle. (Recall that the verification problem is coNP-complete.) We prove that problem HG/E/SC/EXIST is NP NP -hard by showing that the coNP NP -complete problem MINMAXCLIQUE (Lemma 1) can be reduced to the complement of problem HG/E/SC/EXIST. Let graph G = (V,A), set I, which partitions set V into {Vi,0, Vi,1 | i ∈ I} and lower threshold k ∈ N define a restricted instance of MINMAXCLIQUE where ∀i ∈ I, |Vi,0| = |Vi,1| holds. We construct an instance of coHG/E/SC/EXIST addressing the MINMAXCLIQUE instance, as follows. Graph GF⊥ is partially shown in Fig. 2, by keeping Remark 1 on necessary cliques in mind. (1) For every set of vertices Vi,j, we introduce set of vertex-agents Vi,j ≡ Vi,j. For every edge {x, y} in graph G = (V,A), we introduce neutral arcs (x, y) and (y, x) between the agents of V = ⋃i∈I (Vi,0 ∪Vi,1). (There is no edge between Vi,0 and Vi,1.) (2) We introduce two friend-cliques K0 and K1, each of which contains k-2 mutual friends. Between them, agent y is a mutual friend with everyone in K0 and K1. (3) Fulcrum-agent ϕ is a mutual friend with agent y, with everyone in clique K0 (but no one in clique K1) and with everyone in set V . (4) Between every pair of sets Vi,0 and Vi,1, we introduce |Vi,0| = |Vi,1| inhibitors (specified below) by pairing the agents of Vi,0 and Vi,1. Each inhibitor, which is a game connected to one vertex in Vi,0 and one in Vi,1, makes the former vertex xor the latter non-available. (5) To avoid inhibitors going to two different sides for one Vi,j, we connect to every set Vi,j a circuit game Li,j (specified below) in which the strict core is non-empty if and only if the "every agent in Vi,j is inhibited, or none is inhibited" condition is satisfied. (6) Other arcs are for enemies. Figure 1: Reducing MAXCLIQUE to co-HG/E/SC/VERIF: The edges of graph G become neutral arcs for agents V . ![Image](https://ijcai.org/proceedings/2017/fulltext/51/image_000002_c32eac837a983d743d828e0bc68f580db6d97b2f8daa09672fa7e5d0334d7141.png) Recall that we want to show that our reduction addresses problemMINMAXCLIQUE. Therefore, we want to show: But first, observe that in our construct, assuming strict core stability, fulcrum-agent ϕ is either grouped with y and K0 (k - 1 friends) or with a clique in V of at least k friends. If agent ϕ goes to a clique in V , then the game on agents K1 ∪ {y} ∪ K0 is isolated with an empty strict core. (If y groups with K0, then coalition {y} ∪ K1 weakly blocks; and if y groups with K1, then coalition {y} ∪ K0 weakly blocks.) If agent ϕ goes to the right, then the strict core of game {ϕ} ∪ K1 ∪ {y} ∪ K0 is non-empty: agents ϕ,K0, y group and agents K1 group. We say that an agent is available for forming a coalition C if she does not worse off. ('no'⇒'no'): Let function t∗ : I → {0, 1} be such that subgraph G[∪i∈IVi,t∗ (i)] contains no clique of size k, and construct a coalition structure with no weakly blocking coalition. For every i ∈ I, we put all the inhibitors between Vi,0 and Vi,1 on Vi,1-t∗ (i) (so that no circuit game L generates a weakly blocking coalition). Hence, only agents Figure 2: FromMINMAXCLIQUE to coHG/E/SC/EXIST: The corresponding graph GF⊥ specified above. ![Image](https://ijcai.org/proceedings/2017/fulltext/51/image_000003_ad671b4d90323eb0d3be442769490a168028a2f1dd0467b8c400df880a642f54.png) ∪i∈IVi,t∗ (i) are available for grouping with fulcrum-agent ϕ, but never in a clique larger that k - 1 (based on the premise). Therefore, by grouping agents ϕ, y, and K0 into one coalition, fulcrum-agent ϕ would worse off by deviating within ∪i∈IVi,t∗ (i). To conclude, by forming singletons with each agent in ∪i∈IVi,t∗ (i) and a coalition with agents K1, this coalition structure admits no weakly blocking coalition. ('yes'⇒'yes'): Assume that for every function t : I → {0, 1}, subgraph G[∪i∈IVi,t(i)] contains a clique of size k, and for the sake of contradiction let coalition structure π admit no weakly blocking coalition. Then there exists t(π) such that for every i ∈ I, all the inhibitors between Vi,0 and Vi,1 go to side 1-t(π) (i), or otherwise circuit games Li,0 and Li,1 contain a weakly blocking coalition. Consequently, fulcrumagent ϕ is not grouped with agents y and K0, but at least with a k-sized clique in GF⊥[∪i∈IVi,t(π) (i)] that exists based on the premise. Then the game on agents K1 ∪ {y} ∪ K0 is isolated. However, its strict core is empty, a contradiction. Inhibitors pair every vertex x in set Vi,0 with a vertex y in Vi,1. Their construction is depicted in graph GF⊥ below. ![Image](https://ijcai.org/proceedings/2017/fulltext/51/image_000004_a4a576e679b72cec34b220f408f4ede9a6e690de208472d837f6586a27e9c673.png) Crucially, each inhibitor is an enemy of the other agents, preventing x xor y to participate in the game. We show that inhibitor-clique {a, c, b} is either grouped with agent x xor agent y, and if it is grouped with agent x (resp. y), then agent x (resp. y) prefers to stay with the inhibitor upon every other coalition, since she has two friends in it. If agent c joins x, then a and b follow. Similarly, if c joins y, then b and a follow. Finally, if c is not grouped with x or y, then a and b join x and y, and c is interested in joining x or y, and a and b follow c. Each circuit game Li,j is connected to the agents of set Vi,j and constructed so that its strict core is non-empty if and only if "every agent in Vi,j is inhibited, or none is inhibited." This construction relies on a combination of smaller gadget games that model any logical gate under the interpretation where an agent available amounts to Boolean true. Gates NOT, OR, and DUPLIC with inputs x and outputs y (Fig 3) are sufficient to obtain a Boolean algebra. In gate NOT, the availability of x makes y non-available. In gate OR, the availability of x1 or x2 makes α non-available and y available. In gate DUPLIC, the availability of x is duplicated into y1 and y2. Note that gate AND(x1, x2) equals NOT(OR(NOT(x1),NOT(x2))), and gates OR and AND generalize from binary operators to multinary ones. By combining these gadget games, circuit game Li,j is constructed to obtain formula (∧x∈Vi,j x) ∨ (∧x∈Vi,j ¬x) as the following availability of output agent y: "everyone or no-one" (Fig. 4). To ensure that the entire game (of the reduction) is not altered by the agents of the logic game, every agent x in set Vi,j is separated from Li,j by a (double negation) gate where agent s is mutually neutral with every other agent; when x is available, both x and s can join the fulcrum. Figure 3: Gates NOT, OR and DUPLIC (inputs x, outputs y) ![Image](https://ijcai.org/proceedings/2017/fulltext/51/image_000005_0834d1c7829ea7ef79a597df562d8ca31b050001ec75c7a4ea39099c24e2570b.png) Figure 4: Connections of circuit game Li,j ![Image](https://ijcai.org/proceedings/2017/fulltext/51/image_000006_ee9363017039e28c4c5769e488f41e1ad311866fa76848fa62182a4d37f05137.png) ![Image](https://ijcai.org/proceedings/2017/fulltext/51/image_000007_5c50876cabed398dcc8e9f8cd0e28b77751f5e39cce5584bfdf6c47700e6a87e.png) Finally, the validity of the formula and the availability of agent y make z non-available for u and v who remain stable singletons. Otherwise, the game on agents {u, z, v} is isolated and has an empty strict core. To summarize, the circuit game has a non-empty strict core if and only if formula (∧x∈Vi,j x) ∨ (∧x∈Vi,j ¬x) holds. ## 6 Extension to Enemies Aversion and the Core In this section, under enemies aversion, we extend the results on complexity of existence obtained for the strict core to the core. First, the complexity of verification was addressed in the proof of (Th.1) [Sung and Dimitrov, 2007]: Theorem 5 ([Sung and Dimitrov, 2007], Proof of Th.1). Problem HG/E/C/VERIF is coNP-complete. There might be no polynomial-time verification procedure for the existence problem. Indeed, we show the following: Theorem 6. Problem HG/E/C/EXIST is NP NP -complete. Proof (sketch). First, problem HG/E/C/EXIST is in NP NP , since, for 'yes'-instances, a coalition structure π in the core is a certificate that can be verified easily using an NP-oracle. As previously, we prove that HG/E/C/EXIST is NP NP - hard by showing that MINMAXCLIQUE can be reduced to coHG/E/C/EXIST. The proof follows the same ideas developed for the strict core, relying on inhibitors and circuit games. However, due to the structure of circuit games here, we need to introduce vertex-cliques (resp. a fulcrum-clique) instead of vertex-agents (resp. a fulcrum-agent), as follows: (1) First, for each vertex x in V we introduce a vertexclique, Kx, that contains k′ mutual friends (k′ is specified below). For all edges {x, y} in graph G = (V,A), we introduce mutual neutral arcs between each x′ ∈ Kx and y′ ∈ Ky. (2) Second, we introduce a generalization of Example 2 with five cliques {C0, . . . ,C4}, each of which contains (k′′ - 1) mutual friends (k′′ is specified below). (3) Third, we introduce a fulcrum-clique of k′′ mutual friends, Kϕ. Each agent in Kϕ is a mutual friend with each agent in C0 and with everyone in set V . (4) Finally, inhibitors and circuit games (specified below) play the same role as for the strict core. Figure 5: Gates NOT, OR and DUPLIC (in: Kx, out: Ky) ![Image](https://ijcai.org/proceedings/2017/fulltext/51/image_000008_e4f538262e77e9d837d1288fbb235dfb2606d5601e833fdb4ef354b774023e24.png) The main argument for this reduction's validity is the same as for the strict core setting. Fulcrum-clique Kϕ is either grouped with C0 ((k′′ -1) friends) or with at least a k′′ -sized clique in V , in a core stable coalition. Therefore, we only present the inhibitors and the circuit games. An inhibitor is a clique that contains (k′′ + 1) mutual friends and pairs a vertex-clique Kx in Vi,0 with a vertexclique Ky in Vi,1. Each agent of the inhibitor-clique is a mutual friend with every agent in Kx and Ky. Thus, the inhibitor-clique either groups with Kx or Ky in a core stable coalition structure. If the inhibitor-clique is grouped with Kx (resp. Ky), then Kx (resp. Ky) prefers to stay with the inhibitor upon every other coalition. Each circuit game Li,j follows the same principle as in Theorem 4, relying on logic gates NOT, OR, and DUPLIC (Fig. 5) to obtain a Boolean algebra. However, in gate OR, we have to assume that Kx1 or Kx2 are two friends-cliques with identical size t, and we set the size of Kα and Ky to (t - 1). Then the availability of Kx1 or Kx2 makes Kα nonavailable and Ky available. In gate DUPLIC, assuming the size of Kx is t ≥ 3, we set the sizes of Kβ1 and Kβ2 to (t - 2), and the size of Ky1 and Ky2 to (t - 1). Then the availability of Kx is duplicated into Ky1 and Ky2 . As in Theorem 4, using these gates, circuit game Li,j can be constructed, and we connect its output to a specific instance of Example 2 with five cliques of size 3. Also, between each vertex-clique Kx and Li,j , we introduce a double negation, composed of a separating-clique of size k′ and a second clique of size (k′ - 1). To conclude, since the circuit game leads us to set k′ = 9, we set k′′ = 18k because the agents of the separating-clique have to be mutual friends with each agent of the fulcrum-clique to guarantee core stability. ## 7 On Friends Appreciation In this section, we consider hedonic games under friends appreciation. Even though with only friends and enemies the existence of a strict core stable coalition structure is guaranteed, Theorem 2 shows that the existence is not guaranteed with neutral agents. Furthermore, we show the following: Theorem 7. Problem HG/F/SC/VERIF is coNP-complete. Proof (sketch). Surprisingly, the same reduction as for Theorem 3 works with a slight modification: vertex-agents are neutral toward the fulcrum. Then the preferences of vertexagents and the fulcrum lie in P E ∩P F . Moreover, the clique of friends cannot be grouped with vertex-agents. Theorem 8. Problem HG/F/SC/EXIST is NP NP -complete. Proof (sketch). The proof follows a similar sketch as for the strict core and enemies aversion (i.e., a fulcrum-agent between MINMAXCLIQUE, inhibitors, circuit games and Example 3). However, Remark 1 does not hold with friends appreciation. However, we are still able to model gadget games and inhibitors. Here is the main idea for a construction: each agent can be forced to choose between two coalitions where her number of friends is the same but the number of enemies differ. Thus, she will prefer to be in the coalition with the lowest number of enemies if and only if it is available. Although these results show the extreme intractability of the strict core under friends appreciation, the complexitylandscape changes radically to easiness for the core: Theorem 9. Given an HG/F, (1) the existence of a core-stable coalition structure is guaranteed, and (2) it can be computed in polynomial-time as the strongly connected components of graph GF = (N, AF ). Proof. The idea of using strongly connected components is similar to a previous result with only friends and enemies [Dimitrov et al., 2006], which can be computed in time O(n2 ) [Tarjan, 1972]. We extend it to neutrals, with a much shorter proof. Let π = {C1, . . . ,Cm} be the coalition structure corresponding to a decomposition of graph GF = (N,AF ) into strongly connected components, and let us show that it is strict core stable. Since the condensation graph, where each Cj is contracted into one vertex, is a directed acyclic graph, it has at least one sink, which we call Cs. No subset Y ⊆ Cs can be part of any blocking coalition X ⊃ Y , since (if Y ⊂ Cs) at least one would loose friends or (if Y = Cs) one may gain enemies. By repeating this argument on the condensation graph from which Cs was removed, we obtain that no agent can be in a blocking coalition. ## 8 Conclusion We studied the computational complexity of coalitional stability in hedonic games under enemies aversion and friends appreciation, by introducing neutral agents. It was known that without neutral agents, coalitional stability is just NPhard, while in the very general ASHGs it is NP NP -complete, hence a computationally extremely hard requirement. Between these two models, to the best of our knowledge, our models are among the simplest cases of extreme intractability for coalitional stability in hedonic games. An interesting prospect is to explore assumptions that make verification tractable, in order to bring the existence problem to class NP. Also, we did not extend our results to if friend/enemy relations are symmetric. Furthermore, since very few algorithms and methods have been proposed to achieve coalitional stability, numerical experiments could be a good challenge. ## Acknowledgements This work was partially supported by JSPS KAKENHI Grant Number 17H00761 and 15H02751, and JST Strategic International Collaborative Research Program, SICORP. We are grateful to Takamasa Suzuki for his presence. ## References 1. [Aziz and Brandl, 2012] Haris Aziz and Florian Brandl. Ex- istence of stability in hedonic coalition formation games. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS- 2012), volume 2, pages 763-770, 2012. 2. [Aziz et al., 2014] Haris Aziz, Felix Brandt, and Paul Har- renstein. Fractional hedonic games. In Proceedings of the 13th International Conference on Autonomous Agents and Multi-agent Systems (AAMAS-2014), pages 5-12, 2014. 3. [Aziz et al., 2016] Haris Aziz, Paul Harrenstein, Jérôme Lang, and Michael Wooldridge. Boolean hedonic games. In Proceedings of the 15th International Conference on the Principles of Knowledge Representation and Reason- ing (KR-2016), pages 166-175, 2016. 4. [Ballester, 2004] Coralio Ballester. NP-completeness in he- donic games. Games and Economic Behavior, 49(1):1-30, 2004. 5. [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 Wel- fare, 26(2):421-433, 2006. 6. [Elkind and Wooldridge, 2009] Edith Elkind and Michael Wooldridge. Hedonic coalition nets. In Proceedings of the 8th International Conference on Autonomous Agents and Multi-agent Systems (AAMAS-2009), pages 417-424, 2009. 7. [Ko and Lin, 1995] Ker-I Ko and Chih-Long Lin. On the complexity of min-max optimization problems and their approximation. Nonconvex optimization and its applica- tions, 4:219-240, 1995. 8. [Lang et al., 2015] Jérôme Lang, Anja Rey, Jörg Rothe, Hilmar Schadrack, and Lena Schend. Representing and solving hedonic games with ordinal preferences and thresholds. In Proceedings of the 14th International Con- ference on Autonomous Agents and Multiagent Systems (AAMAS-2015), pages 1229-1237, 2015. 9. [Peters and Elkind, 2015] Dominik Peters and Edith Elkind. Simple causes of complexity in hedonic games. In Pro- ceedings of the 24th International Joint Conference on Ar- tificial Intelligence (IJCAI-2015), pages 617-623, 2015. 10. [Peters, 2015] Dominik Peters. Σ p 2 -complete problems on hedonic games. arXiv preprint arXiv:1509.02333, 2015. 11. [Peters, 2016] Dominik Peters. Graphical hedonic games of bounded treewidth. In Proceedings of the 30th AAAI Con- ference on Artificial Intelligence (AAAI-2016), pages 586- 593, 2016. 12. [Rey et al., 2016] Anja Rey, Jörg Rothe, Hilmar Schadrack, and Lena Schend. Toward the complexity of the exis- tence of wonderfully stable partitions and strictly core sta- ble coalition structures in enemy-oriented hedonic games. Annals of mathematics and artificial intelligence, 77(3- 4):317-333, 2016. 13. [Sung and Dimitrov, 2007] Shao Chin Sung and Dinko Dim- itrov. On core membership testing for hedonic coali- tion formation games. Operations Research Letters, 35(2):155-158, 2007. 14. [Tarjan, 1972] Robert Tarjan. Depth-first search and lin- ear graph algorithms. Society for Industrial and Applied Mathematics Journal on Computing, 1(2):146-160, 1972. 15. [Woeginger, 2013] Gerhard J. Woeginger. A hardness result for core stability in additive hedonic games. Mathematical Social Sciences, 65(2):101-104, 2013.