A social choice approach to ordinal group activity selection

We consider the situation in which group activities need to be organized for a set of agents when each agent can take part in at most one activity. The agents' preferences depend both on the activity and the number of participants in that activity. In particular, the preferences are given by means of strict orders over pairs “(activity, group size)”, including the possibility “do nothing”. Our goal will be to assign agents to activities on basis of their preferences, the minimum requirement being that no agent prefers doing nothing, i.e., not taking part in any activity at all. Taking a social choice perspective, we aim at establishing such an assignment by two approaches. On the one hand, we use k-approval and Borda scores, and we apply the Condorcet criterion on the other hand. We analyze the computational complexity involved in finding a desired assignment, with focus on two natural special cases of agents' preferences which allow for some positive complexity results.