Optimality and Nash Stability in Additive Separable Generalized Group Activity Selection Problems

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)

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) =

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".