Online Coalition Structure Generation in Graph Games

We consider the online version of the coalition structure generation in graph games problem, where agents are vertices in a graph. After each step t , in which the t -th agent appears in an online fashion, agents are partitioned into $c(t)$ coalitions $\clust(t)=\\C_1^t, \C_2^t, łdots, \C_c(t) ^t \ $, such that every agent belongs to exactly one coalition $C_i^t$. When an agent appears, it may either join an existing coalition or form a new one having it as the only agent. The profit of a such a coalition structure $\clust(t)$ is the sum of the profits of its coalitions. We consider two cases for the profit of a coalition: (1) the sum of the weights of its edges (which represents the total profit of the agents in the coalition), and (2) the sum of the weights of its edges divided by its size (which represents the average profit of the agents in the coalition). Such 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 profit 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, namely the cases of unrestricted, positive and constant weights. We show tight or nearly tight bounds for the competitive ratio in each case.