License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.27
URN: urn:nbn:de:0030-drops-186809
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18680/
Bullinger, Martin ;
Romen, René
Online Coalition Formation Under Random Arrival or Coalition Dissolution
Abstract
Coalition formation considers the question of how to partition a set of n agents into disjoint coalitions according to their preferences. We consider a cardinal utility model with additively separable aggregation of preferences and study the online variant of coalition formation, where the agents arrive in sequence and whenever an agent arrives, they have to be assigned to a coalition immediately. The goal is to maximize social welfare. In a purely deterministic model, the greedy algorithm, where an agent is assigned to the coalition with the largest gain, 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 Θ(1/(n²)), whereas an alternative algorithm, which is based on alternating between waiting and greedy phases, can achieve a competitive ratio of Θ(1/n). Second, we relax the irrevocability of decisions by allowing to dissolve coalitions into singleton coalitions, presenting a matching-based algorithm that once again achieves a competitive ratio of Θ(1/n). Hence, compared to the base model, we present two ways to achieve a competitive ratio that precisely gets rid of utility dependencies. Our results also give novel insights in weighted online matching.
BibTeX - Entry
@InProceedings{bullinger_et_al:LIPIcs.ESA.2023.27,
author = {Bullinger, Martin and Romen, Ren\'{e}},
title = {{Online Coalition Formation Under Random Arrival or Coalition Dissolution}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {27:1--27:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18680},
URN = {urn:nbn:de:0030-drops-186809},
doi = {10.4230/LIPIcs.ESA.2023.27},
annote = {Keywords: Online Algorithms, Coalition Formation, Online Matching}
}
|
Keywords: |
|
Online Algorithms, Coalition Formation, Online Matching |
|
Collection: |
|
31st Annual European Symposium on Algorithms (ESA 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
30.08.2023 |
