On Simplified Group Activity Selection

摘要

Several real-world situations can be represented in terms of agents that have preferences over activities in which they may participate. Often, the agents can take part in at most one activity (for instance, since these take place simultaneously), and there are additional constraints on the number of agents that can participate in an activity. In such a setting we consider the task of assigning agents to activities in a reasonable way. We introduce the simplified group activity selection problem providing a general yet simple model for a broad variety of settings, and start investigating the case where upper and lower bounds of the groups have to be taken into account. We apply different solution concepts such as envy-freeness and core stability to our setting and provide a computational complexity study for the problem of finding such solutions.