Learning preferences in Additive Separable Hedonic Project Games

We study Additive Separable Hedonic Project Games (ASHPGs), which model coalition formation considering both agents’ subjective preferences over their coalition members and objective incentives for project rewards. In this setting, each autonomous agent selects a single project from a given set to maximize its own utility. We first formalize ASHPGs in a single-shot scenario with known preferences, where each agent has sufficient information to evaluate her preferences before project selection. We then extend the model to a learning setting where preferences are initially unknown, and agents gradually learn them through repeated feedback as they iteratively select projects and form coalitions. Motivated by this, we propose an Upper Confidence Bound (UCB)-based online learning algorithm with semi-bandit feedback, in which each agent observes the feedback received from all individual members of their coalition. Our theoretical analysis demonstrates that ASHPGs with symmetric preferences possess an exact potential function that guarantees the existence of a Nash stable outcome. Furthermore, we prove that the proposed algorithm achieves sublinear Nash regret and converges to an ε-approximate Nash equilibrium over time. Experiments on real and synthetic data validate these theoretical results.