The Power of Matching for Online Fractional Hedonic Games

We study coalition formation in the framework of fractional hedonic games (FHGs). The objective is to maximize social welfare in an online model where agents arrive one by one and must be assigned to coalitions immediately and irrevocably. A recurrent theme in online coalition formation is that online matching algorithms, where coalitions are restricted to size at most 2, yield good competitive ratios. For example, computing maximal matchings achieves the optimal competitive ratio for general online FHGs. However, this ratio is bounded only if agents' valuations are themselves bounded.