Online Learning of Group-Stable Coalition Structures

Coalition formation concerns partitioning agents into disjoint coalitions based on their preferences for one another. In online learning of coalition structures, agents' true preferences may be initially unknown. Thus, coalitions are repeatedly formed based on preferences learned online from iterative feedback derived from interactions in those coalitions. This work introduces a new group stability approach to online learning in coalition formation, relying only on partial noisy feedback observed after agents interact. We analyze the system in terms of common group stability notions, where no group of agents benefits by simultaneously joining other coalitions or forming a new one. Our goal is to learn coalition structures that are robust to such group deviations, while simultaneously determining whether stable outcomes exist under the underlying (unknown) preferences. To this end, we analyze algorithms through two complementary metrics: (1) the error in predicting whether a stable partition exists, and (2) a regret notion that quantifies violations of group stability over time. We propose an algorithm that combines optimistic and pessimistic estimates to both explore potentially stable partitions and certify stability when supported by the observed feedback. We show that when a stable partition exists, our algorithm obtains sublinear error and regret despite relying only on partial noisy feedback, while in the non-existence case, it incurs only a constant number of mistakes. Experiments on synthetic instances validate our findings.