# group_activity_selection_on_social_networks__6c94aaa6.pdf

Group Activity Selection on Social Networks

Ayumi Igarashi, Dominik Peters, Edith Elkind Department of Computer Science University of Oxford, UK {ayumi.igarashi, dominik.peters, edith.elkind}@cs.ox.ac.uk

We propose a new variant of the group activity selection problem (GASP), where the agents are placed on a social network and activities can only be assigned to connected subgroups. We show that if multiple groups can simultaneously engage in the same activity, finding a stable outcome is easy as long as the network is acyclic. In contrast, if each activity can be assigned to a single group only, finding stable outcomes becomes intractable, even if the underlying network is very simple: the problem of determining whether a given instance of a GASP admits a Nash stable outcome turns out to be NPhard when the social network is a path, a star, or if the size of each connected component is bounded by a constant. On the other hand, we obtain fixed-parameter tractability results for this problem with respect to the number of activities.

Introduction Companies assign their employees to different departments, large decision-making bodies split their members into expert committees, and university faculty form research groups: division of labor, and thus group formation, is everywhere. For a given assignment of agents to activities (such as management, product development, or marketing) to be successful, two considerations are particularly important: the agents need to be capable to work on their activity, and they should be willing to cooperate with other members of their group. Many relevant aspects of this setting are captured by the group activity selection problem (GASP), introduced by Darmann et al. (2012). In GASP players have preferences over pairs of the form (activity, group size). The intuition behind this formulation is that certain tasks are best performed in small or large groups, and agents may differ in their preferences over group sizes; however, they are indifferent about other group members identities. In the analysis of GASP, desirable outcomes correspond to stable and/or optimal assignments of players to activities, i.e., assignments that are resistant to player deviations and/or maximize the total welfare. In the work of Darmann et al. (2012), players are assumed to have approval preferences, and a particular focus is placed on individually rational assignments with the maximum number of participants; subsequently, Darmann (2015) investigated a model where players submit ranked ballots.

Copyright c 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

However, the basic model of GASP ignores the relationships among the agents: Do they know each other? Are their working styles and personalities compatible? Typically, we cannot afford to ask each agent about her preferences over all pairs of the form (coalition, activity), as the number of possible coalitions grows quickly with the number of agents. A more practical alternative is to adopt the ideas of Myerson (1977) and assume that the relationships among the agents are encoded by a social network, i.e., an undirected graph where nodes correspond to players and edges represent communication links between them; one can then require that each group is connected with respect to this graph. In this paper we extend the basic model of GASP to take into account the agents social network. We formulate several notions of stability for this setting, including Nash stability and core stability, and study the complexity of computing stable outcomes in our model. These notions of stability are inspired by the hedonic games literature (Aziz and Savani 2016) and were applied in the GASP setting by Darmann et al. (2012) and Darmann (2015). Now, hedonic games on social networks were recently considered by Igarashi and Elkind (2016), who showed that if the underlying network is acyclic, stable outcomes are guaranteed to exist and some of the problems known to be computationally hard for the unrestricted setting become polynomialtime solvable. We obtain a similar result for GASP, but only if several groups of agents can simultaneously engage in the same activity, i.e., if the activities are copyable. In contrast, we show that if each activity can be assigned to at most one coalition, finding a stable outcome is hard even if the underlying network is very simple. Specifically, checking the existence of Nash stable or core stable outcomes turns out to be NP-hard even for very restricted classes of graphs, including paths, stars, and graphs with constant-size connected components. We believe that this result is remarkable since, in the context of cooperative games, such restricted networks usually enable one to design efficient algorithms for computing stable solutions (see, e.g., Chalkiadakis, Greco, and Markakis 2016; Elkind 2014; Igarashi and Elkind 2016). Given these hardness results, we switch to the fixed parameter tractability paradigm. In the context of GASP, a particularly relevant parameter is the number of activities: generally speaking, we expect the number of players to be considerably larger than the number of available activities.

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

Complexity (general case) few activities (FPT wrt p) copyable activities

Nash stability trees NP-c. (Thm 6) poly time (Thm 5) paths NP-c. (Thm 6) 4pp2 poly(n) (Thm 9) poly time (Thm 5) stars NP-c. (Thm 7) pp+12p poly(n) (Thm 11) poly time (Thm 5) small components NP-c. (Thm 8) pc8p poly(n) (Thm 10)

core stability trees NP-c. (Thm 12) poly time (Thm 4) paths NP-c. (Thm 12) poly time (Thm 4) stars NP-c. (Thm 12) poly time (Thm 4) small components NP-c. (Thm 12) pc+18p poly(n) (Thm 13)

Table 1: Overview of our complexity results. Here, n is the number of players, p is the number of activities, and c is a bound on the size of the connected components. The NP-completeness results for small components hold even for c = 4 for Nash stability and for c = 3 for core stability.

We show that for the restricted classes of networks used in our hardness proofs (i.e., paths, stars, and graphs with small connected components), finding a Nash stable outcome is fixed parameter tractable (FPT) with respect to the number of activities; some of our results extend to core stability. Our results are summarized in Table 1. Full version. An extended version with full proofs is available on ar Xiv (Igarashi, Peters, and Elkind 2016).

Preliminaries For s N, let [s] = {1, 2, . . . , s}. An instance of the Group Activity Selection Problem (GASP) is given by a finite set of players N = [n], a finite set of activities A = A {a }, where A = {a1, a2, . . . , ap} and a is the void activity, and a profile ( i)i N of complete and transitive preference relations over the set of alternatives X = A [n] {(a , 1)}. Intuitively, a corresponds to staying alone and doing nothing; multiple agents can make that choice independently from each other. We refer to subsets S N of players as coalitions. We say that two non-void activities a and b are equivalent if for every player i N and every ℓ [n] it holds that (a, ℓ) i (b, ℓ). A non-void activity a A is called copyable if A contains at least n activities that are equivalent to a (including a itself). We say that player i N approves an alternative (a, k) if (a, k) i (a , 1). An outcome of a GASP is an assignment of activities A to players N, i.e., a mapping π : N A. Given an assignment π : N A and a non-void activity a A , we denote by πa = { i N | π(i) = a } the set of players assigned to a. Also, if π(i) = a , we denote by πi = {i} { j N | π(j) = π(i)} the set of players assigned to the same activity as player i N; we set πi = {i} if π(i) = a . An assignment π : N A for a GASP is individually rational (IR) if for every player i N with π(i) = a we have (π(i), |πi|) i (a , 1). A coalition S N and an activity a A strongly block an assignment π : N A if πa S and (a, |S|) i (π(i), |πi|) for all i S. An assignment π : N A for a GASP is called core stable (CR) if it is individually rational, and there is no coalition S N and activity a A such that S and a strongly block π. Given an assignment π : N A for a GASP, a player i N is said to have an NS-deviation to activity a A

if (a, |πa| + 1) i (π(i), |πi|), that is, if i would prefer to join the group πa. An assignment π : N A for a GASP is called Nash stable (NS) if it is individually rational and no player i N has an NS-deviation to some a A .

Our Model We now define a group activity selection problem where communication links between the players are represented by an undirected graph.

Definition 1. An instance of the Group Activity Selection Problem with graph structure (g GASP) is given by an instance (N, ( i)i N, A) of a GASP and a set of communication links between players L { {i, j} | i, j N i = j }.

A coalition S N is said to be feasible if S is connected in the graph (N, L). An outcome of a g GASP is a feasible assignment π : N A such that πi is a feasible coalition for every i N. We adapt the definitions of stability concepts to our setting as follows. We say that a deviation by a group of players is feasible if the deviating coalition itself is feasible; a deviation by an individual player where player i joins activity a is feasible if πa {i} is feasible. We modify the definitions in the previous section by only requiring stability against feasible deviations. Note that an ordinary GASP (without graph structure) is equivalent to a g GASP where the underlying graph (N, L) is complete. In this paper, we will be especially interested in g GASPs where (N, L) is acyclic. This restriction guarantees the existence of stable outcomes in many other cooperative game settings. However, this is not the case for g GASPs: here, both core and Nash stable outcomes may fail to exist, even if (N, L) is a path or a star.

Example 2. Consider a g GASP with N = {1, 2, 3}, A = {a, b}, L = {{1, 2}, {2, 3}}, where preferences ( i)i N are given as follows:

1 : (b, 2) 1 (a, 3) 1 (a , 1) 2 : (a, 2) 2 (b, 2) 2 (a, 3) 2 (a , 1) 3 : (a, 3) 3 (b, 1) 3 (a, 2) 3 (a , 1)

We will argue that each individually rational feasible assignment π admits a strongly blocking feasible coalition and activity. If all players do nothing, then player 3 and activity

b strongly block π. Now, there are only four individually rational feasible assignments where some player is engaged in a non-void activity. First, when π(1) = b, π(2) = b, π(3) = a , the coalition {2, 3} together with activity a strongly blocks π. Second, when π(1) = a , π(2) = a, π(3) = a, the coalition {3} together with activity b strongly blocks π. Third, when π(1) = a , π(2) = a , π(3) = b, the coalition {1, 2, 3} together with activity a strongly blocks π. Finally, when π(1) = a, π(2) = a, and π(3) = a, the coalition {1, 2} together with activity b strongly blocks π.

Similarly, a Nash stable outcome is not guaranteed to exist even for g GASPs on paths and stars. Example 3 (Stalker game). Consider a two-player g GASP where player 1 is happy to participate in any activity as long as she is alone, and player 2 always wants to participate in an activity with player 1. This instance admits no Nash stable outcomes: if player 1 engages in an activity, then player 2 wants to join her coalition, causing player 1 to deviate to another (possibly void) activity.

However, if all activities are copyable, we can effectively treat g GASP as a non-transferable utility game on a graph. In particular, we can invoke a famous result of Demange (2004) concerning the stability of non-transferable utility games on trees. Thus, requiring all activities to be copyable allows us to circumvent the non-existence result for the core (Example 2). The argument is constructive. Theorem 4 (implicit in the work of Demange 2004). For every g GASP where each activity a A is copyable and (N, L) is acyclic, a core stable feasible assignment exists and can be found in time polynomial in p and n. Now, the stalker game in Example 3 does not admit a Nash stable outcome even if we make all activities copyable. However, for copyable activities we can still check the existence of a Nash stable outcome in polynomial time if the social network is acyclic. Theorem 5. Given an instance (N, A, ( i)i N, L) of g GASP where each activity a A is copyable and the graph (N, L) is acyclic, one can decide whether it admits a Nash stable outcome in time polynomial in p and n.

Proof. If the input graph (N, L) is a forest, we can process each of its connected components separately, so we assume that (N, L) is a tree. We choose an arbitrary node as the root and construct a rooted tree by orienting the edges in L towards the leaves. We denote by D(i) the set of descendants of i (including i) in the rooted tree. Then, for each player i N, each alternative (a, k) X, and t [k] we set fi((a, k), t) to true if there exists a feasible assignment π : N A such that |πi D(i)| = t, π(i) = a, each player in D(i) πi likes (a, k) at least as much as any alternative she can deviate to (including the void activity), and no player in D(i) \ πi has an NS feasible deviation. Otherwise, we set fi((a, k), t) to false. By construction, there exists a Nash stable feasible assignment if and only if fr((a, k), k) is true for some alternative (a, k) X, where r is the root of the rooted tree. For each player i N, each alternative (a, k) X, and each t [k], we initialize fi((a, k), t) to true if t = 1 and

i weakly prefers (a, k) to any alternative of size 1, and we set fi((a, k), t) to false otherwise. Then, for i N from the bottom to the root, we iterate through all the children of i and update fi((a, k), t); more precisely, for each child j of i and for t = k, . . . , 1, we set fi((a, k), t) to true if

t 2 and there exists an x [t 1] such that both fi((a, k), x) and fj((a, k), t x) are true, or fi((a, k), t) is true, and players i and j can be separated from each other, i.e., there exists (b, ℓ) X such that (i) fj((b, ℓ), ℓ) is true, (ii) b = a or (a, k) i (b, ℓ+ 1), and (iii) a = a or (b, ℓ) j (a, k + 1).

In cases where fr((a, k), k) is true for some alternative (a, k) X, a Nash stable feasible assignment can be found using dynamic programming.

Hardness Results for Nash Stability We now move on to the case where each activity can be used at most once. We will show that computing Nash stable outcomes of g GASPs is NP-complete even when the underlying network is a path, a star, or a graph with constant size connected components. Clearly, this problem is contained in NP for any social network since we can easily check whether a given assignment is Nash stable. Our proof for paths is by reduction from a restricted version of the NP-complete problem RAINBOW MATCHING. Given a graph G and a set of colors C, a proper edge coloring is a mapping φ : E(G) C where φ(e) = φ(e ) for all edges e, e such that e = e and e e = . Without loss of generality, we assume that φ is surjective. A properly edge-colored graph (G, C, φ) is a graph together with a set of color and a proper edge coloring. A matching M in an edgecolored graph (G, C, φ) is called a rainbow matching if all edges of M have different colors. An instance of RAINBOW MATCHING is an edge-colored graph (G, C, φ) and an integer k. It is a yes -instance if G admits a rainbow matching with at least k edges and a no -instance otherwise. Le and Pfender (2014) show that RAINBOW MATCHING remains NP-complete even for properly edge-colored paths.

Theorem 6. Given an instance of g GASP whose underlying graph is a path, it is NP-complete to determine whether it has a Nash stable feasible assignment.

Proof. The hardness proof proceeds by a reduction from PATH RAINBOW MATCHING. Given an instance (G, C, φ, k) of PATH RAINBOW MATCHING where |C| = q, we construct an instance of g GASP on a path as follows. We create a vertex player v for each v V (G) and an edge player e for each e E(G). To create the social network, we start with G and place each edge player in the middle of the respective edge, i.e., we let NG = V (G) E(G) and LG = { {v, e} | v e E(G) }. To the right of the graph (NG, LG), we attach a path consisting of garbage collectors {g1, g2, . . . , gq k} and q copies (Nc, Lc) of the stalker game where Nc = {c1, c2} and Lc = {{c1, c2}} for each c C. We introduce a color activity c for each color c C. Each vertex player v approves color activities φ(e) of its adjacent edges e with size 3; each edge player e approves the color activity φ(e) of its color

with size 3; each garbage collector gi approves any color activity c with size 1; finally, for players in Nc, c C, player c1 approves its color activity c with size 1, whereas player c2 approves c with size 2. We show that G has a rainbow matching of size at least k if and only if there exists a Nash stable feasible assignment. Suppose that there exists a rainbow matching M of size k. We construct a feasible assignment π where for each e = {u, v} M we set π(e) = π(u) = π(v) = φ(e), each garbage collector gi, i [q k], is arbitrarily assigned to one of the remaining q k color activities, and the remaining players are assigned to the void activity. The assignment π is Nash stable, since every garbage collector as well as every edge or vertex player assigned to a color activity are allocated their top alternative, and no remaining player has an NS feasible deviation. Conversely, suppose that there is a Nash stable feasible assignment π. Let M = { e E(G) | π(e) C }. We will show that M is a rainbow matching of size at least k. To see this, notice that π cannot allocate a color activity to a member of Nc, since otherwise no feasible assignment would be Nash stable. Further, at most q k color activities are allocated to the garbage collectors, which means that at least k color activities should be assigned to vertex and edge players. The only individually rational way to do this is to select triples of the form (u, e, v) where e = {u, v} E(G) and assign to them their color activity φ(e). Thus, M is a rainbow matching of size at least k.

For g GASPs on stars we provide a reduction from the NP-complete problem MINIMUM MAXIMAL MATCHING (MMM). An instance of MMM is a graph G and a positive integer k |E(G)|. It is a yes -instance if G admits a maximal matching with at most k edges, and a no -instance otherwise. The problem remains NP-complete for bipartite graphs (Demange and Ekim 2008).

Theorem 7. Given an instance of g GASP whose underlying graph is a star, it is NP-complete to determine whether it has a Nash stable feasible assignment.

Proof. To prove NP-hardness, we reduce from MMM on bipartite graphs. Given a bipartite graph G = (U V, E) with vertex bipartition (U, V ) and an integer k, we create a star with center c and |V | + 1 leaves: one leaf for each vertex player v V plus one stalker s. We introduce an activity u for each u U, and two additional activities a and b. A player v V approves (u, 1) for each activity u such that {u, v} E as well as (a, |V | k + 1) and prefers the former to the latter. That is, (u, 1) v (a, |V | k + 1) for every u U with {u, v} E; v is indifferent among the activities associated with its neighbors in the graph, that is, (u, 1) v (u , 1) for all u, u U such that {u, v} E and {u , v} E. The center player c approves both (a, |V | k + 1) and (b, 1), and prefers the former to the latter, i.e., (a, |V | k + 1) c (b, 1) c (a , 1). Finally, the stalker s only approves (b, 2). We now show that G admits a maximal matching M with at most k edges if and only if our instance of g GASP admits a Nash stable assignment. Suppose that G admits a maximal

matching M with at most k edges. We construct a feasible assignment π by setting π(v) = u for each {u, v} M, assigning |V | k vertex players and the center to a, and assigning the remaining players to the void activity. Clearly, the center c has no incentive to deviate and no vertex player in a singleton coalition wants to deviate to the coalition of the center. Further, no vertex v has an NS-deviation to an unused activity u, since if π admits such a deviation, this would mean that M {u, v} forms a matching, contradicting maximality of M. Finally, the stalker player does not deviate since the center does not engage in b. Hence, π is Nash stable. Conversely, suppose that there exists a Nash stable feasible assignment π and let M = { {π(v), v} | v V π(v) U }. We will show that M is a maximal matching of size at most k. By Nash stability, the stalker player should not have an incentive to deviate, and hence the center player and |V | k vertex players are assigned to activity a. It follows that k vertex players are not assigned to a, and therefore |M| k. Moreover, M is a matching since each vertex player is assigned to at most one activity, and by individual rationality each activity can be assigned to at most one player. Now suppose towards a contradiction that M is not maximal, i.e., there exists an edge {u, v} E such that M {u, v} is a matching. This would mean that in π no player is assigned to u, and v is assigned to the void activity; hence, v has an NS-deviation to u, contradicting the Nash stability of π.

In the analysis of cooperative games on social networks one can usually assume that the social network is connected: if this is not the case, each connected component can be processed separately. This is also the case for g GASP as long as all activities are copyable. However, if each activity can only be used by a single group, different connected components are no longer independent, as they have to choose from the same pool of activities. Indeed, we will now show that the problem of finding Nash stable outcomes remains NP-hard even if the size of each connected component is at most four. Our hardness proof for this problem proceeds by reduction from a restricted version of 3SAT. Specifically, we consider (3,B2)-SAT: in this version of 3SAT each clause contains exactly 3 literals, and each variable occurs exactly twice positively and twice negatively. This problem is known to be NP-complete (Berman, Karpinski, and Scott 2003).

Theorem 8. Given an instance of g GASP where each connected component of the underlying graph has size at most 4, it is NP-complete to determine whether it has a Nash stable feasible assignment.

Proof. We reduce from (3,B2)-SAT. Consider a formula φ with variable set X and clause set C, where for each variable x X we write x1 and x2 for the two positive occurrences of x, and x1 and x2 for the two negative occurrences of x. For each x X, we introduce four players x1, x2, x1, x2, which correspond to the four occurrences of x. For each clause c C, we introduce one stalker sc and three other players c1, c2, and c3. The network (N, L) consists of one component for each clause a star with center sc and leaves c1, c2, and c3 and of two components for each variable x X consisting of a single edge each: {x1, x2} and { x1, x2}. Thus, the size of

u e v gi Nc c

x1 x2 x1 x2

Figure 1: Graphs constructed in the proofs of Theorem 6, 7, and 8 (pictured left-to-right).

each component of this graph is at most 4. For each x X we introduce one variable activity x, two positive literal activities x1 and x2, two negative literal activities x1 and x2, and two further activities ax and ax. Also, we introduce an activity c for each clause c C. Thus,

x X {x, x1, x2, x1, x2, ax, ax} C.

For each x X the preferences of the positive literal players x1 and x2 are given as follows:

x1: (x, 2) (x, 1) (x1, 1) (x2, 2) (ax, 1) (a , 1), x2: (x, 2) (x2, 1) (x1, 2) (ax, 2) (a , 1).

If one of the positive literal players x1 and x2 is engaged in the void activity and the other is engaged alone in a nonvoid activity, this would cause the former player to deviate to another activity; thus, in a Nash stable assignment, none of the activities ax and a can be assigned to positive literal players. Similarly, for each x X the preferences of the negative literal players x1 and x2 are given as follows:

x1: (x, 2) (x, 1) ( x1, 1) ( x2, 2) ( ax, 1) (a , 1), x2: (x, 2) ( x2, 1) ( x1, 2) ( ax, 2) (a , 1).

As argued above, Nash stable assignments cannot allocate activities ax and a to negative literal players. Hence, if there exists a Nash stable assignment, there are only two possible cases: first, both players x1 and x2 are assigned to x, and players x1 and x2 are assigned to x1 and x2, respectively; second, both players x1 and x2 are assigned to x, and players x1 and x2 are assigned to x1 and x2, respectively. For players in Nc where ℓc 1, ℓc 2, and ℓc 3 are the literals in a clause c, the preferences are given by

cr : (ℓc r, 1) (c, 2) (a , 1), (r = 1, 2, 3) sc : (ℓc 1, 2) (ℓc 2, 2) (ℓc 3, 2) (c, 2) (a , 1).

That is, players c1, c2, and c3 prefer to engage alone in their approved literal activity, whereas sc wants to join one of the adjacent leaves whenever π(sc) = a and that leaf is assigned a literal activity; however, the leaf would then prefer to switch to the void activity. This means that if there exists a Nash stable outcome, at least one of the literal activities must be used outside of Nc, and some leaf and the stalker sc must be assigned to activity c. We will show that φ is satisfiable if and only if there exists a Nash stable outcome. Suppose that there exists a truth assignment that satisfies φ. First, for each variable x that is set to True, we assign positive literal activities x1 and x2 to the positive literal players x1 and

x2, respectively, and assign x to the negative literal players x1 and x2. For each variable x that is set to False, we assign negative literal activities x1 and x2 to the negative literal players x1 and x2, respectively, and assign x to the positive literal players x1 and x2. Note that this procedure uses at least one of the literal activities ℓc 1, ℓc 2 and ℓc 3 of each clause c C, since the given truth assignment satisfies φ. Then, for each clause c C, we select a player cj whose approved activity ℓc j has been assigned to some literal player, and assign cj and the stalker to c, and the rest of the clause players to their approved literal activity if it is not used yet, and to the void activity otherwise. It is easy to see that the resulting assignment π is Nash stable. Conversely, suppose that there exists a Nash stable feasible assignment π. By Nash stability, for each variable x X, either a pair of positive literal players x1 and x2 or a pair of negative literal players x1 and x2 should be assigned to the corresponding pair of literal activities; in addition, for each clause c C, the stalker sc and one of the players c1, c2, and c3 should engage in the activity c, thereby implying that the approved literal activity of the respective leaf should be assigned to some literal players. Then, take the truth assignment that sets the variable x to True if its positive literal players x1 and x2 are assigned to positive literal activities x1 and x2; otherwise, x is set to False. This assignment can be easily seen to satisfy φ.

Fixed Parameter Tractability

In the instances of g GASP that are created in our hardness proofs, the number of activities is unbounded. It is thus natural to wonder what can be said when there are few activities to be assigned. It turns out that for each of the restricted families of graphs considered in the previous section, finding Nash stable assignments in g GASP is fixed parameter tractable with respect to the number of activities. The basic idea behind each of the three algorithms we present is that we fix a set of activities that will be assigned to the players, and for each possible subset B A of activities we check whether there exists a stable assignment using the activities from that subset only. Our algorithms for paths and for small components use dynamic programming, allowing us to build up the set B step-by-step. We begin by giving the dynamic program that works for paths. Briefly, we move along the path from left to right, and, for each initial segment of the path, guess a set B B of activities that will be used by that segment of players. For each guess, we determine whether it is possible to construct

an assignment that does not admit an NS-deviation within the initial segment under consideration.

Theorem 9. There exists an algorithm that, given an instance of g GASP whose underlying graph is a path, checks whether this instance has a Nash stable feasible assignment and finds one if it exists, and runs in time 4pp2 poly(n)

Proof. Suppose that N = [n] and L = { {i, i + 1} | i = 1, 2, . . . , n 1 }. First, we guess a subset B A of nonvoid activities to be used; there are 2p possibilities, so we try them all. For each B, we solve the problem by dynamic programming. For each i [n], each B B, each alternative (a, k) B [n] {(a , 1)}, and each number t [k], we let fi(B, B , (a, k), t) be true if there exists an individually rational feasible assignment π : N A so that

the set of activities assigned to [i] is exactly B ; π(i) = a, |πi| = k, |πi [i]| = t; and every player in [i] weakly prefers her alternative under π to engaging alone in any of the activities in A \ B and has no NS feasible deviation to activities in B .

Otherwise, we let fi(B, B , (a, k), t) be false. For i = 1, if B = {a}, t = 1, and player 1 weakly prefers (a, k) to each alternative (b, 1) such that b A \ B, we set f1(B, B , (a, k), t) to true and otherwise to false. For i = 2, . . . , n, fi(B, B , (a, k), t) is true if k t n i, we have (a, k) i (b, 1) for each b A \ B, and either

t = 1, and players i and i 1 can be separated from each other, i.e., there exists (b, ℓ) X such that (i) fi 1(B, B \ {a}, (b, ℓ), ℓ) is true, (ii) a = a or (b, ℓ) i 1 (a, k + 1), and (iii) b = a or (b, ℓ+ 1) i (a, k); or t 2 and fi 1(B, B , (a, k), t 1) is true.

Otherwise fi(B, B , (a, k), t) is set to false. It is not difficult to see that a Nash stable assignment exists if and only if fn(B, B, (a, k), k) is true for some alternative (a, k) X and some B A . The runtime bound is immediate.

Our algorithm for networks with small connected components is similar to the dynamic program we just discussed. We order the components, and, for each prefix of that ordering, we check if a given subset of activities can be assigned to that prefix in a Nash stable way. Within each component, we have enough time to consider all possible assignments, and each potential deviation involves at most one component. The resulting algorithm is FPT with respect to the combined parameter p + c, where c is a bound on the size of the components of the network.

Theorem 10. There exists an algorithm that given an instance of g GASP on a graph with constant-size connected components checks whether it has a Nash stable feasible assignment, finds one if it exists, and runs in time pc8p poly(n), where c is the maximum size of a connected component.

For stars, we use a different technique to obtain an FPT result, namely (derandomized) color coding. We begin by guessing the alternative (a, k) assigned to the center player. Next, we again guess the precise set B of activities in use

by the players not assigned to alternative (a, k). We then randomly color leaf players by activities in B {a }, rejecting colorings that are infeasible or must lead to NS deviations. Crucially, the latter task reduces to straightforward counting questions, which allows this method to succeed.

Theorem 11. There exists an algorithm that, given an instance of g GASP on a star checks whether it has a Nash stable feasible assignment, finds one if it exists, and runs in time 2ppp+1 poly(n).

Proof. For each (a, k) X and B A \ {a}, we will check whether there exists a Nash stable assignment such that the center c and k 1 leaves engage in a, exactly |B| leaf players are assigned to activities in B, and the rest of the players are assigned to the void activity. First, we will check whether the center player c strictly prefers some alternative (b, ℓ) B {2} (A \ B) {1} to (a, k). If this is the case, there is no Nash stable outcome with the above properties, since the center player would deviate. Next, we decide whether we can assign |B| leaves to activities in B so as to obtain a Nash stable outcome. We use the color-coding technique to design a randomized algorithm: we color each leaf player using colors in B independently and uniformly at random. We say that a Nash stable assignment π that assigns exactly |B| leaves to activities in B is compatible with a coloring χ if π(i) = b implies χ(i) = b for each b B. If there exists a Nash stable assignment π where each of the activities in B is allocated to exactly one player, then the probability that a random coloring χ is compatible with it is |B| |B|: each player i with π(i) B is colored correctly with probability 1/|B|. Since the success probability depends on p only, our algorithm can be derandomized by using a family of k-perfect hash functions (Alon, Yuster, and Zwick 1995). It remains to show how to find a Nash stable outcome compatible with a given random coloring χ, or determine that no such assignment exists, in polynomial time. To this end, fix a coloring χ : N \ {c} B. We seek to assign each player i N \ {c} to one of the activities in {a, χ(i), a } in such a way that exactly one agent of each color engages in the color activity and k players including the center are assigned to a. For b B, let Nb = { i N \ {c} | χ(i) = b }. For each b B and ℓ= 0, . . . , |Nb| 1 let fb(ℓ) be true if we can assign exactly one player in Nb to b and exactly ℓ players in Nb to a so that no player in Nb has an NS deviation. To compute these quantities, we need auxiliary variables. Namely, for each b B, i Nb, and ℓ= 0, . . . , |Nb| 1 let fb(i, ℓ) be true if we can assign b to i, while assigning activity a to exactly ℓplayers in Nb and a to exactly |Nb| 1 ℓplayers in Nb, so that no player in Nb has an NSdeviation. To compute fb(i, ℓ), we first check whether player i has no incentive to deviate, i.e., whether (i) player i weakly prefers (b, 1) to (b , 1) for each b A \ B and (ii) a = a or i weakly prefers (b, 1) to (a, k + 1). In a similar fashion, we check if the remaining players in Nb can be assigned to a and a in the desired proportion. Specifically, let Nb(i, a) be the set of players in Nb \{i} who weakly prefer (a, k) to (b , 1) for each b A \ B and let Nb(i, a ) be the set of players in Nb \ {i} who weakly prefer

(a , 1) to (b , 1) for each b A \ B as well as to (a, k + 1). We set fb(i, ℓ) to true if and only if conditions (i) and (ii) are satisfied and we have Nb(i, a) Nb(i, a ) = Nb \ {i}, |Nb(i, a)| ℓ, and |Nb(i, a )| |Nb| 1 ℓ, i.e., each player in Nb \ {i} can be assigned to a or a , and for each of these activities there is a sufficient number of players who would not deviate when assigned to that activity. Having computed fb(i, ℓ) for all i Nb, we can compute fb(ℓ): we set fb(ℓ) to true if fb(i, ℓ) is true for some i Nb and false otherwise. We are now left with an instance of the MULTIPLECHOICE KNAPSACK problem: we need to check if for each b B there is a value ℓb, 0 ℓb |Nb| 1, such that fb(ℓb) is true and

b B ℓb = k 1. This problem can be solved in polynomial time by a straightforward dynamic programming algorithm.

Core stability

By adapting the reductions for Nash stability, we can show that checking the existence of a core stable outcome is also NP-hard. This result holds for all classes of graph families that we have considered.

Theorem 12. Given an instance of g GASP whose underlying graph is a path, a star, or has connected components whose size is bounded by 3, it is NP-complete to determine whether it has a core stable feasible assignment.

Proof. To verify that a given feasible assignment is core stable, it suffices to check that for every alternative (a, k) there is no connected coalition with at least k players who strictly prefer (a, k) to the alternative of their current coalition. For the networks we consider this can be done in polynomial time, and hence our problem is in NP. The hardness reductions are similar to the respective reductions for Nash stability; essentially, we have to replace copies of the stalker game with copies of the game with an empty core.

Our FPT result for graphs with small connected components can also be adapted to the core. In contrast, our approach for Nash stability for paths and stars does not seem to generalize to core stability, and we leave these cases for future work.

Theorem 13. There exists an algorithm that given an instance of g GASP checks whether it has a core stable feasible assignment, finds one if it exists, and runs in time pc+18p poly(n), where c is the maximum size of the connected components.

In this paper, we have initiated the study of group activity selection problems with network structure, and found that even for very simple families of graphs computing stable outcomes is NP-hard. We identified several ways to circumvent this computational intractability. For g GASPs with copyable activities, we showed that there exists a polynomial time algorithm to compute stable outcomes, and for g GASPs with few activities, we provided fixed parameter algorithms for restricted classes of networks.

We leave several interesting questions for future work. Our fixed-parameter tractability results can be extended to more general graph families, such as graphs with bounded pathwidth and graphs with a bounded number of internal nodes. However, for general graphs, the exact parameterized complexity of determining the existence of stable outcomes is unknown. When the underlying graph is complete, one can adapt techniques of Darmann et al. (2012) to show that the problem of computing Nash stable outcomes is in XP with respect to p; for other networks, including trees, it is not even clear whether our problem is in XP with respect to p. It would be also interesting to investigate the parameterized complexity of g GASPs using other parameters. Another promising research direction is to study analogues of other solution concepts from the hedonic games literature for g GASPs; in particular, it would be interesting to understand the complexity of computing individually stable outcomes in g GASPs. Acknowledgements We thank the anonymous reviewers for helpful comments that improved the presentation of the paper. This work was supported by the European Research Council (ERC) under grant number 639945 (ACCORD).

References Alon, N.; Yuster, R.; and Zwick, U. 1995. Color-coding. J. ACM 42(4):844 856. Aziz, H., and Savani, R. 2016. Hedonic games. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A. D., eds., Handbook of Computational Social Choice. Cambridge University Press. chapter 15. Berman, P.; Karpinski, M.; and Scott, A. D. 2003. Approximation hardness of short symmetric instances of MAX-3SAT. Technical Report 049. http://eccc.hpi-web.de/report/2003/049/. Chalkiadakis, G.; Greco, G.; and Markakis, E. 2016. Characteristic function games with restricted agent interactions: Corestability and coalition structures. Artificial Intelligence 232:76 113. Darmann, A.; Elkind, E.; Kurz, S.; Lang, J.; Schauer, J.; and Woeginger, G. 2012. Group activity selection problem. In WINE 2012, 156 169. Darmann, A. 2015. Group activity selection from ordinal preferences. In ADT 2015, 35 51. Demange, M., and Ekim, T. 2008. Minimum maximal matching is NP-hard in regular bipartite graphs. In TAMC 2008, 364 374. Demange, G. 2004. On group stability in hierarchies and networks. Journal of Political Economy 112(4):754 778. Elkind, E. 2014. Coalitional games on sparse social networks. In WINE 2014, 308 321. Igarashi, A., and Elkind, E. 2016. Hedonic games with graphrestricted communication. In AAMAS 2016, 242 250. A. Igarashi, D. Peters, and E. Elkind. Group activity selection on social networks. arxiv:1611.04524 [cs.GT], 2016. Le, V. B., and Pfender, F. 2014. Complexity results for rainbow matchings. Theoretical Computer Science 524(C):27 33. Myerson, R. B. 1977. Graphs and cooperation in games. Mathematics of Operations Research 2(3):225 229.