New algorithm for group activity selection resists manipulation with hidden preferences

In a new paper from arXiv, computer scientists Maria Fomenko (Gran Sasso Science Institute) and Giovanna Varricchio (University of Calabria) tackle a core challenge in social choice: designing mechanisms for group activity selection that maximize total social welfare while discouraging agents from misreporting their true preferences. They focus on the additively separable Group Activity Selection Problem (AS-GASP), where each agent has private preferences over activities and weights indicating how much they care about others joining the same activity. The goal is to assign agents to activities truthfully and efficiently.

The researchers introduce the concept of non-obvious manipulability (NOM), a weaker but more realistic form of strategy-proofness. Their main result: when preferences and weights are arbitrary or non-negative, any mechanism that achieves optimal social welfare is automatically NOM. However, they also prove that when preferences or weights are binary, optimality and NOM become incompatible — a surprising limitation. On the computational side, they show that finding an optimal assignment is NP-hard, and for arbitrary values no polynomial-time algorithm can guarantee a bounded approximation ratio. But when preferences are non-negative, they offer two asymptotically optimal approximation mechanisms that still satisfy NOM, bridging theory and practice for real-world group decision systems.