Open AccessOn the Online Coalition Structure Generation Problem
Author(s) -
Michele Flammini,
Gianpiero Monaco,
Luca Moscardelli,
Mordechai Shalom,
Shmuel Zaks
Publication year - 2021
Publication title -
journal of artificial intelligence research/the journal of artificial intelligence research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.79
H-Index - 123
eISSN - 1943-5037
pISSN - 1076-9757
DOI - 10.1613/jair.1.12989
Subject(s) - computer science , bounded function , scheduling (production processes) , graph , constant (computer programming) , variety (cybernetics) , value (mathematics) , game theory , mathematical optimization , mathematical economics , mathematics , theoretical computer science , artificial intelligence , mathematical analysis , machine learning , programming language
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 α. 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.