On the online coalition structure generation problem

Basit Öğe Kaydı
dc.authorid0000-0002-0998-5649
dc.authorid0000-0002-9256-481X
dc.authorid0000-0003-0327-3728
dc.authorid0000-0002-2688-5703
dc.contributor.authorFlammini, Micheleen_US
dc.contributor.authorMonaco, Gianpieroen_US
dc.contributor.authorMoscardelli, Lucaen_US
dc.contributor.authorShalom, Mordechaien_US
dc.contributor.authorZaks, Shmuelen_US
dc.date.accessioned2021-12-21T15:42:44Z
dc.date.available2021-12-21T15:42:44Z
dc.date.issued2021
dc.departmentIşık Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümüen_US
dc.departmentIşık University, Faculty of Engineering, Department of Computer Engineeringen_US
dc.descriptionWe 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).en_US
dc.description.abstractWe 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.en_US
dc.description.sponsorshipWe 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)en_US
dc.description.versionPublisher's Versionen_US
dc.identifier.citationFlammini, 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.12989en_US
dc.identifier.doi10.1613/JAIR.1.12989
dc.identifier.endpage1250
dc.identifier.issn1076-9757
dc.identifier.issn1943-5037
dc.identifier.scopus2-s2.0-85122151582
dc.identifier.scopusqualityQ2
dc.identifier.startpage1215
dc.identifier.urihttps://hdl.handle.net/11729/3369
dc.identifier.urihttp://dx.doi.org/10.1613/JAIR.1.12989
dc.identifier.volume72
dc.identifier.wosWOS:000728450200001
dc.identifier.wosqualityQ2
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.indekslendigikaynakScience Citation Index Expanded (SCI-EXPANDED)en_US
dc.indekslendigikaynakSocial Sciences Citation Index (SSCI)en_US
dc.institutionauthorShalom, Mordechaien_US
dc.institutionauthorid0000-0002-2688-5703
dc.language.isoenen_US
dc.peerreviewedYesen_US
dc.publicationstatusPublisheden_US
dc.publisherAI Access Foundationusc Information Sciences Insten_US
dc.relation.ispartofJournal Of Artificial Intelligence Researchen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectCoalition structureen_US
dc.subjectCoalition valueen_US
dc.subjectComputational biologyen_US
dc.subjectComputation theoryen_US
dc.subjectCooperative gamesen_US
dc.subjectGame theoryen_US
dc.subjectOn-line algorithmsen_US
dc.subjectOn-line fashionen_US
dc.subjectOnline versionsen_US
dc.subjectSocial welfareen_US
dc.subjectStabilityen_US
dc.subjectStructure generationen_US
dc.subjectWeight functionsen_US
dc.subjectValue functionsen_US
dc.titleOn the online coalition structure generation problemen_US
dc.typeArticleen_US
dspace.entity.typePublication

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim
Ä°sim:
11729-3369.pdf
Boyut:
514.89 KB
Biçim:
Adobe Portable Document Format
Açıklama:
Publisher's Version
Ä°ndir
Lisans paketi
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
Ä°sim:
license.txt
Boyut:
1.44 KB
Biçim:
Item-specific license agreed upon to submission
Açıklama:
Ä°ndir

Koleksiyon

Makale Koleksiyonu | Bilgisayar Mühendisliği Bölümü
Scopus İndeksli Yayınlar Koleksiyonu
WoS İndeksli Yayınlar Koleksiyonu