AI summaryⓘ
The authors study a problem where people have private preferences and opinions about others when choosing activities, aiming to assign groups in a way that maximizes overall happiness while encouraging honest answers. They focus on a property called non-obvious manipulability (NOM), meaning it’s hard for agents to benefit by lying. Their main findings show that when preferences and weights are unrestricted, the best solutions can still be easily manipulated, but when preferences or weights are simple (binary), NOM and optimal solutions might conflict. They also explore computation limits, proving it's very hard to find or even approximate the best solution in general, but if preferences are only positive, they provide efficient methods that balance good outcomes and prevent easy manipulation.
Group Activity Selection ProblemAdditive separabilityPreferencesWeightsSocial welfareNon-obvious manipulability (NOM)Mechanism designTruthfulnessNP-hardnessApproximation algorithms
Authors
Maria Fomenko, Giovanna Varricchio
Abstract
In this work, we study the additively separable Group Activity Selection Problem (AS-GASP) in an imperfect information setting, where agents have private preferences over activities and weights over other agents. Our goal is to design mechanisms that assign agents to activities based on their declared preferences and weights, with the objective of maximizing social welfare while ensuring truthful reporting. We, therefore, focus on the notion of non-obvious manipulability (NOM), a form of resilience to manipulation. We first investigate the relationship between NOM and social welfare optimality. In this regard, our main result shows that, when preferences and weights are arbitrary or non-negative, any optimal mechanism is non-obviously manipulable. In contrast, when either preferences or weights are binary, we show that optimality and NOM may be incompatible. We then turn to computational aspects. While it is known that computing an optimal outcome for the AS-GASP is NP-hard even in restricted settings, we establish a strong inapproximability result showing that no polynomial-time algorithm can guarantee a bounded approximation ratio when preferences and weights may take arbitrary values. In turn, when preferences are non-negative, we show that a bounded approximation is possible, and we present two asymptotically optimal approximation mechanisms that are also guaranteed to satisfy NOM.