Optimality and Nash Stability in Additive Separable Generalized Group Activity Selection Problems

Optimality and Nash Stability in Additive Separable Generalized Group Activity Selection Problems

Vittorio Bilò, Angelo Fanelli, Michele Flammini, Gianpiero Monaco, Luca Moscardelli

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 102-108. https://doi.org/10.24963/ijcai.2019/15

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.
Keywords:
Agent-based and Multi-agent Systems: Noncooperative Games
Agent-based and Multi-agent Systems: Algorithmic Game Theory
Agent-based and Multi-agent Systems: Computational Social Choice