摘要：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.
