Stability and Efficiency in Hedonic Project Games

Stability and Efficiency in Hedonic Project Games

Jaber Valizadeh, Dongmo Zhang, Omar Mubin

Proceedings of the Thirty-Fifth International Joint Conference on Artificial Intelligence
Main Track. Pages 401-409. https://doi.org/10.24963/ijcai.2026/46

We introduce Hedonic Project Games, a model in which agents choose projects with divisible rewards while holding subjective preferences over coalition composition. This framework captures a fundamental trade-off absent from existing models: agents care simultaneously about who they collaborate with and what they work on. We study three stability notions: classical Nash Stability and two refinements, Joining Stability and Leaving Stability, which account for the welfare of both the deviating agent and the affected coalition members. We evaluate the efficiency of stable outcomes using the Price of Anarchy and Price of Stability, comparing the social welfare of stable outcomes to that of an optimal allocation. While stable outcomes may not exist in general, we identify broad and natural preference classes in which stability and efficiency improve significantly. In particular, under monotonic-decreasing preferences in coalition size, Nash and joining stability coincide and are guaranteed to exist, whereas leaving stability may fail. Under per-capita non-decreasing preferences, socially optimal outcomes are always Nash stable and coincide with leaving stability, although equilibrium inefficiency remains unbounded. Experiments on synthetic and real-world data support the theoretical efficiency results.
Keywords:
Agent-based and Multi-agent Systems: Agent theories and models
Agent-based and Multi-agent Systems: Coordination and cooperation
Agent-based and Multi-agent Systems: Resource allocation
Game Theory and Economic Paradigms: Cooperative games
Game Theory and Economic Paradigms: Noncooperative games