Optimality and Nash Stability inAdditively Separable Generalized Group Activity Selection Problems
Abstract
The generalized group activity selection problem
(GGASP) consists in assigning agents to activities
according to their preferences, which depend on
both the activity and the set of its participants. We
consider additively separable GGASPs, where every agent has a separate valuation for each activity
as well as for any other agent, and her overall utility
is given by the sum of the valuations she has for the
selected activity and its participants. Depending on
the nature of the agents’ valuations, nine different
variants of the problem arise. We completely characterize the complexity of computing a social optimum and provide approximation algorithms for the
NP-hard cases. We also focus on Nash stable outcomes, for which we give some complexity results
and a full picture of the related performance by providing tights bounds on both the price of anarchy
and the price of stability