--- title: "Optimality and Nash Stability in Additive Separable Generalized Group Activity Selection Problems" authors: - "Vittorio Bilò" - "Angelo Fanelli" - "Michele Flammini" - "Gianpiero Monaco" - "Luca Moscardelli" doi: "10.24963/ijcai.2019/15" url: "https://ijcai.org/proceedings/2019/15" pdf: "https://ijcai.org/proceedings/2019/0015.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "102-108" track: "Main track" keywords: - "Agent-based and Multi-agent Systems: Noncooperative Games" - "Agent-based and Multi-agent Systems: Algorithmic Game Theory" - "Agent-based and Multi-agent Systems: Computational Social Choice" --- # Optimality and Nash Stability in Additive Separable Generalized Group Activity Selection Problems Vittorio Bilò, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, Luca Moscardelli *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 102-108. DOI: [10.24963/ijcai.2019/15](https://doi.org/10.24963/ijcai.2019/15) ## Abstract The generalized group activity selection problem (GGASP) consists in assigning agents to activities according to their preferences, which depend on both the activity and the set of its participants. We consider additively separable GGASPs, where every agent has a separate valuation for each activity as well as for any other agent, and her overall utility is given by the sum of the valuations she has for the selected activity and its participants. Depending on the nature of the agents' valuations, nine different variants of the problem arise. We completely characterize the complexity of computing a social optimum and provide approximation algorithms for the NP-hard cases. We also focus on Nash stable outcomes, for which we give some complexity results and a full picture of the related performance by providing tights bounds on both the price of anarchy and the price of stability. ## Full text ## 1 Introduction In many real-life situations, a group of agents has to be assigned to a set of available activities. Specifically, each agent has to be assigned to one of the activities according to her personal preferences that take into account both the activity and the corresponding set of participating agents. A classical example is the organization of a workshop where the organizers plan a set of parallel events and each participant can attend only one of them. Other examples can be the assignment of researchers to university departments, politicians selecting a party to belonging to, the allocation of students to classrooms, etc. Many aspects of this setting are captured by the generalized group activity selection problem (GGASP) (see [Darmann and Lang, 2017]). In the GGASP, we are given a set of activities A = A∗ ∪ {a∅}, where A∗ = {a1, . . . , ak} is a set of concrete activities and a∅ is the void activity; if an agent is assigned to a∅, it means that she is not participating to any concrete activity in A∗ . An alternative for agent i is either a∅ or a pair (a, S) ∈ A∗ × Ni, where Ni is the set of all subsets of agents containing i. By denoting with Xi the set of alternatives for i, agent i has a preference relation over Xi. Unfortunately, Xi can be exponentially large with respect to the number of actions and agents. To overcome this computational obstacle, some restrictions of the model have been proposed. The anonymous group activity selection problem (GASP), introduced in [Darmann et al., 2018]), is a succinct representable version of the GGASP, where agents care only about the activity they belong to and the corresponding number of participants (i.e., agents are considered all equal). In this paper, we consider a different succinct representable version of the GGASP, that we call the additively separable GGASP (AS-GGASP), which is not captured by the GASP. In the AS-GGASP, each agent has a value for any other agent and for each activity. For an assignment of agents to activities, where each agent selects exactly one activity, the overall utility of an agent is given by the value she has for the assigned activity, plus the sum of the values she assigns to the agents who participate in the same activity. We emphasize that the AS-GGASP is not captured by the GASP and viceversa because, on the one hand, agents are not considered all equal in our model and, on the other hand, we have cardinal utilities. A strictly related class of games is the one of hedonic games (HG), introduced in [Dreze and Greenberg, 1980], which is a specific GGASP, where the preferences of an agent i depend only on the set of agents in i's coalition and not on the activity to which i is assigned to, i.e., a HG can be seen as a GGASP which are independent on the set of activities. Symmetric additively separable hedonic games (SAS-HGs) Figure 1: Relations between AS-GGASP and other related problems ![Image](https://ijcai.org/proceedings/2019/fulltext/15/image_000000_fe09a165b70284d239c232741a758403dde10a7156e22ed3da1e90cdf5c40de9.png) is a succinct representable version of HGs, where each agent has a value for any other agent, and the utility of a coalition to a particular agent is simply the sum of the values she assigns to the members of her coalition. We notice that a SAS-HG can be seen as an AS-GGASP in which all agents have value zero for all activities. The relations of the AS-GGASP with all the aforementioned models are schematically represented in Figure 1. ## 1.1 Our Contribution We assume agents' valuations falling into three different numerical categories: real numbers, non-negative real numbers, and {0, 1}. Depending on whether they apply to activity preferences or social relationships, nine different variants of the problem arise (see Section 2 for precise definitions). We first consider the problem of computing a social optimum, i.e., an assignment maximizing the utility of all agents, and completely characterize its complexity as summarized in Table 1. Moreover, for the NP-hard cases in which no negative numbers are allowed, we provide a (2 - 1/k)- approximation and a better 3/2-approximation if all valuations are in {0, 1}. We then consider complexity and efficiency of Nash stable outcomes. We first show, via a potential function argument, that a Nash stable outcome always exists (Theorem 6). Unfortunately, as shown afterwards, the potential function provides only an inefficient way to compute a stable outcome. We provide some complexity results, which are summarized in Table 2, and derive tight bounds on both the price of anarchy and the price of stability (Table 3). ## 1.2 RelatedWork The GASP has been introduced in [Darmann et al., 2018], where the authors show that the problem of deciding whether a given instance of the problem admits a Nash stable outcome is NP-complete. In particular, they prove that the problem is NP-complete even for the special case called a-GASP, where agents have approval-based preferences. They also consider other stability solution concepts and provide complexity results for them. For another special case of the GASP, called o-GASP, in which agents have strict preferences (i.e., without any ties among alternatives), [Darmann, 2015] shows that deciding the existence of a Nash stable assignment is NPcomplete. The parameterized complexity of the GASP has been analized in [Lee and Williams, 2017] with respect to several solution concepts. [Igarashi et al., 2017b] propose a variant of the GASP, called gGASP, in which agents are placed on a social network and activities can only be assigned to connected subgroups. They show that deciding the existence of a Nash stable outcome is NP-hard when the social network is a path or a star, or the size of each connected component is bounded by a constant. The parameterized complexity of gGASP has been treated in [Igarashi et al., 2017a; Igarashi et al., 2017b]. For a nice survey on group activity selection problems, see Chapter 5 in [Endriss, 2017]. For what concerns hedonic games, the SAS-HG always admit a Nash stable outcome. In fact, it is easy to see that the sum of the agents' utilities is a potential function, and a Nash stable outcome is a minimum of such a function. However, in [Gairing and Savani, 2010] the authors show that computing such Nash stable outcome is PLS-complete. Further results on additively separable hedonic games can be found in [Aziz et al., 2013; Elkind et al., 2016; Flammini et al., 2017; Olsen, 2009]. Fractional hedonic games (FHGs) and modified fractional hedonic games (MFHGs) are very similar to SAS-HGs. The main difference is that the utility of each agent is divided by the size of her coalition, and by the size of her coalition excluding herself, respectively. Some results on FHGs and MFHGs can be found in [Aziz et al., 2014; Bil`o et al., 2018; Flammini et al., 2018; Carosi et al., 2019] and in [Elkind et al., 2016; Monaco et al., 2018; Olsen, 2012; Monaco et al., 2019], respectively. ## 2 Definitions and Notation Graph theory notation. Fix an edge weighted undirected graph G = (V,E,w), with w : E ↦→ R. Given an edge {i, j} ∈ E, we write wij as a shorthand for w({i, j}); moreover, for a node i ∈ V , denote by Wi(G) = ∑{i,j}∈E wij the sum of the weights of all edges incident to i in graph G (we drop G from the notation when it is clear from the context). Additive Separable Generalized Group Activity Selection Problems (AS-GGASPs). An AS-GGASP G = (G,A, p) is defined by an edge weighted undirected graph G = (V,E,w), a set of activities A and, for each i ∈ V , a preference function pi : A ↦→ R. We shall denote by n = |V | the number of agents and by k = |A| the number of activities. Each agent must be assigned to one of the k activities in A. For an assignment z and an agent i ∈ V , denote by δi(z) = ∑v∈V :zv=zi wiv the total weight of the edges incident to i and to all other agents assigned to activity zi in z. The utility of agent i in z is defined as ui(z) = δi(z)+pi(zi) and she aims at maximizing it. An assignment z is Nash stable (or z is a Nash stable outcome), if ui(z) ≥ ui(z-i, aj) for each i ∈ V and aj ∈ A, where, as usual, ui(z-i, aj) denotes the strategy profile z in which strategy zi of agent i ∈ V is replaced by strategy aj. Denote by NS(G) the set of Nash stable outcomes of G. We say that G has non-negative weights when w : E ↦→ R≥0 and that it has non-negative preferences when pi : A ↦→ R≥0 for each i ∈ V ; when G has both non-negative weights and preferences, we simply say that it has non-negative quantities. A special case of games with non-negative weights is given by games with unitary weights which captures the case in which G is unweighted. Similarly, a special case of games with non-negative preferences is given by games with boolean preferences, where pi : A ↦→ {0, 1} for each i ∈ V . Hence, by considering all possible combinations of weight and preference functions, we get nine different scenarios. Social Optimum, Price of Anarchy and Price of Stability. Let SW be the function SW(z) = ∑i∈N ui = ∑i∈V (δi(z) + pi(zi)) associating to each assignment the induced social welfare, that is, the sum of all agents' utilities realized in the given assignment. Denote by o a social optimum for G, that is an assignment maximizing SW. The price of anarchy of G is defined as POA(G) = Table 1: The computational complexity of SOCIAL OPTIMUM. All cases have been solved | Complexity of SOCIAL OPTIMUM | General preferences | Non-negative preferences | Boolean preferences | |----------------------------------|--------------------------------------------------|--------------------------------------------------|--------------------------------------------------| | General weights | NP-hard for k ≥ 2 (Th. 1) | NP-hard for k ≥ 2 (Th. 1) | NP-hard for k ≥ 2 (Th. 1) | | Non-negative and unitary weights | NP-hard for k ≥ 3 (Th. 3) in P for k = 2 (Th. 2) | NP-hard for k ≥ 3 (Th. 3) in P for k = 2 (Th. 2) | NP-hard for k ≥ 3 (Th. 3) in P for k = 2 (Th. 2) | Table 2: The computational complexity of NASH STABLE. Six over nine cases have been solved. Results labelled with [*] come from [Gairing and Savani, 2010] | Complexity of NASH STABLE | General preferences | Non-negative preferences | Boolean preferences | |-----------------------------|------------------------------------|---------------------------------------|---------------------------------------| | General weights | PLS-complete for k ≥ 2 (Th. 8 [*]) | PLS-complete for k ≥ 2 (Th. 8 [*]) | PLS-complete for k ≥ 2 (Th. 8 [*]) | | Non-negative weights | open for k = 2 open for k ≥ 3 | in P for k = 2 (Th. 9) open for k ≥ 3 | in P for k = 2 (Th. 9) open for k ≥ 3 | | Unitary weights | in P for k ≥ 2 (Th. 7) | in P for k ≥ 2 (Th. 7) | in P for k ≥ 2 (Th. 7) | Table 3: Tight bounds on the price of anarchy and price of stability for all cases | | Price of Anarchy - General preferences | Price of Anarchy - Non-negative preferences | Price of Anarchy - Boolean preferences | Price of Stability - General preferences | Price of Stability - Non-negative preferences | Price of Stability - Boolean preferences | |----------------------|------------------------------------------|-----------------------------------------------|------------------------------------------|--------------------------------------------|-------------------------------------------------|--------------------------------------------| | General weights | ∞ (Th. 15) | ∞ (Th. 17) | ∞ (Th. 17) | ∞ (Th. 15) | ∞ (Th. 17) | ∞ (Th. 17) | | Non-negative weights | ∞ (Th. 15) | k (Th. 10 & 14) | k (Th. 10 & 14) | ∞ (Th. 15) | 2-1/k (Th. 12 & 15) | 2-1/k (Th. 12 & 16) | | Unitary weights | ∞ (Th. 15) | k (Th. 10 & 14) | k (Th. 10 & 14) | ∞ (Th. 15) | 2-1/k (Th. 12 & 15) | 1 (Th. 13) | maxe∈NS(G) SW(o)/SW(e). The price of stability of G is defined as POS(G) = mine∈NS(G) SW(o)/SW(e). ## 3 Complexity Results In this section, we address the complexity of the problems NASH STABLE and SOCIAL OPTIMUM which, given an AS-GGASP G, asks for the computation of a Nash stable outcome and of a social optimum for G, respectively. We shall make extensive use of the following optimization problems (and some of their variants): - MULTIWAY CUT: it is defined by an undirected connected graph G = (V, E, w) with non-negative edge weights and a set of k nodes S = {s1, . . . , sk}. It asks for a set of edges of minimum total weight whose removal partitions G into k connected components each containing exactly one node in S. MULTIWAY CUT is NP-hard for any fixed k ≥ 3, even when all edges have unitary weight [Dahlhaus et al., 1994]. For the special case of k = 2, MULTIWAY CUT is known as MIN CUT and the two nodes s1 and s2 are usually denoted as s and t. This problem is solvable in polynomial time on graphs with non-negative edge weights by the Max Flow-Min Cut Theorem [Ford and Fulkerson, 1962]. Moreover, the variant defined on graphs with general edge weights, when negative edges are all incident to either s or t, is called NEGATIVE MIN CUT and is shown to be solvable in polynomial time in [McCormick et al., 2003]. - MAX CUT: it is defined by an undirected graph G = (V,E,w) with non-negative edge weights and asks for a set of nodes S ⊆ V such that the value of the cut, i.e., the total weight of all edges between nodes in S and nodes in V \ S, is maximized. MAX CUT is NP-hard [Karp, 1972]. ## 3.1 Computing a Social Optimum We first show that SOCIAL OPTIMUM is NP-hard in problems with general weights and boolean preferences, even when there are two activities only. Theorem 1. In AS-GGASPs with general weights and boolean preferences, SOCIAL OPTIMUM is NP-hard for k = 2. On the positive side, we show that, as soon as the edge weights become non-negative, SOCIAL OPTIMUM becomes solvable in polynomial time when k = 2. Theorem 2. In AS-GGASPs with non-negative weights, SOCIAL OPTIMUM can be solved in polynomial time for k = 2. Proof. We reduce SOCIAL OPTIMUM to NEGATIVE MIN CUT. Given an AS-GGASP G = (G = (V, E, w), {a1, a2}, p) with non-negative weights, we define an instance I = (G′ , s, t) of NEGATIVE MIN CUT as follows. Graph G′ = (V ′ , E′ , w′ ) is such that V ′ = V ∪ {s, t}, E′ = E ∪ {{s, v} : v ∈ V } ∪ {{t, v} : v ∈ V } and Observe that, thanks to the presence of the edges connecting any node in G to both s and t in G′ , it follows that G′ is connected even when G is not. This observation and the fact that edges with negative weights in G′ are all incident to either s or t, make I an instance of NEGATIVE MIN CUT. Any feasible solution for I yields an assignment for G in which all agents belonging to the same connected component of s are assigned to activity a1 and all agents belonging to the same connected component of t are assigned to activity a2. To conclude the proof, we need to show that an optimal solution for I yields a social optimum for G. To this aim, note that the social welfare of an assignment z, induced by a feasible solution (V1, V2) for I such that V ′ = V1 ∪ V2, s ∈ V1 and t ∈ V2, is given by Note that the first three quantities of (1) are fixed constants, while the remaining three ones define the total weight of the cut (V1, V2). Thus, the social welfare is maximized in any assignment induced by an optimal solution for I. However, as soon as the number of activities increases, the problem becomes NP-hard in all cases. Theorem 3. When there are at least three activities, SOCIAL OPTIMUM is NP-hard, even in AS-GGASPs with unitary weights and boolean preferences. Proof. We design a reduction from MULTIWAY CUT on unweighted graphs. Given an instance I = (G, S) of MULTIWAY CUT defined on an unweighted graph G = (V, E) with |V | = n and k = |S|, we create the following AS-GGASP G = (G′ , A, p) with unitary weights and boolean preferences. Graph G′ = (V ′ ,E′ ) is constructed by adding to G a set V ′ (si) of 2(n - 1) nodes all adjacent to node si, for each si ∈ S; so |V ′ | = n+2k(n-1) and |E′ | = |E|+2k(n-1). We set A = {a1, . . . , ak} and the preference functions are defined as follows: We claim that, in any social optimum for G, each agent i ∈ V ′ (si) ∪ {si} is assigned to activity ai. It is immediate to see that, in any assignment in which si is assigned to activity ai, the social welfare is maximized only if also all agents in V ′ (si) are assigned to ai. Hence, assume by way of contradiction that z is a social optimum in which zsi ̸= ai for some si ∈ S. Now, let z′ be the assignment obtained from z after moving all agents in V ′ (si) ∪ {si} to activity ai. Facts 1 and 2 contradict the optimality of z. Thus, any social optimum for G induces a multiway cut for I obtained by considering the assignment of the agents in V only. To complete the proof, we need to show that any social optimum for G induces a multiway cut of minimum cost. Fix a social optimum o for G. We have SW(o) = (6n - 5)k+2 ∑{i,j}∈E:oi=oj wij = (6n-5)k+2 ∑{i,j}∈E wij - 2 ∑{i,j}∈E:oi̸=oj wij. As the first two terms of SW(o) are constant, it follows that o minimizes the quantity ∑{i,j}∈E:oi̸=oj wij which is exactly the value of the multiway cut induced by o, and this shows the claim. Given the hardness result for k ≥ 3, we focus on the computation of approximate solutions. We get the following upper bound. Theorem 4. In AS-GGASPs with non-negative quantities, SOCIAL OPTIMUM can be approximated up to a factor of 2 - 1/k for every k ≥ 3. Proof. Fix an AS-GGASP with non-negative quantities G and let o be a social optimum for G. Define aj ∗ ∈ argmaxaj∈A ∑i∈V pi(aj) as an activity maximizing the overall preference of the agents when they are grouped together on a same activity. Define the assignments z1 and z2 such that z1 is obtained by grouping all agents on activity aj ∗ and z2 is obtained by assigning each agent to the the activity she likes the most (breaking ties arbitrarily). Consider the algorithm outputting the assignment z with the highest social welfare between z1 and z2 . Clearly, this algorithm can be implemented in polynomial time. Define x∗ = ∑i∈V δi(o), y∗ = ∑i∈V pi(oi), x1 = ∑i∈V δi(z1 ), y1 = ∑i∈V pi(z1 i ), x2 = ∑i∈V δi(z2 ) and y2 = ∑i∈V pi(z2 i ). By definition of z1 and the fact that G has non-negative quantities, it follows that x1 +y1 ≥ x∗ +y∗ /k. Moreover, by definition of z2 , we have x2 + y2 ≥ y∗ . Thus, we get SW(o) = x∗ + y∗ = x∗ + y∗ k + k-1 k y∗ ≤ SW(z) + k-1 k SW(z) = (2- 1k ) SW(z), where the inequality follows from SW(z) ≥ max{x1 + y1 , x2 + y2 } ≥ max{x∗ + y∗ /k, y∗ }. For problems with unitary weights and boolean preferences, a better bound is possible. Theorem 5. Given any positive integer α, SOCIAL OPTIMUM can be approximated up to a factor of (3α+1)k 2αk+α+1 in time O(nkα) in AS-GGASPs with unitary weights and boolean preferences. ## 3.2 Computing a Nash Stable Outcome First, we show that AS-GGASPs admit Nash stable outcomes via a potential function argument. Theorem 6. Function φ(z) = 12 ∑i∈V (δi(z) +2pi(zi)) is an exact potential for the AS-GGASP. Proof. Fix an assignment z, a player j ∈ V and an activity a ∈ A. We have where equality 2 holds because all contributions due to edges not incident to j ∈ V and the preferences of all agents but j cancel each other out (notice that each edge incident to node j has to be counted twice, i.e., for node j and for its other endpoint). Given that the potential function defined in the previous theorem can be computed in polynomial time with respect to the dimensions of the problem, as observed in [Fabrikant et al., 2004], we immediately obtain that NASH STABLE belongs to the complexity class PLS. By leveraging on the potential function given in the previous theorem, for AS-GGASPs with unitary edge weights, we show that any sequence of better-responses converges to a Nash stable outcome in polynomial time. Theorem 7. Any sequence of better-responses converges to a Nash stable outcomes after O(k2n2 ) steps in AS-GGASPs with unitary edge weights. [Gairing and Savani, 2010] show that NASH STABLE in additive separable hedonic games is PLS-complete for any k ≥ 2 as long as negative weights are allowed. As AS-GGASPs are a generalization of additive separable hedonic games (it suffices defining the preference function of each player as the identically null function), the PLS-completeness of NASH STABLE in presence of negative weights can be inherited directly. Theorem 8 ([Gairing and Savani, 2010]). NASH STABLE in AS-GGASPs with general weights and boolean preferences is PLS-complete for each k ≥ 2. Theorem 8 leaves open the complexity of NASH STABLE in AS-GGASPs with non-negative quantities. We could not provide an answer to this question, except for the basic case of k = 2, where a simple polynomial time algorithm can be designed. Theorem 9. NASH STABLE in AS-GGASPs with nonnegative quantities can be solved in polynomial time for k = 2. Proof. Consider a better-response dynamics starting from an assignment in which all agents are grouped on a same activity, say a1. This dynamics converges to a Nash stable outcome in at most n steps. This holds because it is never profitable for a deviating agent to go back to a1, as every better-response never worsens the desirability of a2 and never improves that of a1. ## 4 Price of Anarchy and Stability In this section, we exactly characterize the efficiency of Nash stable outcomes for all nine variants of AS-GGASPs with respect to both the price of anarchy and the price of stability. ## 4.1 Upper Bounds We start by showing that the price of anarchy of AS-GGASPs with non-negative quantities is upper bounded by the number of activities. Theorem 10. The price of anarchy of AS-GGASPs with nonnegative quantities is at most k. Proof. Fix an AS-GGASP (G,A, p) with non-negative weights and a pair of assignments e and o such that e is a Nash stable outcome and o is a social optimum for (G, A, p), respectively. For an agent i ∈ V , as e is a Nash stable outcome, we have ui(e) = ∑i′∈V :ei′=ei wii′ + pi(ei) ≥ ∑i′∈V :ei′=j wii′ + pi(aj) for each j ∈ [k]. By summing all the inequalities for each j ∈ [k], we get ui(e) ≥ 1k (∑i′∈V wii′ + ∑j∈[k] pi(aj)). Moreover, by the fact that G has non-negative quantities, it trivially holds ui(o) ≤ ∑i′∈V wii′ + maxj∈[k] pi(aj) ≤ ∑i′∈V wii′ + ∑j∈[k] pi(aj). For the price of stability, we derive an upper bound of 2 - 1/k for games with non-negative quantities. To prove the claim, we first need the following technical lemma. Lemma 11. Fix a game (G, A, p) with non-negative weights and a social optimum o. Then, ∑i∈V ∑j∈[k] pi(aj) ≤ k ∑i∈V pi(oi). Theorem 12. The price of stability of AS-GGASPs with nonnegative quantities is at most 2 - 1/k. Proof. Fix a game G = (G,A, p) with non-negative quantities and a social optimum o. Denote by e the global maximum of the potential function φ(z) = 1 2 ∑i∈V (δi(z) +2pi(zi)), so that φ(e) ≥ φ(o). By Theorem 6, e is a Nash stable outcome for G. For the sake of brevity, define x = 1 2 ∑i∈V δi(e) and y = ∑i∈V pi(ei). Similarly, define x∗ = 1 2 ∑i∈V δi(o) and y∗ = ∑i∈V pi(oi). We get SW(e) = 2x+y, SW(o) = 2x∗ +y∗ , φ(e) = x + y and φ(o) = x∗ + y∗ . By φ(e) ≥ φ(o), we get We divide the proof into two cases, depending on the relationship between x∗ and y∗ . Assume first x∗ ≤ (k-1)y∗ . By using this hypothesis, we derive: which implies Thus, we get SW(e) = 2x + y ≥ x + y ≥ x∗ + y∗ ≥ k 2k-1 (2x∗+y∗ ) = k 2k-1 SW(o), which yields the claim. Note that the assumption that weights are non-negative is crucial to derive the first inequality. The second and third inequalities follow from (3) and (4), respectively. Assume now x∗ ≥ (k - 1)y∗ . We get: which yields the claim. The first inequality follows from (3) and the second one from y = ∑i∈V pi(ei) ≤ ∑i∈V ∑j∈[k] pi(aj). Note that this condition requires that preferences are non-negative. The third inequality comes from Lemma 11 and the last one from the hypothesis x∗ ≥ (k - 1)y∗ . For the special case of games with unitary weights and boolean preferences, the price of stability becomes 1, as any social optimum can be shown to be a Nash stable outcome. Theorem 13. The price of stability of AS-GGASPs with unitary weights and boolean preferences is equal to 1. Proof. Fix an AS-GGASP G = (G,A, p) with unitary weights and boolean preferences and a social optimum o for G. Assume, by way of contradiction, that o is not a Nash stable outcomes. Then, there exists an agent i ∈ V and an activity aj ∈ A such that ui(o) < ui(o-i, aj). Given an assignment z, an agent i ∈ V and an activity a ∈ A, let ni(z, a) denote the number of agents assigned to activity a in z which are adjacent to agent i in G. The fact that weights are unitary and i improves by deviating to aj in o gives the following inequality: ni(o, σi) + pi(σi) < ni(o, aj) + pi(aj). As preferences are boolean, this implies that ni(o, aj) ≥ ni(o, σi) + pi(σi) - pi(aj ) + 1. Thus, we get: which contradicts the assumption that o is a social optimum for G. Hence, o has to be a Nash stable outcome. ## 4.2 Lower Bounds The following theorem shows a lower bound matching the upper bound on the price of anarchy given in Theorem 10 that holds even under the assumptions of unitary weights and boolean preferences. This completely characterizes the price of anarchy of all problems in which negative values are not allowed. For either general weights or general preferences, both the price of anarchy and the price of stability are unbounded and this is shown later in the subsection. Theorem 14. The price of anarchy of AS-GGASPs with unitary weights and boolean preferences is at least k. For the price of stability, four different lower bounds are necessary to complete the picture. They are presented in the following three theorems. Theorem 15. The price of stability of AS-GGASPs is at least 2-1/k for unitary weights and non-negative preferences and it is unbounded for unitary weights and general preferences. Proof. Consider the AS-GGASP G = (G,A, p) defined as follows. Graph G is such that |V | = k, there is an edge {1, i} of weight 1 for each 2 ≤ i ≤ k. For each i ∈ [k], function pi is such that pi(ai) = α and pi(aj) = β for each j ∈ [k] with j ̸= i, where α > β + 1. First, observe that each agent i, with 2 ≤ i ≤ k, has a unique dominant strategy consisting in choosing activity ai. Then, under the hypothesis that each of these agents can only be assigned to her dominant strategy, agent 1 also has a unique dominant strategy consisting in choosing activity a1. Thus, there exists a unique Nash stable outcome e in G where each agent i gets a utility equal to α, so that SW(e) = kα. Let us compare the social welfare of z to the social welfare of the assignment o in which all agents are assigned to activity a1. We get POS(G) ≥ SW(o) SW(e) = α+(2+β)(k-1) kα . Let us consider the following two cases, both verifying α > β+1 as required. By setting α = 1+ε, with ε > 0, and β = 0, which define a problem with unitary weights and non-negative preferences, we get that POS(G) tends to (2k - 1)/k for ε going to zero. By setting α = ε, with ε > 0, and β = -1, which define a problem with unitary weights and general preferences, we get that POS(G) tends to infinity for ε going to zero. Theorem 16. The price of stability of AS-GGASPs with nonnegative weights and boolean preferences is at least 2-1/k. Theorem 17. The price of stability of AS-GGASPs with general weights and boolean preferences is unbounded. ## Acknowledgments Angelo Fanelli was partially supported by the French Project ANR-14-CE24-0007-01 "CoCoRICo-CoDec". Michele Flammini was partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR "Algorithms, Games, and Digital Markets". ## References 1. [Aziz et al., 2013] Haris Aziz, Felix Brandt, and Hans Georg Seedig. Computing desirable partitions in additively sepa- rable hedonic games. Artificial Intelligence, 195:316-334, 2013. 2. [Aziz et al., 2014] Haris Aziz, Felix Brandt, and Paul Har- renstein. Fractional hedonic games. In Proc. 13th AAMAS, pages 5-12, 2014. 3. [Bilò et al., 2018] Vittorio Bilò, Angelo Fanelli, Muchele Flammini, Gianpiero Monaco, and Luca Moscardelli. Nash stable outcomes in fractional hedonic games: Ex- istence, efficiency and computation. J. Artif. Intell. Res., 62:315-371, 2018. 4. [Carosi et al., 2019] Raffaello Carosi, Gianpiero Monaco, and Luca Moscardelli. Local core stability in simple sym- metric fractional hedonic games. In Proc. 18th AAMAS, pages 574-582, 2019. 5. [Dahlhaus et al., 1994] Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, and Mihalis Yannakakis. The complexity of multiterminal cuts. SIAM J. Comput., 23(4):864-894, 1994. 6. [Darmann and Lang, 2017] Andreas Darmann and Jérôme Lang. Group activity selection problems. In U. Endriss, editor, Trends in computational social choice, chapter 5, page 385-410. AI Access, 2017. 7. [Darmann et al., 2018] Andreas Darmann, Edith Elkind, Sascha Kurz, Jérôme Lang, Joachim Schauer, and Ger- hard J. Woeginger. Group activity selection problem with approval preferences. Int. J. Game Theory, 47(3):767-796, 2018. 8. [Darmann, 2015] Andreas Darmann. Group activity selec- tion from ordinal preferences. In Proc. 4th Algorithmic Decision Theory ADT, pages 35-51, 2015. 9. [Dreze and Greenberg, 1980] Jacques H. Dreze and Joseph Greenberg. Hedonic coalitions: Optimality and stability. Econometrica, 48(4):987-1003, 1980. 10. [Elkind et al., 2016] Edith Elkind, Angelo Fanelli, and Michele Flammini. Price of pareto optimality in hedonic games. In Proc. 30th AAAI, pages 475-481, 2016. 11. [Endriss, 2017] Ulle Endriss. Trends in Computational So- cial Choice. Lulu.com, 2017. 12. [Fabrikant et al., 2004] Alex Fabrikant, Christos H. Pa- padimitriou, and Kunal Talwar. The complexity of pure nash equilibria. In Proc. 36th STOC, pages 604-612. ACM, 2004. 13. [Flammini et al., 2017] Michele Flammini, Gianpiero Monaco, and Qiang Zhang. Strategyproof mechanisms for additively separable hedonic games and fractional hedonic games. In Proc. 15th WAOA, pages 301-316, 2017. 14. [Flammini et al., 2018] Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Mordo Shalom, and Shmuel Zaks. Online coalition structure generation in graph games. In Proc. 17th AAMAS, pages 1353-1361, 2018. 15. [Ford and Fulkerson, 1962] Lester R. Ford and Delbert R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, NJ, 1962. 16. [Gairing and Savani, 2010] Martin Gairing and Rahul Sa- vani. Computing stable outcomes in hedonic games. In Proc. 3rd SAGT, pages 174-185. Springer-Verlag, 2010. 17. [Igarashi et al., 2017a] Ayumi Igarashi, Robert Bredereck, and Edith Elkind. On parameterized complexity of group activity selection problems on social networks. In Proc. 16th AAMAS, pages 1575-1577, 2017. 18. [Igarashi et al., 2017b] Ayumi. Igarashi, Dominik Peters, and Edith Elkind. Group activity selection on social net- works. In Proc. 31st AAAI, pages 565-571, 2017. 19. [Karp, 1972] Richard M. Karp. Reducibility among com- binatorial problems. In Proceedings of a symposium on the Complexity of Computer Computations, page 85-103. Plenum Press, 1972. 20. [Lee and Williams, 2017] Hooyeon Lee and Virginia V. Williams. Parameterized complexity of group activity se- lection. In Proc. 16th AAMAS, pages 353-361, 2017. 21. [McCormick et al., 2003] S. Thomas McCormick, Mendu R. Rao, and Giovanni Rinaldi. Easy and difficult objec- tive functions for max cut. Mathematical Programming, 94(2-3):459-466, 2003. 22. [Monaco et al., 2018] Gianpiero Monaco, Luca Moscardelli, and Yllka Velaj. Stable outcomes in modified fractional hedonic games. In Proc. 17th AAMAS, pages 937-945, 2018. 23. [Monaco et al., 2019] Gianpiero Monaco, Luca Moscardelli, and Yllka Velaj. On the performance of stable outcomes in modified fractional hedonic games with egalitarian social welfare. In Proc. 18th AAMAS, pages 873-881, 2019. 24. [Olsen, 2009] Martin Olsen. Nash stability in additively sep- arable hedonic games and community structures. Theory Comput. Syst., 45(4):917-925, 2009. 25. [Olsen, 2012] Martin Olsen. On defining and computing communities. In Proceedings of the Conferences in Re- search and Practice in Information Technology, pages 97- 102, 2012.