Group activity selection on social networks

Journal article

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.

Authors: Igarashi, A; Peters, D; Elkind, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for the Advancement of Artificial Intelligence
• Journal: Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)
• Publication date: 2017-02-01
• Acceptance date: 2016-11-11
• Keywords: cs.GT