2025/05/09 by Martin Bullinger, Bullinger, Martin, René Romen +3
Computer Science · Decision Sciences · Economics, Econometrics and Finance · #05C70 #68W27 (Primary) 91B68 #91A12 (Secondary) #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2 #Game Theory and Voting Systems #I.2.11 #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2505.06163
openalex publication_date 2025/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. We identify optimal algorithms with constant competitive ratios in two related settings, independent of the range of agent valuations. First, under random agent arrival, we present an asymptotically optimal ((1)/(3)-\frac 1n)-competitive algorithm, where n is the number of agents. This result builds on our identification of an optimal matching algorithm in a general model of online matching with edge weights and an unknown number of agents. In this setting, we also achieve an asymptotically optimal competitive ratio of (1)/(3)-\frac 1n. Second, when agents arrive in an arbitrary order but algorithms are allowed to irrevocably and entirely dissolve coalitions, we show that another matching-based algorithm achieves an optimal competitive ratio of (1)/(6 + 4√(2)).