You are an expert at summarizing long articles. Proceed to summarize the following text: 
in mutliagent systems , agents form coalitions to perform tasks . a useful model for analyzing how tasks can be allocated to groups of agents is the _ group activity selection problem _ ( ) , proposed by darmann et al . @xcite . in s , participants express preferences over pairs of the form ( activity , group size ) . the activities are then assigned to participants so as to achieve the best performance for the whole system as well as to satisfy individual agents . the key idea behind this formulation is that ideal group size depends on the task at hand : in a company , an ideal size of the sales team may differ from that of a web developers team . however , there is one important feature missing from the standard model , namely the _ feasibility _ of resulting groups . in many real - life scenarios , smooth communication among members of a group is crucial in order for different individuals to work together , and hence one needs to take into account communication structures among agents . for instance , a group of employers are unable to realize their full potential if no agent knows each other . nevertheless , the basic  framework imposes no restrictions on how agents can split into different groups . a succinct way to capture such restrictions is to represent communication structures by undirected graphs . this idea dates back to cooperative games with graph structure , proposed by myerson  @xcite . under myerson s proposal , nodes of the graph correspond to players and edges represent communication links between them . recently , igarashi et al . @xcite considered group activity selection on social networks ( ) , where groups need to be connected in their underlying social network in order to achieve certain tasks . the focus of that work was on core stability and nash stability . in contrast with similar settings in cooperative games @xcite , many of the computational problems were shown to be np - complete for very simple network structures ; in particular , deciding the existence of core and nash stable outcomes was shown to be np - complete even when the social network is either a path , a star , or has connected components of size at most four .    motivated by the work of igarashi et al . @xcite , we investigate the parameterized complexity of finding stable outcomes in group activity selection problems . a problem is fixed parameter tractable ( fpt ) with respect to a parameter @xmath0 if each instance @xmath1 of this problem can be solved in time @xmath2 where @xmath3 is a computable function . we show that the problem of deciding the existence of nash stable outcomes for s on acyclic graphs is fixed parameter tractable with respect to the number of activities , thereby solving a problem left open by igarashi et al .  @xcite . for general graphs , we obtain a w[1]-hardness result , implying that this problem is unlikely to admit an fpt algorithm ; in fact , our hardness result holds even for s on cliques ( which correspond to the classic ) . we then consider a weaker stability concept , namely , _ individual stability_. in the context of hedonic games , it is known that an individually stable solution always exists and can be computed in polynomial time when the communication structure is acyclic  @xcite . in contrast , we show that an instance of  may have no individually stable outcomes , even if the underlying network is a path . we then analyze the complexity of computing individually stable solutions , and discover that from an algorithmic point of view individual stability is very similar to nash stability . = 0.6 mm    [ cols="<,<,^,^,^,^",options="header " , ]     [ table ]    unfortunately , our fpt results do not extend to core stability : we prove that checking the existence of core stable assignments is np - complete even for s on stars with two activities ; for classic , we can prove that this problem is hard if there are at least four activities . on the other hand , if there is only one activity , a core stable assignment always exists and can be constructed efficiently , for any network structure . another parameter we consider is the number of players . somewhat surprisingly , we show that this parameterization does not give rise to an fpt algorithm for s on general networks . specifically , for all stability notions we consider , it is w[1]-hard to decide the existence of a stable outcome even when the underlying graph is a clique . we summarize our complexity results in table  [ table ] . for @xmath4 where @xmath5 , let @xmath6=\{1,2,\ldots , s\}$ ] and @xmath7=\{s , s+1,\ldots , t\}$ ] . we start by defining a group activity selection problem with a graph structure  @xcite . an instance of the _ group activity selection problem with graph structure ( ) _ is given by a finite set of _ players _ , or _ agents _ , @xmath8 $ ] , a finite set of _ activities _ @xmath9 where @xmath10 and @xmath11 is the _ void activity _ , a _ profile _ @xmath12 of complete and transitive preference relations over the set of _ alternatives _ \{(a_{\emptyset},1)\}$ ] , as well as a set of communication links between players @xmath14 .    in what follows , we will write @xmath15 or @xmath16 to indicate that player @xmath17 strictly prefers alternative @xmath18 to alternative @xmath19 ; similarly , we will write @xmath20 or @xmath21 if @xmath17 is indifferent between @xmath18 and @xmath19 . also , given two sets of alternatives @xmath22 and a player @xmath17 , we write @xmath23 to indicate that @xmath17 is indifferent among all alternatives in @xmath24 as well as among all alternatives in @xmath25 , and prefers each alternative in @xmath24 to each alternative in @xmath25 .    two non - void activities @xmath26 and @xmath27 are said to be _ equivalent _ if for each player @xmath28 and every @xmath29 $ ] it holds that @xmath30 . a non - void activity @xmath31 is called _ copyable _ if @xmath32 contains at least @xmath33 activities that are equivalent to @xmath26 ( including @xmath26 itself ) . player @xmath28 is said to _ approve _ an alternative @xmath34 if @xmath35 . when describing a player s preferences , by convention we only list the alternatives that she approves as well as @xmath36 . an outcome of a  is a _ feasible assignment _ of activities @xmath37 to players @xmath38 , i.e. , a mapping @xmath39 where for each @xmath40 the set @xmath41 of players assigned to @xmath26 is connected in @xmath42 . note that we place no constraints on the set of players who can simultaneously engage in the void activity ( i.e. , do nothing ) . for @xmath28 with @xmath43 , we let @xmath44 denote the set of players assigned to the same activity as player @xmath28 ; for @xmath28 with @xmath45 , we set @xmath46 . a feasible assignment @xmath39 of a  is _ individually rational _ ( ir ) if each player weakly prefers her own activity to doing nothing , i.e.@xmath47 for all @xmath28 .    a subset @xmath48 of players is called a _ coalition _ , and said to be _ feasible _ if it is connected in the graph @xmath49 . a feasible coalition @xmath50 and an activity @xmath31 _ strongly block _ an assignment @xmath39 if @xmath51 and @xmath52 for all @xmath53 . a feasible assignment @xmath39 of a  is called _ core stable _ ( cr ) if it is individually rational , and there is no feasible coalition @xmath50 and activity @xmath31 such that @xmath54 and @xmath26 strongly block @xmath55 . given a feasible assignment @xmath39 of a , a player @xmath28 is said to have    * an _ ns - deviation _ to activity @xmath31 if @xmath56 is connected , and @xmath17 strictly prefers to join the group @xmath57 , i.e. , @xmath58 . * an _ is - deviation _ if it is an ns - deviation , and all players in @xmath57 accept it , i.e. , @xmath59 for all @xmath60 . a feasible assignment @xmath39 of a  is called _ nash stable _ ( ns ) ( respectively , _ individually stable _ ( is ) ) if it is individually rational and no player @xmath61 has an ns - deviation ( respectively , an is - deviation ) to some @xmath31 . the first stability concept we will consider is nash stability . the following example , due to igarashi et al . @xcite , shows that nash stable outcomes may not exist even in very simple instances of . [ ex : ns : empty ] _ we consider an instance of  with two players : one is a loner and another is a stalker . the loner only approves alternatives of the form @xmath62 , where @xmath63 , and the stalker only approves alternatives of the form @xmath64 , where @xmath63 . clearly , no assignment for this instance is nash stable : if a loner engages in an activity alone , the stalker would wish to join , and if the loner and the stalker are together , the loner prefers to deviate to  @xmath65 . _ igarashi et al . @xcite show that it is np - complete to decide if a given instance of  admits a nash stable outcome , even if the underlying graph @xmath42 is a path or a star ; on the other hand , they demonstrate that for paths and stars the problem of finding a nash stable outcome is fixed - parameter tractable with respect to the number of activities . we will now show that this fpt result extends to arbitrary acyclic networks . [ thm : fpt : tree : ns ] the problem of deciding whether an instance of @xmath66 with @xmath67 whose underlying social network @xmath42 is acyclic has a nash stable feasible assignment and finding one if it exists is in fpt with respect to @xmath68 . we will first present a proof for the case where @xmath42 is a tree ; in the end , we will show how to extend the result to arbitrary forests . fix an instance @xmath69 of  such that @xmath42 is a tree . we choose an arbitrary node in @xmath38 as the root of this tree , thereby making @xmath42 a rooted tree ; we denote by @xmath70 the set of children of @xmath17 and by @xmath71 the set of descendants of @xmath17 ( including @xmath17 herself ) . we process the nodes from the leaves to the root . for each @xmath61 , each @xmath72 , each @xmath73 , each @xmath74 \cup \{(a_{\emptyset},1)\}$ ] and each @xmath75 $ ] , we let @xmath76 be _ true _ if there is an assignment @xmath77 where    * the set of activities assigned to players in @xmath71 is exactly @xmath78 ; * player @xmath17 is assigned to @xmath26 and is in a coalition with @xmath0 other players ; * exactly @xmath79 players in @xmath71 belong to the same group as @xmath17 ; * the @xmath79 players in @xmath80 weakly prefer @xmath34 to @xmath81 for each @xmath82 , and have no incentive to deviate to the other groups , i.e. , every player in @xmath80 whose children do not belong to @xmath83 likes @xmath84 at least as much as each of the alternatives she can deviate to ; * the players in @xmath85 weakly prefer their alternative under @xmath55 to engaging alone in any of the activities in @xmath86 , have no ns deviation to activities in @xmath87 , and have no incentive to deviate to @xmath17 s coalition , i.e. , if @xmath88 , then every player @xmath89 whose parent belongs to @xmath83 likes @xmath90 at least as much as @xmath91 .    otherwise , we let @xmath76 be _ false_.    by construction , our instance admits a nash stable assignment if and only if @xmath92 is _ true _ for some combination of the arguments @xmath93 , and @xmath84 , where @xmath94 is the root . if @xmath17 is a leaf , we set @xmath76 to _ true _ if @xmath95 , @xmath96 , and @xmath17 weakly prefers @xmath34 to every alternative @xmath81 such that @xmath82 ; otherwise , we set @xmath76 to _ false_. now , consider the case where @xmath17 is an internal vertex . we first check whether @xmath17 strictly prefers some alternative @xmath97 such that @xmath82 to @xmath34 ; if so , we set @xmath76 to _ false_. otherwise , we proceed and check for each partition @xmath98 of @xmath99 whether there is an allocation of each activity set @xmath100 to some subtree rooted at @xmath17 s child that gives rise to an assignment with the conditions described above .    we do this by using the color - coding technique ; we ` color ' each child of @xmath17 using colors from @xmath98 independently and uniformly at random . suppose that @xmath55 is an assignment satisfying the properties described above where each activity set @xmath100 is assigned to @xmath101 for some @xmath102 ; we denote by @xmath54 the set of @xmath17 s children whose subtrees are assigned to some @xmath100 . then , the probability that the subtrees associated with @xmath54 are assigned to these activities by a coloring @xmath103 chosen at random is @xmath104 , since there are @xmath105 possible colorings , and @xmath106 of them coincide with @xmath55 on @xmath54 . we can then derandomize our algorithm using a family of @xmath0-perfect hash functions  @xcite . now , let us fix a coloring @xmath107 . for each @xmath108 , we denote by @xmath109 the set of @xmath17 s children of color @xmath110 . we seek to assign each subtree rooted at the @xmath111-th element of @xmath70 to the activities @xmath112 in such a way that exactly one subtree of each color @xmath108 uses all the activities in @xmath110 . we will show that there exists an efficient algorithm that finds an assignment compatible with @xmath103 , or determines that no such assignment exists . we will first determine for each color @xmath108 , each @xmath113 , and each @xmath114 $ ] whether the subtree rooted at @xmath111 can be assigned to the activity set @xmath110 , and exactly @xmath115 players in the subtrees of @xmath116 can be assigned to @xmath26 ; we refer to this subproblem by @xmath117 . we initialize @xmath117 to _ true _ if    * @xmath118 , and @xmath17 and @xmath111 can be _ separated _ from each other , that is , there exists an alternative @xmath119\cup \{(a_{\emptyset},1)\}$ ] such that ( i. ) @xmath120 is _ true _ , ( ii . ) @xmath121 or @xmath17 weakly prefers @xmath34 to @xmath122 , and ( iii . ) @xmath123 or @xmath111 weakly prefers @xmath124 to @xmath91 ; or * @xmath125 , and @xmath126 is _ true_.    we set @xmath117 to _ false _ otherwise . then , we iterate through all the subtrees associated with players in @xmath127 and update @xmath128 : for each @xmath129 and for @xmath130 , we set @xmath128 to _ true _ if    * @xmath131 , and , moreover , there exists an @xmath132 $ ] such that both @xmath133 and @xmath134 are _ true _ ; or * both @xmath135 and @xmath128 are _ true _ , and @xmath123 or player @xmath136 weakly prefers @xmath137 to @xmath91 ;    we set @xmath128 to _ false _ otherwise .    in a similar manner , we determine whether exactly @xmath115 successors of @xmath17 can be assigned to activity @xmath26 ; we denote this problem by @xmath138 . we initialize @xmath139 to _ true _ and @xmath138 to _ false _ for each @xmath140 $ ] . we iterate through all the colors in @xmath98 and update @xmath138 one by one ; for each color @xmath108 and each number @xmath141 , we set @xmath138 to _ true _ if there exists @xmath142 $ ] such that @xmath143 is true for some @xmath113 and @xmath144 is _ true _ , and we set @xmath138 to _ false _ otherwise . finally , we reject the coloring @xmath103 if @xmath145 is _ , if there exists a nash stable feasible assignment that is compatible with @xmath103 , then the algorithm does not reject the coloring . we omit the proof for the bound on the running time . now , if @xmath42 is a forest , we can combine the algorithm described above with the algorithm for graphs with small connected components proposed by igarashi et al . the running time of the latter algorithm is a product of the time required to find a nash stable assignment for a single connected component and the time required to combine solutions for different components ; in the analysis of igarashi et al . , the former is @xmath146 , where @xmath147 is the maximum component size and the latter is @xmath148 . in our case , each connected component is a tree , so instead of the @xmath146 algorithm for general graphs we can use our fpt algorithm for trees . this shows that our problem is in fpt for arbitrary forests . it is unlikely that theorem  [ thm : fpt : tree : ns ] can be extended to general graphs or even cliques : our next result shows that the problem of finding a nash stable outcome is w[1]-hard with respect to the number of activities even for ` vanilla ' , i.e. , when the social network imposes no constraints on possible coalitions . [ thm : w1:clique : ns ] the problem of determining whether an instance of   admits a nash stable assignment is _ w[1]_-hard with respect to the number of activities , even if the underlying graph @xmath149 is a clique . we reduce from clique on regular graphs , which is known to be w[1]-hard ( see e.g. theorem 13.4 in the book of cygan  @xcite ) . given a graph @xmath150 and an integer @xmath0 , where @xmath151 , @xmath152 , and each vertex of @xmath153 has degree @xmath154 , we create an instance of  whose underlying graph is a clique , as follows . we define the set of activities as @xmath155 where @xmath156 , @xmath157 . notice that @xmath158 .    for each @xmath159 , we create a vertex player @xmath160 , and for each edge @xmath161 , we create two edge players @xmath162 and @xmath163 . let @xmath164\}$ ] , and let @xmath165 be a bijection that assigns a distinct number in @xmath24 to each vertex @xmath166 . note that @xmath167 implies that the intervals @xmath168 $ ] and @xmath169 $ ] are disjoint . similarly , let @xmath170\}$ ] and let @xmath171 be a bijection that assigns a distinct number in @xmath25 to each edge @xmath172 . for each @xmath166 we construct a set of @xmath173 dummy players @xmath174 ; similarly , for each @xmath172 we construct a set of @xmath175 dummy players @xmath176 . we let @xmath177 finally , we create five additional players @xmath178 and let @xmath179 intuitively , @xmath180 and @xmath181 will form two instances of the stalker game , with @xmath182 used to stabilize the latter . let @xmath183 be the set of pairs of distinct players of @xmath38 . note that @xmath184 depends on @xmath0 , but not on @xmath33 , and the size of our instance of  is bounded by @xmath185 . we will now define the players preferences . each vertex player @xmath159 and the players in @xmath174 approve each alternative in @xmath186 $ ] . each edge player @xmath163 approves each alternative in @xmath186 $ ] as well as each alternative in @xmath187 , whereas its dummies only approve the alternatives in @xmath187 . all of these players are indifferent among all alternatives they approve . the stabilizer @xmath182 approves each alternative of the form @xmath188 with @xmath189 , @xmath190 $ ] and is indifferent among them ; she also approves @xmath191 , but likes it less than all other approved alternatives . also , we have @xmath192    we will now argue that the graph @xmath153 contains a clique of size @xmath0 if and only if there exists a nash stable assignment for our instance of . suppose that @xmath153 contains a clique @xmath54 of size @xmath0 . we construct an assignment @xmath55 as follows . we establish a bijection @xmath193 between @xmath54 and @xmath194 , and for each @xmath166 we form a coalition of size @xmath195 that engages in @xmath196 : this coalition consists of @xmath160 , all players in @xmath174 , and all edge players @xmath163 such that @xmath197 . also , we establish a bijection @xmath198 between the edge set @xmath199 and @xmath78 , and assign the activity @xmath200 to the edge players @xmath162 , @xmath163 as well as to all players in @xmath176 . finally , we set @xmath201 , and assign the void activity to the remaining players . we will now argue that the resulting assignment @xmath55 is nash stable .    clearly , no player assigned to an activity in @xmath194 or @xmath202 wishes to deviate . now , consider a player @xmath203 with @xmath204 ; by construction , @xmath160 only wants to join a coalition if it engages in an activity in @xmath194 and its size is in the interval @xmath205 $ ] , and no such coalition exists . the same argument applies to players in @xmath174 . similarly , consider an edge player @xmath163 with @xmath206 . we have @xmath207 , and therefore @xmath163 does not want to join any of the existing coalitions ; the same argument applies to all dummies of @xmath163 . further , @xmath208 and @xmath209 do not want to deviate since each activity @xmath189 is assigned to at least three players , and players @xmath210 and @xmath211 do not want to deviate since they are allocated one of their top choices . finally , the stabilizer @xmath182 does not want to deviate , since there is no coalition of size @xmath212 $ ] that engages in an activity @xmath213 . hence , @xmath55 is nash stable . conversely , suppose that there exists a nash stable feasible assignment @xmath55 . notice that @xmath55 can not allocate an activity @xmath189 to @xmath208 or @xmath209 , or leave it unallocated , since no such assignment can be nash stable . thus , each activity in @xmath194 is allocated to a coalition whose size lies in the interval @xmath214 $ ] for some @xmath159 . further , nash stability implies that @xmath55 allocates @xmath18 to @xmath210 , @xmath211 and @xmath182 . now , if some activity @xmath189 is assigned to @xmath215 players , where @xmath216 $ ] for some @xmath159 , the stabilizer @xmath182 would then deviate to that coalition ; hence , for each @xmath213 we have @xmath217 for some @xmath166 . now , let @xmath218 . by construction , @xmath219 . we will show that @xmath54 is a clique . consider a player @xmath220 , and let @xmath221 be the activity assigned to @xmath195 players under @xmath55 . we have @xmath222 , since otherwise @xmath160 could deviate to @xmath26 ; similarly , all players in @xmath174 are assigned to @xmath26 . the only other players who approve @xmath223 are edge players @xmath163 . thus , @xmath224 such players must be assigned to @xmath221 , and the remaining @xmath225 of these players must be assigned to some activity @xmath226 , since otherwise they would deviate to @xmath221 . now , consider an edge player @xmath163 with @xmath227 for some @xmath226 . by individual rationality we have @xmath228 and hence @xmath229 consists of @xmath163 , @xmath162 and all dummies of the edge @xmath230 .    for each @xmath220 , consider the set of players @xmath231 . the size of this set is @xmath232 , and we have argued that all players in such sets need to be assigned to activities in @xmath202 . however , @xmath157 , and each activity in @xmath202 can be assigned to at most two edge players simultaneously . thus , @xmath233 . as each edge player @xmath234 can belong to at most two sets @xmath235 , it follows that it belongs to exactly two such sets , namely , @xmath236 and @xmath237 . thus , both @xmath238 and @xmath239 are in @xmath54 , i.e. , @xmath54 is a clique , which is what we wanted to prove .    on the positive side , for s on cliques , we can place the problem of finding a nash stable assignment in the complexity class xp with respect to the number of activities . however , it is not clear if this result can be extended to general s.    [ thm : xp : ns ] there exist an algorithm that , given an instance @xmath69 of  with @xmath240 , @xmath241 such that @xmath42 is a clique , determines whether it admits a nash stable assignment in time @xmath242 .    for every mapping @xmath243 $ ] , we will check if there is a nash stable assignment such that @xmath244 for each @xmath40 . there are at most @xmath245 such mappings ; hence , it remains to show that each check will take at most @xmath246 steps . fix a mapping @xmath243 $ ] . we construct an instance of the network flow problem as follows . we introduce a source @xmath215 , a sink @xmath79 , a node @xmath17 for each player @xmath28 , and a node @xmath26 for each activity @xmath40 . we create an arc with unit capacity from the source @xmath215 to each player , and an arc with capacity @xmath247 from node @xmath40 to the sink @xmath79 . then , for each @xmath61 we create an arc of unit capacity from player @xmath17 to an activity @xmath40 if and only if @xmath17 weakly prefers @xmath248 to @xmath249 and to all pairs of the form @xmath250 , where @xmath251 . it can be easily verified that an integral flow of size @xmath252 in this network corresponds to a nash stable assignment where exactly @xmath247 players are engaged in each activity @xmath40 . it remains to note that one can check in polynomial time whether a given network admits a flow of a given size . we will next consider a less stringent stability requirement , namely , individual stability . igarashi and elkind  @xcite showed that in the context of hedonic games , acyclicity is sufficient for individually stable outcomes to exist : an individually stable partition of players always exists and can be computed in polynomial time . in contrast , it turns out that for s this is not the case : an individually stable outcome may fail to exist even if the underlying social network is a path ; moreover , this may happen even if there are only three players and their preferences are strict . [ ex : empty : is ]    _ consider a  with @xmath253 , @xmath254 , @xmath255 , where players preferences are as follows : @xmath256 _    we will argue that each individually rational feasible assignment @xmath55 admits an is - deviation . indeed , if @xmath257 then no player is engaged in @xmath147 and hence player @xmath258 can deviate to @xmath147 . similarly , if @xmath259 then no player is engaged in @xmath27 and hence player @xmath260 can deviate to @xmath27 . there are @xmath261 individually rational feasible assignments where @xmath262 , @xmath263 ; for each of them we can find an is deviation as follows ( we write @xmath264 to indicate that player @xmath17 has an is - deviation to activity @xmath18 ) :    1 . @xmath265 , @xmath266 , @xmath267 : @xmath268 ; 2 . @xmath269 , @xmath266 , @xmath267 : @xmath270 ; 3 . @xmath269 , @xmath266 , @xmath271 : @xmath272 ; 4 . @xmath273 , @xmath274 , @xmath271 : @xmath275 ; 5 . @xmath273 , @xmath266 , @xmath276 : @xmath270 ; 6 . @xmath273 , @xmath266 , @xmath271 : @xmath272 ; 7 . @xmath273 , @xmath277 , @xmath267 : @xmath270 ; 8 . @xmath273 , @xmath277 , @xmath271 : @xmath278 ; 9 . @xmath273 , @xmath277 , @xmath279 : @xmath280 .    in example [ ex : empty : is ] all activities are distinct . on the other hand , if all activities are copyable , an individually stable outcome is guaranteed to exist . moreover , we can adapt the result of igarashi and elkind  @xcite for hedonic games and obtain an efficient algorithm for computing an individually stable outcome . [ thm : is : copyable ] each instance of  where each activity @xmath31 is copyable and @xmath49 is acyclic admits an individually stable feasible assignment ; moreover , such as assignment can be found in polynomial time . the algorithm is similar to the one for hedonic games  @xcite . the basic idea is to create a rooted tree for each connected component and construct an assignment for every subtree in a bottom - up manner . when considering a subtree rooted at player @xmath17 , we start with the assignment obtained by combining the previously constructed assignments for the subtrees rooted at the children of @xmath17 and assigning @xmath17 to the void activity . we then let player @xmath17 join the most preferred activity among those to which she has an is deviation . after that we keep adding players to @xmath17 s coalition as long as the resulting coalition remains feasible , the player being added is willing to move , and such a deviation is acceptable for all members of @xmath17 s coalition . similarly to the proof in theorem  1 of igarashi and elkind  @xcite , one can show that the resulting assignment is individually stable . in contrast , when activities are not copyable , finding an individually stable feasible assignment is hard , even for very simple social networks . indeed , for every class of simple social networks for which igarashi et al . @xcite show that finding a nash stable outcome is np - complete , finding an individually stable outcome is np - complete as well . the proof of the following theorem is similar to the proofs of the respective results of igarashi et al . @xcite : essentially , we have to replace each instance of the stalker game in these proofs with an instance of the game from example  [ ex : empty : is ] . [ thm : np : is ] given an instance of  whose underlying graph is a path , a star , or has connected components whose size is bounded by a constant , it is _ np_-complete to determine whether it has an individually stable feasible assignment . moreover , the problem of finding individually stable feasible assignments remains hard even if the number of activities is small , and even if the social network is a clique . the proof if similar to that of theorem  [ thm : w1:clique : ns ] and is omitted due to space constraints . [ thm : w1:clique : is ] the problem of determining whether an instance of   admits an individually stable assignment is _ w[1]_-hard with respect to the number of activities , even if the underlying graph @xmath149 is a clique . again , we reduce from clique on regular graphs . given a graph @xmath150 and an integer @xmath0 where @xmath151 , @xmath152 , and each vertex of @xmath153 has degree @xmath154 , we create an instance of  on a clique as follows . first , we create the same sets @xmath281 and @xmath78 of non - void activities as in the proof of theorem [ thm : w1:clique : ns ] ; we then create five other activities @xmath282 , @xmath283 , @xmath284 , @xmath285 , and @xmath286 . the set of non - void activities is given by @xmath287 notice that @xmath288 . also , we create the same set @xmath289 of players as in the proof of theorem [ thm : w1:clique : ns ] ; we create two copies @xmath290 and @xmath291 of the empty is instance together with the stabilizer @xmath292 for the latter ; we let @xmath293 and @xmath183 be the set of pairs of distinct players of @xmath38 .    for players in @xmath289 , each vertex player @xmath159 and its dummies approve any activity @xmath189 with size within the interval @xmath214 $ ] ; each edge player @xmath163 approves any activity @xmath189 with size within the same interval @xmath214 $ ] as well as any activity @xmath294 with size @xmath295 , whereas its dummies only approve the activities in @xmath78 with size @xmath295 . the stabilizer @xmath292 approves any activity @xmath189 with size within @xmath296 $ ] and the alternative @xmath297 , and strictly prefers the former alternatives to the latter . for players in @xmath298 , their top alternative is @xmath297 ; however , their preference over the alternatives of @xmath284 , @xmath285 , and @xmath286 is cyclic and given as follows : @xmath299    hence , in an individually stable assignment @xmath55 , the activity @xmath284 should be assigned to all the players in @xmath298 together with its stablizer @xmath292 ; otherwise @xmath55 can not be individually stable as we have seen in example [ ex : empty : is ] . similarly , the preference for players in @xmath300 is cyclic and satisfies the following relation : for any @xmath189 , @xmath301    notice that in an individually stable assignment @xmath55 , all the activities in @xmath281 must be used outside of @xmath302 , since otherwise @xmath55 can not be individually stable . similarly to the proof for nash stability , one can show that @xmath153 contains a clique of size @xmath0 if and only if there exists an individually stable feasible assignment . suppose that there exists a clique of size @xmath0 . we construct an assignment @xmath55 as follows . for each vertex @xmath303 , we choose unused activity @xmath189 and form a coalition of size @xmath195 by assigning @xmath26 to the vertex player @xmath160 , all the dummies of @xmath160 , and the edge players @xmath163 whose endpoint @xmath238 does not belong to @xmath54 . for each edge @xmath161 such that @xmath304 , we choose unused activity @xmath294 and assign @xmath27 to the edge players @xmath162 , @xmath163 , and all the dummies of @xmath305 . we assign @xmath284 to all the players in @xmath298 and the player @xmath292 , and assign @xmath282 to all players in @xmath302 . finally , we assign the void activity to the rest of the players . we will now show that the resulting assignment @xmath55 is an individually stable . clearly , no assigned vertex @xmath160 and edge players @xmath163 as well as their assigned dummies wish to deviate . no unassigned vertex @xmath160 and edge players @xmath163 as well as their unassigned dummies want to deviate , since neither alternative of the form @xmath306 where @xmath189 and @xmath307 $ ] nor alternative of the form @xmath308 where @xmath294 is played among the other players ; no players in @xmath300 wish to deviate since each activity @xmath309 is already assigned to more than @xmath260 players ; clearly , the players in @xmath298 do not want to deviate since they are assigned to their favorite alternative ; lastly , the stabilizer @xmath292 can not deviate since no alternative of the form @xmath306 where @xmath309 and @xmath310 $ ] for some @xmath159 is played . hence , @xmath55 is individually stable . conversely , suppose that there exists an individually stable feasible assignment @xmath55 . notice that @xmath55 can not allocate an activity @xmath189 to a member of @xmath300 , since otherwise no feasible assignment would be individually stable ; hence , all activities in @xmath281 should be assigned to the outside of @xmath302 . the only individual rational way to do this is to form @xmath0 coalitions of size within the interval @xmath214 $ ] for some @xmath159 and allocate each activity @xmath189 to each of the @xmath0 coalitions . further , @xmath55 should allocate activity @xmath284 to the players in @xmath298 and the stabilizer @xmath215 , since otherwise @xmath55 would not be individually stable . if activity @xmath189 is assigned to more than @xmath195 players for some @xmath159 , the stabilizer @xmath292 would then deviate to the coalition ; hence , the @xmath0 coalitions assigned to @xmath26 are of size exactly @xmath195 for some @xmath159 . now , let @xmath54 be the set of vertex players @xmath160 whose target size @xmath195 is achieved by some coalition . clearly , @xmath219 . we will show that @xmath54 is a clique of size @xmath0 . observe that for each @xmath303 whose corresponding coalition of size @xmath195 is assigned to @xmath189 , @xmath160 should be assigned to @xmath26 , since otherwise the vertex player would have an is deviation to @xmath26 ; likewise , all dummies of @xmath160 must be assigned to @xmath26 ; and @xmath311 edge players @xmath163 must be allocated to @xmath26 , and the other @xmath312 edge players @xmath163 together with @xmath162 and @xmath175 of @xmath305 s copies must be assigned to some activity @xmath27 . since the activities in @xmath78 can cover at most @xmath313 edge players in an individually rational way , this means that all the activities in @xmath78 should be played among exactly @xmath313 edge players @xmath163 whose left endpoint @xmath160 belongs to @xmath54 . hence , we can not assign @xmath294 to edge players @xmath163 such that @xmath303 but @xmath314 , since if there exists such a player , this would imply that @xmath315 for some @xmath189 and @xmath314 . it follows that for each vertex player @xmath220 and edge player @xmath163 such that @xmath227 for some @xmath294 , the other endpoint @xmath238 also belongs to @xmath54 ; thus , each @xmath303 is adjacent to @xmath225 distinct vertices in @xmath54 , thereby concluding that @xmath54 is a clique . however , just as in the case of nash stability , if we both restrict the structure of the social network and assume that the number of activities is small , we can obtain positive algorithmic results . the proof of the next theorem is similar to that of theorem  [ thm : fpt : tree : ns ] ; again , we omit it due to space constraints . [ thm : fpt : tree : is ] the problem of deciding whether an instance of @xmath66 with @xmath67 whose underlying social network @xmath42 is acyclic has an individually stable feasible assignment and finding one if it exists is in fpt with respect to @xmath68 . again , given a tree @xmath49 , we choose an arbitrary node as the root and construct a rooted tree by orienting the edges in @xmath183 towards the leaves ; we denote by @xmath70 the set of children of @xmath17 and by @xmath71 the set of descendants of @xmath17 ( including @xmath17 ) . we process the nodes from the leaves to the root . for each @xmath28 , each @xmath316 , each @xmath317 , each @xmath74 \cup \{(a_{\emptyset},1)\}$ ] , and each @xmath318 $ ] , we let @xmath76 be _ true _ if there exists a feasible assignment @xmath39 where    * the set of activities assigned to players in @xmath71 is exactly @xmath78 ; * player @xmath17 is assigned to @xmath26 and is in a coalition with @xmath0 other players ; * exactly @xmath79 players in @xmath71 belong to the same group as @xmath17 ; * the @xmath79 players in @xmath319 weakly prefer @xmath34 to @xmath81 for each @xmath82 , and has no is - deviation to the activities assigned to players in @xmath320 ; and * the players in @xmath85 weakly prefer their alternative under @xmath55 to engaging alone in any of the activities in @xmath86 , have no is - deviation to activities in @xmath87 .    otherwise , we let @xmath76 be _ false_. we let @xmath321 be _ true _ if there exists a feasible assignment @xmath322 with the above properties where @xmath123 or some player in @xmath319 strictly prefers @xmath34 to @xmath91 ; we let @xmath321 be _ false _ otherwise . we let @xmath323 be _ true _ if there exists a feasible assignment @xmath322 with the above properties where @xmath123 or no player in @xmath324 strictly prefers @xmath91 to their alternative under @xmath55 ; we let @xmath323 be _ false _ otherwise .    by construction , our instance admits an individually stable assignment if and only if there exists a combination of the arguments @xmath325 , @xmath78 , and @xmath34 such that @xmath326 is _ true _ or @xmath327 is _ true _ , where @xmath94 is the root . if @xmath17 is a leaf , we set both @xmath76 and @xmath323 to _ true _ if @xmath95 , @xmath96 , and @xmath17 weakly prefers @xmath34 to any other alternative @xmath81 such that @xmath82 ; otherwise , we set both @xmath76 and @xmath323 to _ false_. we set @xmath321 to _ true _ if @xmath76 is true , and @xmath123 or @xmath17 strictly prefers @xmath34 to @xmath91 ; otherwise , we set @xmath321 to _ false_. now consider the case where @xmath17 is an internal vertex . we first check whether @xmath17 strictly prefers some alternative @xmath97 such that @xmath82 to @xmath34 ; if so , we set @xmath76 , @xmath321 , and @xmath323 to _ false_. otherwise , we proceed and check for each partition @xmath98 of @xmath99 whether there is an allocation of each activity set @xmath100 to some subtree rooted at @xmath17 s child that gives rise to an assignment with the conditions described before . again , we use the color - coding technique ; we ` color ' each child of @xmath17 using colors from @xmath98 independently and uniformly at random , and check whether or not the coloring gives rise to a desirable outcome . now , let us fix a coloring @xmath107 . for each @xmath108 , we denote by @xmath109 the set of @xmath17 s children of color @xmath110 . we seek to assign each subtree rooted at the @xmath111-th element of @xmath70 to the activities @xmath112 in such a way that exactly one subtree of each color @xmath108 uses all the activities in @xmath110 . we will show that there exists an efficient algorithm that finds an assignment compatible with @xmath103 , or determines that no such assignment exists .    to begin with , for each color @xmath108 , each @xmath113 , and each @xmath328 $ ] , we will run the following three checks : first , whether the subtree rooted at @xmath111 can be assigned to the activity set @xmath110 , and exactly @xmath115 players in the subtrees of @xmath116 can be assigned to @xmath26 ; second , whether the subtree rooted at @xmath111 can be assigned to the activity set @xmath110 , exactly @xmath115 players in the subtrees of @xmath116 can be assigned to @xmath26 , and @xmath123 or some of the @xmath115 players strictly prefers @xmath34 to @xmath91 ; third , whether the subtree rooted at @xmath111 can be assigned to the activity set @xmath110 , exactly @xmath115 players in the subtrees of @xmath116 can be assigned to @xmath26 , and no player in @xmath329 has an incentive to deviate to @xmath17 s coalition ; we refer to these subproblems by @xmath117 , @xmath330 , and @xmath331 , respectively . we initialize @xmath117 to _ true _ if    * @xmath118 , and there exists an alternative @xmath332 \cup \{(a_{\emptyset},1)\}$ ] such that @xmath333 , @xmath17 weakly prefers @xmath34 to @xmath334 , or @xmath335 is true ; or * @xmath336 , and @xmath126 is true . we set @xmath117 to _ false _ otherwise . we initialize @xmath331 to _ true _ if    * @xmath118 , and there exists an alternative @xmath332\cup \{(a_{\emptyset},1)\}$ ] such that @xmath17 can not deviate to @xmath111 s coalition without hurting the member of the coalition , i.e. , @xmath121 , @xmath17 weakly prefers @xmath34 to @xmath122 , or @xmath335 is true , and @xmath111 has no incentive to deviate , i.e. , @xmath123 or @xmath111 weakly prefers @xmath124 to @xmath91 ; or * @xmath336 , and @xmath337 is true . we set @xmath331 to _ false _ otherwise . we initialize @xmath330 to _ true _ if @xmath336 and @xmath338 is true , and initialize @xmath330 to _ false _ otherwise . then , we iterate through all the subtrees associated with players in @xmath127 and update @xmath128 , @xmath339 , and @xmath331 : for each @xmath129 and for @xmath130 , we set @xmath128 to _ true _ if @xmath131 and there exists @xmath132 $ ] such that both @xmath134 and @xmath133 are true ; or both @xmath128 and @xmath135 are true . likewise , we set @xmath340 to _ true _ if @xmath341 and there exists @xmath132 $ ] such that both @xmath342 and @xmath343 are true ; or both @xmath340 and @xmath344 are true , and if @xmath88 , then player @xmath136 weakly prefers @xmath137 to @xmath91 . we set @xmath339 to _ true _ if @xmath131 and there exists @xmath132 $ ] such that both @xmath134 and @xmath133 are true , and at least one of @xmath345 and @xmath346 is true ; or both @xmath330 and @xmath135 are true .    finally , we will run the following three checks : first , whether exactly @xmath115 players in @xmath71 can be assigned to @xmath26 ; second , whether exactly @xmath115 players in @xmath71 can be assigned to @xmath26 , and @xmath123 or some of the @xmath115 players strictly prefers @xmath34 to @xmath91 ; third , whether exactly @xmath115 players in @xmath71 can be assigned to @xmath26 , and no player in @xmath329 has an incentive to deviate to @xmath17 s coalition . we denote these subproblems by @xmath138 , @xmath347 , and @xmath348 , respectively . we initialize both @xmath139 and @xmath349 to _ true _ , and @xmath138 to _ false _ for each @xmath350 $ ] . we initialize @xmath351 to _ true _ if @xmath123 or player @xmath17 strictly prefers @xmath34 to @xmath91 , and @xmath351 to _ false _ otherwise ; we set @xmath347 to _ false _ for each @xmath350 $ ] . we iterate through all the colors in @xmath98 and update @xmath138 , @xmath347 , and @xmath348 : for each color @xmath108 and each number @xmath141 ,    * we set @xmath138 ( respectively , @xmath348 ) to _ true _ if there exists @xmath352 $ ] such that @xmath143 ( respectively , @xmath353 ) is true for some @xmath113 and @xmath144 ( respectively , @xmath354 ) is true , and we set @xmath138 ( respectively , @xmath348 ) to _ false _ otherwise ; and * we set @xmath347 to _ true _ if there exists @xmath352 $ ] such that @xmath355 is true for some @xmath113 and @xmath144 is true , or @xmath143 is true for some @xmath113 and @xmath356 is true , and we set @xmath347 to _ false _ otherwise .    for @xmath357 ( respectively , @xmath358 and @xmath359 ) , we reject the coloring , if @xmath145 ( respectively , @xmath360 and @xmath361 ) is false . if there exists a feasible assignment that is compatible with @xmath103 and satisfies respective conditions , then the algorithm does not reject the coloring . we omit the proof for the bound on the running time . the results for individual stability presented so far indicate that from the complexity perspective it is very similar to nash stability . however , it is not clear if the xp algorithm presented in theorem  [ thm : xp : ns ] extends to individual stability . the difficulty is that , to determine whether an agent @xmath17 has an is deviation to an activity @xmath26 , it is not sufficient to know how many players engage in @xmath26 : knowing their preferences is important to decide whether @xmath17 s deviation will be vetoed by one of the players currently assigned to @xmath26 . another important difference concerns copyable activities and games on acyclic graphs : in this setting , individually stable outcomes always exist ( theorem  [ thm : is : copyable ] ) , whereas for nash stable outcomes this is not the case , as illustrated by the stalker game . igarashi et al . @xcite have demonstrated that the core can be empty even for s on paths with @xmath362 players and @xmath260 activities . we reproduce their example below . [ ex : core : empty ] _ consider a  with @xmath253 , @xmath363 , @xmath255 , where agents preferences @xmath12 are as follows : @xmath364 it can be shown that this instance admits no core stable assignment @xcite . _    on the positive side , we can show that checking whether a given feasible assignment is core stable is easy , irrespective of the structure of the social network . the proposition below generalizes theorem  11 of darmann  @xcite and theorem  12 of igarashi et al . @xcite . [ prop : in - core ] given an instance @xmath365 of  and a feasible assignment @xmath55 for that instance , we can decide in polynomial time whether @xmath55 is core stable . let @xmath366 and let @xmath367 . by scanning the assignment @xmath55 and the players preferences , we can check whether @xmath55 is individually rational . now , suppose that this is the case . then , for each @xmath63 and each @xmath368 $ ] we can check if there is a deviation by a connected coalition of size @xmath215 that engages in @xmath26 . to this end , we consider the set @xmath369 of all players who strictly prefer @xmath188 to their assignment under @xmath55 and verify whether @xmath369 has a connected component of size at least @xmath215 that contains @xmath57 ; if this is the case , @xmath57 ( which is itself connected or empty ) could be extended to a connected coalition of size exactly @xmath215 that strongly blocks @xmath55 . if no such deviation exists , @xmath55 is core stable .    however , core stability turns out to be more computationally challenging that nash stability and individual stability when the number of activities is small : we will now show that core stable assignments are hard to find even if there are only two activities and the underlying graph is a star ( and thus one can not expect an fpt result with respect to the number of activities for this setting ) . later , we will see that this hardness result can be extended to the case where @xmath42 is a clique , i.e. , to classic , thereby solving a problem left open by the work of darmann  @xcite . [ thm : np : star : core ] it is _ np_-complete to determine whether an instance of   admits a core stable assignment even when the underlying graph is a star and the number of non - void activities is  @xmath260 . our problem is in np by proposition  [ prop : in - core ] . to establish np - hardness , we reduce from the np - complete problem hitting set  @xcite . an instance of hitting set is a family @xmath370 of subsets of a finite set @xmath371 and an integer @xmath0 with @xmath372 . it is a `` yes''-instance if @xmath373 admits a _ hitting set _ @xmath374 of size at most @xmath0 , i.e. , @xmath375 and @xmath376 for each @xmath377 ; otherwise , it is a `` no''-instance .    given an instance of hitting set , we can create three disjoint copies of @xmath378 : for each @xmath166 we create elements @xmath379 , @xmath380 and @xmath381 , set @xmath382 and for each @xmath383 $ ] we let @xmath384 , @xmath385 , @xmath386 and set @xmath387\}$ ] . in what follows , we will use the fact that @xmath388 admits a hitting set of size @xmath389 if and only if @xmath378 admits a hitting set of size  @xmath362 . consider an instance @xmath390 of hitting set and construct the pair @xmath388 as described above . for readability , we renumber the elements of @xmath391 as @xmath392 . we construct an instance of  as follows . we define the set of activities to be @xmath363 . we introduce a center player @xmath147 , two players @xmath393 and @xmath394 , and a player @xmath239 for each @xmath395 . also , for each @xmath396 $ ] , we let @xmath397 and create a set @xmath398 of dummy players . we then attach @xmath393 , @xmath394 , each player @xmath399 and each of the dummies to the center . formally , the graph @xmath49 is given by @xmath400 intuitively , for each @xmath396 $ ] the number @xmath401 is the target coalition size when all players in @xmath402 are engaged in activity @xmath27 , together with @xmath147 and the players in @xmath403 . the agents preferences over alternatives are defined as follows . we let @xmath404 $ ] . for each @xmath395 , we let @xmath405 ; also , set @xmath406 . the preferences of each player @xmath395 are given by @xmath407 for each @xmath396 $ ] the dummy players in @xmath403 only approve the alternative @xmath408 . the preferences of the center player @xmath147 are given by @xmath409 finally , the preferences of players @xmath393 and @xmath394 are given by @xmath410 note that the preferences of @xmath147 , @xmath393 and @xmath394 , when restricted to @xmath411 $ ] , form an instance of  with an empty core ( example  [ ex : core : empty ] ) . we will show that @xmath378 admits a hitting set of size at most @xmath0 if and only if there exists a core stable feasible assignment . let @xmath412 be a hitting set of size at most @xmath0 in @xmath378 . set @xmath413 ; we have @xmath414 , and , by construction , @xmath415 is a hitting set for @xmath388 . then , we construct a feasible assignment @xmath55 by assigning activity @xmath26 to @xmath147 , @xmath393 , @xmath394 , and the players @xmath416 , and assigning the void activity to the remaining players . clearly , @xmath55 is individually rational , since @xmath417 . further , notice that no connected subset @xmath54 together with activity @xmath26 strongly blocks @xmath55 : every such subset has to contain players @xmath393 and @xmath394 , who are currently enjoying one of their top alternatives . it remains to show that no connected subset @xmath54 together with activity @xmath27 strongly blocks @xmath55 . suppose towards a contradiction that such a subset @xmath54 exists ; as @xmath393 and @xmath394 are not interested in deviating , it must be the case that @xmath418 for some @xmath419 $ ] and hence @xmath54 consists of agents who approve @xmath420 , i.e. , @xmath421 for some @xmath396 $ ] . however , since @xmath415 is a hitting set , there is an agent @xmath422 with @xmath423 , and this agent prefers @xmath424 to @xmath420 , a contradiction . hence , @xmath55 is core stable . conversely , suppose that there exists a core stable feasible assignment @xmath55 and let @xmath425 . we will first argue that @xmath426 . indeed , if @xmath427 , then @xmath428 and agents @xmath147 , @xmath393 and @xmath394 can deviate to @xmath26 . if @xmath429 and the only other agent to engage in @xmath27 is @xmath393 , then @xmath428 and @xmath147 and @xmath394 can deviate to @xmath26 . if @xmath429 and @xmath430 for some @xmath431 $ ] then @xmath428 , and @xmath147 , @xmath393 and @xmath394 can deviate to @xmath26 . it follows that @xmath426 . now , if @xmath432 then @xmath433 and agent @xmath394 can deviate to @xmath27 . similarly , if @xmath434 then @xmath433 , and @xmath147 and @xmath393 can deviate to @xmath27 . if follows that @xmath435 $ ] and hence @xmath436 ; also , either @xmath437 or @xmath433 . now , if @xmath415 is not a hitting set for @xmath388 , there exists a set @xmath438 such that all players in @xmath402 are assigned to the void activity . then if @xmath433 the coalition @xmath439 together with the activity @xmath27 strongly blocks @xmath55 , and if @xmath437 the coalition @xmath440 together with the activity @xmath27 strongly blocks @xmath55 . in either case , we obtain a contradiction with the stability of @xmath55 . thus , @xmath441 is a hitting set for @xmath388 . at least one of the three sets @xmath442 , @xmath443 , and @xmath444 contains at most @xmath0 elements ; assume without loss of generality that @xmath445 . by construction , @xmath446 is a hitting set for @xmath378 . thus , @xmath378 admits a hitting set of size at most @xmath0 , which is what we wanted to prove . the hardness result in theorem  [ thm : np : star : core ] immediately generalizes to instances of with more than two activities : we can modify the construction in our hardness reduction by introducing additional activities that no player wants to engage in . also , theorem  [ thm : np : star : core ] can be extended from stars to cliques ; however , our proof for cliques relies on having at least four non - void activities . it remains an interesting open problem whether core stable outcomes of s on cliques can be found efficiently if the number of activities does not exceed @xmath362 . we conjecture that the answer is ` no ' , i.e. , the problem of computing core stable outcomes remains np - hard for @xmath447 . [ thm : np : clique : core ] it is _ np_-complete to determine whether an instance of  admits a core stable assignment even when the underlying graph is a clique and the number of activities is @xmath448 . in contrast , checking the existence of core stable assignments in  is easy if @xmath449 , irrespective of the structure of the social network . [ prop : core - single ] every instance of  with @xmath450 admits a core stable assignment ; moreover , such an assignment can be computed in polynomial time . consider an instance @xmath365 of  with @xmath450 , and let @xmath367 . for each @xmath368 $ ] , let @xmath451 be the set of all players who weakly prefer @xmath188 to @xmath249 . if for each @xmath368 $ ] the largest connected component of @xmath451 with respect to @xmath42 contains fewer than @xmath215 agents , then no outcome in which a non - empty set of agents engages in @xmath26 is individually rational , whereas the assignment @xmath55 given by @xmath452 for all @xmath61 is core stable . otherwise , consider the largest value of @xmath215 such that @xmath451 has a connected component of size at least @xmath215 . find a connected subset of @xmath451 of size exactly @xmath215 , and assign the agents in this subset to @xmath26 ; assign the remaining agents to @xmath65 . to see that this assignment is core stable , note that for every deviating coalition @xmath54 we would have @xmath453 , and hence such a coalition is either disconnected or some players in @xmath54 prefer @xmath249 to @xmath454 . it is not clear if the problem of finding core stable assignments in   is in fpt with respect to the number of activities when the underlying graph is a path . however , we can place this problem in xp with respect to this parameter . in fact , we have the following more general result for graphs with few connected coalitions ( see the work of elkind  @xcite for insights on the structure of such graphs ) . [ prop : core - xp ] given an instance @xmath365 of  with @xmath240 , @xmath241 , such that the number of non - empty connected subsets of @xmath42 is @xmath455 , we can decide in time @xmath456 whether this instance admits a core stable assignment , and find one such assignment if it exists . let @xmath457 be the list of all non - empty connected subsets of @xmath42 . since each assignment of players to activities has to assign a connected ( possibly empty ) subset of players to each activity , we can bound the number of possible assignments by @xmath458 : each of the @xmath68 non - void activities is assigned to a coalition in our list or to no player at all , and the remaining players are assigned the void activity . we can then generate all these assignments one by one and check if any of them is core stable ; by proposition  [ prop : in - core ] , the stability check can be performed in time polynomial in @xmath33 and @xmath68 . if the social network @xmath42 is a path , it has @xmath459 connected subsets . thus , we obtain the following corollary . [ cor : core - xp - path ] the problem of deciding whether a given instance of  whose underlying graph is a path admits a core stable assignment is in _ xp _ with respect to the number of activities . in the previous sections , the parameter that we focused on was the number of activities @xmath68 . although we expect this parameter to be small in many realistic settings , there are also situations where players can choose from a huge variety of possible activities . it is then natural to ask if stability - related problems for s are tractable in the number of players @xmath33 is small . this is the question that we consider in this section . we first observe that for all stability concepts considered in this paper the problem of finding a stable feasible assignment is in xp with respect to @xmath33 : we can simply guess the activity of each player ( there are at most  @xmath460 possible guesses ) and check whether the resulting assignment is feasible and stable . [ obs : xpplayers ] the problem of deciding whether a given instance of  admits a core stable , nash stable , or individually stable assignment is in _ xp _ with respect to the number of players @xmath33 . the following theorem shows that is unlikely to be fixed - parameter tractable with respect to @xmath33 . this is somewhat surprising , because an fpt algorithm with respect to  @xmath33 could afford to iterate through all possible partitions of the players into coalitions . interestingly , in the following hardness reduction there is a unique partition of players into coalitions that can lead to a stable assignment ; that is , computational hardness comes solely from assigning known coalitions of players to activities . [ thm : w1players : clique ] the problem of determining whether an instance of  whose underlying graph is a clique admits a core stable ( nash stable , or individually stable ) assignment is _ w[1]_-hard with respect to the number of players @xmath33 .    due to space constraints , we only provide a proof for nash stability . we describe a parameterized reduction from the w[1]-hard multicolored clique problem . an instance of this problem is given by an undirected graph  @xmath150 , a positive integer  @xmath461 , and a vertex coloring  @xmath462 . it is a ` yes'-instance if  @xmath153 admits a colorful @xmath463-clique , that is , a size-@xmath463 vertex subset  @xmath464 such that the vertices in @xmath465 are pairwise adjacent and have pairwise distinct colors . without loss of generality , we assume that there are exactly @xmath466 vertices of each color for some @xmath467 , and that there are no edges between vertices of the same color . let @xmath468 be an instance of multicolored clique with @xmath469 . for every @xmath470 $ ] , we write @xmath471 to denote the set of vertices of color  @xmath17 . for each vertex @xmath160 , we write @xmath472 to denote the set of edges incident to  @xmath160 . we construct our  instance as follows . we have one _ vertex activity _ @xmath473 for each vertex  @xmath474 , @xmath470 $ ] , one _ edge activity _ @xmath475 for each edge  @xmath476 , two _ color activities _ @xmath477 and  @xmath478 for each color  @xmath470 $ ] , and one _ colorpair activity _ @xmath479 for each color pair  @xmath480 , i \neq j$ ] . _ we will have one _ color gadget _ for each color  @xmath470 $ ] and one _ colorpair gadget _ for each color pair  @xmath481 . for most of the possible assignments , these gadgets will be unstable , unless the following holds :    1 . for each color  @xmath470 $ ] the first two players from the color gadget select a vertex of color  @xmath17 ( by being assigned together to the corresponding vertex activity ) . 2 .   for each color pair  @xmath482 , i \neq j$ ] the first two players of the colorpair gadget select an edge connecting one vertex of color  @xmath17 and one vertex of color  @xmath111 ( by being assigned together to the corresponding edge activity ) . every selected edge for the color pair  @xmath483 must be incident to both vertices selected for color  @xmath17 and color  @xmath111 . if the three conditions above hold , then the assignment must encode a colorful @xmath463-clique .    _ construction details . _ the color gadget  @xmath70 , @xmath484 $ ] consists of the following four players . @xmath485 the colorpair gadget  @xmath486 , @xmath487 , i \neq j$ ] , consists of three players . players  @xmath488 and  @xmath489 approve all edge activities corresponding to edges between vertices of color  @xmath17 and  @xmath111 with size two and the colorpair activity  @xmath479 with size two and one , and strictly prefer the former alternatives to the latter . player @xmath490 approves only the colorpair activity  @xmath479 with size three .    _ _ we will now argue that the graph @xmath153 admits a colorful clique of size @xmath463 if and only if our instance of  admits a nash stable assignment . suppose that there exists a colorful clique  @xmath491 of size @xmath463 . assign the first two players of the color gadget  @xmath70 to the activity corresponding to the vertex of color  @xmath17 from  @xmath491 . assign the first two players of the colorpair gadget  @xmath486 to the activity corresponding to the edge between the vertices of color  @xmath17 and  @xmath111 in  @xmath491 . assign all other players to the void activity . clearly , the resulting assignment is feasible . observe that for a successful nash deviation a player must join an existing non - empty coalition , because no player prefers a size - one activity to the currently assigned one . by construction , the last two players of each color gadget and the last player of the colorpair gadget can not deviate ( no other players engage in an approved activity ) . consider the first two players of color gadget  @xmath70 . they can not deviate to a vertex activity , because their current activity is their only approved vertex activity that has some players assigned to it . they can not deviate to an edge activity either , because they would only prefer edge activities corresponding to edges that are not incident to the vertex of color  @xmath17 that is part of colorful clique  @xmath491 ; these activities , however , have no players assigned to them . finally , the first two players of a colorpair gadget  @xmath486 can not deviate since no player is assigned to any of their more preferred activities . thus , we have a nash stable feasible assignment . suppose that there exists a nash stable feasible assignment  @xmath55 . observe that the first two players of each colorpair gadget  @xmath486 are assigned to the same edge activity corresponding to some edge @xmath492 . otherwise , they would need to be assigned to the colorpair activity  @xmath479 and be stalked by the third player of the gadget ( similarly to the stalker game from example  [ ex : ns : empty ] ) . we say that these players `` select edge  @xmath493 '' . by similar reasoning the first two players of each color gadget  @xmath70 are assigned to the same vertex activity corresponding to some vertex  @xmath494 . they can not be assigned to an edge activity , because the third player would necessarily be a player from a colorpair gadget , and these players do not want to engage in activities with two other players . we say that these players `` select vertex  @xmath494 '' . ( note that at this point , the coalition structure of any stable outcome is already fixed : the first two players of each color gadget and of each colorpair gadget must form a coalition of size two , respectively , and all other players must be assigned to the void activity . )    now , assume towards a contradiction that the selected vertices and edges do not form a colorful clique of size  @xmath463 . the size and colorfulness are clear from the construction . hence , there must be some pair  @xmath495 of selected vertices that is not adjacent . however , this would imply that colorpair gadget  @xmath483 selected an edge that is either not incident to vertex  @xmath494 or not incident to vertex  @xmath496 . without loss of generality let it be non - adjacent to vertex  @xmath494 . now , there are two cases . first , if @xmath497 with @xmath498 , then player  @xmath499 would deviate to the activity corresponding to  @xmath493 . second , if @xmath497 with @xmath500 , then player  @xmath501 would deviate to the activity corresponding to  @xmath493 . in both cases we have a contradiction to the assumption that  @xmath55 is nash stable .    note that although we showed w[1]-hardness for each of the parameters  @xmath68 and @xmath33 , parameterizing by the combined parameter  @xmath502 immediately gives fixed - parameter tractability , since the input size is trivially upper - bounded by @xmath503 . we have investigated the parameterized complexity of computing stable outcomes of group activity selection problems on networks , with respect to two natural parameters . many of our hardness results hold for the classic  problem , where there are no constraints on possible coalitions ; however , some of our positive results only hold for acyclic graphs . interestingly , one of our tractability results holds for s , but it is not clear if it can be extended to s ; thus , while simple networks may decrease complexity , allowing for arbitrary networks may have the opposite effect . in some of our hardness reductions players have non - strict preferences . in some cases , it is easy to modify our gadgets to rely on strict preferences only ; in other cases ( notably , in individual stability proofs ) our arguments make crucial use of indifferences .    confirming our intuition , we showed that finding core stable assignments tends to be computationally more difficult than finding nash stable or individually stable assignments ; we note that this distinction only becomes visible from the parameterized complexity perspective , as all of these problems are np - hard . our results for games with few players are somewhat preliminary : we have only investigated the complexity of our problems with respect to this parameter for general networks and for cliques , and have not considered simple networks such as stars and paths . these questions offer an interesting direction for future work . a.  darmann , e.  elkind , s.  kurz , j.  lang , j.  schauer , and g.  woeginger . group activity selection problem . in _ proceedings of the 8th international conference on internet and network economics _ , wine 2012 , pages 156169 , 2012 . a.  igarashi and e.  elkind . hedonic games with graph - restricted communication . in _ proceedings of the 15th international conference on autonomous agents and multiagent systems _ , aamas 2016 , pages 242250 , 2016 . a.  igarashi , d.  peters , and e.  elkind . group activity selection on social networks . in _ proceedings of the 31st aaai conference on artificial intelligence _ , aaai 2017 , 2017 . accepted for publication . long version available as arxiv:1611.04524 [ cs.gt ] .
in group activity selection problem ( ) , players form coalitions to participate in activities and have preferences over pairs of the form ( activity , group size ) . recently , 
 igarashi et al . 
 @xcite have initiated the study of group activity selection problems on social networks ( ): a group of players can engage in the same activity if the members of the group form a connected subset of the underlying communication structure . 
 igarashi et al . 
 have primarily focused on nash stable outcomes , and showed that many associated algorithmic questions are computationally hard even for very simple networks . in this paper 
 we study the parameterized complexity of  with respect to the number of activities as well as with respect to the number of players , for several solution concepts such as nash stability , individual stability and core stability . 
 the first parameter we consider in the number of activities . for this parameter 
 , we propose an fpt algorithm for nash stability for the case where the social network is acyclic and obtain a w[1]-hardness result for cliques ( i.e. , for classic ) ; similar results hold for individual stability . 
 in contrast , finding a core stable outcome is hard even if the number of activities is bounded by a small constant , both for classic and when the social network is a star . 
 another parameter we study is the number of players . 
 while all solution concepts we consider become polynomial - time computable when this parameter is bounded by a constant , we prove w[1]-hardness results for cliques ( i.e. , for classic ) .