# Group Activity Selection on Social Networks

arXiv: https://arxiv.org/abs/1611.04524 · HTML: https://mlsanity.com/paper/1611.04524/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Nov 2016.

## Built on by (most cited first, 1 of 1)

- [Strategic Resource Selection with Homophilic Agents](https://mlsanity.com/paper/2305.00843/) (2023)

## Abstract (arXiv)

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 NP-hard 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.