
arXiv: 2306.16965
Coalition formation explores how to partition a set of \( n \) agents into disjoint coalitions according to their preferences. We consider a cardinal utility model with an additively separable aggregation of preferences and study the online variant, where agents arrive in sequence. The goal is to achieve competitive social welfare. In the basic model, agents arrive in an arbitrary order and have to be assigned to coalitions immediately and irrevocably. There, the natural greedy algorithm is known to achieve an optimal competitive ratio, which heavily relies on the range of utilities. We complement this result by considering two related models. First, we study a model where agents arrive in a random order. We find that the competitive ratio of the greedy algorithm is \(\Theta\left(\frac{1}{n^{2}}\right)\) . In contrast, an alternative algorithm, which is based on alternating between waiting and greedy phases, can achieve a competitive ratio of \(\Theta\left(\frac{1}{n}\right)\) . Second, we relax the irrevocability of decisions by allowing the dissolution of coalitions into singleton coalitions. We achieve an asymptotically optimal competitive ratio of \(\Theta\left(\frac{1}{n}\right)\) by drawing a close connection to a general model of online matching. Hence, in both models, we obtain a competitive ratio that removes the unavoidable utility dependencies in the basic model and essentially matches the best possible approximation ratio by polynomial-time algorithms.
FOS: Computer and information sciences, 330, Computer Science - Computer Science and Game Theory, Computer Science - Data Structures and Algorithms, Online Algorithms, Data Structures and Algorithms (cs.DS), Online Matching, 004, Coalition Formation, Computer Science and Game Theory (cs.GT), ddc: ddc:004, ddc: ddc:
FOS: Computer and information sciences, 330, Computer Science - Computer Science and Game Theory, Computer Science - Data Structures and Algorithms, Online Algorithms, Data Structures and Algorithms (cs.DS), Online Matching, 004, Coalition Formation, Computer Science and Game Theory (cs.GT), ddc: ddc:004, ddc: ddc:
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
