Introduction
This research introduces the Additively Separable Generalized Group Activity Selection Problem (AS-GGASP), a theoretical framework for assigning agents to activities where their utility depends on both the activity itself and the specific individuals in their group. By utilizing additive separability, the authors bridge the gap between anonymous group selection models and identity-focused hedonic games, providing a succinct yet expressive model for complex social coordination problems.
Problem Context
Traditional models in group selection often face a trade-off between simplicity and computational tractability. The Group Activity Selection Problem (GASP) assumes anonymity, while Hedonic Games (HG) ignore the activity context. The Generalized GASP (GGASP) attempts to combine these but often results in exponentially large preference structures that are difficult to compute.
AS-GGASP addresses these limitations by assuming that an agent’s utility is the sum of their value for the activity and their individual values for every other person in their group. This additive structure makes the problem computationally approachable while remaining expressive enough for real-world scenarios like classroom assignments or workshop groupings.
Methodology
The authors analyze nine variants of the problem based on valuation types (general, non-negative, or boolean). Key technical contributions include:
- Potential Game Discovery: Proving that AS-GGASP is a potential game, which guarantees the existence of a Nash stable outcome.
- Complexity Mapping: Using reductions from Multiway Cut and Max Cut to establish NP-hardness for various social optimum scenarios.
- Algorithmic Bounds: Designing approximation algorithms for cases where finding the absolute social optimum is computationally difficult, such as a $2 - 1/k$ approximation.
Key Results
The study provides a comprehensive characterization of the problem's complexity and efficiency across several technical dimensions:
- Social Optimum: Computing the best possible assignment is generally difficult. For general weights, the problem is NP-hard for $k \ge 2$. For non-negative and unitary weights, it is NP-hard for $k \ge 3$ but solvable in polynomial time for $k = 2$.
- Nash Stability: Because AS-GGASP is a potential game, a stable outcome always exists. For general weights, finding it is PLS-complete. However, for unitary weights, a stable outcome can be found in polynomial time using better-response dynamics.
- Efficiency (Price of Anarchy and Stability): The authors quantify the efficiency loss due to selfish behavior using the Price of Anarchy (PoA) and Price of Stability (PoS).
As shown in the results, for non-negative weights and preferences, the PoA is exactly $k$ (the number of activities). The PoS for these cases is at most $2 - 1/k$. Remarkably, for boolean preferences and unitary weights, the PoS is 1, indicating that the social optimum is inherently a Nash stable equilibrium.
Conclusion
The AS-GGASP model provides a robust framework for understanding group activity selection. While the research maps out most of the complexity landscape, the complexity of finding Nash stable outcomes for non-negative weights when $k \ge 3$ remains an open question. Future work could extend this model to non-additive preference structures or explore alternative stability concepts like Core stability.
Summary updated