Approximate Strategyproof Mechanisms for the Additively Separable Group Activity Selection Problem

We investigate strategyproof mechanisms in the Group Activity Selection Problem with the additively separable property. Namely, agents have distinct preferences for each activity and individual weights for the other agents. We evaluate our mechanisms in terms of their approximation ratio with respect to the maximum utilitarian social welfare. We first show that, for arbitrary non-negative preferences, no deterministic mechanism can achieve a bounded approximation ratio. Thus, we provide a randomized k-approximate mechanism, where k is the number of activities, and a corresponding 2 - 2/k+1 lower bound. Furthermore, we propose a tight (2 -1/k )-approximate randomized mechanism when activities are copyable. We then turn our attention to instances where preferences can only be unitary, that is 0 or 1. In this case, we provide a k-approximate deterministic mechanism, which we show to be the best possible one within the class of strategyproof and anonymous mechanisms. We also provide a general lower bound of Ω ( √k ) when anonymity is no longer a constraint. Finally, we focus on unitary preferences and weights, and prove that, while any mechanism returning the optimum is not strategyproof, there exists a 2-approximate deterministic mechanism.