On the online coalition structure generation problem
Yükleniyor...
Dosyalar
Tarih
2021
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
AI Access Foundationusc Information Sciences Inst
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
We consider the online version of the coalition structure generation problem, in which agents, corresponding to the vertices of a graph, appear in an online fashion and have to be partitioned into coalitions by an authority (i.e., an online algorithm). When an agent appears, the algorithm has to decide whether to put the agent into an existing coalition or to create a new one containing, at this moment, only her. The decision is irrevocable. The objective is partitioning agents into coalitions so as to maximize the resulting social welfare that is the sum of all coalition values. We consider two cases for the value of a coalition: (1) the sum of the weights of its edges, and (2) the sum of the weights of its edges divided by its size. Coalition structures appear in a variety of application in AI, multi-agent systems, networks, as well as in social networks, data analysis, computational biology, game theory, and scheduling. For each of the coalition value functions we consider the bounded and unbounded cases depending on whether or not the size of a coalition can exceed a given value alpha. Furthermore, we consider the case of a limited number of coalitions and various weight functions for the edges, i.e., unrestricted, positive and constant weights. We show tight or nearly tight bounds for the competitive ratio in each case.
Açıklama
We thanks the anonymous referees for their valuable comments that helped improving the presentation of the paper. This work was partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR "Algorithms, Games, and Digital Markets" (2017R9FHSR 002).
Anahtar Kelimeler
Coalition structure, Coalition value, Computational biology, Computation theory, Cooperative games, Game theory, On-line algorithms, On-line fashion, Online versions, Social welfare, Stability, Structure generation, Weight functions, Value functions
Kaynak
Journal Of Artificial Intelligence Research
WoS Q Değeri
Q2
Scopus Q Değeri
Q2
Cilt
72
Sayı
Künye
Flammini, M., Monaco, G., Moscardelli, L., Shalom, M. & Zaks, S. (2021). On the online coalition structure generation problem. Journal Of Artificial Intelligence Research, 72, 1215-1250. doi:10.1613/JAIR.1.12989
