Paper deep dive
Control in Hedonic Games
Jiehua Chen, Jakob Guttmann, Merisa Mustajbašić, Sofia Simola
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 7/21/2026, 1:45:27 AM
Summary
This paper introduces and analyzes the computational complexity of control in hedonic games, where an external actor influences coalition formation by adding or deleting agents. The study focuses on three control goals: ensuring an agent is not alone (NA), ensuring a pair is together (PA), and forming a grand coalition (GR). These goals are examined under two preference models (friend-oriented and additive) and four stability concepts (individual rationality, individual stability, Nash stability, and core stability). The authors provide a complete complexity classification, revealing that adding agents can be tractable for certain goals, while deleting agents is often impossible (immune) or intractable.
Entities (19)
Relation Signals (17)
Merisa Mustajbašić → affiliatedwith → TU Wien
confidence 99% · affiliation institution TU Wien
Sofia Simola → affiliatedwith → TU Wien
confidence 99% · affiliation institution TU Wien
Jakob Guttmann → affiliatedwith → TU Wien
confidence 99% · affiliation institution TU Wien
Jiehua Chen → affiliatedwith → TU Wien
confidence 99% · affiliation institution TU Wien
Control in Hedonic Games → publishedin → AAMAS 2026
confidence 98% · Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026)
Control in Hedonic Games → analyzesfor → Friend-Oriented Preferences (FriHG)
confidence 95% · We analyze these problems for friend-oriented and additive preferences
Control in Hedonic Games → analyzesfor → Additive Preferences (AddHG)
confidence 95% · We analyze these problems for friend-oriented and additive preferences
Control in Hedonic Games → evaluatesunder → Individual Rationality (IR)
confidence 95% · under individual rationality, individual stability, Nash stability, and core stability.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We initiate the study of control in hedonic games, where an external actor influences coalition formation by adding or deleting agents. We consider three basic control goals (1) enforcing that an agent is not alone (NA); (2) enforcing that a pair of agents is in the same coalition (PA); (3) enforcing that all agents are in the same grand coalition (GR), combined with two control actions: adding agents (AddAg) or deleting agents (DelAg). We analyze these problems for friend-oriented and additive preferences under individual rationality, individual stability, Nash stability, and core stability. We provide a complete computational complexity classification for control in hedonic games.
Tags
Links
- Source: https://arxiv.org/abs/2602.18506v1
- Canonical: https://arxiv.org/abs/2602.18506v1
Trouble viewing inline? Open PDF directly →
Full Text
164,246 characters extracted from source content.
Expand or collapse full text
ifaamas [AAMAS ’26]Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026)May 25 – 29, 2026 Paphos, CyprusC. Amato, L. Dennis, V. Mascardi, J. Thangarajah (eds.) 2026 2026 Wien Wien Wien Wien Control in Hedonic Games Jiehua Chen jiehua.chen@ac.tuwien.ac.at , Jakob Guttmann e11810289@student.tuwien.ac.at , Merisa Mustajbašić e12450330@student.tuwien.ac.at and Sofia Simola ssimola@ac.tuwien.ac.at Abstract. We initiate the study of control in hedonic games, where an external actor influences coalition formation by adding or deleting agents. We consider three basic control goals (1) enforcing that an agent is not alone ( ); (2) enforcing that a pair of agents is in the same coalition ( ); (3) enforcing that all agents are in the same grand coalition ( ), combined with two control actions: adding agents ( ) or deleting agents ( ). We analyze these problems for friend-oriented and additive preferences under individual rationality, individual stability, Nash stability, and core stability. We provide a complete computational complexity classification for control in hedonic games. Key words and phrases: Hedonic Games, Control; Computational Social Choice; Additive Preferences; Friend-Oriented Preferences doi: WVYI7850 1. Introduction Hedonic games Drèze and Greenberg (1980) are coalition formation games where agents form coalitions based on their preferences over which coalition to join. The task is to partition agents into disjoint coalitions satisfying certain stability criteria. Typical stability criteria include individual rationality (no agent prefers being alone to his current coalition), individual stability (no agent prefers to join an existing coalition that would accept them), Nash stability (no agent can improve by unilaterally moving to another existing coalition), and core stability (no group of agents can all improve by forming a new coalition together). Since their introduction, hedonic games have become an important research topic in algorithmic game theory Chalkiadakis et al. (2011); Bullinger et al. (2016) and computational social choice Aziz and Savani (2016). Most research has focused on analyzing fixed hedonic games–proposing new stability concepts, investigating existential questions (does a stable partition exist?), and computational questions (verifying stability, finding stable partitions when they exist). Far less attention has been paid to how external influence–such as adding or deleting agents–can shape outcomes in hedonic games. Such external influence is formalized as control in voting Bartholdi I et al. (1992), where an external actor manipulates elections by adding or deleting voters or candidates. Control naturally arises in coalition formation settings where external actors shape outcomes: department chairs forming research collaborations, conference organizers balancing working groups, or managers assigning employees to project teams. In this paper, we introduce and perform a systematic study of control in hedonic games, where an external party influences outcomes by adding or deleting agents. We formalize control problems combining two actions: adding agents ( AddAg) or deleting agents ( DelAg), with three goals: ensuring a specific agent is not alone ( NA), ensuring a specific pair is together ( PA), or forming a grand coalition ( GR), all while reaching a stable partition. These goals capture common control scenarios: – NA: A company forms project teams. A new employee joins who has not built relationships yet. Without intervention, they might remain isolated and unassigned. The manager can hire another employee with complementary skills, making them willing to form a team together or more attractive to existing teams. – PA: The department chair wants two senior researchers to collaborate. A third, polarizing colleague, cannot work with one of them, which prevents a stable joint assignment. Reassigning this colleague to another project enables a mutually acceptable collaboration between the two senior researchers. – GR: Multiple small research labs work on similar problems but compete rather than collaborate. A funding agency wants to form a single large consortium for a major grant. The agency can offer funding for postdocs who would only join if everyone collaborates, forcing consolidation into a grand coalition. We analyze these problems for friend-oriented (FriHG) and additive (AddHG) preferences under four stability concepts: individual rationality ( IR), individual stability ( IS), Nash stability ( NS), and core stability ( CS). Our contributions. Besides introducing the control model, we provide a comprehensive complexity picture of control in hedonic games. We summarize the key findings below: – We provide a few polynomial-time algorithms for achieving NA and PA by adding agents in the friend-oriented preference setting. The algorithms exploit specific graph structures: For IR (and IS), we reduce to finding minimum-weight paths and cycles in arc-weighted directed graphs; For CS, we reduce to finding minimum-weight subgraphs in Steiner networks. These positive results show that targeted control goals (ensuring individuals are not isolated or specific pairs collaborate) are computationally tractable via agent addition. – We discover that for most stability concepts, achieving NA or PA by deleting agents is impossible–the problems are immune; see Definition 6. This asymmetry between addition and deletion is somewhat surprising: You can add agents to force desired coalitions, but removing agents rarely helps. – For all intractable ( NP-hard, coNP-hard, or Σ2P ^P_2-hard) control problems, the base problem–verifying whether the goal already holds without any control–is already intractable. This provides a natural barrier against control: If determining whether control is necessary is already hard, executing control attacks is not easier. – For the control goal GR, the problem is mostly polynomial-time solvable for constant number k of control actions (i.e., in XP wrt. k). Interestingly, the complexity picture inverts between preference types: GR is more resistant to control than NA and PA in FriHG, but less resistant in AddHG. This suggests grand coalition formation has different structural properties than targeted pair or individual goals. Our main results regarding the computational complexity are summarized in Table 1. Table 1. Complexity results of control in hedonic games, by either adding ( AddAg) or deleting agents ( DelAg), with the goals of ensuring that either a given agent is not alone ( NA), or a pair of agents is in the same coalition ( PA), or all agents are in the grand coalition ( GR). We study two compact preference representations–additive preferences (AddHG) or friend-oriented preferences in the friends-and-enemies model (FriHG)–and four stability concepts–individual rationality ( IR), individual stability ( IS), Nash stability ( NS), and core stability ( CS). All hardness results hold even if no control action is allowed (i.e., k=0k=0). Problems with tag “DAG” (resp. “SYM”) means that the corresponding hardness results hold even if the preference graph is a DAG (resp. symmetric). Entries labeled “ P” denote polynomial-time solvability, “ NPc” NP-completeness, and “Σ2Pc ^P_2c” Σ2P ^P_2-completeness. “ imm” means immune and “⋆ imm ” means that it is immune while deciding yes-instances with k=0k=0 remains NP-hard. [] W[2]h and XP are with respect to the budget k. “ never” means that the given instance is always a no instance. Results in bold are our contributions. HG NA- AddAg NA- DelAg PA- AddAg PA- DelAg GR- AddAg GR- DelAg FriHG- IR, IS, CSSYM P [T10,T12] imm [Proposition 8] P [T10,T12] imm [Proposition 8] [] W[2]h, XP [Theorem 13] P [Proposition 14] FriHG- NS NPc Brandt et al. (2024),[Observation 5] NPc Brandt et al. (2024),[Observation 5] NPc Brandt et al. (2024),[Observation 5] NPc Brandt et al. (2024),[Observation 5] [] W[2]h, XP [Theorem 13] P [Proposition 14] SYM P [Proposition 11] imm [Proposition 8] P [Proposition 11] imm [Proposition 8] [] W[2]h, XP [Theorem 13] P [Proposition 14] FriHG- IR, IS, NS, CS DAG never [Observation 8] never [Observation 8] never [Observation 8] never [Observation 8] never [Observation 8] never [Observation 8] AddHG- IR NPc [Theorem 15] ⋆ imm [Proposition 9] NPc [T19,T20] ⋆ imm [Proposition 9] [] W[2]h, XP [T21,T22] [] W[2]h, XP [T21,T22] DAG/ SYM P [Proposition 16] imm [Proposition 9] NPc [T19,T20] ⋆ imm [Proposition 9] [] W[2]h, XP [T21,T22] [] W[2]h, XP [T21,T22] AddHG- IS, NS NPc Sung and Dimitrov (2010),[Observation 5] NPc Sung and Dimitrov (2010),[Observation 5] NPc Sung and Dimitrov (2010),[Observation 5] NPc Sung and Dimitrov (2010),[Observation 5] [] W[2]h, XP [T21,T22] [] W[2]h, XP [T21,T22] DAG/ SYM NPc [T17,T18] NPc [T17,T18] NPc [T17,T18] NPc [T17,T18] [] W[2]h, XP [T21,T22] [] W[2]h, XP [T21,T22] AddHG- CSSYM Σ2Pc ^P_2c Woeginger (2013b); Peters (2017),[Observation 5] Σ2Pc ^P_2c Woeginger (2013b); Peters (2017),[Observation 5] Σ2Pc ^P_2c Woeginger (2013b); Peters (2017),[Observation 5] Σ2Pc ^P_2c Woeginger (2013b); Peters (2017),[Observation 5] coNPc [Theorem 23] coNPc [Theorem 23] DAG P [Proposition 16] imm [Proposition 9] NPc [Theorem 19] ⋆ imm [Proposition 9] [] W[2]h, XP [Theorem 21] [] W[2]h, XP [Theorem 21] Related work. Hedonic games were first conceptualized by Drèze and Greenberg (1980) and formally reintroduced by Banerjee et al. (2001) and Bogomolnaia and Jackson (2002). They independently defined hedonic coalition formation games and analyzed fundamental stability concepts such as the core and Nash stability for additive preferences. Dimitrov et al. (2006) introduced the friends-and-enemies model. Woeginger (2013a) surveyed different preference models for core stability. Brandt et al. (2024) demonstrated that most stability-related problems remain intractable even under fairly restrictive preference assumptions. For a comprehensive overview of complexity results regarding verifying whether a partition is stable and determining the existence of stable partitions, we refer to a recent survey by Chen et al. (2025a). To our knowledge, no prior work has studied control in hedonic games. Bartholdi I et al. (1992) introduced electoral control (adding or deleting voters or candidates to change the election winner) into voting theory. Hemaspaandra et al. (2007) explored both constructive and destructive control in elections under various voting rules, showing that many forms of control can be computationally difficult (a desirable property for election security), and providing a template for defining control actions in a precise algorithmic way; also see the book chapter by Faliszewski and Rothe (2016) for more references on voting control. Boehmer et al. (2021) first studied control in matching markets, systematically exploring external control in Stable Marriage by defining a range of manipulative actions including adding or deleting agents. Chen and Schlotter (2025) recently provided a comprehensive complexity overview of adding or removing agents in both Stable Marriage and Stable Roommates settings to achieve certain outcomes (such as guaranteeing the existence of a stable matching or ensuring a particular pair is matched). For control problems in other domains, we refer to a recent survey by Chen et al. (2025b). Outline of the paper. In Section 2, we define hedonic games, the stability concepts we consider, and our control problems. In Section 3, we provide some structural results for hedonic games and our control problems. In Sections 4 and 5, we investigate the complexity for the friend-oriented preference and additive preference settings, respectively. For both sections, we first consider the control goal of NA, then PA, and finally GR. We conclude with a discussion on potential areas for future research in Section 6. Proofs and statements marked with (⋆ ) are deferred to the Appendix. 2. Preliminaries Given an integer t, let [t][t] denote the set 1,2,…,t\1,2,…,t\. Given a directed graph G and a vertex v∈V(G)v∈ V(G), let +(v)N^+_G(v) and −(v)N^-_G(v) denote the out- and in-neighborhood of v, respectively. Given a directed graph G=(V,A)G=(V,A) and a subset V′⊆V V of vertices, a subgraph by V′V , written as [V′]G[V ], is a subgraph (V′,A′)(V ,A ) of G where A′=a′∈A∣a′⊆V′A =\a ∈ A a V \. Let V be a finite set of n agents. A is a non-empty subset of V. We call the entire agent set V the coalition. The input of a hedonic game is a tuple (,(⪰i)i∈)(V,( _i)_i ), where V is the agent set, and each agent i∈i has a preference order ⪰i _i over all coalitions that contain ii. Each preference order is a weak order (i.e., complete, reflexive, and transitive). For two coalitions S and T containing ii, we say that agent ii prefers S to T if S⪰iTS _iT; ii ( ) S to T (written as ≻iTS _iT) if S⪰iTS _iT, but T⋡iST _iS; ii is between S and T (written as ∼iTS _iT) if S⪰iTS _iT and T⪰iST _iS. A Π of V is a division of V into disjoint coalitions, i.e., the coalitions in Π are pairwise disjoint and ⋃A∈ΠA= _A∈ A=V. Given a partition Π of V and an agent i∈i , let Π(i) (i) denote the coalition which contains ii. We also call the partition where every agent is in the grand coalition the coalition partition. Compact preference representations of hedonic games. In this paper, we focus on two compact presentation models that can be encoded polynomially in the number of agents. The first setting is called hedonic games with separable preferences (AddHG). In AddHG, every agent only needs to express a cardinal utility to every other agent. The second setting is simple restriction of the first setting and is called hedonic games with -oriented preferences (FriHG). In FriHG, every agent regards every other agent either as a or an such that he prefers coalitions with more friends to those with less friends. Definition 0 (AddHG Banerjee et al. (2001)). Let V be a set of agents. The input of AddHG is a tuple (,(μi)i∈)(V,( _i)_i ), where every agent i∈i has a utility function μi:→ℝ _i → R such that for each two coalitions S and T containing ii, agent ii weakly prefers S to T if ∑j∈Sμi(j)≥∑j∈Tμi(j) _j∈ S _i(j)≥ _j∈ T _i(j). We assume μi(i)=0 _i(i)=0. The utility functions can also be compactly represented by a graph. It is a tuple (,ω)(G,ω), where G is a directed graph on the agent set and ω is an arc-weighting function. For each two agents ii and jj there is an arc (i,j)(i,j) if and only if the utility of ii to jj is non-zero. The weight of this arc is equal to the non-zero utility ω(i,j)=μi(j)ω(i,j)= _i(j). Definition 0 (FriHG Dimitrov et al. (2006)). The input of FriHG is a directed graph ℱF where every vertex corresponds to an agent such that every agent ii considers another agent jj as a if and only if there is an arc from ii to jj; otherwise ii considers jj as an . Graph ℱF is also called a graph. For each agent i∈i and each two coalitions S and T containing ii, agent i prefers S to T if (i) either |Nℱ+(i)∩S|>|Nℱ+(i)∩T||N^+_F(i)∩ S|>|N^+_F(i)∩ T|, or (i) |Nℱ+(i)∩S|=|Nℱ+(i)∩T||N^+_F(i)∩ S|=|N^+_F(i)∩ T| and |S∖Nℱ+(i)|≤|T∖Nℱ+(i)||S N^+_F(i)|≤|T N^+_F(i)|. Remark 0. Note that FriHG is a simple restriction of AddHG: Set μx(y)=n _x(y)=n if (x,y)(x,y) is an arc in ℱF, and μx(y)=−1 _x(y)=-1 otherwise. We say that an instance of AddHG (resp. FriHG) is a DAG if the preference graph (resp. friendship graph) is acyclic. Correspondingly, we say that it has f feedback arcs if the graph can be turned acyclic by deleting at most f arcs. Further, we say that AddHG is if for every pair of agents i,ji,j it holds that μi(j)=μj(i) _i(j)= _j(i). Similarly, we say that an instance of FriHG is if the friendship graph ℱF is symmetric. In these cases we can assume that the preference graph (resp. friendship graph) is undirected. Relevant stability concepts. In this paper, we study four relevant stability concepts. Definition 0. Let Π be a partition of V. A coalition B is a partition Π if every agent i∈Bi∈ B prefers B to Π(i) (i). An agent ii and a coalition B form a tuple if ii prefers B∪iB∪\i\ to Π(i) (i) and each agent j∈Bj∈ B weakly prefers B∪iB∪\i\ to Π(j) (j). – Π is rational ( IR) if no agent ii prefers i\i\ to Π(i) (i). If ii prefers i\i\ to Π(i) (i), we say he wishes to from Π . – Π is stable ( NS) if no agent ii and coalition B∈Π∪∅B∈ ∪\ \ exist such that ii strictly prefers B∪iB∪\i\ to his coalition Π(i) (i). – Π is stable ( IS) if no agent ii and coalition B∈Π∪∅B∈ ∪\ \ can form a blocking tuple. – Π is stable ( CS) if no coalition is blocking Π . By definition, the stability concepts satisfy the following: Observation 1. An NS partition is IS. An IS partition is IR. A CS partition is IR. Our control problems and their complexity upper bounds. In this paper, we study three different control goals (1) enforcing that an agent is not alone ( NA); (2) enforcing that a pair of agents is in the same coalition ( PA); (3) enforcing that all agents are in the same grand coalition ( GR). Moreover, we study two possible control actions we can use to obtain the control goals: adding agents ( AddAg) or deleting agents ( DelAg). Example 0. Let U=x=u1,u2,u3U=\x=u_1,u_2,u_3\ and W=w1,w2W=\w_1,w_2\, where U is a set of consisting of three original agents while W consisting of two additional agents, respectively. The preference graph of the agents U∪WU∪ W is depicted below. Throughout, we use blue dotted line to indicate friendship relation, and red solid line enemy relation. u1u_1u2u_2u3u_3w1w_1w2w_2−1-1−2-22211−1-111−1-111 Our special agent is x=u1x=u_1. In the original instance, consisting of only U, agent u1u_1 must be alone in an IR partition since he dislikes u2u_2 but u3u_3 dislikes him. One can verify that it is impossible to make u1u_1 not alone by deleting agents since otherwise the new IR partition augmented with the deleted agents in singletons would yield an IR partition for the original instance. We can add agent w2w_2 (not w1w_1) to the original instance to obtain an IR partition, where every agent is in the same grand coalition. Now we are ready to formally define our control problems (as decision problems) HG- S-G-A, where ∈,,, S∈\ IR, IS, NS, CS\ denotes one of the four stability concepts, ∈,,G∈\ [rgb]0.6,0,0 [named]pgfstrokecolorrgb0.6,0,0 NA, [rgb]0,0,0.7 [named]pgfstrokecolorrgb0,0,0.7 PA, [rgb]0,0.5,0 [named]pgfstrokecolorrgb0,0.5,0 GR\ one of the three control goals, and ∈,A∈\ AddAg, DelAg\ one of the two control actions, respectively. The problem of control by adding agents is defined as follows: HG- S- NA- AddAg (resp. HG- S- PA- AddAg) Input: A hedonic game instance (=∪,(⪰i)i∈)(V=U ,( _i)_i ), a selected agent x∈x (resp. selected agent pair x,y⊆\x,y\ ), and a non-negative value k∈ℕ∪0k∈ N∪\0\. Question: Is there a subset ′⊆W of size |′|≤k|W |≤ k such that ∪′U admits an S-partition Π where Π(x)≠x (x)≠\x\ (resp. Π(x)=Π(y) (x)= (y))? For the control goal GR, the input only consists of the hedonic game instance and a budget: HG- S- GR- AddAg Input: A hedonic game instance (=∪,(⪰i)i∈)(V=U ,( _i)_i ) and a non-negative value k∈ℕ∪0k∈ N∪\0\. Question: Is there a subset ′⊆W of size |′|≤k|W |≤ k such that the partition consisting of the grand coalition ∪′U is S? In the above, we call the set U the agents and the set W the agents. Similarly, we define the problems for the setting where we can delete agents. HG- S- NA- DelAg (resp. HG- S- PA- DelAg) Input: A hedonic game instance (,(⪰i)i∈)(U,( _i)_i ), a selected agent x∈x (resp. selected agent pair x,y⊆\x,y\ ), and a non-negative value k∈ℕ∪0k∈ N∪\0\. Question: Is there a subset ′⊆U of size |′|≤k|U |≤ k such that ∖′U admits an S-partition Π where Π(x)≠x (x)≠\x\ (resp. Π(x)=Π(y) (x)= (y))? HG- S- GR- DelAg Input: A hedonic game instance (,(⪰i)i∈)(U,( _i)_i ) and a non-negative value k∈ℕ∪0k∈ N∪\0\. Question: Is there a subset ′⊆U of size |′|≤k|U |≤ k such that the partition consisting of the grand coalition ∖′U is S? If the hedonic game is restricted to be AddHG or FriHG, we replace the prefix HG with AddHG or FriHG. To classify cases where control is impossible, we define the following. Definition 0 (immune and never). We say a hedonic game control problem is if for every No-instance with k=0k=0, it remains a No-instance even if we set k=∞k=∞. We say that the problem is if all instances containing at least two agents are No-instances. Clearly, an instance with the control goal NA with one agent overall is always a No-instance, and an instance with the control goal PA contains at least two agents by definition. On the other hand, an instance with the control goal GR that contains one agent is trivially a Yes-instance. It is known that for both preference settings, one can check in polynomial time whether a given partition is IR, IS, or NS. However, the verification problem for CS is coNP-complete Chen et al. (2023). This immediately yields the following complexity upper bounds for our control problems. Observation 2. For preference model ∈AddHG M∈\ AddHG, FriHG FriHG\, control goal ∈,,G∈\ [rgb]0.6,0,0 [named]pgfstrokecolorrgb0.6,0,0 NA, [rgb]0,0,0.7 [named]pgfstrokecolorrgb0,0,0.7 PA, [rgb]0,0.5,0 [named]pgfstrokecolorrgb0,0.5,0 GR\, and control action ∈,A∈\ AddAg, DelAg\, the first three sets of problems M- IR-G-A, M- IS-G-A, and M- NS-G-A are in NP, while the problems M- CS- NA-A and M- CS- PA-A are in Σ2P ^P_2, and the problem M- CS- GR-A is in coNP. [] W[2] and XP. In this paper, we prove that several problems are [] W[2]-hard (resp. in XP) with respect to a parameter p. [] W[2]-hardness is shown via a reduction from a [] W[2]-hard problem Q (parameter q) running in time f(q)⋅|IQ|O(1)f(q)·|I_Q|^O(1) and producing an instance with parameter p≤g(q)p≤ g(q), for computable f,gf,g. Thus, it is unlikely that the problems are fixed-parameter tractable (FPT), i.e., solvable in time f′(p)⋅|I|O(1)f (p)·|I|^O(1) for computable f′f , unless =[] FPT= W[2]. Membership in XP wrt. p means solvability in time |I|h(p)|I|^h(p) for some computable h (equivalently, polynomial time for every constant p). If a problem remains NP-hard for some fixed constant value of p, then it is not in XP wrt. p, unless = P= NP. See Niedermeier (2006); Cygan et al. (2015) for details. 3. Structural Observations In this section, we collect some useful structural properties that may be of independent interest. Relations among the stability concepts. The first two observations describe two cases when a more stringent stability concept is equivalent to IR. This is useful in searching for both algorithms and hardness results. The first observation follows directly from definition. Observation 3. For every ∈, S∈\ NS, IS\, the grand coalition partition is S if and only if it is IR. Next, we observe that if the preference graph is a DAG, the two stability concepts IR and CS coincide. Observation 4. For every instance of AddHG with an acyclic preference graph, a partition is CS if and only if it is IR. Proof. By Observation 1, it suffices to show that IR implies CS. Suppose, for the sake of contradiction, that Π is IR but not CS. Let B be a blocking coalition with at least two agents. Since the preference graph is acyclic, one agent t∈Bt∈ B is a sink in the preference graph induced by B. Such a sink t has zero utility towards B, but has utility at least zero towards Π(t) (t), since Π is IR. Thus, agent t has no incentive to deviate to B, a contradiction. ∎ The next lemma shows that under the friend-oriented model and for the control goal PA, the existence questions for IR and IS are essentially the same. Lemma 0 (⋆ ). Let I=(,ℱ)I=(V,F) be a FriHG-instance, and xx and yy two agents in V. From each IR partition Π with Π(x)=Π(y) (x)= (y), one can construct in polynomial time an IS partition Π′ with Π′(x)=Π′(y) (x)= (y). Proof sketch.. The idea is to start with an IR partition where xx and yy are in the same coalition, say C, and merge it with all strongly connected components in ℱF. We then repeatedly add agents to C whenever they can reach some agent in C. All remaining agents will be in their own singleton coalitions. ∎ Influence of the control goals on the complexity. The next result implies that enforcing the control goal NA or PA will not help in lowering the complexity if the underlying problem of determining the existence of a stable partition is hard. Observation 5 (⋆ ). For every ∈AddHG M∈\ AddHG, FriHG FriHG\ and ∈ S∈\ IR, ,, NS, IS, CS\ if it is Σ2P ^P_2-hard (resp. NP-hard) to determine the existence of an S-partition under preference representation M, then so is M- S-G-A for every control goal ∈,G∈\ [rgb]0.6,0,0 [named]pgfstrokecolorrgb0.6,0,0 NA, [rgb]0,0,0.7 [named]pgfstrokecolorrgb0,0,0.7 PA\, control action ∈,A∈\ AddAg, DelAg\, even when k=0k=0. The same implication holds even when the preferences are symmetric. Proof sketch.. Add two additional agents x,y\x,y\ who have positive utility towards each other and negative to all other agents. They will not affect the stability of the rest of the structure. ∎ The next result allows us to focus on the control goal PA when searching for efficient algorithms for the goal NA. Observation 6 (⋆ ). For every ∈AddHG,FriHG M∈\ AddHG, FriHG\, ∈, S∈\ IR, NS, , IS, CS\, and ∈,A∈\ AddAg, DelAg\, if M- S- PA-A is polynomial-time solvable, then so is M- S- NA-A. Proof sketch. We guess the other agent y∈(∪y∈(U ) with whom x should be paired with. If there is no y such that M- S- PA-A is a Yes-instance, x will be always alone. ∎ Next, we state a well-known tight relation between the coalitions in a CS partition and the strongly connected components of the friendship graph, which is very useful for the PA goal and CS stability. Observation 7 (Dimitrov et al. (2006); Woeginger (2013a),⋆ ). For every FriHG-instance and two agents xx and yy, there is a core stable partition Π such that x and y belong to the same coalition if and only if they belong to the same strongly connected component. Immune cases. We close this section by summarizing cases when control is immune. Proposition 0. For each stability concept ∈,, S∈\ IR, IS, CS\ and each control goal ∈,G∈\ [rgb]0.6,0,0 [named]pgfstrokecolorrgb0.6,0,0 NA, [rgb]0,0,0.7 [named]pgfstrokecolorrgb0,0,0.7 PA\, FriHG- S-G- DelAg is immune. Under symmetric preferences FriHG- NS- NA- DelAg and FriHG- NS- PA- DelAg are immune. Proof. First observe that if it is possible to delete some agents to have an IR-partition such that x is not alone (resp. x and y are in the same coalition), then adding back the deleted agents each as a singleton coalition would be an IR-partition with the same goal as well. By Lemma 7, this result extends to IS as well. By Observation 7, if it is possible to delete some agents to have a CS-partition such that x is not alone (resp. x and y are in the same coalition), then x must be part of a connected component of size at least two (resp. x and y are part of the same strongly connected component) in the friendship graph of the remaining agents. If the agents are connected, they are also connected after adding back the agents. By Observation 7, there is then a CS partition of the original agent set such that x is not alone (resp. x and y are together). If it is possible to delete some agents to have a NS partition such that x is not alone (resp. x and y are in the same coalition), then x must have a friend (resp. x and y both have a friend). Let us now add back all the removed agents. Consider the partition in which all agents with degree at least one are placed in the same big coalition, while all remaining agents form singleton coalitions. This partition is NS. Since preferences are symmetric, no agent in the big coalition is friends with the singletons, and since every agent in the big coalition has a friend within that coalition, he prefers it to being alone. Since x has a friend (resp. x and y have a friend) he (resp. they) must be in the big coalition. ∎ DAGs in FriHG are very restrictive. The IR partition is unique and no two agents are together in it. Observation 8 (⋆ ). For FriHG-instances with acyclic friendship graph, the only partition that may be stable for S∈,,,S∈\ IR, IS, NS, CS\ consists of every agent being in a singleton coalition. Proposition 0. For control goal ∈,G∈\ [rgb]0.6,0,0 [named]pgfstrokecolorrgb0.6,0,0 NA, [rgb]0,0,0.7 [named]pgfstrokecolorrgb0,0,0.7 PA\, AddHG- IR-G- DelAg is immune. Proof. If it would be possible to delete some agents to have an IR-partition such that x is not alone (resp. x and y are in the same coalition), then adding back the deleted agents each as a singleton coalition would be an IR-partition with the same goal as well. ∎ 4. Friend-Oriented Preferences In this section, we discuss the results relating to FriHG. For the control goals NA and PA, we discover that IR, IS, and CS are all polynomial-time solvable for the control action AddAg: These stability concepts require certain friendship structures and finding a minimum number of agents to add to realize those can be done in polynomial time. In Proposition 8 we saw that these stability concepts were also immune to the control action DelAg. For NS, on the other hand, FriHG- NS-G-A is NP-hard for every ∈,,∈,G∈\ [rgb]0.6,0,0 [named]pgfstrokecolorrgb0.6,0,0 NA, [rgb]0,0,0.7 [named]pgfstrokecolorrgb0,0,0.7 PA\,A∈\ AddAg, DelAg\ even when k=0k=0 by a result from Brandt et al. (2024). We however discover that symmetric preferences make the problems tractable. Finally, we look into enforcing that the grand coalition partition is stable ( GR) and see that regardless of the stability concept, obtaining grand coalition through agent deletion is computationally easier than through agent addition. We start the section by presenting an algorithm that solves FriHG- IR- PA- AddAg. Theorem 10 (⋆ ). For each stability concept ∈, S∈\ IR, IS\ and each control goal ∈,G∈\ [rgb]0.6,0,0 [named]pgfstrokecolorrgb0.6,0,0 NA, [rgb]0,0,0.7 [named]pgfstrokecolorrgb0,0,0.7 PA\, FriHG- S-G- AddAg is polynomial-time solvable. Proof Sketch. xxy yyyx xx xy yx xy y Figure 1. The three possible substructures for an IR coalition containing xx and yy. The arcs indicate paths of varied lengths. Structure on left corresponds to line 1, middle to line 1, and right to line 1. Input: (=∪,ℱ=(∪,),x,y,k)(V=U ,F=(U ,A),x,y,k) 1 foreach (i,j)∈(i,j) do ω((i,j))←1, if i∈0, otherwise.ω((i,j))← cases1,& if i \\ 0,& otherwise. cases; 2 3foreach i,j∈i,j do 4 ωP(i,j)←ω^P(i,j)← weight of a min-weight path from ii to jj. 5 6foreach i∈i do ωC(i)←ω^C(i)← weight of a min-weight non-trivial cycle containing ii.; 7 8foreach ^x,^y∈ x, y do 9 if ωP(x,^y)+ωP(y,^y)+ωP(^y,^x)+ωC(^x)≤kω^P(x, y)+ω^P(y, y)+ω^P( y, x)+ω^C( x)≤ k then 10 return yes 11 12 if ωP(x,^x)+ωP(y,^y)+ωP(^x,^y)+ωP(^y,^x)≤kω^P(x, x)+ω^P(y, y)+ω^P( x, y)+ω^P( y, x)≤ k and ^x≠^y x≠ y then return yes ; 13 14 if ωP(x,^x)+ωP(y,^y)+ωC(^x)+ωC(^y)≤kω^P(x, x)+ω^P(y, y)+ω^C( x)+ω^C( y)≤ k then 15 return yes 16 17return no Algorithm 1 Algorithm for FriHG- IR-PA- AddAg. The idea is that a coalition containing both xx and yy, which is part of an IR partition, must contain one of three possible structures, which we illustrate in Figure 1. Any agent who is part of an IR partition must be part of a “ρ-shaped” subgraph (Galbraith, 2012, Chapter 14), that is, a graph that consists of a directed cycle of length at least two and a path (possibly of length zero) that reaches a vertex in it. This is a consequence of every agent obtaining a friend in an IR coalition of size at least two: If we start from an agent and follow a friendship path, we must eventually encounter an agent we have already seen. Since xx and yy are both a part of an IR coalition, they both must be a part of a “ρ-shaped” subgraph. There are three ways in which they can intersect, as shown in Figure 1. We show that these structures can be found in polynomial time by combining with finding minimum-weight paths. The algorithm is in Algorithm 1. In the algorithm we construct an arc-weight function ω for ℱF based on whether an arc starts with an agent in W or not. We compute the all-pair minimum-weight paths on (ℱ,ω)(F,ω) in polynomial time using Floyd-Warshall Floyd (1962) or some other algorithm. While running the algorithm, we also store, for each agent, an extra entry that records the minimum-weight path from the agent to himself of length at least one, i.e., the minimum-weight non-trivial cycle containing the agent. Then, we use those paths and cycles to search for the structures shown in Figure 1. By Lemma 7, this algorithm can also be used to solve FriHG- IS- PA- AddAg. By Observation 6, we then can solve the remaining FriHG- IR- NA- AddAg and FriHG- IS- NA- AddAg. However, the latter two problems can be solved more efficiently by searching for a single “ρ-shaped” subgraph containing xx. ∎ Brandt et al. (2024) show that determining the existence of an NS partition is NP-hard for FriHG, and thus FriHG- NS-G-A is NP-hard for every ∈,,∈,A∈\ AddAg, DelAg\,G∈\ [rgb]0.6,0,0 [named]pgfstrokecolorrgb0.6,0,0 NA, [rgb]0,0,0.7 [named]pgfstrokecolorrgb0,0,0.7 PA\ by Observation 5. Moreover, if an instance of FriHG is a DAG, then by Observation 8 we cannot hope to have any pair of agents in the same coalition in a stable partition. However, we obtain a non-trivial–although simple–algorithm when the preferences are symmetric for adding agents, whereas deleting agents is immune (see Proposition 8). Proposition 0 (⋆ ). For symmetric preferences, FriHG- NS- NA- AddAg and FriHG- NS- PA- AddAg are polynomial-time solvable. Proof sketch. For symmetric friendship relations, the following partition is NS: Put all agents who have at least one friend together, while all agents without any friends form singleton coalitions. Due to this, the problem of ensuring x and y are together reduces to adding at most two agents to the original graph and checking whether afterwards x and y will each have a friend. ∎ For core stability, we can solve the control goal PA efficiently by reducing to finding a minimum-weight subgraph where xx and yy are mutually reachable. This is connected to the 2-DSN problem, which admits a polynomial-time algorithm Feldman and Ruhl (2006); Li et al. (1992): Directed Steiner Network (2-DSN) Input: A directed graph G=(V,A)G=(V,A) with an arc-weighting function ω:A→ℝω A→ R, two pairs (s1,t1),(s2,t2)(s_1,t_1),(s_2,t_2), and δ∈ℝδ∈ R. Question: Is there a subgraph H=(V′,A′)H=(V ,A ) of G which contains a path from s1s_1 to t1t_1 and from s2s_2 to t2t_2, respectively, such that ∑a∈A′ω(a) _a∈ A ω(a) ≤δ≤ 10000\ δ? Theorem 12 (⋆ ). FriHG- CS- NA- AddAg and FriHG- CS- PA- AddAg are polynomial-time solvable. Proof Sketch. By Observation 7, two agents xx and yy can be in the same coalition in a CS partition if and only if they are in the same strongly connected component of the friendship graph, i.e., if there is a path from xx to yy and vice versa. This is closely related to the polynomial-time solvable 2-DSN-problem Feldman and Ruhl (2006); Li et al. (1992). The main difference is that 2-DSN has arc-weights, whereas we have vertex weights. To address this, we replace every agent in W with two agents, one taking care of the in-arcs and the other the out-arcs. Let ((=∪,ℱ),x,y,k)((V=U ,F),x,y,k) be an instance of FriHG- CS- PA- AddAg. We will transform this instance into an instance I=(G,ω,(s1,t1),(s2,t2))I=(G,ω,(s_1,t_1),(s_2,t_2)) of 2-DSN as follows: – For every i∈i , we add to G a vertex uiu_i. – For every i∈i , we add to G two vertices, wi1w^1_i and wi2w^2_i. The idea is that wi1w^1_i inherits the in-arcs of i∈i and wi2w^2_i the out-arcs. Formally, we construct the following arcs with weights and add them to G. – For every arc (i,j)∈A(ℱ)(i,j)∈ A(F), we add to G an arc (u,v)(u,v) with weight 0, where ∙ if i∈i , then u≔uiu u_i, otherwise u≔wi2u w^2_i and ∙ if j∈j , then v≔ujv u_j, otherwise v≔wj1v w^1_j. – For every i∈i , we construct the arc (wi1,wi2)(w^1_i,w^2_i) with weight 11. We set (s1,t1)≔(ux,uy)(s_1,t_1) (u_x,u_y) and (s2,t2)≔(uy,ux)(s_2,t_2) (u_y,u_x). Moreover, we set δ≔kδ k. The correctness is deferred to the appendix. ∎ We finally look into enforcing that grand coalition is stable. For every ∈ S∈\ IR, IS, NS, CS\, we discover an algorithm for FriHG-S- GR- AddAg that runs in time ||k||O(1)|W|^k|V|^O(1). However, we show that the problem is W[2]-hard wrt. k, i.e., it is unlikely to admit an algorithm that runs in time f(k)⋅||O(1)f(k)·|V|^O(1), where f is some computable function. The result is through a straightforward reduction from Set Cover, which is W[2]-hard wrt. the set cover size h Downey and Fellows (2013). Theorem 13 (⋆ ). For every ∈ S∈\ IR, IS, NS, CS\, FriHG-S- GR- AddAg is W[2]-hard wrt. k even when the preference graph is symmetric and in XP wrt. k. In contrast to FriHG- S- GR- AddAg, FriHG- S- GR- DelAg is solvable in polynomial time for every ∈,,, S∈\ IR, IS, NS, CS\. For each stability concept, we can determine in polynomial time a maximum subset of agents such that the grand coalition partition of it is stable. For IR, IS, and NS, we obtain this set by recursively removing agents who have no friends, as they cannot be contained in an IR partition. For CS, it is known that every coalition in a stable partition is a strongly connected component of the friendship graph. Thus we only need to keep a largest strongly connected component. Proposition 0 (⋆ ). For every stability concept ∈,,, S∈\ IR, IS, NS, CS\, FriHG- S- GR- DelAg is polynomial-time solvable. 5. Additive Preferences In this section, we consider the case with additive preferences. It turns out that most of our control problems remain intractable even in very restricted cases such as when the budget is zero or the preference graph is a DAG or symmetric. As in the previous section, we first consider NA, then PA, and finally GR. First, we show that even the most basic stability requirement IR becomes difficult to determine once we enforce some control goal. Theorem 15. For each control action ∈,A∈\ AddAg, DelAg\, AddHG- IR- NA-A is NP-complete; NP-hardness remains even if the budget is k=0k=0 and the preference graph has only one feedback arc. Proof. The NP-containment follows directly from Observation 2. Moreover, since k=0k=0, both control problems reduce to checking whether there is an IR partition with agent x not alone in his coalition. It remains to show the NP-hardness for the mentioned restriction. In the remainder of the proof, we will focus on this restricted variant and reduce from the following well-known NP-complete problem Gonzalez (1985). Restricted Exact Cover by 3-Sets (RX3C) Input: A 3n^3 n-element set ℰ=[3n^]E=[3 n] and a collection =S1,…,S3n^S=\S_1,…,S_3 n\ of 33-element subsets of ℰE such that each element appears in exactly three members of S. Question: Does S contain an cover for ℰE, i.e., a subcollection ⊆K such that ||=n^|K|= n and ∪Sj∈Sj=ℰ _S_j S_j=E? Let I=(ℰ=[3n^],)I=(E=[3 n],S) be an instance of RX3C. We construct an AddHG-instance whose preference graph has one feedback arc. The set of agents is =x,y0,y1∪ui∣i∈ℰ∪sj∣Sj∈U=\x,y_0,y_1\∪\u_i i \∪\s_j S_j \, where – xx is the special agent not to be alone, – y0,y1y_0,y_1 are auxiliary-agents, – each element i∈ℰi has one -agent uiu_i, – each set Sj∈S_j has one -agent sjs_j. We construct the utilities as follows; the unmentioned utilities are 0: – For each agent a∈∖xa \x\, set μa(x)=−1 _a(x)=-1. – For each element i∈[3n^−1]i∈[3 n-1], set μui(ui+1)=1 _u_i(u_i+1)=1, for element-agent u3n^u_3 n, set μu3n^(y0)=1 _u_3 n(y_0)=1. – For auxiliary-agent y0y_0, set μy0(y1)=1 _y_0(y_1)=1, for y1y_1, set μy1(u1)=1 _y_1(u_1)=1. – For each element i∈[3n^]i∈[3 n], set μui(y1)=−1 _u_i(y_1)=-1. – For each set Sj∈S_j and all elements i∈Sji∈ S_j, set μui(sj)=1 _u_i(s_j)=1. – For each set Sj∈S_j , set μsj(y1)=1 _s_j(y_1)=1. – For all Sj,Sℓ∈S_j,S_ with j<ℓj< and Sj∩Sℓ≠∅S_j∩ S_ ≠ , set μsj(sℓ)=−1 _s_j(s_ )=-1. An illustration of the preference graph of the AddHG-instance is depicted in Figure 2. To complete the construction, we define xx as the agent not being alone. Before we show the correctness, we first observe that by deleting the arc (y1,u1)(y_1,u_1) we obtain a DAG with following topological order: u1,…,u3n^,s1,…,s3n^,y0,y1,xu_1,…,u_3 n, s_1,…,s_3 n, y_0,y_1, x. Claim 15.1 (⋆ ). If K is an exact cover for I, then the following partition Π with Π(x)=x,u1,u2,…,u3n^,y0,y1∪sj∣Sj∈ (x)=\x,u_1,u_2,…,u_3 n,y_0,y_1\∪\s_j S_j \ and Π(sj)=sj (s_j)=\s_j\ for all Sj∉S_j is IR. Claim 15.2. If Π is an IR partition with |Π(x)|≥2| (x)|≥ 2, then the sets corresponding to the set-agents in Π(x) (x) form an exact cover of I. Proof. Let C≔Π(x)C (x) be the coalition containing special agent xx with |C|≥2|C|≥ 2. We want to show that the sets corresponding to set-agents contained in C form an exact cover of I. We start by showing that auxiliary-agent y1y_1 must be in C. If sj∈Cs_j∈ C for some Sj∈S_j , then he needs to be in the same coalition with y1y_1 for C to be IR, because he has negative utility towards xx and the only positive utility is towards y1y_1. The same argument holds if y0∈Cy_0∈ C: He has negative utility towards x and his only positive utility towards y1y_1. If an element-agent ui∈Cu_i∈ C for some i∈[3n^]i∈[3 n], then there is a set-agent sjs_j with i∈Sji∈ S_j such that sj∈Cs_j∈ C, which implies y1∈Cy_1∈ C, or ui+1∈Cu_i+1∈ C; otherwise uiu_i has negative utility towards C. By repeating this argument, either a set-agent–and thus y1y_1–must be in C, or u3n^∈Cu_3 n∈ C. However, if u3n^u_3 n is in C, then either a set-agent or y0y_0 must be in C; in both cases, this implies y1y_1 must also be in C. Thus y1∈Cy_1∈ C and hence u1∈Cu_1∈ C, because y1y_1 has negative utility towards xx and only positive utility towards u1u_1. Agent u1u_1 has -1 utility towards xx and y1y_1 in C, so u1u_1 needs at least one set-agent sjs_j with 1∈Sj1∈ S_j to not deviate. However, there can be at most one sj∈Cs_j∈ C with 1∈Sj1∈ S_j: Suppose, towards a contradiction, that there are sj,sj′∈C,j<j′s_j,s_j ∈ C,j<j with 1∈Sj1∈ S_j and 1∈Sj′1∈ S_j . Then sjs_j has negative utility towards x and sj′s_j . But he has only one positive out-arc to y1y_1, so C would not be IR anymore, contradiction. Hence we have exactly one set-agent sj∈Cs_j∈ C with 1∈Sj1∈ S_j. Thus u2∈Cu_2∈ C for C to be IR. Similarly to element 11, there must be exactly one sj∈Cs_j∈ C with 2∈Sj2∈ S_j. Same arguments hold for u3,…,u3n^u_3,…,u_3 n. To summarize, we need for every element-agent uiu_i for i∈[3n^]i∈[3 n] at least one set-agent sjs_j with i∈Sji∈ S_j which implies we have a set cover of all sets corresponding to the set-agents contained in C. As we have discussed, the sets must also be disjoint, so the set cover is also an exact-cover. (end of the proof of Claim 15.2) ⋄ The correctness follows immediately from Claims 15.1 and 15.2. ∎ The above result is tight since for DAGs or symmetric preferences, we can solve the problem in polynomial time. In both cases we need to find only one agent a∈a , such that xx has non-negative utility towards agent a or vice versa: Proposition 0 (⋆ ). For DAGs, AddHG- IR- NA- AddAg and hence AddHG- CS- NA- AddAg is polynomial-time solvable. For symmetric preferences, AddHG- IR- NA- AddAg is polynomial-time solvable. Next, we consider the two more stringent stability concepts IS and NS. It is known that determining the existence of NS and IS partitions is NP-hard on AddHG Sung and Dimitrov (2010). Hence, by Observation 3, the control problems with goals NA and PA are NP-hard as well. We discover that the control problems remain NP-hard even when the preference graph is a DAG or symmetric. Theorem 17 to Theorem 20 are all shown via reductions from RX3C, using approaches that are similar in structure but distinct in their technical details. Theorem 17 (⋆ ). For each stability concept ∈, S∈\ IS, NS\ and each control action ∈,A∈\ AddAg, DelAg\, AddHG- S- NA-A and AddHG- S- PA-A are NP-complete; NP-hardness remains even if the budget is k=0k=0 and the preference graph is a DAG. Hardness for IS and NS extend to symmetric preferences. Theorem 18. For each stability concept ∈, S∈\ IS, NS\ and each control action ∈,A∈\ AddAg, DelAg\, AddHG- S- NA-A is NP-complete; NP-hardness remains even if the budget is k=0k=0 and the preference graph is symmetric. Proof. The NP-containment follows directly from Observation 2. As before, we will reduce from RX3C to show the NP-hardness for the mentioned control problem. Let I=(ℰ=[3n^],)I=(E=[3 n],S) be an instance of RX3C. Let us construct a hedonic game instance with additive and symmetric preferences as follows. The set of agent is =x,y∪ui∣i∈ℰ∪sj∣Sj∈∪dℓ∣ℓ∈[2n^]U=\x,y\∪\u_i i \∪\s_j S_j \∪\d_ ∈[2 n]\, where – xx is the special agent and y an auxiliary-agent, – each element i∈ℰi has one -agent uiu_i, – each set Sj∈S_j has one -agent sjs_j, – and auxiliary-agents dℓd_ for ℓ∈[2n^] ∈[2 n]. We construct the symmetric utilities as follows; the unmentioned utilities are 0: – Set μx(y)=μy(x)=1 _x(y)= _y(x)=1. – For each agent a∈∖x,ya \x,y\, set μx(a)=μa(x)=−1 _x(a)= _a(x)=-1. – For each Sj∈S_j , set μsj(y)=μy(sj)=1 _s_j(y)= _y(s_j)=1. – For each set Sj∈S_j and all elements i∈Sji∈ S_j, set μsj(ui)=μui(sj)= 1 _s_j(u_i)= _u_i(s_j)= 10000\ 1. – For each set Sj∈S_j and every auxiliary-agent dℓd_ for ℓ∈[2n^] ∈[2 n], set μsj(dℓ)=μdℓ(sj)=3 _s_j(d_ )= _d_ (s_j)=3. A sketch of the preference graph can be found in the appendix, see Figure 4. To complete the construction, let agent xx be the special agent not to be alone. In the forward direction of the correctness proof, we show that if I has an exact cover, we can construct a NS partition with |Π(x)|≥2| (x)|≥ 2, which is, by Observation 1, also IS. In the backward direction, we assume the partition Π being IS–an even weaker assumption than NS–and show that this implies the existence of an exact cover for I. Claim 18.1 (⋆ ). If K is an exact cover for I, then the following partition Π with Π(x)=x,y (x)=\x,y\, Π(sj)=sj,uj1,uj2,uj3 (s_j)=\s_j,u_j_1,u_j_2,u_j_3\ for Sj=j1,j2,j3∈S_j=\j_1,j_2,j_3\ and Π(sj)=sj,dℓ (s_j)=\s_j,d_ \ for Sj∉S_j and ℓ∈[2n^] ∈[2 n] is NS. Claim 18.2 (⋆ ). If Π is an IS partition with |Π(x)|≥2| (x)|≥ 2, then y∈Π(x)y∈ (x) and all set-agents which are in a coalition with their three element-agents form an exact cover of I. The correctness follows immediately from Claims 18.1 and 18.2. ∎ In contrast to Proposition 16, PA remains NP-hard on DAGs or symmetric preferences, even when no agent can be added or deleted. Theorem 19 (⋆ ). For each stability concept ∈, S∈\ IR, CS\ and each control action ∈,A∈\ AddAg, DelAg\, AddHG- S- PA-A is NP-complete; NP-hardness remains even if the budget is k=0k=0 and the preference graph is acyclic with maximum vertex degree nine. The hardness remains for symmetric preferences. Theorem 20 (⋆ ). For each stability concept ∈,, S∈\ IR, IS, NS\ and each control action ∈,A∈\ AddAg, DelAg\, AddHG- S- PA-A is NP-hard even if the budget is k=0k=0 and the preference graph is symmetric. Finally, we consider the control goal GR: Making the grand coalition partition stable. We already know from the previous section that for every ∈,,, S∈\ IR, IS, NS, CS\, FriHG- S- GR- AddAg is NP-hard and [] W[2]-hard wrt. k even for symmetric preferences. We strengthen this result by showing the same for the DelAg case. Theorem 21 (⋆ ). For each stability concept ∈,,, S∈\ IR, IS, NS, CS\ and each control action ∈,A∈\ AddAg, DelAg\, AddHG- S- GR-A is in XP and [] W[2]-hard wrt. k when the preference graph is a DAG. Theorem 22 (⋆ ). For each stability concept ∈,, S∈\ IR, IS, NS\ and each control action ∈,A∈\ AddAg, DelAg\, AddHG- S- GR-A is [] W[2]-hard and in XP wrt. k. The hardness holds even when the preference graph is symmetric. For core stability, Theorem 21 shows that AddHG- CS- GR- AddAg and AddHG- CS- GR- DelAg admit a polynomial-time algorithm when the preference graph is a DAG and the budget is a constant. However, in contrast with IR, IS, and NS, the problems for CS are in general coNP-complete even when k=0k=0. The hardness holds even when the preferences are symmetric. Theorem 23 (⋆ ). For each control action ∈,A∈\ AddAg, DelAg\, AddHG- CS- GR-A is coNP-complete. It remains coNP-hard even when k=0k=0 and the preference graph is symmetric. 6. Conclusion Motivated by control in other computational social choice problems, we introduce control in hedonic games. We study three control goals: ensuring an agent is not alone ( NA), ensuring a pair of agents is together ( PA), and ensuring the grand coalition is stable ( GR), combined with two control actions: adding and deleting agents. We present a complete complexity picture for these control goals and actions across four stability concepts and two preference representations–FriHG and AddHG. Our work opens several potential directions for future research. First, alternative control actions remain unexplored. In Stable Roommates and Marriage settings, a common control action is removing acceptability–making previously acceptable pairs unacceptable to each other. Analogously, one could study removing friendship relations in FriHG or adjusting utility values in AddHG. Second, inspired by destructive control in voting Hemaspaandra et al. (2007), one could study destructive control in hedonic games: ensuring a specific agent remains isolated or preventing a specific pair from being in the same coalition. Third, other solution concepts merit investigation, such as Pareto optimal or strictly core stable partitions. Finally, other simple compact preference representations warrant exploration, such as fractional hedonic games Aziz et al. (2019), anonymous preferences Bogomolnaia and Jackson (2002) or B- and W-preferences Cechlárová and Romero-Medina (2001). We conjecture that the ideas of many of our hardness reductions could work also for fractional hedonic games, since Observation 5 extends to any compact preference representation. However, anonymous, B- and W-preferences have a different structure and therefore likely require different ideas. References (1) Aziz et al. (2019) Haris Aziz, Florian Brandl, Felix Brandt, Paul Harrenstein, Martin Olsen, and Dominik Peters. 2019. Fractional Hedonic Games. ACM Transactions on Economics and Computation 7, 2 (2019). Aziz and Savani (2016) Haris Aziz and Rahul Savani. 2016. Hedonic Games. In Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia (Eds.). Cambridge University Press, 356–376. Banerjee et al. (2001) Suryapratim Banerjee, Hideo Konishi, and Tayfun Sönmez. 2001. Core in a Simple Coalition Formation Game. Social Choice and Welfare 18, 1 (2001), 135–153. Bartholdi I et al. (1992) John Bartholdi I, Craig A. Tovey, and Michael A. Trick. 1992. How hard is it to control an election? Mathematical and Computer Modelling 16, 8/9 (1992), 27–40. Boehmer et al. (2021) Niclas Boehmer, Robert Bredereck, Klaus Heeger, and Rolf Niedermeier. 2021. Bribery and Control in Stable Marriage. Journal of Artificial Intelligence Research 71 (2021), 993–1048. Bogomolnaia and Jackson (2002) Anna Bogomolnaia and Matthew O. Jackson. 2002. The Stability of Hedonic Coalition Structures. Games Economic Behavior 38, 2 (2002), 201–230. Brandt et al. (2024) Felix Brandt, Martin Bullinger, and Leo Tappe. 2024. Stability based on single-agent deviations in additively separable hedonic games. Artificial Intelligence 334 (2024), 104160. Bullinger et al. (2016) Martin Bullinger, Edith Elkind, and Jörg Rothe. 2016. Cooperative Game Theory. In Economics and Computation, An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, Jörg Rothe (Ed.). Springer, 135–193. Cechlárová and Romero-Medina (2001) Katarína Cechlárová and Antonio Romero-Medina. 2001. Stability in coalition formation games. International Journal of Game Theory 29 (2001), 487–494. Chalkiadakis et al. (2011) Georgios Chalkiadakis, Edith Elkind, and Michael J. Wooldridge. 2011. Computational Aspects of Cooperative Game Theory. Morgan & Claypool Publishers. Chen et al. (2023) Jiehua Chen, Gergely Csáji, Sanjukta Roy, and Sofia Simola. 2023. Hedonic Games With Friends, Enemies, and Neutrals: Resolving Open Questions and Fine-Grained Complexity (AAMAS 2023). 251–259. Chen et al. (2025a) Jiehua Chen, Christian Hatschka, and Sofia Simola. 2025a. Computational Social Choice: Parameterized Complexity and Challenges. Computer Science Review (2025). To appear. Chen et al. (2025b) Jiehua Chen, Joanna Kaczmarek, Paul Nüsken, Jörg Rothe, Ildikó Schlotter, and Tessa Seeger. 2025b. Control in Computational Social Choice. In Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI 2025). 10391–10399. Chen and Schlotter (2025) Jiehua Chen and Ildikó Schlotter. 2025. Control in Stable Marriage and Stable Roommates: Complexity and Algorithms. Technical Report. arXiv:2502.01215. Cygan et al. (2015) Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer. Dimitrov et al. (2006) Dinko Dimitrov, Peter Borm, Ruud Hendrickx, and Shao Chin Sung. 2006. Simple priorities and core stability in hedonic games. Social Choice and Welfare 26, 2 (2006), 421–433. Downey and Fellows (2013) Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer. Drèze and Greenberg (1980) Jacques H. Drèze and Joseph Greenberg. 1980. Hedonic Coalitions: Optimality and Stability. Econometrica 48, 4 (1980), 987–1003. Faliszewski and Rothe (2016) Piotr Faliszewski and Jörg Rothe. 2016. Control and Bribery in Voting. In Handbook of Computational Social Choice, F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia (Eds.). Cambridge University Press, Chapter 7, 146–168. Feldman and Ruhl (2006) Jon Feldman and Matthias Ruhl. 2006. The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals. SIAM J. Comput. 36, 2 (2006), 543–561. Floyd (1962) Robert W. Floyd. 1962. Algorithm 97: Shortest path. Commun. ACM 5, 6 (June 1962), 345. Galbraith (2012) Steven D. Galbraith. 2012. Mathematics of Public Key Cryptography. Cambridge University Press. Gonzalez (1985) Teofilo F. Gonzalez. 1985. Clustering to Minimize the Maximum Intercluster Distance. Theoretical Computer Science 38 (1985), 293–306. Hemaspaandra et al. (2007) Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe. 2007. Anyone but Him: The Complexity of Precluding an Alternative. Artificial Intelligence 171, 5-6 (2007), 255–285. Li et al. (1992) Chung-Lun Li, S Thomas McCormick, and David Simchi-Levi. 1992. The point-to-point delivery and connection problems: complexity and algorithms. Discrete Applied Mathematics 36, 3 (1992), 267–292. Natu and Shu-Cherng (1997) Madan Natu and Fang Shu-Cherng. 1997. The point-to-point connection problem—analysis and algorithms. Discrete Applied Mathematics 78, 1-3 (1997), 207–226. Niedermeier (2006) Rolf Niedermeier. 2006. Invitation to Fixed-Parameter Algorithms. Oxford University Press. Peters (2017) Dominik Peters. 2017. Precise complexity of the core in dichotomous and additive hedonic games. In Proceedings of the International Conference on Algorithmic Decision Theory (ADT 2017). Springer, 214–227. Sung and Dimitrov (2010) Shao-Chin Sung and Dinko Dimitrov. 2010. Computational Complexity in Additive Hedonic Games. European Journal of Operational Research 203, 3 (2010), 635–639. Woeginger (2013a) Gerhard J. Woeginger. 2013a. Core Stability in Hedonic Coalition Formation. In Proceedings of the 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2013) (Lecture Notes in Computer Science, Vol. 7741). 33–50. Woeginger (2013b) Gerhard J. Woeginger. 2013b. A hardness result for core stability in additive hedonic games. Mathematical Social Science 65, 2 (2013), 101–104. Supplementary Material for the Paper “Control in Hedonic Games” Appendix A Additional material for Section 2 A.1. Proof of Lemma 7 See 7 Proof. Let I,x,y,ΠI,x,y, be as defined. The desired IS partition Π′ will consist of a big coalition M with possibly some singleton coalitions. Step 1: Add the agents of all size-at-least-two coalitions in Π to M. Formally, M≔⋃A∈Π,|A|≥2AM _A∈ ,|A|≥ 2A. Since Π(x)=Π(y) (x)= (y), it holds that x,y∈Mx,y∈ M. Step 2: For each strongly connected component C of size at least two in ℱF, add the agents in C to M. Step 3: Add all agents to M that can reach some agent in M. For every agent not in M, set his coalition as the singleton coalition under Π′ . Clearly by Step 1 it holds that Π′(x)=Π′(y)=M (x)= (y)=M. It remains to show that Π′ is IS. Let us first show that Π′ is IR, i.e., no agent can prefer deviating to singleton coalition. Clearly the agents in the singleton coalitions cannot deviate. Now consider an agent ii in M. If ii was added to M in Step 1, then |Π(i)|≥2| (i)|≥ 2. This means that ii must obtain at least one friend in Π(i) (i), because otherwise ii would prefer i\i\ to Π(i) (i), and hence Π would not be IR. Since ii obtains at least one friend in Π(i) (i) and Π(i)⊆M (i) M, he also obtains a friend under Π′(i)=M (i)=M, and thus prefers M to i\i\. If instead ii was added to M in Step 2, then ii is part of a strongly connected component C of size at least 22. It must hold that ii considers someone in C a friend and C⊆MC M. Thus, ii obtains a friend in Π′(i)=M (i)=M, and thus prefers M to i\i\. Next we must show that no agent, coalition pair (i,A)(i,A), where i∈,A∈Π′i ,A∈ forms a blocking tuple. We have three cases to consider: Case 1: Agent ii is in a singleton coalition under Π′ and A is a singleton coalition. Let A=jA=\j\. Since ii prefers i,j\i,j\ to i\i\, agent jj must be a friend of ii. Since jj weakly prefers i,j\i,j\ to j\j\, agent ii must be a friend of jj. But then ii and jj are mutually reachable and they must be in the same strongly connected component of ℱF. However, we did not add them to M in Step 2, a contradiction. Case 2: Agent ii is in a singleton coalition under Π′ and A=MA=M. Then ii prefers i∪M\i\∪ M to ii and thus must have a friend in M. But then ii can reach an agent in M, a contradiction to not adding ii to M in Step 3. Case 3: Agent i∈Mi∈ M and A is a singleton coalition. Let A=jA=\j\. Since jj weakly prefers i,j\i,j\ to j\j\, agent ii must be a friend of jj. But then jj can reach an agent in M, a contradiction to not adding jj to M in Step 3. Since all cases lead to contradiction, it must be that Π′ is IS, as required. ∎ A.2. Proof of Observation 5 See 5 Proof. Take any hardness reduction which shows that the existence of an S-partition for M is Σ2P ^P_2-hard (resp. NP-hard). Add two additional agents x,y\x,y\ to the instance of M who have positive utility towards each other and negative to all other agents (resp. in the friends-setting, agents x,yx,y are mutual friends and have no other friends). Now the reduction also holds for M- S-G-A for every control goal ∈,G∈\ [rgb]0.6,0,0 [named]pgfstrokecolorrgb0.6,0,0 NA, [rgb]0,0,0.7 [named]pgfstrokecolorrgb0,0,0.7 PA\ by requiring that xx is not alone (resp. x,y\x,y\ are paired). ∎ A.3. Proof of Observation 6 See 6 Proof. Let (=∪,(⪰i)i∈,x,k)(V=U ,( _i)_i ,\x\,k) be an instance of M- S- NA-A. If M- S- PA-A is polynomial-time solvable, we can try to pair the special agent xx with every other agent a∈∪a . We iteratively solve M- S- PA-A with (=∪,(⪰i)i∈,x,a,k)(V=U ,( _i)_i ,\x,a\,k), which is possible in polynomial-time. If a∈a , we additionally decrease the budget k by one and move a from W to U. If for some pair x,a∗\x,a^*\, M- S- PA-A is a Yes-instance, then M- S- NA-A is also a Yes-instance by taking the partition returned for the paired version. If, on the other hand, for every pair x,a\x,a\, M- S- PA-A is a No-instance, then no S partition exists in which xx is paired with another agent. Hence, xx must be lone in every S partition. ∎ A.4. Proof of Observation 7 See 7 Proof. We show the statement for the sake of completion. For the “if” part, assume that xx and yy are in the same strongly connected component (SCC). Since, by Dimitrov et al. (2006), there exists a CS partition, where each coalition corresponds to an SCC in the graph, this CS partition must include a coalition with xx and yy being together. For “only if” part, assume that Π is a CS partition with Π(x)=Π(y) (x)= (y). Suppose, for the sake of contradiction, that xx and yy do not belong to the same SCC. This implies that the friendship graph ℱ[Π(x)]F[ (x)] induced by Π(x) (x) has more than one SCC. Let C be a sink component in the topological ordering of the SCCs in ℱ[Π(x)]F[ (x)]. Then, every agent in C has the same number of friends in C as in Π(x) (x) and at least one enemy less in C than in Π(x) (x), meaning that C is blocking, a contradiction. ∎ A.5. Proof of Observation 8 See 8 Proof. For each coalition of size at least two, there is always an agent who is a sink in the induced subgraph. This sink agent will prefer to be alone. Hence, the only IR partition is to have every agent alone. ∎ A.6. Proof of Theorem 10 See 10 Proof. Given two agents i,j∈i,j , we use ωP(i,j)ω^P(i,j) to denote the weight of the minimum-weight path from ii to jj and ωC(i)ω^C(i) to denote the weight of the minimum-weight non-trivial cycle containing ii. Similarly, let P(i,j)P(i,j) denote the set of agents on a minimum-weight path from ii to jj and C(i)C(i) denote the set of agents on a minimum-weight cycle containing ii, as discovered by the minimum-weight paths algorithm. Let us first show that if the Algorithm 1 returns yes, then I is indeed a Yes-instancefor FriHG- IR- PA- AddAg. Since the algorithm returns yes, there are i∈,j∈i ,j such that one of the checks was satisfied. First assume line 1 returns yes. Consider the coalition A that consists of the agents on P(x,^y)+P(y,^y)+P(^y,^x)+C(^x)P(x, y)+P(y, y)+P( y, x)+C( x). Observe that every agent in this coalition is contained in a path that does not end on him, or in a cycle. Thus, every agent has an out-arc in ℱ[A]F[A] and thus obtains a friend. Hence no agent wishes to deviate from A. Next observe that |A∩|≤k|A |≤ k: Every agent w∈A∩w∈ A is the non-last agent on a path or is contained in a cycle, and hence the respective path or cycle contains an arc starting from ww. This arc contributes one to the sum on line 1. Clearly x,y∈Ax,y∈ A. We can form an IR partition Π such that A∈ΠA∈ by assigning all the other agents in singleton coalitions. Through similar reasoning, we obtain an IR partition if line 1 or line 1 returns yes. Now assume that I is a Yes-instance of FriHG- IR- PA- AddAg. Let ′⊆W such that |′|≤k|W |≤ k and let Π be an IR partition of ∪′V∪W such that Π(x)=Π(y) (x)= (y) and let A≔Π(x)=Π(y)A (x)= (y). Clearly |A|≥2|A|≥ 2. Thus, every agent in A must obtain a friend. Construct a sequence (x,x1,…,xt)(x,x_1,…,x_t) by starting from xx, picking an arbitrary friend x1x_1 of xx from A, picking an arbitrary friend x2x_2 of x1x_1 and so on until. We stop when we reach an agent xtx_t who has a friend x,x1,…,xt−1\x,x_1,…,x_t-1\. Let us call this friend x x. Since A is finite, we must reach such an agent eventually. Now construct a sequence (y,y1,…,ys)(y,y_1,…,y_s) similarly, except instead of stopping when we reach an agent ysy_s with a friend in (y,y1,…,ys−1)(y,y_1,…,y_s-1), we may also stop earlier if we encounter an agent ysy_s who has a friend among x,x1,…,xt\x,x_1,…,x_t\. Similarly to the previous case, we use y y to refer to the friend of ysy_s. This agent y y is either x,x1,…,xt\x,x_1,…,x_t\ or y,y1,…,ys−1\y,y_1,…,y_s-1\. Note that it is possible that y∈x,x1,…,xty∈\x,x_1,…,x_t\, in which case the sequence is empty and y^=y y=y. Moreover, if yy has a friend among (x,x1,…,xt)(x,x_1,…,x_t), then the sequence is just (y)(y). By construction, all the agents in these two sequences are pairwise disjoint, and they are all in A. We proceed in three possible cases regarding the identity of y y. Case 1 Agent y y is before x x on the sequence x,x1,…,xtx,x_1,…,x_t or y^=x y= x. First consider the set of agents in x,x1,…,xtx,x_1,…,x_t who precede y y. Let us call this set X1X_1. We observe that ωP(x,y^)≤|X1∩′|ω^P(x, y)≤|X_1∩W |: By construction, the agents in X1∪y^X_1∪\ y\ form a path from xx to y y and the weight of this path is the number of arcs whose first element is in W. Note that if X1=∅X_1= , then y^=x y=x and both sizes of the inequality are zero. Similarly, consider the set of agents Y that are in the sequence (y,y1,…,ys)(y,y_1,…,y_s). We obtain that ωP(y,y^)≤|Y∩′|ω^P(y, y)≤|Y∩W |, because by construction the agents in Y∪y^Y∪\ y\ form a path from yy to y y and the weight of this path is the number of arcs whose first element is in W. Note that if Y=∅Y= , then y^=y y=y and both sizes of the inequality are zero. Now consider the set of agents on the sequence (x,x1,…,xt)(x,x_1,…,x_t) who are after y y (including y y) but before x x (excluding x x). Let us call this set X2X_2. We observe that ωP(y^,x^)≤|X2∩′|ω^P( y, x)≤|X_2∩W |, because by construction the agents in X2∪x^X_2∪\ x\ form a path from y y to x x and the weight of this path is the number of arcs whose first element is in W. Finally, consider the set of agents X3X_3 on the sequence (x,x1,(x,x_1, …,xt)…,x_t) who are after x x (including x x). We observe that ωC(x^)ω^C( x) ≤|X3∩′|≤|X_3∩W |: Since x x is, by construction, an agent such that xtx_t considers him a friend, graph ℱ[X3]F[X_3] contains a friendship cycle containing x x. By construction, the weight of this path is the number of arcs on it whose first element is in W. This is equivalent to the number of agents in the cycle who are in W. Recall that X1,X2,X3X_1,X_2,X_3, and Y are all pairwise disjoint sets that are subsets of A and hence subsets of ∪′V∪W . We obtain that k k ≥|′|≥|A∩′| ≥|W |≥|A∩W | ≥|X1∩′|+|Y∩′|+|X2∩′|+|X3∩′| ≥|X_1∩W |+|Y∩W |+|X_2∩W |+|X_3∩W | ≥ωP(x,y^)+ωP(y,y^)+ωP(y^,x^)+ωC(x^). ≥ω^P(x, y)+ω^P(y, y)+ω^P( y, x)+ω^C( x). We obtain that line 1 returns yes. Case 2 Agent y y is after x x on the sequence x,x1,…,xtx,x_1,…,x_t. This implies that x^≠y x≠ y, so the second part of line 1 is satisfied. First consider the set of agents in x,x1,…,xtx,x_1,…,x_t who precede x x. Let us call this set X1X_1. By reasoning analogous to the previous case we have that ωP(x,x^)≤|X1∩′|ω^P(x, x)≤|X_1∩W |. Similarly, consider the set of agents Y that are in the sequence (y,y1,…,ys)(y,y_1,…,y_s). Again ωP(y,y^)≤|Y∩′|ω^P(y, y)≤|Y∩W |. Now consider the set of agents on the sequence (x,x1,…,xt)(x,x_1,…,x_t) who are after x x (including x x) but before y y (excluding y y). Let us call this set X2X_2. We observe that ωP(x^,y^)≤|X2∩′|ω^P( x, y)≤|X_2∩W |. Finally, consider the set of agents X3X_3 on the sequence (x,x1,(x,x_1, …,xt)…,x_t) who are after y y (including y y). We observe again that ωP(y^,x^)≤|X3∩′|ω^P( y, x)≤|X_3∩W |. Recall that X1,X2,X3X_1,X_2,X_3, and Y are all pairwise disjoint subsets of A, and hence subsets of ∪′V∪W . It follows that k k ≥|X1∩′|+|Y∩′|+|X2∩′|+|X3∩′| ≥|X_1∩W |+|Y∩W |+|X_2∩W |+|X_3∩W | ≥ωP(x,x^)+ωP(y,y^)+ωP(x^,y^)+ωP(y^,x^). ≥ω^P(x, x)+ω^P(y, y)+ω^P( x, y)+ω^P( y, x). We obtain that line 1 returns yes. Case 3 Agent y y is not on the sequence x,x1,…,x,x_1,…, xtx_t, i.e., y y is in y,y1,…,ys\y,y_1,…,y_s\. First consider the set of agents in x,x1,…,xtx,x_1,…,x_t who precede x x. Let us call this set X1X_1. Again we have that ωP(x,x^)≤|X1∩′|ω^P(x, x)≤|X_1∩W |. Now consider the set of agents X2X_2 on the sequence (x,x1,…,(x,x_1,…, xt)x_t) who are after x x (including x x). We observe that ωC(x^)≤|X2∩′|ω^C( x)≤|X_2∩W |: Since x x is, by construction, an agent such that xtx_t considers him a friend, graph ℱ[X2]F[X_2] contains a friendship cycle containing x x. By construction, the weight of this cycle is the number of arcs–and hence agents–in it whose first element is in W. Now consider the set of agents in y,y1,…,ysy,y_1,…,y_s who precede x x. Let us call this set Y1Y_1. Again we have that ωP(y,y^)≤|Y1∩′|ω^P(y, y)≤|Y_1∩W |. Next consider the set of agents Y2Y_2 on the sequence (y,y1,…,(y,y_1,…, ys)y_s) who are after y y (including y y). Analogously to the set X2X_2, we observe that ωC(y^)≤|Y2∩′|ω^C( y)≤|Y_2∩W |. Recall that X1,X2,Y1X_1,X_2,Y_1, and Y2Y_2 are all pairwise disjoint sets that are subsets of A and hence subsets of ∪′V∪W . Hence k k ≥|X1∩′|+|Y1∩′|+|X2∩′|+|Y2∩′| ≥|X_1∩W |+|Y_1∩W |+|X_2∩W |+|Y_2∩W | ≥ωP(x,x^)+ωP(y,y^)+ωC(x^)+ωC(y^). ≥ω^P(x, x)+ω^P(y, y)+ω^C( x)+ω^C( y). We obtain that line 1 returns yes. Thus, the algorithm correctly solves FriHG- IR- PA- AddAg. By Observation 6, FriHG- IR- NA- AddAg is then also polynomial-time solvable. However, it is straightforward to prove that we can obtain a more efficient algorithm by looking for i∈∖xi \x\ such that ωP(x,i)+ωC(i)≤kω^P(x,i)+ω^C(i)≤ k. Finally, Lemma 7 implies that the algorithm can also be used to solve FriHG- IS- PA- AddAg and FriHG- IS- NA- AddAg. ∎ A.7. Proof of Proposition 11 See 11 Proof. We first note that when the preferences are symmetric, the partition that contains all the agents with degree at least one in one coalition M, and the remaining agents in singleton coalitions, is NS. Since preferences are symmetric, every agent who has friends has all of his friends in M, and thus cannot prefer any other coalition to M. An agent who has no friends cannot prefer any other coalition to the singleton coalition containing him. Moreover, there is no NS partition where an agent who has no friends is in a coalition other than the coalition containing only him. Thus, to enforce that xx and yy are together in an NS partition, it is sufficient and necessary to make them have a friend. Hence, we can determine FriHG- NS- PA- AddAg as follows: Case 1 k=0k=0. Return yes if and only if both xx and yy have a friend in U. Case 2 k=1k=1. If both xx and yy have a friend in U, then return yes. If only xx (resp. only yy) does not have a friend in U, then return yes if W contains an agent who is a friend of xx (resp. yy). If neither xx nor yy has a fried in U, then return yes if W contains an agent who is a friend of both xx and yy. If the above does not return yes, return no. Case 3 k≥2k≥ 2. If both xx and yy have a friend in U, then return yes. If only xx (resp. only yy) does not have a friend in U, then return yes if W contains an agent who is a friend of xx (resp. yy). If neither xx nor yy has a fried in U, then return yes if W contains an agent who is a friend of xx and an agent who is a friend of yy. If the above does not return yes, return no. For FriHG- NS- NA- AddAg it is sufficient to check if xx has a friend among U when k=0k=0, or among ∪U when k≥1k≥ 1. ∎ A.8. Proof of Theorem 12 See 12 Proof. We continue the proof by showing the correctness of our reduction. Claim 23.1. If ((=∪,ℱ),x,y,k)((V=U ,F),x,y,k) is a Yes-instance of FriHG- CS- PA- AddAg, then I is a Yes-instance of 2-DSN. Proof. Let ′⊆W such that |′|≤k|W |≤ k and ∪′U∪W admits a core stable partition Π such that Π(x)=Π(y) (x)= (y). We construct a subgraph H of G as follows: let V′≔ui∣i∈∪wi1,wi2∣i∈′V \u_i i \∪\w^1_i,w^2_i i∈W \ and let H≔G[V′]H G[V ]. Let us first show that uxu_x is reachable from uyu_y and vice versa. By Observation 7, we must have that xx and yy belong to the same strongly connected component of ℱ[∪′]F[U∪W ]. In other words, agent xx must be reachable from yy and vice versa on ℱ[∪′]F[U∪W ]. Let x,i1,…,it,yx,i_1,…,i_t,y be a path from xx to yy on ℱ[∪′]F[U∪W ]. We construct a path from uxu_x to uyu_y on H. For every ℓ∈[t] ∈[t]: – If iℓ∈i_ , add the vertex uiℓu_i_ to the path. Since iℓ∈i_ , we have that uiℓ∈V′u_i_ ∈ V . – If iℓ∈i_ , add the vertices wiℓ1,wiℓ2w^1_i_ ,w^2_i_ to the path. Since iℓ∈′i_ ∈W , we have that wiℓ1,wiℓ2∈V′w^1_i_ ,w^2_i_ ∈ V . Consider every successive pair (u,v)(u,v) of vertices on the constructed path. If both u and v correspond to vertices in U, then clearly there is an arc from u to v by construction, because u and v inherit all the in- and out-arcs of the corresponding vertices. If u=wiℓ1u=w^1_i_ for some ℓ∈[t],iℓ∈ ∈[t],i_ , then by construction, it must be that v=wiℓ2v=w^2_i_ , because wiℓ1w^1_i_ has no other out-neighbors. By construction, arc (u,v)(u,v) clearly exists on H. Similarly, if v=wiℓ2v=w^2_i_ for some ℓ∈[t],iℓ∈ ∈[t],i_ , then it must be that u=wiℓ1u=w^1_i_ , because wiℓ2w^2_i_ has no other in-neighbors. Now consider the case when u=wiℓ2u=w^2_i_ for some ℓ∈[t],iℓ∈ ∈[t],i_ . If v corresponds to agent v^∈ v , then by construction H has an arc from u to v if and only if there is an arc from iℓi_ to v v in ℱF. Since v v and iℓi_ are consecutive agents on the path from xx to yy, such an arc must exist. Similarly, if v instead corresponds to an agent iℓ+1∈i_ +1 , then by construction v=wiℓ+11v=w^1_i_ +1 and H has an arc from u to v if and only if there is an arc from iℓi_ to iℓ+1i_ +1 on ℱF. Since they are on the path from xx to yy, such an arc must exist. The case where v=wiℓ1v=w^1_i_ for some ℓ∈[t],iℓ∈ ∈[t],i_ is analogous. We have now shown that H contains a path from uxu_x to uyu_y. We can analogously show that H contains a path from uyu_y to uxu_x. It remains to show that the total weight of the arcs in H does not exceed δ=kδ=k. Observe that the only arcs with a positive weight in H are (wi1,wi2)∣i∈′\(w^1_i,w^2_i) i∈W \ and each of those has weight one. Clearly |(wi1,wi2)∣i∈′|=|′|≤k=δ|\(w^1_i,w^2_i) i∈W \|=|W |≤ k=δ, as required. (end of the proof of Claim 23.1) ⋄ Claim 23.2. If I is a Yes-instance of 2-DSN, then ((=∪,ℱ),x,y,k)((V=U ,F),x,y,k) is a Yes-instance of FriHG- CS- PA- AddAg. Proof. Let H=(V′,A′)H=(V ,A ) be a subgraph of G that contains a path from uxu_x to uyu_y and vice versa and ∑a∈A′ω(a)≤δ _a∈ A ω(a)≤δ. We construct a subset ′⊆W as follows: For every a∈A′a∈ A , if a=(wi1,wi2)a=(w^1_i,w^2_i) for some i∈i , then add ii to ′W . Observe that since the arcs that are (wi1,wi2)(w^1_i,w^2_i) for some i∈i are the only arcs in G with non-zero weight, and their weight is 1, we must have that |′|≤δ=k|W |≤δ=k, as required. Let us first show that ℱ[∪′]F[U∪W ] admits a core stable partition where xx and yy are in the same coalition. By Observation 7, it is sufficient to show that ℱ[∪′]F[U∪W ] admits a path from xx to yy and vice versa. Let ux,v1,…,vt,uyu_x,v_1,…,v_t,u_y be a path from uxu_x to uyu_y in H. If v1v_1 corresponds to an agent i∈i , then by construction ℱ[∪′]F[U∪W ] must contain the arc (x,i)(x,i). Since x∈x , we can continue the reasoning starting from v1v_1. If v1=wi1v_1=w^1_i for some i∈i , then we must have that v2=wi2v_2=w^2_i, because wi1w^1_i only has an out-arc to wi2w^2_i and wi1w^1_i is on a path to uyu_y. Then i∈′i∈W and moreover ℱF contains the arc (x,i)(x,i). Since i∈∪′i ∪W , we can continue the reasoning starting from v2v_2; recall that wi2w^2_i inherits all the out-arcs of ii. By repeating this reasoning, we obtain that there must be a path from xx to yy in ∪′U∪W . Analogous reasoning shows us that there is a path from yy to xx as well. (end of the proof of Claim 23.2) ⋄ By Claims 23.1 and 23.2 we can construct every instance of FriHG- CS- PA- AddAg to an equivalent instance of 2-DSN. As 2-DSN is solvable in time O(mn+n2log(n))O(mn+n^2 (n)) Feldman and Ruhl (2006); Li et al. (1992); Natu and Shu-Cherng (1997), FriHG- CS- PA- AddAg is solvable in time O(n3)O(n^3), where n is the number of agents. Observation 3 shows that FriHG- CS- NA- AddAg is then also polynomial-time solvable, in particular solvable in time O(n4)O(n^4). However, the algorithm obtained through Observation 3 is suboptimal: We can obtain a n2n^2 running time by using Dijkstra’s algorithm to find the minimum-weight cycle containing xx. ∎ A.9. Proof of Theorem 13 See 13 Proof. We first show that FriHG-S- GR- AddAg is W[2]-hard wrt. k for every ∈ S∈\ IR, IS, NS, CS\. As mentioned, we reduce from the following problem, which is W[2]-hard wrt. the solution size h: Set Cover Input: A n n-element set ℰ=[n^]E=[ n] and a collection =S1,…,SmS=\S_1,…,S_m\ of subsets of ℰE, an integer h. Question: Does S contain a of size at most h for ℰE, i.e., a subcollection ⊆K such that ||≤h|K|≤ h and ∪Sj∈Sj=ℰ _S_j S_j=E? Let I=(ℰ=[n^],,I=(E=[ n],S, h)h) be an instance of Set Cover. Let us construct an instance of FriHG with an agent set =∪V=U and friendship graph ℱF as follows: Let ≔ui∣i∈[n^]U \u_i i∈[ n]\ and ≔sj∣Sj∈W \s_j S_j \. For every i∈[n^]i∈[ n], agent uiu_i is mutually friends with sjs_j if and only if i∈Sji∈ S_j. Moreover, the agents in sj∣Sj∈\s_j S_j \ are all friends with each other. The preferences are symmetric. Moreover, we set k≔hk h to complete the construction. Claim 23.3. If I is a Yes-instance of Set Cover, then there is ′⊆W such that |′|≤h|W |≤ h and the grand coalition partition of ∪′U∪W is CS. Proof. Let K be a cover of ℰE such that ||≤h|K|≤ h. Let ′≔sj∣Sj∈W \s_j S_j \. Clearly |′|=||≤k|W |=|K|≤ k. It remains to show that the grand coalition partition is a CS partition of ∪′U∪W . Recall that by Dimitrov et al. (2006) it is sufficient to show that ℱ[∪′]F[U∪W ] is strongly connected. Since K is a cover of [n^][ n], for every i∈[n^]i∈[ n] there is a set Sj∈S_j such that i∈Sji∈ S_j. Thus uiu_i has a mutual friend SjS_j among ∪′U∪W . Since the ℱ[′]F[W ] is a clique, we must have that ℱ[∪′]F[U∪W ] is strongly connected, as required. (end of the proof of Claim 23.3) ⋄ Claim 23.4. If there is ′⊆W such that |′|≤k|W |≤ k and the grand coalition partition of ∪′U∪W is IR, then I is a Yes-instance of Set Cover. Proof. Let ≔Sj∈∣sj∈′K \S_j s_j∈W \. Clearly ||=|′|≤h|K|=|W |≤ h. It remains to show that K is a cover of ℰE. Since grand coalition partition is IR, every agent must obtain a friend, as otherwise he would prefer being alone. Observe that for every i∈[n^]i∈[ n], agent uiu_i must have a friend among ∪′U∪W . By construction the only friends of uiu_i are sjs_j such that Sj∈,i∈SjS_j ,i∈ S_j. Thus K must contain a set SjS_j such that i∈Sji∈ S_j. As this holds for every i∈ℰ,i , K is a cover of ℰE. (end of the proof of Claim 23.4) ⋄ Claims 23.3 and 23.4 show that for every ∈ S∈\ IR, IS, NS, CS\, FriHG-S- GR- AddAg is W[2]-hard wrt. k: If (ℰ,,h)(E,S,h) is a Yes-instance, then by Claim 23.3 ((=∪),k)((V=U ),k) is also a Yes-instance; recall that by definition CS implies IR and by Observation 3 the grand coalition partition is IR if and only if it is also IS and NS. Next, if ((=∪),k)((V=U ),k) is a Yes-instance, then so is ((ℰ,),h)((E,S),h) by Claim 23.4. We can use Claim 23.4 because a partition that is IS, NS, or CS must also be IR. This concludes showing that FriHG-S- GR- AddAg is W[2]-hard wrt. k. Next we show that FriHG- S- GR- AddAg is in XP wrt. k for every ∈ S∈\ IR, IS, NS, CS\. Observe that we can verify in polynomial time whether the grand coalition partition is S: For IR, IS, and NS this is clear from the definition, and by Observation 7 to verify CS it is sufficient to check that the friendship graph of the grand coalition partition is strongly connected. Thus we can try every subset of W of cardinality at most k. The number of such subsets is in O(||k)O(|W|^k), and thus this simple brute-force algorithm is in XP wrt. k. ∎ A.10. Proof of Proposition 14 See 14 Proof. Recall that by Observation 3 IR, IS, and NS are equivalent for grand coalition partition. Thus FriHG- IR- GR- DelAg, FriHG- IS- GR- DelAg, and FriHG- NS- GR- DelAg are equivalent. To solve FriHG- IR- GR- DelAg, we start with the agent set U and recursively remove every agent who does not have any friends among the remaining agents. We repeat this as long as every remaining agent has at least one friend. If the number of removed agents is at most k, then we return yes, otherwise no. For correctness, first observe that after the recursive removal, every agent has a friend among the remaining agents. Thus the grand coalition partition is IR. Also observe that a grand coalition partition of a set of agents is IR if and only if everyone has a friend in it. No agent who is removed can be in a coalition where every agent has a friend. Hence the algorithm removes the smallest number of agents such that the grand coalition partition of the remaining agents is IR. Initially checking whether an agent has no friends can be done in time O(||)O(|V|). When recursively deleting agents, we touch any edge only when we delete it. For each edge deletion, we can check whether someone who considers him a friend should be removed. Hence the number of operations during the deletion process is in O(|A(ℱ)|)O(|A(F)|) and the algorithm’s time complexity is O(||+|A(ℱ)|)O(|V|+|A(F)|). Next, let us describe an algorithm for FriHG- CS- GR- DelAg. We compute the strongly connected components of ℱF, select a largest-cardinality strongly connected component, and remove all the other agents. If the cardinality of the removed agents is at most k, we return yes, otherwise we return no. For correctness, recall that by Observation 7 grand coalition partition is CS if and only if it is connected. Observe that after the removal, the remaining set of agents form a strongly connected component of ℱF. Moreover, since removing agents cannot make a pair of agents connected, the agents in a largest strongly connected component is a largest subset of agents such that the grand coalition partition of them is CS. The algorithm runs in the same time as computing strongly connected components. We can recognize strongly connected components in time O(||+|A(ℱ)|)O(|V|+|A(F)|). ∎ Appendix B Additional material for Section 5 B.1. Figure for Theorem 15 Sketch of of the preference graph for Theorem 15; see Figure 2. 111111111111−1-111−1-1−1-1−1-1−1-111111111111111111111−1-1−1-1−1-1−1-1xxu1u_1u2u_2u3n^−1u_3 n-1u3n^u_3 ny0y_0y1y_1s1s_1s2s_2sjs_js3n^s_3 n… Figure 2. Illustration of the relevant part of the reduction for Theorem 15, assuming that S1=1,2,3n^−1S_1=\1,2,3 n-1\ and Sj=2,3n^−1,3n^S_j=\2,3 n-1,3 n\. The remaining negative utilities to xx and the negative utilities of the set-agents are omitted in the figure. B.2. Proof of Claim 15.1 See 15.1 Proof. To show the statement, we show that every agent has zero utility towards his coalition under Π . Let us first consider agent xx, he has no preference to any of the agents, thus his utility towards his coalition Π(x) (x) is 0. Next we show that every element-agent ui,i∈[3n^]u_i,i∈[3 n], has zero utility towards his coalition. All have -1 utility towards xx and y1y_1. Every element-agent is together with ui+1u_i+1 for which uiu_i has positive utility, except u3n^u_3 n has positive utility towards y0y_0. Since K is an exact cover, there must be a set Sj∈S_j such that i∈Sji∈ S_j. Thus, μui(Π(ui))=μui(x,y1,ui+1,sj)=−1−1+1+1=0 _u_i( (u_i))= _u_i(\x,y_1,u_i+1,s_j\)=-1-1+1+1=0 for i∈[3n^−1]i∈[3 n-1] and μu3n^(Π(u3n^))=μu3n^(x,y1,y0,sj)=−1−1+1+1=0 _u_3 n( (u_3 n))= _u_3 n(\x,y_1,y_0,s_j\)=-1-1+1+1=0. Auxiliary-agents y0,y1y_0,y_1 both have negative utility towards xx, but y0y_0 has positive utility towards y1y_1 and y1y_1 has positive utility towards u1u_1. Thus, both have zero utility towards their coalition. All set-elements sjs_j whose corresponding set Sj∈S_j have negative utility towards x and positive utility towards y1y_1. Hence, set K is an exact cover, all sets in K are pairwise disjoint, ensuring that no set-agent sjs_j has negative utility towards any other set-agent in Π(sj) (s_j). It holds that μsj(Π(sj))=μsj(x,y1)=−1+1=0 _s_j( (s_j))= _s_j(\x,y_1\)=-1+1=0 and so Π(sj) (s_j) is IR for every set-agent from K. Clearly, every set-agent sjs_j with Sj∉S_j has zero utility towards his singleton coalition. This concludes the proof of Π being IR. ∎ B.3. Proof of Proposition 16 See 16 Proof. If the preference graph of the AddHG- IR- NA- AddAg instance is a DAG, then the special agent x∈x will always be alone in an IR partition Π if and only if xx has only negative in- or out-arcs to every other agent. Considering the case where xx has only negative in- or out-arcs. If xx is in a coalition C with agent a with μx(a)<0 _x(a)<0, then xx will always have negative utility towards C and wishes to deviate from C. Now suppose that xx is in a coalition C with agent a with μa(x)<0 _a(x)<0. In order for a not to deviate, there must exist another agent i∈Ci∈ C with μa(i)≥μa(x) _a(i)≥ _a(x). However, again either μx(i)<0 _x(i)<0 or μi(x) _i(x) holds. In the first case, as we have already seen, xx wishes to deviate from C. In the second case, agent i must itself be compensated by another agent j∈Cj∈ C such that μi(j)≥μi(x) _i(j)≥ _i(x). Repeating this argument, we must eventually terminate with an agent i∗∈∖xi^* \x\ who has negative utility towards C or agent xx has negative utility towards C. Hence, C cannot be IR. In the other case where there exists an agent a∈∪a with μx(a)≥0 _x(a)≥ 0 or μa(x)≥0 _a(x)≥ 0, then the partition Π with Π(x)=Π(a)=x,a (x)= (a)=\x,a\ and Π(a′)=a′ (a )=\a \ for all a′∈∖x,aa \x,a\ is IR. If the utilities of the AddHG- IR- NA- AddAg instance is symmetric, then we only need to find an agent a∈a with μx(a)=μa(x)≥0 _x(a)= _a(x)≥ 0. Note that in both cases, when the instance is a DAG or has symmetric preferences, we would need to add at most one additional agent from W to find an IR partition with x not being alone. ∎ B.4. Proof of Theorem 17 See 17 Proof. The NP-containment follows directly from Observation 2. Moreover, since k=0k=0, both control problems reduce to checking whether there is an IS or NS partition where a given pair of agents is in the same coalition. It remains to show the NP-hardness for the mentioned restriction. We reduce again from RX3C. Let I=(ℰ=[3n^],)I=(E=[3 n],S) be an instance of RX3C and we construct an AddHG-instance with an acyclic preference graph. The set of agents is =x,y∪ui∣i∈ℰ∪sj∣Sj∈∪dℓ1,dℓ2,dℓ3∣ℓ∈[2n^]U=\x,y\∪\u_i i \∪\s_j S_j \∪\d_ ^1,d_ ^2,d_ ^3 ∈[2 n]\, where – x is the special agent, – each element i∈ℰi has one -agent uiu_i, – each set Sj∈S_j has one -agent sjs_j, – and auxiliary-agent dℓ1,dℓ2,dℓ3d_ ^1,d_ ^2,d_ ^3, for ℓ∈[2n^] ∈[2 n] occurring in triples. We construct the utilities as follows; the unmentioned utilities are 0: – For each element i∈[3n^]i∈[3 n], set μy(ui)=1 _y(u_i)=1. – For each agent a∈∖x,ya \x,y\, set μx(a)=−1 _x(a)=-1. – For each set Sj∈S_j and all elements i∈Sji∈ S_j, set μsj(ui)=1 _s_j(u_i)=1. – For each set Sj∈S_j and each index ℓ∈[2n^] ∈[2 n], set μsj(dℓ1)=μsj(dℓ2)=μsj(dℓ3)=1 _s_j(d_ ^1)= _s_j(d_ ^2)= _s_j(d_ ^3)=1. – For all ℓ∈[2n^] ∈[2 n], set μdℓ1(dℓ2)=μdℓ1(dℓ3)=μdℓ2(dℓ3)=1 _d_ ^1(d_ ^2)= _d_ ^1(d_ ^3)= _d_ ^2(d_ ^3)=1. The preference graph of the instance is depicted in Figure 3. Before we show the correctness, we first observe that the following sequence is a topological order of the preference graph: y,x,s1,s2,…,s3n^,u1,u2,…,u3n^,d11,d12,d13,d21,d22,d23…,d2n^1,d2n^2,d2n^3y,x,s_1,s_2,…,s_3 n, u_1,u_2,…,u_3 n, d_1^1,d_1^2,d_1^3, d_2^1,d_2^2,d_2^3…, d_2 n^1,d_2 n^2,d_2 n^3. In the forward direction of the correctness proof, we show that if I has an exact cover, we can construct a NS partition with |Π(x)|≥2| (x)|≥ 2, which is by Observation 1 also IS. In the backward direction, we assume the partition Π being IS–an even weaker assumption than NS–and show that this implies the existence of an exact cover for I. Claim 23.5. If K is an exact cover for I, then the following partition Π is NS: Π(x)=x,y (x)=\x,y\, Π(sj)=sj,uj1,uj2,uj3 (s_j)=\s_j,u_j_1,u_j_2,u_j_3\ for Sj=j1,j2,j3∈S_j=\j_1,j_2,j_3\ and Π(sj)=sj,dℓ1,dℓ2,dℓ3 (s_j)=\s_j,d_ ^1,d_ ^2,d_ ^3\ for Sj∉S_j for some ℓ∈[2n^] ∈[2 n]. Proof. To show the statement, we need to show that every agent i∈i has no incentive to leave his current coalition, i.e., there exist no other coalition C∈ΠC∈ with C∪i≻iΠ(i)C∪\i\ _i (i). Let us first consider agent x. He has negative utility towards every agent except agent y and therefore wants to stay in his current coalition. Agent y has utility 1 towards his coalition x,y\x,y\ and also towards all the other coalitions C∈ΠC∈ , because they all contain only one set-agent sjs_j. Hence, agent y also wants to stay in his coalition with agent x. For the set-agents sj,Sj∈s_j,S_j , they are either in a coalition with their three element-agents uiu_i or with three auxiliary-agents dℓ1,dℓ2,dℓ3\d_ ^1,d_ ^2,d_ ^3\ for some ℓ∈[2n^] ∈[2 n]. In both cases, the set-agents have utility 3 towards their coalitions and therefore, leaving a coalition would not strictly improve the utility. The element-agents uiu_i, for i∈[3n^]i∈[3 n], do not have any preferences, so they also do not want to deviate. Auxiliary-agents dℓ1d_ ^1 for ℓ∈[2n^] ∈[2 n] have utility 2 towards their coalitions and dℓ2d_ ^2 for ℓ∈[2n^] ∈[2 n] have utility 1 which is in both cases the maximum utility they can get. The agents dℓ3d_ ^3 do not have any preferences, so they also do not want to deviate. (end of the proof of Claim 23.5) ⋄ Claim 23.6. If Π is an IS partition with |Π(x)|≥2| (x)|≥ 2, then y∈Π(x)y∈ (x) and all set-agents which are in a coalition with their three element-agents form an exact cover of I. Proof. We aim to show that all set-agents which are in a coalition with their three element-agents form an exact cover of I. By assumption, let C be the coalition containing x. The only coalition C with x not alone is x,y\x,y\, because agent x has negative utility towards every other agent and would then prefer being alone. Hence, agent y has utility 1 towards coalition C. As we know that Π is IS, no two set-agents are in the same coalition. Otherwise, agent y would prefer joining that coalition. We also know that for all ℓ∈[2n^] ∈[2 n], all three auxiliary-agents–dℓ1d_ ^1, dℓ2d_ ^2 and dℓ3d_ ^3–must be in the same coalition. If dℓ1d_ ^1 is not in the same coalition with dℓ2,dℓ3\d_ ^2,d_ ^3\, dℓ1d_ ^1 would have utility 0 towards his coalition and would therefore want to deviate to a coalition containing dℓ2d_ ^2 or dℓ3d_ ^3. If dℓ2d_ ^2 is not in the same coalition with dℓ1,dv3\d_ ^1,d_v^3\, he would want to deviate to the coalition containing dℓ3d_ ^3. The same happens if dℓ3d_ ^3 was separated: Then also dℓ2d_ ^2 would want to join the coalition containing dℓ3d_ ^3. Two auxiliary-agent triples dℓ1,dℓ2,dℓ3\d_ ^1,d_ ^2,d_ ^3\ and dℓ′1,dℓ′2,dℓ′3\d_ ^1,d_ ^2,d_ ^3\ cannot be in the same coalition. Suppose, towards a contradiction, there exists a coalition C′C containing at least two different auxiliary-agents triples, i.e. C′⊆dℓ1,dℓ2,dℓ3,dℓ′1,dℓ′2,dℓ′3C \d_ ^1,d_ ^2,d_ ^3,d_ ^1,d_ ^2,d_ ^3\. Any set-agent sjs_j has utility 6 towards C′C , therefore all set-agents sjs_j must have utility at least 6 towards their coalition in order for Π to remain IS. Hence, the set-agents are together either with (1) their three element-agents and an auxiliary-agent triple or (2) two auxiliary-agent triples. However, at most n n set-agents can be together with his three element-agents and an auxiliary-agent triple. For the remaining 2n^2 n set-agents, only n n auxiliary-agents triples are available. Therefore, there must exist one set-agent sj∗s_j^* without any element-agent nor auxiliary-agents because all set-agents are in different coalitions. The set-agent sj∗s_j^* has utility 0 towards his coalition, wanting to deviate to a coalition with auxiliary-agents, a contradiction to Π being IS. It remains to show that every set-agents sj,Sj∈s_j,S_j are either together with his three element-agents uj1,uj2,uj3u_j_1,u_j_2,u_j_3 contained in Sj=j1,j2,j3S_j=\j_1,j_2,j_3\ or with exactly three auxiliary-agents dℓ1,dℓ2,dℓ3\d_ ^1,d_ ^2,d_ ^3\ for some ℓ∈[2n^] ∈[2 n]. We have shown that an auxiliary-agent triple dℓ1,dℓ2,dℓ3\d_ ^1,d_ ^2,d_ ^3\ is together in a coalition and no two different auxiliary-agent triples dℓ1,dℓ2,dℓ3\d_ ^1,d_ ^2,d_ ^3\ and dℓ′1,dℓ′2,dℓ′3\d_ ^1,d_ ^2,d_ ^3\ are in the same coalition. Hence, every set-agent sjs_j must have utility at least three towards his coalition. But at most 2n^2 n set-agents can be together with an auxiliary-agent triple. Thus, n n set-agents must be together with their corresponding three element-agents, which implies that the sets corresponding to these set-agents form an exact-cover. (end of the proof of Claim 23.6) ⋄ −1-1−1-1−1-1−1-11111111111111111111111111111111111111111111111xxyyu1u_1u2u_2uiu_iu3n^u_3 ns1s_1s2s_2sjs_js3n^s_3 nd11d_1^1d12d_1^2d13d_1^3d2n^1d_2 n^1d2n^2d_2 n^2d2n^3d_2 n^3… Figure 3. Illustration of the relevant part of the reduction for Theorem 17, assuming that S1=1,2,iS_1=\1,2,i\ and Sj=2,i,3n^S_j=\2,i,3 n\. The correctness follows immediately from Claims 23.5 and 23.6. Finally, we note that the same construction also works for PA when we enforce that x and y must be in the same coalition. ∎ B.5. Figure of Theorem 18 Sketch of the preference graph for Theorem 18, see Figure 4. −1-1−1-1−1-1−1-1111111111133333333111111111111xxyyu1u_1u2u_2uiu_iu3n^u_3 ns1s_1s2s_2sjs_js3n^s_3 nd1d_1d2n^d_2 n… Figure 4. Illustration of the relevant part of the reduction for Theorem 18, assuming that S1=1,2,iS_1=\1,2,i\ and Sj=2,i,3n^S_j=\2,i,3 n\. Note that x has negative edges between all other agents (except y) and s1,…,s3n^,d1,…,d2n^\s_1,…,s_3 n\,\d_1,…,d_2 n\ form a complete bipartite graph. B.6. Proof of Claim 18.1 See 18.1 Proof. To show the statement, we need to show that every agent i∈i has no incentive to leave his current coalition, i.e., there exist no other coalition C∈ΠC∈ with C∪i≻iΠ(i)C∪\i\ _i (i). Let us first consider special agent xx. It has utility 1 towards his coalition x,y\x,y\ but to all others he has negative utility. So agent xx wants to stay in his coalition. Agent y has also utility 1 towards his coalition, so do all other coalitions containing exactly one set-agent sjs_j. Therefore, agent y would not improve by joining another existing coalition. All set-agents sjs_j, for Sj∈S_j , have utility 3 towards their coalitions. Either they are together with three element-agents uiu_i with i∈Sji∈ S_j or with an auxiliary-agent dℓd_ , for some ℓ∈[2n^] ∈[2 n]. Joining another coalition would not increase the utility and thus the set-agents sjs_j have no incentive to leave their current coalitions. The element-agents uiu_i have utility 1 towards their coalitions with a set-agent. They also have at most utility 1 towards every other set-agent, but they all are in different coalitions, hence no element-agent would improve by switching to another coalition. The same argument holds for auxiliary-agents dℓd_ , as they have utility 3 towards their coalitions. No two set-agents are in the same coalition. Therefore, the auxiliary-agents also do not have an incentive to leave their current coalitions. ∎ B.7. Proof of Claim 18.2 See 18.2 Proof. We aim to show that all set-agents which are in a coalition with their three element-agents form an exact cover of I. By assumption, let C:=Π(x)C:= (x) with |C|≥2|C|≥ 2 be a coalition containing x in an IS partition. All coalitions with x not alone must be at least with agent y, because agent x has negative utility towards every other agent. There can be at most one other agent besides y in C, otherwise x would deviate to his singleton coalition. A set-agent with sj∈Cs_j∈ C is not possible because sjs_j would have utility 0 towards C. But sjs_j has only negative utility towards agent x, so he would prefer any different coalition containing an auxiliary-agent dℓd_ or an element-agent uiu_i with i∈Sji∈ S_j. Element-agents uiu_i and auxiliary-agents dℓd_ already have negative utility for the coalition x,y⊆C\x,y\ C, so they would prefer to be alone rather than join it. Thus, the only coalition C containing x is x,y\x,y\. Every agent a∈∖x,ya \x,y\ has negative utility only toward agent x. Thus, for every agent j∈j and every a∈∖xa \x\ holds that agent j is indifferent between the coalitions Π(j)∪a (j)∪\a\ and Π(j) (j). Therefore, we can argue in the following that no agent has an incentive to deviate to an existing coalition in Π . We know that y does not want to deviate to another coalition, so no two set-agents sjs_j can be in the same coalition; otherwise y would prefer to join them, contradicting Π being IS. We now want to show that no two auxiliary-agents can be in the same coalition in Π . Suppose, towards a contradiction, that for two auxiliary-agents dℓ,dℓ′d_ ,d_ , it holds that C′:=Π(dℓ)=Π(dℓ′)C := (d_ )= (d_ ). So all set-agents sjs_j have utility 6 towards C′C . Since Π is IS all set-agents must also have utility 6 towards their coalition Π(sj) (s_j). We can say that at most n n coalitions with at least two auxiliary-agents can exist. Thus, at most n n set-agents can be within those coalitions and at least the remaining 2n^2 n set-agents must be together with their element-agents. But every set-agent has only three element-agents with utility greater than 0, so they can have at most utility 3 towards their coalition. They would then want to deviate to, e.g., C′C and therefore Π would not be IS anymore, contradiction. No two set-agents sjs_j can be in the same coalitions and no two auxiliary-agents dℓd_ can be in the same coalition. In order for Π to be IS, every dℓd_ must be with a set-agent sjs_j in a coalition; otherwise dℓd_ would deviate to a coalition containing a set-agent. Therefore, 2n^2 n set-agents are with exactly one auxiliary-agent in the same coalition and have utility 3 towards their coalitions. The remaining n n set-agents sjs_j without any auxiliary-agent must also have utility 3 towards their coalitions, this can only be achieved being together with all their element-agents uiu_i with i∈Sji∈ S_j. This means, the sets corresponding to these n n set-agents must form a set cover, and since every set contains exactly three elements, these n n sets cover 3n^3 n elements, which implies these sets form an exact cover. ∎ B.8. Proof of Theorem 19 See 19 Proof. By Observation 4, it suffices to consider the stability concept IR. To show NP-hardness, we again reduce from RX3C. Let I=(ℰ=[3n^],)I=(E=[3 n],S) be an instance of RX3C. Let us construct a hedonic game instance with additive preferences as follows. The set of agents is =y0∪yi,ui∣i∈ℰ∪sj∣Sj∈U=\y_0\∪\y_i,u_i i \∪\s_j S_j \, where – y0y_0 is a special agent, – each element i∈ℰi has one -agent uiu_i and an -agent yiy_i, – and each set Sj∈S_j has one -agent sjs_j. We construct the utilities as follows; the unmentioned utilities are 0: – Set μy0(y1)=−2,μy0(u1)=1 _y_0(y_1)=-2, _y_0(u_1)=1, and μy0(y2)=1 _y_0(y_2)=1. – For all i∈[3n^−2]i∈[3 n-2], set μyi(yi+1)=−2 _y_i(y_i+1)=-2, μyi(ui+1)=μyi(yi+2)=1 _y_i(u_i+1)= _y_i(y_i+2)=1. – Set μy3n^−1(y3n^)=−1,μy3n^−1(u3n^)=1 _y_3 n-1(y_3 n)=-1, _y_3 n-1(u_3 n)=1. – For all i∈[3n^]i∈[3 n], set μui(yi)=−1 _u_i(y_i)=-1. – For all Sj∈S_j and all i∈Sji∈ S_j, set μui(sj)=1 _u_i(s_j)=1. – For all Sj,Sℓ∈S_j,S_ with j<ℓj< and Sj∩Sℓ≠∅S_j∩ S_ ≠ , set μsj(sℓ)=−1 _s_j(s_ )=-1. The preference graph of the instance is depicted in Figure 5. To complete the construction, we define x,y=y0,y1\x,y\=\y_0,y_1\ as the pair of agents which we aim to be in the same coalition in an IR partition. Before we show the correctness, we first observe that the following sequence is a topological ordering of the preference graph: y0,u1y_0,u_1, y1y_1, u2,y2,…,u3n^,y3n^,u_2,y_2,…,u_3 n,y_3 n, s1,…,s3n^s_1,…,s_3 n. We observe the following regarding the maximum degree in the preference graph: Observation 9. Every vertex in the preference graph has degree at most nine. We analyze the degree of every vertex one by one. – The agent y0y_0 has two out-arcs and no in-arcs. – Every auxiliary-agent yiy_i has at most three in-arcs and three out-arcs. – Every element-agent uiu_i has at most one in-arc and four out-arcs. – Every set-agent sjs_j has three in-arcs from the element-agents corresponding to the elements contained in SjS_j. Moreover, since every element appears in exactly three sets, there are at most six sets that intersect any given set. Thus, a set-agent has maximum degree nine. Claim 23.7. If K is an exact cover for I, then the following partition Π with Π(y0)=y0,y1,…,y3n^,u1,…,u3n^∪sj∣Sj∈ (y_0)=\y_0,y_1,…,y_3 n,u_1,…,u_3 n\∪\s_j S_j \, and Π(sj)=sj (s_j)=\s_j\ for all Sj∉S_j is IR. Proof. To show the statement, we show that every agent has zero utility towards his coalition under Π . Let us first consider agent y0y_0 and all the auxiliary-agents. We observe that μy0(Π(y0))=μy0(y1,y2,u1)=−2+1+1=0 _y_0( (y_0))= _y_0(\y_1,y_2,u_1\)=-2+1+1=0, as required. For every i∈[3n^−2]i∈[3 n-2], it holds that μyi(Π(yi))=μyi(yi+1,yi+2, _y_i( (y_i))= _y_i(\y_i+1,y_i+2, ui+1)=−2+1+1=0u_i+1\)=-2+1+1=0, as required. We have that μy3n^−1(Π(y3n^−1))=μy3n^−1(y3n^,u3n^)=−1+1=0 _y_3 n-1( (y_3 n-1))= _y_3 n-1(\y_3 n,u_3 n\)=-1+1=0, as required. Since y3n^y_3 n has utility zero towards every other agent, his utility is zero as well. Next we show that every element-agent uiu_i, for i∈[3n^]i∈[3 n], has zero utility towards his coalition as well. Since K is an exact cover, there must be a set Sj∈S_j such that i∈Sji∈ S_j. Thus μui(Π(ui))=μui(yi,sj)=−1+1=0 _u_i( (u_i))= _u_i(\y_i,s_j\)=-1+1=0, as required. Finally, we show that every set-agent sjs_j, with Sj∈S_j , has zero utility towards his coalition. This is clearly the case for each set-agent sjs_j with Sj∉S_j since he is in his own singleton coalition. Since K is an exact cover, no two sets in K intersect (as otherwise ||>n^|K|> n). Hence, μsj(Π(sj))=0 _s_j( (s_j))=0 also holds for every set-agent sjs_j with Sj∈S_j . This concludes the proof. (end of the proof of Claim 23.7) ⋄ Claim 23.8. If Π is an IR partition with Π(y0)=Π(y1) (y_0)= (y_1), then the sets corresponding to the set-agents contained in Π(y0) (y_0) form an exact cover of I. Proof. By assumption, let C be the coalition containing y0y_0 and y1y_1. We aim to show that the sets corresponding to the set-agents contained in C form an exact cover of I. We first show that all auxiliary- and element-agents are contained in C. We achieve this by showing that for each i∈0∪[3n^−2]i∈\0\∪[3 n-2], if yi,yi+1∈Cy_i,y_i+1∈ C, then yi+2,ui+1∈Cy_i+2,u_i+1∈ C as well. Notice that for each i∈0∪[3n^−2]i∈\0\∪[3 n-2], agent yiy_i has −2-2 utility towards yi+1y_i+1, 11 utility towards yi+2y_i+2 and ui+1u_i+1, and zero utility towards all remaining agents. Since yiy_i and yi+1y_i+1 are both in C, in order for C to be IR, we have both yi+2y_i+2 and ui+1u_i+1 in C. Since every element-agent uiu_i has −1-1 utility towards his auxiliary-agent yiy_i, by previous paragraph and by the utilities of uiu_i, coalition C has to have at least one set-agent sjs_j such that i∈Sji∈ S_j to make sure overall utility of uiu_i become non-negative. This implies that the sets corresponding to the set-agents in C form a set cover. Let K be the set =Sj∣sj∈CK=\S_j s_j∈ C\. To show that K is indeed an exact cover it suffices to show that no two sets in K intersect. Suppose, towards a contradiction, that K contains SjS_j and Sj′S_j with Sj∩Sj′≠∅S_j∩ S_j ≠ . Without loss of generality, let j<j′j<j . Then, sjs_j has −1-1 utility towards sj′s_j . Since no set-agent has positive utility towards any other agent, coalition C yields negative utility for sjs_j and is not IR for him, a contradiction. (end of the proof of Claim 23.8) ⋄ −2-2−2-2−2-2−2-2−1-11111111111111111−1-1−1-1−1-1−1-1−1-1−1-1111111−1-1−1-11111y0y_0y1y_1y2y_2y3y_3y3n^−2y_3 n-2y3n^−1y_3 n-1y3n^y_3 nu1u_1u2u_2u3u_3u3n^−2u_3 n-2u3n^−1u_3 n-1u3n^u_3 ns1s_1s2s_2s3s_3s3n^−2s_3 n-2s3n^s_3 n… Figure 5. Illustration of the relevant part of the reduction for Theorem 19, assuming that element 11 appears in sets S1,S3S_1,S_3, and S3n^S_3 n. By Observation 1, the correctness of the construction follows immediately from Claims 23.7 and 23.8. ∎ B.9. Proof of Theorem 20 See 20 Proof. We again provide a reduction from RX3C problem. Let I=(ℰ=[3n^],)I=(E=[3 n],S) be an instance of RX3C and we construct a hedonic game instance with symmetric preferences as follows. The set of agents is =x∪ui∣i∈ℰ∪sj∣Sj∈∪dℓ∣ℓ∈[2n^]U=\x\∪\u_i i \∪\s_j S_j \∪\d_ ∈[2 n]\, where – x is an auxiliary-agent – each element i∈ℰi has one -agent uiu_i, – each set Sj∈S_j has one -agent sjs_j, – and auxiliary-agents dℓd_ for ℓ∈[2n^] ∈[2 n]. We construct the symmetric utilities as follows; the unmentioned utilities are 0: – For all i∈[3n^]i∈[3 n], set μx(ui)=μui(x)=−3 _x(u_i)= _u_i(x)=-3. – For all Sj∈S_j , set μx(sj)=μsj(x)=9 _x(s_j)= _s_j(x)=9. – For all i∈[3n^−1]i∈[3 n-1], set μui(ui+1)=μui+1(ui)=1 _u_i(u_i+1)= _u_i+1(u_i)=1 and μu1(u3n^)=μu3n^(u1)=1 _u_1(u_3 n)= _u_3 n(u_1)=1. – For all Sj∈S_j and all i∈Sji∈ S_j, set μui(sj)=μsj(ui)=1 _u_i(s_j)= _s_j(u_i)=1. – For all Sj,Sℓ∈S_j,S_ with Sj∩Sℓ≠∅S_j∩ S_ ≠ , set μsj(sℓ)=μsℓ(sj)=−13 _s_j(s_ )= _s_ (s_j)=-13. – For all Sj∈S_j and all ℓ∈[2n^] ∈[2 n], set μsj(dj)=μdj(sj)=1 _s_j(d_j)= _d_j(s_j)=1. – For all ℓ∈[2n^] ∈[2 n], set μx(dℓ)=μdℓ(x)=−9 _x(d_ )= _d_ (x)=-9 – For all ℓ∈[2n^] ∈[2 n] and i∈[3n^]i∈[3 n], set μdℓ(ui)=μui(dℓ)=−3 _d_ (u_i)= _u_i(d_ )=-3. The preference graph of the instance is depicted in Figure 6. To complete the construction, we define x,u1\x,u_1\ as the pair of agents which we aim to be in the same coalition in an ,,\ IR, IS, NS\ partition. In the forward direction of the correctness proof, we show that if I has an exact cover, we can construct a NS partition with |Π(x)|=Π(u1)| (x)|= (u_1), which is by Observation 1 also ISand IR. In the backward direction, we assume the partition Π being IR–an even weaker assumption than NS–and show that this implies the existence of an exact cover for I. Claim 23.9. If K is an exact cover for I, then the following partition Π with Π(x)=x,u1,…,u3n^∪sj∣Sj∈ (x)=\x,u_1,…,u_3 n\∪\s_j S_j \, and for each Sj∉S_j , Π(sj)=sj,dℓ (s_j)=\s_j,d_ \ for one ℓ∈[2n^] ∈[2 n], is NS. Proof. To show the statement, we need to show that every agent i∈i has no incentive to leave his current coalition, i.e., there exist no other coalition C∈ΠC∈ with C∪i≻iΠ(i)C∪\i\ _i (i). Let us first consider agent x. Being together with all element-agents uiu_i leads to utility 3n^(−3)=−9n^3 n(-3)=-9 n. Since K is an exact cover, there are n n set-agents sjs_j in the same coalition with x. For each such set-agent, x has positive utility 99, so agent x has utility −9n^+9n^=0-9 n+9 n=0 to his coalition. For every coalition Π(sj) (s_j) with Sj∉S_j , agent xx also has utility 0 towards it. Therefore, agent xx does not want to deviate. Every element-agent uiu_i, for i∈[3n^]i∈[3 n], has negative utility of −3-3 towards x and positive utility of 11 to his predecessor ui−1u_i-1 and successor ui+1u_i+1 (Here, u1u_1 is the successor of u3n^u_3 n and u3n^u_3 n is the predecessor of u1u_1). Since K is an exact cover, there must exist a set Sj∈S_j with i∈Sji∈ S_j and so μui(sj)=1 _u_i(s_j)=1. Thus, μui(Π(ui))=μui(x,ui−1,ui+1,sj)=−3+1+1+1=0 _u_i( (u_i))= _u_i(\x,u_i-1,u_i+1,s_j\)=-3+1+1+1=0. For every coalition Π(sj) (s_j) with Sj∉S_j , each element-agent can have utility at most -2 towards it, because uiu_i has utility -3 towards dℓd_ and at most utility 1 to sjs_j. Thus, uiu_i does not want to deviate. All set-agents sjs_j, for Sj∈S_j , have positive utility 9 to x and 11 for each element-agent uiu_i with i∈Sji∈ S_j. Hence, K is an exact cover, there are no two sets Sj,Sℓ∈S_j,S_ with Sj∩Sℓ≠∅S_j∩ S_ ≠ . Therefore, the utility for every set-agent sjs_j towards his coalition is μsj(Π(sj))=μsj(x,uj1,uj2,uj3)=9+1+1+1=12 _s_j( (s_j))= _s_j(\x,u_j_1,u_j_2,u_j_3\)=9+1+1+1=12. Also, the set-agents sjs_j have no incentive to leave to a coalition with set-agents not in the exact cover, because this would only lead at most to utility 1. Clearly, every set-agent sjs_j with Sj∉S_j has utility one towards his coalition containing himself and an auxiliary-agent. They would not want to switch to another coalition with an auxiliary-agent because this does not improve the utility. Also, the coalition Π(x) (x) yields negative utility for sjs_j because SjS_j intersects with at least two sets in K, each contributing a utility of -13. The auxiliary-agents do not want to join the coalitions Π(sj) (s_j) with Sj∉S_j , because it would not yield a higher utility. Moreover, the coalition Π(x) (x) yields negative utility towards dℓd_ , since for each element-agent ui∈Π(x)u_i∈ (x), agent dℓd_ has utility -3. We showed that no agent has incentive to leave his current coalition, therefore, the constructed partition Π is NS. (end of the proof of Claim 23.9) ⋄ Claim 23.10. If Π is an IR partition with Π(x)=Π(u1) (x)= (u_1), then the sets corresponding to the set-agents contained in Π(x) (x) form an exact cover of I. Proof. Let C be the coalition containing agents x and u1u_1. We aim to show that the sets corresponding to set-agents contained in C form an exact cover of I. First, we show that there cannot be an auxiliary-agent dℓ∈Cd_ ∈ C. Suppose, by contradiction, that there is an auxiliary-agent dℓ∈Cd_ ∈ C. This would mean, u1u_1 would have utility -3 towards xx and dℓd_ in C. However, u1u_1 can obtain at most utility 5 from a coalition (three from a set-agent and two from u2u_2 and u3n^u_3 n), so C would be not IR for u1u_1, contradiction. Secondly, we show that there cannot be two set-agents sj,sj′∈Cs_j,s_j ∈ C with Sj∩Sj′≠∅S_j∩ S_j ≠ . Suppose, towards a contradiction, C contains two set-agents sj,sj′s_j,s_j with Sj∩Sj′≠∅S_j∩ S_j ≠ . Then, sjs_j has utility −13-13 towards sj′s_j and vice versa. Since every set-agent can have at most 12 utility towards any coalition (9 towards x and 1 for the three element-agents), coalition C must yield a negative utility for sjs_j and sj′s_j and is not IR for these two, a contradiction. Then, we show that all element-agents uiu_i for i∈[3n^]i∈[3 n] are contained in C. Agent u1u_1 has a negative utility −3-3 towards agent x. To make coalition C IR for u1u_1, we have to include at least one set-agent sjs_j with 1∈Sj1∈ S_j. As shown before, we cannot add two sets which have common elements, so we can add at most one set-agent sjs_j with 1∈Sj1∈ S_j. Therefore, we also need to add u2u_2 and u3n^u_3 n to make C IR for u1u_1. The same argument holds for u2,…,u3n^−1u_2,…,u_3 n-1 that they have to be together with their predecessor and successor. Therefore, for every element i, the coalition C must contain at least one set-agent sjs_j with i∈Sji∈ S_j in order to make C IR for every element-agent uiu_i. This implies that the sets corresponding to the set-agents in C form a set cover. Let =Sj∣sj∈CK=\S_j s_j∈ C\. Because of our first observation, K is indeed an exact cover. (end of the proof of Claim 23.10) ⋄ −3-3−3-3−3-3−3-3−3-3−3-3111111111111111111111111−13-13−13-139999−3-3−3-3xxy=u1y=u_1u2u_2u3u_3u3n^−2u_3 n-2u3n^−1u_3 n-1u3n^u_3 ns1s_1s2s_2s3s_3s3n^−2s_3 n-2s3n^−1s_3 n-1s3n^s_3 nd1d_1d2n^d_2 n… Figure 6. Illustration of the relevant part of the reduction for Theorem 20, assuming that element 11 appears in sets S1,S3S_1,S_3, and S3n^S_3 n. Note that not all utilities from the auxiliary-agents dℓd_ are drawn. The correctness of the construction follows immediately from Claims 23.9 and 23.10. ∎ B.10. Proof of Theorem 21 See 21 Proof. Throughout this proof, given an instance I=(ℰ=[n^],,h)I=(E=[ n],S,h) of Set Cover, for every i∈[n^]i∈[ n], let d(i)d(i) denote the number of sets containing i. Recall that, by Observations 3 and 4, IR, IS, NS, and CS are all equivalent for the grand coalition partition. Thus, we present the whole proof only for IR. We present the proof for the two different control actions separately. Claim 23.11. AddHG- IR- GR- AddAg is [] W[2]-hard wrt. k even when the preference graph is a DAG. Proof. We reduce from Set Cover. Let I=(ℰ=[n^],,I=(E=[ n],S, h)h) be an instance of Set Cover. W.l.o.g., we assume that every element i∈ℰi appears in at least one member of S. We construct an instance of AddHG- IR- GR- AddAg. The set of agents is ≔ui∣i∈[n^]∪bU \u_i i∈[ n]\∪\b\ and ≔sj∣Sj∈W \s_j S_j \. We construct the utilities as follows, the unmentioned utilities are 0: – For every i∈[n^]i∈[ n], we set μui(b)=−1 _u_i(b)=-1. – For every Sj∈S_j , we set μui(sj)=1 _u_i(s_j)=1 for every i∈Sji∈ S_j. We set k≔hk h. Clearly u1,…,un^,s1,…,sm,bu_1,…,u_ n,s_1,…,s_m,b is a topological order of the preference graph. First assume that I admits a cover K such that ||≤h|K|≤ h. Let us construct ′≔sj∣Sj∈W \s_j S_j \. Clearly |′|=||≤h|W |=|K|≤ h. It remains to show that the grand coalition partition is an IR partition of ∪′U∪W . The agents in ′∪bW ∪\b\ have no out-arcs, so they do not wish to deviate. For every i∈[n^]i∈[ n], because K is a cover, there must be at least one Sj∈S_j such that i∈Sji∈ S_j. We obtain that ∑a∈∪μui(a)=∑a∈μui(a)+∑a∈′μui(a)≥−1+1≥0 _a _u_i(a)= _a _u_i(a)+ _a∈W _u_i(a)≥-1+1≥ 0 and thus uiu_i does not wish to deviate from the grand coalition. Hence, the grand coalition partition is an IR partition of ∪′U∪W . Now assume that there is a subset ′⊆W such that |′|≤h|W |≤ h and the grand coalition partition is an IR partition of ∪′U∪W . Let us define ≔Sj∈∣sj∈′K \S_j s_j∈W \. Assume, towards a contradiction, that there is an element i∈[n^]i∈[ n] such that no set in K contains i. We obtain that ∑a∈∪′μui(a)=∑a∈μui(a)+∑a∈′μui(a)≥−1+0=−1 _a ∪W _u_i(a)= _a _u_i(a)+ _a∈W _u_i(a)≥-1+0=-1 and thus uiu_i deviates from the grand coalition, a contradiction to individual rationality. Thus, K is a cover for I. (end of the proof of Claim 23.11) ⋄ Claim 23.12. AddHG- IR- GR- DelAg is [] W[2]-hard wrt. k even when the preference graph is a DAG. Proof. We reduce from Set Cover. Let I=(ℰ=[n^],,h)I=(E=[ n],S,h) be an instance of Set Cover. We construct an instance of AddHG- IR- GR- DelAg. The set of agents is ≔ui∣i∈[n^]∪aiz∣i∈[n^],z∈[d(i)−1]∪sj∣Sj∈U \u_i i∈[ n]\∪\a^z_i i∈[ n],z∈[d(i)-1]\∪\s_j S_j \. We construct the utilities as follows, the unmentioned utilities are 0: – For every i∈[n^]i∈[ n], we set μui(aiz)=1 _u_i(a^z_i)=1 for every z∈[d(i)−1]z∈[d(i)-1]. – For every Sj∈,i∈SjS_j ,i∈ S_j, we set μui(sj)=−1 _u_i(s_j)=-1. We set k≔hk h. Clearly u1,…,un^,s1,…,sm,a11,…,a1d(1),…,am1,…,u_1,…,u_ n,s_1,…,s_m,a^1_1,…,a^d(1)_1,…,a^1_m,…, amd(m)a^d(m)_m is a topological order of the preference graph. First assume that I admits a cover K such that ||≤h|K|≤ h. Let us construct ′≔sj∣Sj∈U \s_j S_j \. Clearly |′|=||≤h|U |=|K|≤ h. It remains to show that the grand coalition partition is an IR partition of ∖′U . The agents in aiz∣i∈[n^],z∈[d(i)−1]∪sj∣Sj∈∖′\a^z_i i∈[ n],z∈[d(i)-1]\∪\s_j S_j \ do not wish to deviate, because they have no non-zero utilities. For every i∈[n^]i∈[ n], recall that, since K is a cover, there is at least one set in it that contains i. Thus, we obtain that ∑x∈∖′μui(x)=∑x∈μui(x)−∑x∈′μui(x)≥(d(i)−1−d(i))+1≥0 _x _u_i(x)= _x _u_i(x)- _x _u_i(x)≥(d(i)-1-d(i))+1≥ 0, and thus uiu_i does not deviate. Therefore, the grand coalition partition is an IR partition of ∖′U . Now assume that there is a subset ′⊆U such that |′|≤h|U |≤ h and the grand coalition partition is an IR partition of ∖′U . First observe that if an agent in aiz∣i∈[n^],z∈[d(i)−1]\a^z_i i∈[ n],z∈[d(i)-1]\ is in ′U , we can remove this agent from ′U and the grand coalition partition of ∖′U remains IR; this holds because no agent has negative utility towards him and he has no negative utility towards anyone. Thus we can assume that aiz∣i∈[n^],z∈[d(i)−1]∩′=∅\a^z_i i∈[ n],z∈[d(i)-1]\ = . Next we show that if an agent uiu_i is in ′U for some i∈[n^]i∈[ n], then we can replace uiu_i with sjs_j for some Sj∈S_j such that i∈Sj,sj∉′i∈ S_j,s_j . If no such sjs_j exists, we just remove uiu_i from ′U . Call the updated ′U with the name U. No agent in ui′∣i′∈[n^]∖(′∪ui)\u_i i ∈[ n]\ (U ∪\u_i\) has negative utility towards uiu_i or positive utility towards sjs_j, so if they do not wish to deviate from ∖′U , they also do not wish to deviate from ∖^U U. The agents in sj∣Sj∈\s_j S_j \ have no non-zero utilities towards other agents, so they never deviate from any coalition. It remains to show that uiu_i does not wish to deviate from the new grand coalition partition of ∖^U U. Recall that no agent from aiz∣i∈[n^],z∈[d(i)−1]\a^z_i i∈[ n],z∈[d(i)-1]\ is in ^ U and there is a set SjS_j such that sj∈s_j and uiu_i has utility −1-1 towards sjs_j. Thus we obtain that ∑x∈∖^μui(x)=∑x∈μui(x)−∑x∈^μui(x)≥(d(i)−1−d(i))+1≥0 _x U _u_i(x)= _x _u_i(x)- _x∈ U _u_i(x)≥(d(i)-1-d(i))+1≥ 0, and thus uiu_i does not deviate from ∖^U U. We have now shown that we may assume ^⊆sj∣Sj∈ U \s_j S_j \. Let ≔Sj∈∣sj∈^K \S_j s_j∈ U\. Clearly ||=|^|≤h|K|=| U|≤ h. It remains to show that K covers [n^][ n]. Assume, towards a contradiction, that there is an element i∈[n^]i∈[ n] such that no set in K contains i. Then ∑x∈∖^μui(x)=∑x∈μui(x)−∑x∈^μui(x)=(d(i)−1−d(i))−0=−1 _x U _u_i(x)= _x _u_i(x)- _x∈ U _u_i(x)=(d(i)-1-d(i))-0=-1, and uiu_i prefers being alone to the grand coalition, a contradiction to individual rationality. Thus, K is a cover for I. (end of the proof of Claim 23.12) ⋄ It remains to show that the problems are in XP. A simple brute-force approach is sufficient to show this. Claim 23.13. For each control action ∈,A∈\ AddAg, DelAg\, AddHG- IR- GR-A is in XP wrt. k. Proof. Observe that we can verify in polynomial time whether the grand coalition partition is IR. Thus we can try every subset of W (resp. U) of cardinality at most k. The number of such subsets is in O(||k)O(|W|^k) (resp. O(||k)O(|U|^k)), and thus this simple brute-force algorithm is in XP wrt. k. (end of the proof of Claim 23.13) ⋄ This concludes the proof. ∎ B.11. Proof of Theorem 22 See 22 Proof. Throughout this proof, given an instance I=(ℰ=[n^],,h)I=(E=[ n],S,h) of Set Cover, for every i∈[n^]i∈[ n], let d(i)d(i) denote the number of sets containing i. Recall that, by Observation 3, IR, IS, and NS are equivalent for the grand coalition partition. Thus we present the whole proof only for IR. For symmetric preferences and the control action AddAg the hardness is a consequence of Theorem 13. Thus it is sufficient to show the hardness for DelAg. Claim 23.14. For each stability concept ∈,, S∈\ IR, IS, NS\, AddHG- S- GR- DelAg is [] W[2]-hard wrt. k even when the preference graph is symmetric. Proof. We reduce from Set Cover. Let I=(ℰ=[n^],,h)I=(E=[ n],S,h) be an instance of Set Cover. We construct an instance of AddHG- S- GR- DelAg with symmetric utilities. The set of agents is ≔ui∣i∈[n^]∪aiz∣i∈[n^],z∈[d(i)−1]∪sj∣Sj∈∪bjw∣Sj∈,w∈[|Sj|+||]U \u_i i∈[ n]\∪\a^z_i i∈[ n],z∈[d(i)-1]\∪\s_j S_j \∪\b_j^w S_j ,w∈[|S_j|+|S|]\. We construct the utilities as follows, the unmentioned utilities are 0: – For every i∈[n^]i∈[ n], we set μui(aiz)=μaiz(ui)=1 _u_i(a^z_i)= _a^z_i(u_i)=1 for every z∈[d(i)−1]z∈[d(i)-1]. – For every Sj∈S_j , we set μsj(bjw)=μbjw(sj)=1 _s_j(b^w_j)= _b^w_j(s_j)=1 for every w∈[|Sj|+||]w∈[|S_j|+|S|]. – For every Sj∈,i∈SjS_j ,i∈ S_j, we set μui(sj)=μsj(ui)=−1 _u_i(s_j)= _s_j(u_i)=-1. – For every Sj,Sj′∈S_j,S_j , we set μsj(sj′)=μsj′(sj)=−1 _s_j(s_j )= _s_j (s_j)=-1. We set k≔hk h. First assume that I admits a cover K such that ||≤h|K|≤ h. Let us construct ′≔sj∣Sj∈U \s_j S_j \. Clearly |′|=||≤h|U |=|K|≤ h. It remains to show that the grand coalition partition is an IR partition of ∖′U . The agents in aiz∣i∈[n^],z∈[d(i)−1]∪bjw∣Sj∈,w∈[|Sj|+||]\a^z_i i∈[ n],z∈[d(i)-1]\∪\b_j^w S_j ,w∈[|S_j|+|S|]\ do not wish to deviate, because they have only non-negative utilities towards other agents. For every Sj∈∖S_j , we have that ∑a∈∖′μsj(a)≥|Sj|+||−||−|Sj|≥0 _a _s_j(a)≥|S_j|+|S|-|S|-|S_j|≥ 0, and thus sjs_j does not deviate. For every i∈[n^]i∈[ n], recall that, since K is a cover, there is at least one set in it that contains i. Thus we obtain that ∑a∈∖′μui(a)=∑a∈μui(a)−∑a∈′μui(a)≥(d(i)−1−d(i))+1≥0 _a _u_i(a)= _a _u_i(a)- _a _u_i(a)≥(d(i)-1-d(i))+1≥ 0, and thus uiu_i does not deviate. Therefore the grand coalition partition is an IR partition of ∖′U . Now assume that there is a subset ′⊆U such that |′|≤h|U |≤ h and the grand coalition partition is an IR partition of ∖′U . First observe that if an agent in aiz∣i∈[n^],z∈[d(i)−1]∪bjw∣Sj∈,w∈[|Sj|+||]\a^z_i i∈[ n],z∈[d(i)-1]\∪\b_j^w S_j ,w∈[|S_j|+|S|]\ is in U, we can remove this agent from ′U and the grand coalition partition of ∖′U remains IR; this holds because no agent has negative utility towards him and he has no negative utility towards anyone. Thus we can assume that aiz∣i∈[n^],z∈[d(i)−1]∪bjw∣Sj∈,w∈[|Sj|+||]∩′=∅\a^z_i i∈[ n],z∈[d(i)-1]\∪\b_j^w S_j ,w∈[|S_j|+|S|]\ = . Next we show that if an agent uiu_i is in ′U for some i∈[n^]i∈[ n], then we can replace uiu_i with sjs_j for some Sj∈S_j such that i∈Sj,sj∉′i∈ S_j,s_j . If no such sjs_j exists, we just remove uiu_i from ′U . Call the updated ′U with the name U. No agent in ui′∣i′∈[n^]∖(′∪ui)\u_i i ∈[ n]\ (U ∪\u_i\) has negative utility towards uiu_i or positive utility towards sjs_j, so if they do not wish to deviate from ∖′U , they also do not wish to deviate from ∖^U U. Every agent in sj′∣Sj′∈∖(′∪sj)\s_j S_j \ (U ∪\s_j\) who has negative utility uiu_i has the same negative utility for sjs_j, so if they do not wish to deviate from ∖′U , they also do not wish to deviate from ∖^U U. Moreover, the only agents who have negative utility towards uiu_i are the agents sj′s_j where Sj′∈,i∈SjS_j ,i∈ S_j; if we are in the case where we remove uiu_i without adding any agents to U, then all of the agents who have negative utility towards uiu_i are already in ′U . It remains to show that uiu_i does not wish to deviate from the new grand coalition partition of ∖^U U. Recall that no agent from aiz∣i∈[n^],z∈[d(i)−1]∪bjw∣Sj∈,w∈[|Sj|+||]\a^z_i i∈[ n],z∈[d(i)-1]\∪\b_j^w S_j ,w∈[|S_j|+|S|]\ is in ′U and there is a set SjS_j such that sj∈s_j and uiu_i has utility −1-1 towards sjs_j. Thus we obtain that ∑a∈∖^μui(a)=∑a∈μui(a)−∑a∈^μui(a)≥(d(i)−1−d(i))+1≥0 _a U _u_i(a)= _a _u_i(a)- _a∈ U _u_i(a)≥(d(i)-1-d(i))+1≥ 0, and thus uiu_i does not deviate from ∖^U U. We have now shown that we may assume ^⊆sj∣Sj∈ U \s_j S_j \. Let ≔Sj∈∣sj∈^K \S_j s_j∈ U\. Clearly ||=|^|≤h|K|=| U|≤ h. It remains to show that K covers [n^][ n]. Assume, towards a contradiction, that there is an element i∈[n^]i∈[ n] such that no set in K contains i. Then ∑a∈∖^μui(a)=∑a∈μui(a)−∑a∈^μui(a)=(d(i)−1−d(i))−0=−1 _a U _u_i(a)= _a _u_i(a)- _a∈ U _u_i(a)=(d(i)-1-d(i))-0=-1, and uiu_i prefers being alone to the grand coalition, a contradiction to individual rationality. Thus K covers [n^][ n]. (end of the proof of Claim 23.14) ⋄ To show XP containment observe that Claim 23.13 does not require the graph to be a DAG. ∎ B.12. Proof of Theorem 23 See 23 Proof. We show coNP-hardness for AddHG- CS- GR- AddAg; containment is discussed in Observation 2. Since k=0k=0, the proof for AddHG- CS- GR- DelAg is analogous. We reduce from the classic NP-complete problem Clique. Clique Input: An undirected graph G=(V,E)G=(V,E), an integer h. Question: Does G admit a clique of size at least h? Let I=(G=(V,E),h)I=(G=(V,E),h) be an instance of Clique and we construct an AddHG-instance with a symmetric preference graph G. We use Δ(v) (v) to denote the degree of a vertex v. The set of agents is =av∣v∈V∪bU=\a_v v∈ V\∪\b\, where av,v∈Va_v,v∈ V is a vertex-agent, and b is a dummy-agent. We construct the utilities as follows: – For each v,v′∈Vv,v ∈ V such that v and v′v are adjacent in G, set μav(av′)=μav′(av)=1. _a_v(a_v )= _a_v (a_v)=1. – For each v,v′∈Vv,v ∈ V such that v and v′v are not adjacent, set μav(av′)=μav′(av)=−|V|. _a_v(a_v )= _a_v (a_v)=-|V|. – For each v∈Vv∈ V, set μav(b)=μb(av)=|V|⋅(|V|−Δ(v)−1)−Δ(v)+h−2. _a_v(b)= _b(a_v)=|V|·(|V|- (v)-1)- (v)+h-2. We assume that every vertex has at least one vertex which is not adjacent to them, so b has positive utility towards every agent. The budget k is zero. We show that I is a Yes-instance of Clique if and only if G is a No-instance of AddHG- CS- GR- AddAg. Observe that for every v∈Vv∈ V ∑x∈μav(x) _x _a_v(x) =∑v′∈V∖N(v)μav(av′)+∑v′∈N(v)μav(av′)+μav(b) = _v ∈ V N(v) _a_v(a_v )+ _v ∈ N(v) _a_v(a_v )+ _a_v(b) =(−|V|⋅(|V|−Δ(v)−1))+Δ(v) =(-|V|·(|V|- (v)-1))+ (v) +(|V|⋅(|V|−Δ(v)−1)−Δ(v)+h−2) +(|V|·(|V|- (v)-1)- (v)+h-2) =h−2. =h-2. (1) First assume I is a Yes-instance of Clique. Let K be a clique of cardinality at least h. We show that A≔av∣v∈KA \a_v v∈ K\ blocks the grand coalition partition of U. For every v∈Kv∈ K, the utility ava_v obtains under A is ∑av′∈Aμav(av′)=h−1>(1)∑x∈μav(x) _a_v ∈ A _a_v(a_v )=h-1 eq:AD-CS-GS> _x _a_v(x), because every pair of vertices in a clique is adjacent. Thus A blocks the grand coalition partition and G is a No-instance. Now assume G is a No-instance for AddHG- CS- GR- AddAg, i.e., some coalition A blocks the grand coalition partition of U. Observe that, since b obtains all of the agents he has positive utility towards and he has no negative utilities, he cannot be in A. Thus A must consist of vertex-agents only. Let K≔v∈V∣av∈AK \v∈ V a_v∈ A\. Let us first show that K must be a clique. Assume, towards a contradiction, that there is a pair of vertices v,v′∈Kv,v ∈ K that are not adjacent. Then ∑x∈Aμav(x)=μav(av′)+∑v^∈K∖v′μav(av^)≤−|V|+|V|−1<0<(1)∑x∈μav(x) _x∈ A _a_v(x)= _a_v(a_v )+ _ v∈ K \v \ _a_v(a_ v)≤-|V|+|V|-1<0 eq:AD-CS-GS< _x _a_v(x), and thus A cannot block the grand coalition partition. Next assume that K is a clique of cardinality at most h−1h-1. Then ∑v′∈Kμav(av′)=|K|−2≤h−2=(1)∑x∈μav(x) _v ∈ K _a_v(a_v )=|K|-2≤ h-2 eq:AD-CS-GS= _x _a_v(x) and thus A does not block the grand coalition partition, a contradiction. Thus K must be a clique of size at least h. This concludes the proof. ∎