Group Activity Selection on Social Networks
Igarashi, Peters, Elkind · cs.GT · 2016-11-14 · 原文
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.
讲义
讲义·推断 依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。
1. 人话版
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.
2. 领域脉络
本文类目：cs.GT，属于其所在研究脉络的最新进展。
3. 机制拆解
On the other hand, we obtain fixed-parameter tractability results for this problem with respect to the number of activities.
4. 证据与数字
摘要未给出量化结果——留意原文的实验与数据。
5. 反例与边界
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.
6. 跨领域连接与意外收获
思考本文机制能否迁移到你正在跟进的问题。
7. 可复用方法
把本文机制与你手头项目对照，找一个两周内能验证的最小实验。
8. 术语表
精读时把不熟的术语记入此处，作为下次回忆的锚点。