# on_the_online_coalition_structure_generation_problem__e431d897.pdf Journal of Artificial Intelligence Research 72 (2021) 1215-1250 Submitted 05/2021; published 12/2021 On the Online Coalition Structure Generation Problem Michele Flammini michele.flammini@gssi.it GSSI, L Aquila, Italy Gianpiero Monaco gianpiero.monaco@univaq.it University of L Aquila, Italy Luca Moscardelli luca.moscardelli@unich.it University of Chieti-Pescara, Italy Mordechai Shalom cmshalom@gmail.com Isik University, Istanbul, Turkey Shmuel Zaks zaks@cs.technion.ac.il Technion, Haifa, Israel 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. 1. Introduction Coalition structure generation (CSG) is a major research challenge in AI, multi-agent systems, and networking communities. The CSG problem consists in partitioning a set of agents into coalitions, so as to maximize the resulting social welfare. Specifically, given a set of agents A = {1, 2, . . . , n} and a value function v : 2A R (that may map to negative values) assigning a value to each set of agents (coalition) S A, a coalition structure is a partition of A into disjoint exhaustive coalitions. The objective is to identify coalition structures that maximize the overall outcome of the system, that is the sum of all coalition values. This function that we want to maximize is known as the utilitarian social welfare. CSG models a variety of real world scenarios and not surprisingly is one of the major problems investigated in AI. For instance, consider a set of agents who can work in teams: some agents work well together, while others find it hard to do so. When two agents work 2021 AI Access Foundation. All rights reserved. Flammini, Monaco, Moscardelli, Shalom, & Zaks well together, a team which contains both of them can achieve better results due to their synergy. On the other hand, when the agents are not able to integrate in a satisfactory way, a team that contains them has a reduced utility due to their inability to cooperate, and may even perform better if they are removed. There are many other real world applications of CSG like electronic commerce, e-business, distributed vehicle routing, information gathering, multi-sensor networks, grid computing, autonomous sensors and virtual power plants (Rahwan, Michalak, Wooldridge, & Jennings, 2015; Voice, Polukarov, & Jennings, 2012). Several papers of the literature dealing with CSG (see the Related Work Section) consider the problem under a classical computational setting, where a centralized deterministic authority (i.e., an offline algorithm) decides how to partition the agents into coalitions, and where it is assumed that all the information on the input is known at the beginning. However, there exist scenarios (e.g., hiring employees and assigning them to existing teams, people entering social networks, etc.) in which it is more realistic to assume that agents arrive over time and the entire input is not available from the start. For this reason, in this work we study CSG in the classical online setting with agents introduced in an online fashion. Specifically, we assume that agents arrive one after the other and when an agent arrives, only the values of subsets of agents arrived until this moment are known. The authority (i.e., an online 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 and clearly depends on the cost function associated with the resulting coalitions. The objective is still partitioning agents into coalitions so as to maximize the resulting utilitarian social welfare. We evaluate the performance of online algorithms by using the competitive analysis, where an online algorithm is compared with an optimal offline algorithm that knows the entire request sequence in advance. We notice that every setting of CSG in which (i) agents arrive over time and (ii) an irrevocable choice has to be made upon their arrival, naturally fits our model. For instance, consider (a) social-network games, among the most played in the world (Shin & Shin, 2011), receiving players over time to be assigned to rooms and not allowed to change room before the end of the game; (b) a research institute aiming at assigning researchers (hired over time) to departments: the cost of moving a researcher already inserted in a department could be very high in terms of productivity and of organization and administrative issues; (c) similarly, a company with geographically spread agencies to which hired employees have to be assigned. This work may be considered as a fundamental step towards the study of these realistic CSG applications. Further steps, for instance considering some degree of uncertainty regarding the weight of edges, deserve future research in order to capture these scenarios in an increasingly realistic way. It is not difficult to see that if we consider general value functions there is no competitive algorithm A with bounded competitive ratio. In fact, consider the online input that is supplied to A by the following adversary. The adversary releases two agents 1 and 2, where v({1}) = 0, v({2}) = 0 and v({1, 2}) = 0. The online algorithm A can either put both agents in the same coalition or in two different coalitions. In the first case, the adversary release a third agent 3 such that v({3}) = 0, v({1, 3}) = 1, v({2, 3}) = 0 and v({1, 2, 3}) = 0. We have that the optimal offline solution that put agents 1 and 3 together and agent 2 alone has social welfare 1, while the social welfare of the solution returned by the online algorithm A is 0, regardless of the decision about agent 3. In the second case, the adversary release On the Online Coalition Structure Generation Problem a third agent 3 such that v({3}) = 0, v({1, 3}) = 0, v({2, 3}) = 0 and v({1, 2, 3}) = 1. We have that the optimal offline solution that put the three agents together in the same coalition has social welfare 1, while the social welfare of the solution returned by the online algorithm A is 0, regardless of the decision about agent 3. Despite the non-existence of competitive algorithms with bounded competitive ratio, considering general value functions has also the drawback that the problem is defined by the 2n distinct coalition values and the mere specification of the input would be intractable. In this work we focus on a natural and succinct representation of the problem, where the agents are vertices of an undirected weighted graph, and the value of a coalition depends on the weights of the edges between coalition members. It is arguably one of the most basic variant of coalition value functions to consider, however, this simple setting generates a rich set of problems to study. This graph model has been first studied by Deng and Papadimitriou (1994) and further considered by Aziz and de Keijzer (2011), Bachrach, Kohli, Kolmogorov, and Zadimoghaddam (2013), Bistaffa and Farinelli (2018), Voice et al. (2012). As noted by Voice et al. (2012), it well models various contexts of interest to computer scientists, where agents represent humans or resources (e.g., machines, computers, service providers or communication lines), which are typically structured and embedded in a social or computer network. When an agent (i.e., a node of the considered graph) arrives, only the weights of her incident edges toward previously arrived agents are known. After each step t, the current graph is partitioned into coalitions C(t) = {Ct 1, Ct 2, . . . , Ct c(t)}, such that every agent belongs to exactly one coalition Ct i, starting from the coalition structure C(t 1) determined in the previous step. In particular, when an agent appears, she can either join an existing coalition or form a new one consisting only of her. The utilitarian social welfare of the coalition structure C(t) is the sum of the values of all of its coalitions. We consider two different definitions of coalition value: (1) the sum of the weights of the edges between coalition members, and (2) the sum of the weights of the edges between coalition members divided by the number of agents in the coalition. We refer to these two value functions as total weight and fractional weight, respectively. The former is the most natural one can think of, while the latter captures social, economic, and political settings in which agents seek to maximize the average agreement with the members of their coalition. Both of them have been also widely considered in the literature (see the Related Work Section). 1.1 Our Contribution We consider the online variant of the CSG problem, where we assume that the input contains two numbers α, k > 0, that constitute upper bounds for the size of a coalition and for the number of coalitions, respectively. Furthermore, we consider different types of edge weights: unrestricted, positive and constant weights. We show tight or nearly tight bounds for the competitive ratio in each of the cases. Table 1 and Table 2 summarize our results for the total weight and fractional weight measures, respectively. Our main technical results are the Ω(log2 W) lower bound (Thm. 4.5) for the competitive ratio of Maximum Fractional Weight Coalition Structure Generation with positive weights, and the matching upper bound (Thm. 4.4), where W is the maximum absolute value of the edge weights. Flammini, Monaco, Moscardelli, Shalom, & Zaks Bounds Weights Lower Bound Upper Bound α = General W (n 2)( ) max {W (n 2), n 1} (Thm. 3.1) (Thm. 3.2) General 2W (α 1) 2W (α 1) (Thm. 3.6) (Thm. 3.7) Positive W 1 ϵ (α 1) W α (Thm. 3.8) (Thm. 3.9) k < General (Thm. 3.3) 1 ( ) (Thm. 3.4) Table 1: The competitive ratio of Maximum Weight Coalition Structure Generation. Lower bounds holding only for the strict competitive ratio are marked by ( ). Bounds Weights Lower Bound Upper Bound General 4W 4W (Thm. 4.1) (Aziz et al., 2015) Unweighted 4 4 (Thm. 4.3) (Aziz et al., 2015) Positive Ω(log2 W) O(log2 W) (Thm. 4.5) (Thm. 4.4) α < General Ω(W) 4W (Thm. 4.8) (Aziz et al., 2015) Unweighted 4(1 1/α) 4(1 1/α) (Thm. 4.6) (Thm. 4.7) General (Thm. 4.9) 1 ( ) (Thm. 4.10) Positive n 2 n 2 (Thm. 4.11) (Observation 1) Table 2: The competitive ratio of Maximum Fractional Weight Coalition Structure Generation. Lower bounds holding only for the strict competitive ratio are marked by ( ). A preliminary version of this work appeared in the proceedings of AAMAS 2018 (Flammini, Monaco, Moscardelli, Shalom, & Zaks, 2018). We would like to remark that, besides substantially improving the presentation and including all proofs that were omitted in the conference version, we have significantly strengthened the results by providing, in almost all cases, lower bounds holding not only for the strict competitive ratio, but also for the more challenging general non-strict notion of competitive ratio. On the Online Coalition Structure Generation Problem 1.2 Related Work There exist many offline algorithms designed for the CSG problem. One of the main approach is using dynamic programming algorithms (Rothkopf, Pekec, & Harstad, 1998). The most efficient one for the CSG problem with general coalition values has been designed by Rahwan and Jennings (2008) which returns an optimal solution in time O(3n). Another typical approach is using anytime algorithms, which can return a solution at anytime during the running time with the property that the quality of this solution improves monotonically as the computation time increases. Several authors have developed anytime algorithms for the CSG problem (Dang & Jennings, 2004; Rahwan, Michalak, Wooldridge, & Jennings, 2012; Rahwan, Ramchurn, Jennings, & Giovannucci, 2009; Sandholm, Larson, Andersson, Shehory, & Tohm e, 1999). The problem of partitioning a set of agents, where larger coalitions get higher value but only up to a certain fixed coalition size, has been considered by Dutta, Dasgupta, Baca, and Nelson (2013). In particular, they deal with the scenario, where initially agents can be in any arbitrary configuration (coalition structure), and consider the problem of obtaining a partition that maximizes the social welfare starting from the initial one by taking into account the cost of transforming from one coalition structure to another. All these algorithms that solve the CSG problem with general coalition values have a worst case time complexity exponential in n. Therefore several heuristics have been proposed. For instance, Shehory and Kraus (1998) propose a greedy algorithm which restricts the search space by imposing constraints on the size of the coalition. Another greedy algorithm (Mauro, Basile, Ferilli, & Esposito, 2010) is based on GRASP a general purpose greedy algorithm that, after each iteration, performs a quick local search to try and improve its solution. Sen and Dutta (2000) propose a genetic algorithm which uses a stochastic search process to identify the optimal coalition structure. Deng and Papadimitriou (1994) are the first to consider the graph model (also called weighted graph games) that we consider in our paper. Specifically, they consider the offline scenario of the CSG problem and provide complexity results for it. This graph model has been further considered by Bachrach et al. (2013) who show that finding the optimal coalition structure is hard even for planar graphs. Moreover, the authors provide constant factor approximation algorithms for minor-free graphs (that include the family of planar graphs) and bounded degree graphs. Voice et al. (2012) consider a different version of the graph model for the CSG problem, which is a well known graph restricted game considered by Myerson (1977). In particular, their input is an undirected graph and the coalition value for a subset of agents (i.e., a coalition) is any function which is independent of disconnected members, that is, two nodes have no effect on each other s marginal contribution to their vertices separator. They consider the problem of computing optimal coalition structures and provide complexity results for general and specific graphs. Aziz and de Keijzer (2011) show polynomial time algorithms for coalition structure generation in contexts of spanning tree games, edge path coalitional games and vertex path coalitional games, where the value of a coalition of nodes is either 1 or 0, depending on whether or not it contains a spanning tree, an edge path or a vertex path, respectively. To the best of our knowledge the online setting adopted in this work was not considered before. A related (but different) problem in the online setting was initiated by Augustine, Avin, Liaee, Pandurangan, and Rajaraman (2016). They study the problem of balanced Flammini, Monaco, Moscardelli, Shalom, & Zaks repartitioning: given an online sequence of pairs of agents to be interconnected, the objective is to dynamically partition the agents into coalitions of similar size, at a minimum cost. Coalition structures can be updated dynamically, by migrating agents between coalitions at a given cost per migration. Thus, the three main differences between that model and ours are that we do not require equal size coalitions, we consider different value functions, and coalitions in our model cannot be reconfigured. Moreover, Nguyen and Zick (2018) extend the class of weighted voting games to the more general one of resource based coalitional games and provide several results about the computation of optimal coalition structure, some of them also holding in the online setting. It is worth noticing that their work deeply differs from ours because every agent is assigned a weight and the value of a coalition is either zero or a fixed value that is obtained if and only if the sum of weights of the agents belonging to it is at least a given threshold. Interestingly, it holds that there are several correlations among this model and the family of big packing problem, and some (online) algorithms (e.g., the next-fit one) holding for the bin packing problem can be adapted to this setting. Furthermore, Buchbinder, Feldman, Filmus, and Garg (2020) study another online setting that is somewhat related to ours: it consists in assigning items (arriving in an online fashion) to bidders, where each bidder has a non-negative monotone submodular utility function, such that a partition of items among the bidders maximizing the total utility of the bidders is obtained. Our problem is also related to game theoretic works. Hedonic games, first formalized by Dr eze and Greenberg (1980), model the formation of coalitions (groups) of players when players have preferences over which group they belong to. In particular, each player has a subjective utility function over the coalitions they join (a preference order over them, often induced by some cardinal utility function). Work on hedonic games mainly studies the existence, computation and performance of stable solutions, i.e., solutions where no agent or group of agents has interest in deviating from the outcome. Nevertheless, it is also considered the problem of computing coalition structures that maximize the social welfare. Additively-separable hedonic games (ASHGs) constitute a natural and succinctly representable class of hedonic games. Like in our graph model, they can be represented by a weighted graph, where the set of agents coincides with the set of vertices and the utility of a coalition to a particular agent is simply the sum of the weights of the edges adjacent to the agent in the subgraph induced by the coalition. Properties guaranteeing the existence of stable allocations for ASHGs have been provided by Banerjee, Konishi, and S onmez (2001), Bogomolnaia and Jackson (2002), while computational complexity issues have been studied by Ballester (2004), Aziz, Brandt, and Seedig (2011), Olsen (2009). ASHGs where the utility of a coalition to a particular agent is the sum of the weights of the edges adjacent to the agent in the subgraph induced by the coalition plus the weight on the particular coalition has been studied by Bil o, Fanelli, Flammini, Monaco, and Moscardelli (2019). Fractional hedonic games (FHGs) (Aziz, Brandl, Brandt, Harrenstein, Olsen, & Peters, 2019) constitute another natural and succinctly representable class of hedonic games. They are similar to ASHGs, with the difference that the utility of an agent is divided by the number of agents of the coalition. Brandl, Brandt, and Strobel (2015) study the computational complexity of deciding whether a stable coalition structure exists in a given game. Carosi, Monaco, and Moscardelli (2019) study local-core stable coalition structure in FHGs and Bil o, Fanelli, Flammini, Monaco, and Moscardelli (2018) also consider the On the Online Coalition Structure Generation Problem problem of computing optimal coalition structures. Fanelli, Monaco, and Moscardelli (2021) consider relaxed core stability in FHGs. Aziz, Gaspers, Gudmundsson, Mestre, and Taubig (2015) consider the computational complexity of computing optimal coalition structures for FHGs under utilitarian and egalitarian social welfare. Some results have been improved by Flammini, Kodric, Monaco, and Zhang (2021), where also strategyproof mechanisms for ASHGs and FHGs have been proposed. We note that our value coalition functions are equivalent to the ones of the corresponding ASHGs and FHGs, being just scaled by a constant factor of 2. Monaco, Moscardelli, and Velaj (2019, 2020) consider modified fractional hedonic games (MFHGs), where, slightly differently than FHGs, the utility of an agent is divided by the size of the coalition she belongs minus 1. Elkind, Fanelli, and Flammini (2020) study Pareto Optimality in ASHGs, FHGs and MFHGs. In this work we deal with coalition formation, where the value of a coalition does not depend on agents who are not part of the coalition. However, there exist coalition formation settings with externalities (Rahwan et al., 2012). Moreover, we assume that each agent is member of exactly one coalition. However, there exist coalition formation settings in which coalitions do not constitute a partition of the agents, but may also overlap (Chalkiadakis, Elkind, Markakis, Polukarov, & Jennings, 2010; Zick, Markakis, & Elkind, 2014). 1.3 Paper Organization In Section 2 we present definitions and notation used throughout the paper, and also the problems statement. In Sections 3 and 4 we analyze the total weight measure and the fractional weight measure, respectively. Section 5 contains concluding remarks. 2. Preliminaries In this section, we first provide all the necessary definitions and notation. Then, we formally define our problem. 2.1 Definitions and Notation For an integer k > 0, we denote by [k] the set {1, . . . , k}. Through this work G is an undirected edge-weighted graph (V, E, w) on n vertices having no self-loops, with w : E R. Each vertex is associated with an agent. We denote by uv and wu,v, the edge {u, v} E and its weight w({u, v}), respectively. We assume that |wu,v| 1 for every uv E. We denote by W = maxuv E |wu,v| the maximum absolute value of the edge weights. We say that G is unweighted if wu,v = 1 for any uv E. We denote by G+ = (V, E+, w+) the subgraph of G consisting of its positive-weighted edges, that belong to E+ E. Given a set of edges F E, we denote by w(F) = P uv F wu,v, the total weight of edges in F. We denote by G[S], the subgraph of G induced by a subset S of its vertices, i.e., G[S] = (S, ES, w S), where ES = {uv E : u, v S} and w S is the restriction of w to ES. We denote by δS(v), the set of edges incident to v and S, i.e., δS(v) = {uv E : u S}, and by NS(v) (resp. NS[v]) the open (resp. closed) neighborhood of v in S. A clique (resp. independent set) of G is a set of pairwise adjacent (resp. non-adjacent) vertices of G. Flammini, Monaco, Moscardelli, Shalom, & Zaks A coalition structure C of G is a partition of V into coalitions C1, C2, . . . , Cc, for some positive integer c. We use the term coalition for both Ci and the weighted graph G[Ci]. Two coalitions Ci and Cj are adjacent if there exist vi Ci and vj Cj with vivj E. For a vertex v V , we denote by C(v) the unique coalition Ci C such that v Ci. For two positive integers α and k, we say that a coalition structure C is (α, k)-bounded if |C| k and |Ci| α, for every Ci C. We assume that α 2 and k 2. We denote by w(Ci) the total weight of the edges of G[Ci]. The fractional weight of a coalition Ci is w F (Ci) = w(Ci) |Ci| . Clearly, when Ci is an independent set, and in particular a single vertex, we have w F (Ci) = w(Ci) = 0. We refer to the unique agent of a singleton coalition of C as an isolated agent of C. When G is unweighted we have w F (Ci) = |Ci| 1 2 whenever Ci is a clique, and w F (Ci) = 1 1 |Ci| whenever G[Ci] is a tree. The weight of a coalition structure C is w(C) = P Ci C w(Ci), and its fractional weight is w F (C) = P Ci C w F (Ci). We name the coalition structure {V } as the Grand Coalition. 2.2 Problem Statement We consider the following two optimization problems under the online setting in which the vertices of G (i.e., the agents) appear one at a time (along with their incident edges) in the order v1, v2, . . . , vn and one has to decide on the coalition C(vi) of every vi upon her arrival. Max W-CSG (Maximum Weight Coalition Structure Generation) Input: A weighted graph G = (W, E, w). Two positive integers α and k. Output: An (α, k)-bounded coalition structure C. Measure to be maximized: w(C). Max FW-CSG (Maximum Fractional Weight Coalition Structure Generation) Input: A weighted graph G = (W, E, w). Two positive integers α and k. Output: An (α, k)-bounded coalition structure C. Measure to be maximized: w F (C). Let Π {Max W-CSG, Max FW-CSG} be a problem and I an instance of Π; given a solution S of an instance I, we denote by f(S) its measure. Moreover, we denote by OPTΠ(I) an arbitrary optimal solution of Π on input I. Given an algorithm A for Π, we denote by A(I) a solution returned by A on input I. A feasible solution S of an instance I is a ρ-approximation if f(S) f(OPTΠ(I)) ρ . An algorithm A is a ρ-approximation algorithm for Π if every solution A(I) is a ρ-approximation for every instance I of Π. As usual in the online setting (see Fiat & Woeginger, 1998), an instance of an online optimization problem Π is a sequence I = σ1, σ2, . . ., where, given the weighted graph G in input, for every i = 1, 2, . . ., σi = (vi, δ{v1,...,vi 1}(vi), wδ{v1,...,vi 1}(vi)), where wδ{v1,...,vi 1}(vi) is the restriction of w to edges in δ{v1,...,vi 1}(vi). It is worth remarking that, since the number of nodes and edges of G is not known in advance, from the point of view of the online algorithm the length of sequence I can be considered potentially infinite. An online algorithm has to produce partial output for every σi without the knowledge of the future entries, i.e. σi+1, σi+2, . . .. Furthermore, the output produced by the algorithm at step i On the Online Coalition Structure Generation Problem cannot be modified at later steps. An online algorithm A is r-competitive for Π if there exists some b 0 such that f(A(I)) f(OPTΠ(I)) r b for every instance I. If b = 0 then A is strictly r-competitive. The competitive ratio (resp. strict competitive ratio) of A is the smallest r such that A is r-competitive (resp. strictly r-competitive) (Borodin & El-Yaniv, 1998). Notice that an upper bound holding for the strict competitive ratio is an upper bound for the competitive ratio with b = 0; conversely, a lower bound is stronger when holds for any b 0. When no ambiguity arises we omit the subscript Π, the instance I and the objective function f. In such cases OPT stands for OPTΠ(I) and also for f(OPTΠ(I)). Similarly, A may stand for either A(I) or for f(A(I)) besides being the name of an algorithm. 3. Maximum Weight Coalition Structure Generation In this section we deal with the Max W-CSG problem. 3.1 Unbounded Coalition Size Note that when the size of a coalition is unbounded the case of non-negative weights is trivial, since Grand Coalition is optimal in this case. Therefore, in this section we consider only instances containing both positive and negative edges. In Section 3.1.1 we consider the case where the number of coalitions is unbounded, and in Section 3.1.2 we consider the case of bounded number of coalitions. 3.1.1 Unbounded Number of Coalitions Theorem 3.1 Given any ϵ > 0, there exists no deterministic online algorithm for Max W-CSG having strict competitive ratio W(n 2) ϵ. Proof: Let us assume, by the way of contradiction, that A is a strictly r-competitive deterministic online algorithm for Max W-CSG with r = W(n 2) ϵ. Consider the online input that is supplied to A by the following adversary. The adversary releases two adjacent agents v1 and v2. If A does not put both agents in the same coalition the adversary stops. In this case OPT = 1 and A = 0, thus the strict competitive ratio of A is unbounded. Therefore, A has to put v1 and v2 in the same coalition, say C1. At this point the weight of the solution is 1. The adversary releases x additional agents each of which is adjacent only to v1 and v2 with edges of weight W and W, respectively. The weight of the coalition structure of A remains 1, since every agent will add zero to f(A) regardless whether the agent joins coalition C1, joins any other coalition or forms a new coalition. Consider the coalition structure C = {{v2}, V \ {v2}}. We have OPT w(C) = x W. Therefore, the strict competitive ratio of A is at least A x W = W(n 2), a contradiction. Notice that Theorem 3.1 also implies a lower bound of Ω(Wn) to the (non-strict) competitive ratio of Max W-CSG. In fact, assuming by contradiction that there exists an Flammini, Monaco, Moscardelli, Shalom, & Zaks algorithm A with (non-strict) competitive ratio r = o(Wn), we would have that, for a given constant b 0, OPT r(A + b) = o(Wn)A for every possible input instance. In other words, A OPT o(Wn), that is A is strictly o(Wn)-competitive: a contradiction to Theorem 3.1. We now consider the following greedy algorithm. Upon presentation of an agent vi, algorithm Greedy adds her to the coalition Cj that brings the maximum increase in the weight of the current coalition structure, if this increase is at least 1. If no coalition brings an increase of at least 1 in the weight, Greedy creates a new coalition {vi} (see Algorithm 1). Algorithm 1 Greedy Initialization: When agent vi arrives: 3: for all Cj C do 4: if δCj(vi) > gain then 5: gain δCj(vi) 7: if gain 1 then 8: Add vi to the coalition C j 9: else 10: Create a new coalition {vi} and add it to C. Theorem 3.2 The strict competitive ratio of Greedy is (exactly) max {W(n 2), n 1}. Proof: A newly created coalition contains one agent and its weight is zero. Whenever an agent vi is added to an existing coalition Cj, since the weight of the coalition increases, there is at least one positive-weighted edge in δCj(vi). Moreover, the size of the coalition increases by 1, and, by the definition of the algorithm, its weight increases by at least 1. Therefore, every coalition C returned by Greedy is connected in G+ and its weight is at least |C| 1. Denoting by ci the number of coalitions of Greedy having i agents, we have i=1 (i 1)ci = i=1 ci = n c, where c is the number of coalitions of Greedy. Whenever c = n we have Greedy = OPT = 0. Therefore, in the rest of the proof we assume c [n 1]. Consider two coalitions C and C and assume without loss of generality that the first agent v of C arrived before the first agent v of C . Since v has formed her coalition rather than joining C, we conclude that the sum of the weights of δC(v ) is less than 1, thus either δC(v ) is empty or it contains at least one edge that is not in E+. We conclude that there is at least a couple of nodes u C and v C such that {u, v} E+, and, by the generality of C and C , the same holds for any pair of coalitions returned by Greedy. Therefore, On the Online Coalition Structure Generation Problem Figure 1: Bounds on the total weight of edges in C1 C2. (i) u arrives before x. (ii) u arrives between x and y. (iii) u arrives after y. |E+| n 2 c 2 . We proceed as follows OPT Greedy W |E+| Greedy W n(n 1) c(c 1) W n(n 1) (n 1)(n 2) 2 = W(n 1), where the inequality in the last line is due to the fact that the quotient is a non-decreasing function on c, thus it attains maximum at c = n 1. For the same reason, whenever c n 3 we have OPT Greedy W n(n 1) (n 3)(n 4) 6 = W(n 2). We now consider the cases of c = n 1 and c = n 2. c = n 2: In this case the non-singleton coalitions of C consist of either two coalitions of two agents, or one coalition of three agents. We analyze these cases separately. c1 = n 4, c2 = 2: Let the two non-singleton coalitions be C1 = {x, y}, C2 = {u, v}, let a = wx,y, b = wu,v, and assume without loss of generality that v is the last agent among these four agents, and that y arrives after x. Consider now the three different possibilities that may arise (see Figure 1). (i) If u arrives before x or (ii) u arrives between x and y, by the definition of Greedy, if edge xu E, wx,u is not positive, if edge yu exists in E, wy,u a W and, whenever edges vx and/or vy exist, wv,x + wv,y b W. (iii) If u arrives after y, by the definition of Greedy, if edges xu and/or yu exist in E, wx,u + wy,u a W and, whenever edges vx and/or vy exist in E, wv,x + wv,y b W. Therefore, the total weight of positive edges in C1 C2 is at most 2W. Notice that, by the definition of Greedy, for any singleton coalition {z}, one of the edges zx and zy (and also one of zu and zv) is non-positive (or does not exist in E): there is at most a positive edge between z and C1 and another positive edge between z and C2. Moreover, again by the definition of the algorithm, no positive edge can exist in E between nodes belonging to two singleton coalitions. Therefore, OPT 2W(n 4) + 2W + a + b 2W(n 2) and Greedy 2, thus OPT/Greedy W(n 2). Flammini, Monaco, Moscardelli, Shalom, & Zaks Figure 2: Bounds on the total weight of edges between C = {x, y, z} and u. (i) u arrives before x. (ii) u arrives between x and y. (iii) u arrives between y and z. (iv) u arrives after z. c1 = n 3, c2 = 0, c3 = 1: Let the only non-singleton coalition be C = {x, y, z}, where the agents appear in this order in the input, and let a = wx,y and b = wy,z = Greedy a. For a singleton coalition {u} we consider the possible orders of arrival of u, relative to x, y, z, as depicted in Figure 2. * (i) and (ii), u arrives before y: In this case, by the definition of Greedy, if edge xu E, wx,u is not positive, wu,y a and wu,z b = Greedy a, thus implying that the total weight of positive edges in δC(u) is at most Greedy W + Greedy a. * (iii), u arrives between y and z: In this case, whenever edges ux and/or uy exist, wu,x + wu,y < 1, and, if edge uz E, wu,z b = Greedy a, implying that only one edge, between ux and uy, can have a positive weight, and therefore the total weight of positive edges in δC(u) is at most W + Greedy a. * (iv), u arrives after z: In this case, whenever edges ux and/or uy and/or uz exist, wu,x+wu,y+wu,z < 1. We get that the total weight of positive edges in δC(u) is at most W +1 since, if one of the three edges is positive, then the sum is at most W, while if two of them are positive, then, since the negative one has value at least W, their sum is at most W +1. Finally, we have that the total weight of positive edges in δC(u) is at most W +1 W +Greedy a, because Greedy a + 1. We conclude that OPT (n 3)(W + Greedy a) + Greedy (n 3)(W + Greedy 1) + Greedy = (n 2)Greedy + (W + 1)(n 3) OPT Greedy n 2 + (W 1)(n 3) n 2 + (W 1)(n 3) c = n 1: In this case the C consists of a coalition C = {x, y} and n 2 singleton coalitions. Assume without loss of generality that x appears before y in the input. On the Online Coalition Structure Generation Problem Figure 3: Bounds on the total weight of edges between C = {x, y} and u. (i) u arrives before x. (ii) u arrives between x and y. (iii) u arrives after y. Figure 4: Lower bound to the competitive ratio of alg. (i) Execution of Greedy. (ii) The grand coalition. Since y joined x, we have wx,y 1. Let a = wx,y, and let {u} be a singleton coalition of C. We now bound the total weight w of the edges ux and uy that fall within the same coalition of a solution. We consider the possible orders of arrival of u, relative to x and y, as depicted in Figure 3. (i) and (ii), u arrives before y: By the definition of Greedy, we have that, if edge ux E, wu,x 0 and, if edge uy E, wu,y a: In this case, it holds that w a. (iii), u arrives after y: By the definition of Greedy, we have that wu,x+wu,y 1. Therefore, w 1 a if x and y are in the same coalition, and w W if x and y are in different coalitions. Therefore, if x and y are in the same coalition of OPT we have OPT a+(n 2)a = (n 1)a, i.e. OPT Greedy n 1. Otherwise, i.e. if x and y are in different coalitions of OPT, we have OPT (n 2)W and Greedy = a 1. We proceed to show that this bound is tight. Since the competitive ratio of any deterministic online algorithm is at least W(n 2), we need to show that the competitive ratio of Greedy is at least n 1. This is easily proven using an adversary that first presents an independent set of n 1 agents followed by an agent connected to every other agent by an edge of unit weight. Greedy puts the first n 1 agents in n 1 different coalitions and the Flammini, Monaco, Moscardelli, Shalom, & Zaks last agent in one of these coalitions (see Figure 4.i), i.e., Greedy = 1. On the other hand Grand Coalition is a solution with weight n 1, thus OPT n 1 (see Figure 4.ii). 3.1.2 Bounded Number of Coalitions In this section we present impossibility results for the case where the number of coalitions is bounded by some k 2, the case of k = 1 being trivial. In the following two theorems, the adversary releases an independent set of at most k+1 agents until two agents vi, vj are put together, and then an agent only adjacent to vi and vj. Theorem 3.3 There exists no competitive deterministic algorithm for Max W-CSG for any k 2. Proof: Let us assume, by the way of contradiction, that A is a r-competitive algorithm for Max W-CSG with an additive term b, i.e. A OPT r b for some b 0, with r being either constant or a function of n. The adversary releases an independent set of at most k + 1 agents until A puts two agents vi, vj in the same coalition. Then it releases an agent adjacent to only vi and vj with edges of weights bc + 1 and (bc + 1) respectively. Then, regardless of the decisions of A, we have A = 0. On the other hand, one can form a coalition consisting of vi together with the last agent, and form a second coalition from the remaining agents which constitute an independent set. Thus, OPT > bc implying A = 0 < OPT r b, a contradiction. In the following theorem, it is shown that the strict competitive ratio remains unbounded even when W = 1. Theorem 3.4 There exists no strictly competitive deterministic algorithm for Max W-CSG for any k 2, even when W = 1. Proof: Let us assume, by the way of contradiction, that A is a r-competitive algorithm for Max W-CSG, i.e. A OPT r , with r being either constant or a function of n. The adversary releases an independent set of at most k + 1 agents until A puts two agents vi, vj in the same coalition. Then it releases an agent adjacent to only vi and vj with edges of weights 1 and 1 respectively. Then, regardless of the decisions of A, we have A = 0. On the other hand, one can form a coalition consisting of vi together with the last agent, and form a second coalition from the remaining agents which constitute an independent set. Thus, OPT = 1 implying A = 0 < OPT r , a contradiction. The next result is obtained by exploiting a polynomial reduction from the k-colorability problem, in which given an unweighted and undirected graph G and k colors, the answer is yes if and only if it is possible to find a mapping of all vertices of G to colors {1, . . . , k} such that for any edge of G the colors associated with its endpoints are different. On the Online Coalition Structure Generation Problem Theorem 3.5 The offline variant of the problem Max W-CSG is inapproximable for any k 3, unless P = NP. Proof: Given an instance G of k-colorability, we construct the following edge-weighted graph G. G is complete graph on the same vertex set as G . The weight of an edge e of G is 1 if e is a non-edge of G and |E(G )| otherwise. If k = n the instance is clearly a YES instance. Therefore, we assume k < n. To conclude the proof we show that G is k-colorable if and only if OPT > 0. Suppose that G is k-colorable. Then its vertex set can be partitioned into k k independent sets that induces a coalition structure C with k coalitions. The weight of an independent set I of G is w(I) = |I| 2 |I| 1 2 . Therefore, OPT w(C) n k 2 > 0. Conversely, suppose that OPT > 0. Then, there is a coalition structure C of G with w(C) > 0 and |C| k. We claim that every coalition of C is an independent set of G . Suppose that C contains a coalition C that is not an independent set. Then G[C] contains an edge of weight |E(G )|. Since w(E+) = |E(G )| we conclude that w(C) 0. 3.2 Bounded Coalition Size Recall that we assume α 2. When both the size of a coalition and the number of coalitions is bounded, the size of the instance becomes bounded in which case every algorithm is 1-competitive. Therefore, in this section we assume that the number of coalitions is unbounded. Since in this case Grand Coalition is not necessarily a feasible solution, the case of positive weights is not trivial. We analyze the cases of general weights and positive weights in two different sections. In this section we consider Greedyα, i.e., the variant of Greedy that does not consider coalitions of size α as possible coalitions for the arriving agent (see Algorithm 2). Algorithm 2 Greedyα Initialization: When agent vi arrives: 3: for all Cj C such that |Cj| < α do 4: if δCj(vi) > gain then 5: gain δCj(vi) 7: if gain 1 then 8: Add vi to the coalition C j 9: else 10: Create a new coalition {vi} and add it to C. Flammini, Monaco, Moscardelli, Shalom, & Zaks 3.2.1 General Weights We show that Greedyα is an optimal deterministic online algorithm for Max W-CSG. We start with the lower bound. Theorem 3.6 Given any ϵ > 0, there exists no deterministic online algorithm for Max W-CSG having competitive ratio 2W(α 1) ϵ. Proof: Let us assume, by the way of contradiction, that A is a r-competitive deterministic online algorithm for Max W-CSG with r = 2W(α 1) ϵ and an additive term b 0. The adversary issues the agents in various phases, starting from phase 0. We show by induction on the phase i that the cost Ai of the algorithm at the beginning of phase i is Ai = i. Clearly, the base of the induction holds for i = 0. In phase i, let pi be an integer greater than 4W(b+i) α . The adversary issues ℓi piα agents vi 1, . . . , vi ℓi with wvi j,vi k = 1 for every j, k [ℓi] until A puts two agents in the same coalition. This must happen, because otherwise we have r b > OPT 2W(α 1) b pi α 2 2W(α 1) b > 2W(α 1) b = i = Ai, where the optimal solution is obtained by grouping the piα agents into coalitions of size α. Let vi k, vi ℓi (k < ℓi) the two agents that are in the same coalition of the solution computed by A. The adversary issues 2(α 1) agents in V i = {vi ℓi+1, , vi ℓi+2(α 1)}, each being adjacent to both vi k and vi ℓi. For every new agent vi j (j = ℓi + 1, . . . , ℓi + 2(α 1)) the weight wvi j,vi k is W if j is even and W otherwise. As for the other edge, we have wvi j,vi ℓi = wvi j,vi k. At this point, phase i ends. Given that, by the induction hypothesis, Ai = i, we obtain that Ai+1 = Ai + 1 = i + 1, regardless of the decision of algorithm A. Consider now coalition structure C with the following coalitions: for each phase i = 0, 1, . . . , T 1 performed by the adversary, there is a coalition consisting of vi k and the α 1 agents in V i with even index, and another one consisting of vi ℓand α 1 agents in V i with odd index. Since C is a feasible solution with w(C) 2WT(α 1), It directly follows that OPT 2WT(α 1) = T(r + ϵ). By choosing T > br ϵ , it holds that T(r+ϵ) r > T + b. We therefore obtain r b T(r + ϵ) r b > T + b b = AT = A, a contradiction. We proceed with the analysis of Greedyα. We denote by ci the number of coalitions with exactly i agents in a given coalition structure returned by Greedyα. The following is a technical lemma. Lemma 3.1 The following propositions hold: On the Online Coalition Structure Generation Problem 1. The set of isolated agents of Greedyα is an independent set of G+. 2. If all the weights are positive, G+ contains an independent set that intersects every component of Greedyα with less than α agents. 3. Greedyα Pα i=1(i 1)ci. 1. Suppose that Greedyα contains two isolated agents {vi} and {vj} with wvi,vj > 0, and without loss of generality i < j. Then, when vj appears to Greedyα she would be added to {vi} contradicting the fact that vj is an isolated agent of Greedyα. 2. Consider the set I consisting of the first agent of every coalition of Greedyα with less than α agents. Clearly, I intersects every coalition of size less than α. It remains to show that I is an independent set of G+. Suppose, for a contradiction, that there are two agents vi, vj I with i < j and wvi,vj > 0. When vj appears to Greedyα the option of adding vj to the coalition of vi brings an increase of at least wvi,vj > 0 since all the edges have positive weights. This contradicts the fact that vj is the first agent of her coalition. 3. Whenever an agent is added to an existing coalition she increases the weight of the coalition structure by at least 1. Theorem 3.7 Greedyα is a strictly (2W(α 1))-competitive deterministic online algorithm for Max W-CSG. Proof: Let I be the set of isolated agents of Greedyα. Notice that n |I| = Pα i=2 ici. Combining with Lemma 3.1 (3.) we have 2 Greedyα n |I|. By Lemma 3.1, I constitute an independent set of G+. Therefore, every edge of G+ is incident to at least one of the n |I| other agents. Every such agent has degree at most α 1 in every solution. Therefore, OPT W(n |I|)(α 1). Then, the strict competitive ratio of Greedyα is at most: W(n |I|)(α 1) Greedyα 2W(α 1). 3.2.2 Positive Weights We observe that the proof of Theorem 3.6 is not valid in this case, since the adversary uses negative edges. In this section we show that the lower bound of Theorem 3.6 does not hold in this case, and that Greedyα is almost optimal. Theorem 3.8 Given any ϵ > 0, there exists no deterministic online algorithm for Max W-CSG having competitive ratio W 1 ϵ(α 1), even when all edge weights are positive. Flammini, Monaco, Moscardelli, Shalom, & Zaks Proof: Let us assume, by the way of contradiction, that A is a W 1 ϵ(α 1 )-competitive deterministic online algorithm with an additive term b 0 for Max W-CSG. Consider the online input that is supplied to A by the following adversary. The adversary chooses α > b and releases a sufficiently large independent set of agents until A forms either a coalition of size α, or α 1 coalitions. A forms a coalition C1 of α agents. In this case, the adversary releases a set U of α(α 1) agents such that U C1 is a complete biparite graph with edges of weight W. We have A = 0, because A cannot add any agent uj to C1. On the other hand, there is a solution with α coalitions each of which consists of one agent C1 and α 1 agents of U. Therefore, OPT Wα(α 1). Then OPT W(α 1) b α b > 0 = A, a contradiction. A forms α 1 coalitions C1, . . . , Cα 1. Let vi be an arbitrary agent of Ci, for every i [α 1]. The adversary releases additional agents u1, u2, . . . until A creates a new coalition (which must happen at some step ℓ α(α 1) + 1). Every agent uj is adjacent to agents v1, . . . , vα 1 with all her incident edges having the same weight wj = b + 1 + Pj 1 k=1 wk 1/ϵ . At each step j < ℓ, A can increase the total weight of the coalition structure, by adding at most one edge of weight wj. Therefore, A Pℓ 1 k=1 wk. On the other hand, there is a solution that puts uℓand her adjacent agents in one coalition, implying OPT wℓ(α 1) and W = wℓ. We conlude OPT W 1 ϵ(α 1) b W(α 1) W 1 ϵ(α 1) b = W ϵ b = 1 + k=1 wk > A, a contradiction. The proof of the following theorem exploits Lemma 3.1, and it is slightly more involved than the proof of Theorem 3.7. Theorem 3.9 The strict competitive ratio of Greedyα is αW when all the weights are positive. Proof: By Lemma 3.1, G+ contains an independent set I of size Pα 1 i=1 ci. Since n = Pα i=1 ici, we have that n |I| = Pα 1 i=1 (i 1)ci + αcα. Every edge of G+ is incident to at least one of the remaining n |I| agents of Greedyα. Every such agent has degree at most α 1 in every solution. Therefore, OPT W(α 1)(n |I|) i=1 (i 1)ci + αcα W(α 1)(Greedyα + cα). On the Online Coalition Structure Generation Problem Since Greedyα (α 1)cα, we obtain OPT W(α 1) Greedyα + Greedyα αW Greedyα. We now show an example showing that the competitive ratio of Greedyα is at least αW. Let G be the following graph on α2 vertices. v1, v2, , vα is a path each edge of which has weight 1. Greedyα will put all these agents in one coalition C1 with w(C1) = α 1. The rest of the input is an independent set I. Since C1 has already α agents, every other agent will be isolated in Greedyα. Therefore, we have Greedyα = α 1. The vertices of I are grouped into α groups of α 1 vertices and every vertex v of group i is adjacent to vi with an edge of weight W. A possible solution consists of α stars each of which is centered at one of the vertices v1, . . . , vα and has α 1 leaves from I. Therefore, OPT Wα(α 1) = Wα Greedyα. 4. Maximum Fractional Weight Coalition Structure Generation In this section our objective is to maximize the fractional weight of the coalition structure. We note that, as opposed to problem Max W-CSG, for non-negative weights, Grand Coalition is not necessarily an optimal solution even when coalition size is unbounded. We start with a general lower bound and then analyze the cases of unbounded and bounded coalition sizes separately. Theorem 4.1 Given any ϵ > 0, there exists no deterministic online algorithm for Max FW-CSG having competitive ratio 4W ϵ. Proof: The proof exploits arguments similar to the ones used in the proof of Theorem 3.6. Let us assume, by the way of contradiction, that A is a r-competitive deterministic online algorithm for Max FW-CSG with r = 4W ϵ and an additive term b 0. The adversary issues the agents in various phases, starting from phase 0. We show by induction on the phase i that the cost Ai of the algorithm at the beginning of phase i is Ai i 2. Clearly, the base of the induction holds for i = 0. In phase i = 0, 1, . . ., let ni be an integer such that ni 1 2. The adversary issues ℓi ni agents vi 1, . . . , vi ℓwith wvi j,vi k = 1 for every j, k [ℓi] until A puts two agents in the same coalition. This must happen, because otherwise we have r b (ni 1)/2 where the optimal solution is obtained by grouping all the ℓagents together into a unique coalition. Let vi k, vi ℓi (k < ℓi) the two agents that are in the same coalition in the solution computed by A. The adversary issues 2T agents in V i = {vi ℓi+1, , vi ℓi+2T }, each being adjacent to Flammini, Monaco, Moscardelli, Shalom, & Zaks both vi k and vi ℓ. For every new agent vi j (j = ℓ+ 1, . . . , ℓ+ 2T) the weight wvi j,vi k is W if j is even and W otherwise. As for the other edge, we have wvi j,vi ℓ= wvi j,vi k. Given that, by the induction hypothesis, Ai i 2, we obtain that Ai+1 Ai + 1 2 , regardless of the decision of algorithm A. In fact, notice that the contribution of edge vi kvi ℓi to A is less or equal to 1/2, with the equality holding whenever vi k and vi ℓi are the only vertices belonging to their coalition in the solution computed by A. Consider now coalition structure C with the following coalitions: for each phase i = 0, 1, . . . , T 1 performed by the adversary, there is a coalition consisting of vi k and the T agents in V i with even index, and another one consisting of vi ℓand the T agents in V i with odd index. Notice that each of these coalitions has a fractional weight equal to W T T+1. Since C is a feasible solution, it follows that OPT w(C) 2W T 2 By choosing T > r(1+4b) ϵ , it holds (by multiplying both sides by Tϵ) that T 2ϵ > r T(1 + 4b). Moreover, as T 1 implies that r T(1 + 4b) r T(1 + 2b) + 2br, it holds that T 2ϵ > r T(1 + 2b) + 2br. This last inequality finally implies that r+ϵ 2r T 2 T+1 > T 2 + b. We therefore obtain OPT T + 1 b > T 2 + b b AT = A, a contradiction. 4.1 Unbounded Coalition Size In this section we analyze the Max FW-CSG problem when the coalition size is unbounded. 4.1.1 General Weights For the case of general weights, the following result is known. Theorem 4.2 [Theorem 5 in: (Aziz et al., 2015)] Any maximal matching is a 4Wapproximation. A maximal matching is a coalition structure in which every coalition is connected and consists of at most two agents. Moreover, for any pair of non-matched agents, they are not connected by a positive weight edge. A maximal matching can be computed online by the following algorithm that we name as Maximal Matching (see Algorithm 3). Whenever an agent vi appears, she is added to an existing coalition of size 1 that is adjacent to vi by means of a positive weight edge. If no such coalition exists, a new coalition {vi} is created. We note that Maximal Matching is an optimal algorithm for this case because Theorem 4.1 implies a matching lower bound of 4W. We observe that the adversary in the proof of Theorem 4.1 uses edges with negative weights. Therefore, it makes sense to consider the case of graphs having edges with only positive weights. We start with the analysis of unweighted graphs and then proceed with the case of general positive weights. On the Online Coalition Structure Generation Problem Algorithm 3 Maximal Matching Initialization: When agent vi arrives: 2: for all Cj C such that |Cj| = 1 do 3: if δCj(vi) 1 then 4: Add vi to the coalition Cj 5: return 6: Create a new coalition {vi} and add it to C. 4.1.2 Unweighted Graphs Since Maximal Matching is 4W competitive in general, it is 4-competitive for unweighted graphs. It is possible to show that this is the best possible for deterministic algorithms in this case. Theorem 4.3 Given any ϵ > 0, there exists no deterministic online algorithm for Max FW-CSG having competitive ratio 4 ϵ, even for unweighted graphs. Proof: Let us assume, by the way of contradiction, that A is a (4 ϵ)-competitive deterministic online algorithm with an additive term b > 0. First of all, we show that, for every non-negative integer k, there is an adversary that causes the output of A to be a matching of k edges, i.e. k coalitions of two agents and n 2k singleton coalitions. In fact, there exists an adversary that causes A to add a coalition of two agents given that the current output is a matching of ℓedges, thus causing the output to be a matching of ℓ+ 1 edges: The adversary issues a clique of at most 3ℓ+ 8b + 2 vertices (none of which is adjacent to the rest of the input) until A puts two of them in one coalition. We have to show that this must happen. Assume, by contradiction, that A does not put any of the agents of the clique in one coalition. On the one hand, the output of A is a matching with ℓedges, thus A = ℓ/2. On the other hand, a possible coalition structure consists of a matching with ℓedges and a clique of 3ℓ+ 8b + 2 agents. Therefore, OPT ℓ/2+(3ℓ+8b+1)/2 = 2ℓ+4b+1/2 > 2ℓ+4b. Then, OPT 2 +b = A+b, a contradiction. We conclude that A must add an edge to its output to augment it to a matching of ℓ+ 1 agents. The adversary chooses x = 8/ϵ , and an integer k 1 to be determined later. In the first stage, the adversary causes the output of A to be a matching with k edges. Let C1, . . . , Ck be the coalitions of A consisting of two edges. These coalitions will possibly grow in the second stage. At any given point during the execution of A we denote by Fi the first four agents of Ci, or Fi = Ci if |Ci| < 4. Notice that sets Fi can grow during the second stage. We define F def = k i=1Fi. At the beginning of the second stage we have |F| = 2k, and by definition, |F| 4k. The adversary issues a new agent adjacent only to some agent u of F where u is chosen from F in a round robin manner. The adversary stops when every agents of F has x neighbours outside of F. Since |F| is bounded, F will not grow after a certain point. After at most 4kx steps every agent of F will have x neighbours not in F and the adversary will stop. Flammini, Monaco, Moscardelli, Shalom, & Zaks Let k2, k3, k4 be the number of coalitions with 2, 3 and at least 4 agents, respectively. Clearly, k2 + k3 + k4 = k. We have A 1 3k3 + k4, since the solution consists of k2 matchings, k3 trees with 3 vertices and k4 trees (of at least 4 vertices). On the other hand, there is a solution that consists of |F| stars, each of which contains at least x + 1 vertices. Therefore, OPT (2k2 + 3k3 + 4k4) 1 1 x+1 (2k2 + 3k3 + 4k4) 1 ϵ 8 . Note that 1 ϵ/8 4, and let δ be such that 1 ϵ/8 4 ϵ = 1 4 δ. We conclude 4 ϵ A (2k2 + 3k3 + 4k4) 1 ϵ = 2k2 + 3k3 + 4k4 δ 2(4 δ)(k2 + k3 + k4) = δ 2(4 δ)k, where the last inequality holds because, since δ [0, 4), we obtain that i) 2 4 δ 1 2 = δ 2(4 δ), ii) 3 4 δ 2 3 > δ 2(4 δ), and iii) 4 4 δ 1 δ 2(4 δ). Therefore, the adversary chooses k such that δ 2(4 δ)k > b, a contradiction arises and the claim follows. 4.1.3 Positive Weights In the previous sections we have shown that Maximal Matching is an optimal algorithm for the general case and also for the unweighted case. In this section we show that quite surprisingly this is not the case for positive weights. We present an O(log2 W)-competitive algorithm and also a matching lower bound of Ω(log2 W). Our algorithm partitions the edges into classes according to their weights. We denote the class of an edge e by class(e) and it is equal to the smallest integer i such that w(e) < 2i. We note that class(e) > 0. The class of a coalition Ci is denoted by class(Ci) and is equal to the class of its heaviest edge. If a coalition contains no edge, its class is 0. Upon presentation of an agent vi, Algorithm Classify considers the edges incident to vi in non-increasing order with respect to their weights and adds vi to a coalition whose class is lower than the one of the edge under consideration. If this is not possible, it creates a new coalition (see Algorithm 4). Theorem 4.4 Classify is strictly (O(min {n, 1 + log W})2)-competitive. Proof: Consider an optimal coalition structure OPT, and a coalition structure C = {C1, C2, . . . , Cc} returned by Classify. Denote by OPTEXT (resp. OPTINT ) the set of edges whose endpoints fall within a same coalition of OPT, i.e., contribute to w F (OPT), but within different coalitions (resp. a same coalition) of C. We denote by OPTEXT and OPTINT also the contribution of these edges to w F (OPT). Clearly, OPT = OPTEXT + OPTINT . In the sequel we upper bound each of these values. On the Online Coalition Structure Generation Problem Algorithm 4 Classify Initialization: When agent vi arrives: 2: for all edges e = vivj in descending order of w(e) do 3: if class(e) > class(C(vj)) then 4: Add vi to the coalition C(vj) 6: Create a new coalition {vi} and add it to C. Figure 5: Given any edge vv OPTEXT , there exists a coalition C(vv ) {C(v), C(v )} such that class(C(vv )) class(vv ). (i) v is the first agent of C. (ii) Edge uv caused Classify to add v to C. Upper bounding OP TEXT : We exploit the following property: For every edge vv OPTEXT there exists a coalition C(vv ) {C(v), C(v )} such that class(C(vv )) class(vv ). In fact, let vv OPTEXT , C = C(v) and C = C(v ) (see Figure 5). Assume without loss of generality that v appears before v in the input. If v is the first agent of C (Figure 5.i), since v is not added to C by Classify we conclude that class(C ) class(vv ) and we are done. Otherwise (Figure 5.ii), v is not the first agent of C thus there exists an edge e incident to v that caused Classify to add v to C. If w(e) wv,v we have class(C) class(e) class(vv ) and we are done. Otherwise, wv,v > w(e) thus vv was considered before e by Classify and v was not added to C . Therefore, class(C ) class(vv ) and also in this case the property holds. Consider a coalition Cj C, and let OPTEXT,Cj be the set of edges e OPTEXT such that C(e) = Cj. Since Cj contains an edge of weight at least 2class(Cj) 1, the contribution of the edges in Cj to Classify is w F (Cj) 2class(Cj) 1 Consider now an agent v Cj, the set OPTEXT,v of edges of OPTEXT,Cj incident to v, and let a = |OPTEXT,v|. Let also h be the class of the heaviest edge of OPTEXT,v. Notice that the edges of OPTEXT,v are in the same coalition of OPT, that contains at least Flammini, Monaco, Moscardelli, Shalom, & Zaks a + 1 agents. Therefore, the contribution of the edges in OPTEXT,v to OPT is less than a2h a+1 < 2h 2class(Cj). Summing up for all agents v Cj, we get OPTEXT,Cj < |Cj| 2class(Cj) 2 |Cj|2 w F (Cj), where the last inequality holds by (1). Finally, we sum up over all coalitions Cj, thus obtain j=1 OPTEXT,Cj < 2 |Cj|2 w F (Cj) 2 max j [c] |Cj| 2 Classify. (2) Upper bounding OP TINT : Let OPTINT,Cj be the contribution to OPT of the edges of OPTINT that fall within some coalition Cj. OPTINT,Cj is at most half of the sum of weights of all edges of Cj, because every edge has to be in a coalition of at least two agents. Therefore, it holds that OPTINT,Cj X e OPTINT,Cj 2 w F (Cj). By summing up over all coalitions we get j=1 OPTINT,Cj maxj [c] |Cj| 2 Classify. (3) Upper bounding OP T : By the way agents are added to Cj by Classify, it holds that |Cj| class(Cj). Therefore, max j [c] |Cj| max j [c] class(Cj) = log W 1 + log W. (4) Since 1 maxj [c] |Cj| n, by exploiting (2), (3) and (4), we conclude that OPT = OPTEXT + OPTINT 2 max j [c] |Cj| 2 + maxj [c] |Cj| max j [c] |Cj| 2 Classify 5 2 (min {n, 1 + log W})2 Classify, thus proving the claim. On the Online Coalition Structure Generation Problem Theorem 4.5 provides a matching lower bound. In order to prove it, we need the following technical lemma. Lemma 4.1 Given any integer k, there exists h k such that, for any sequence of nonnegative integers y1, y2, . . . , yk, . . . , yh with y1 = 1 and yi 2i 1 for any i = 1, . . . , h, where σh = Ph i=1 yi and αh = Ph i=1 yi 2h i , i.e., αh = yh + yh 1 4 + . . . + y1 2h 1 . Proof: Assume by contradiction that σ2 h αh < h2 210 for any h k. We divide the subsequence starting at yk in consecutive blocks of length 1, 2, 3, . . . (block j has length j). Let start(j) and end(j) be the first and the last indices of block j, respectively, i.e., start(j) = k + j(j 1) 2 and end(j) = start(j + 1) 1 = k + j(j+1) 2 1 = O(k + j2). In order to complete the proof, it is sufficient to show by induction on j that σend(j) j(end(j) k + 1)22j+1 4. In fact, it implies that, when end(j) > 2k, there exists an integer yh (h {1, . . . , end(j)}) such that yh j22j+1 5. By recalling that h end(j) = O(k + j2), this is a contradiction to the fact that yh 2h 1. Since y1 = 1, we have σend(1) 1, that is the base of the induction (for j = 1). It remains to prove the induction step. The induction hypothesis is that σend(j) j(end(j) k + 1)22j+1 4. Our aim is to show that σend(j+1) (j + 1)(end(j + 1) k + 1)22j+2 4. For every i = start(j + 1), . . . , end(j + 1), by the induction hypothesis, it holds that j2(end(j) k+1)222j+2 8 αi σ2 end(j) αi σ2 i αi < i2 210 . It follows that αi > 210j2(end(j) k + 1)222j+2 8 > 2102 4j222j+2 8 (5) = 2 2j222j+2, where inequality (5) holds because, i2 end2(j) 9 < 24 (since i end(j + 1)). By summing over all i [start(j+1), end(j+1)], we obtain Pend(j+1) i=start(j+1) αi > 2 2(j+1)j222j+2. Since, as it can be easily checked, it holds that, for any ℓ 1, Pℓ i=1 αi 2 Pℓ i=1 yi = 2σℓ, it follows that 2σend(j+1) Pend(j+1) i=1 αi Pend(j+1) i=start(j+1) αi > 2 2(j + 1)j222j+2. Therefore, we obtain σend(j+1) > 2 3(j + 1)j222j+2 > (j + 1)(end(j + 1) k + 1)22j+2 4, where the last inequality holds because 2j2 end(j + 1) k + 1, for any j 1. Flammini, Monaco, Moscardelli, Shalom, & Zaks Theorem 4.5 The competitive ratio of any deterministic online algorithm for Max FW-CSG is Ω(log2 W), even when all weights are positive. Proof: Assume by contradiction that there exists an r-competitive deterministic online algorithm A for Max FW-CSG with r = o(log2 W). Namely, there exists some constant b 0 such that A OPT r b for every input. The adversary works in phases i = 1, 2, . . .. In phase 1, she releases one agent. The adversary maintains the following invariant which clearly holds after the first phase: a solution of A consists of a single component C1 and possibly singleton coalitions. Let σi be the number of agents of C1 at the end of phase i, and let these agents be v1, v2, . . . , vσi. Clearly, σ1 = 1. The adversary releases, in phase i (for i = 2, 3, . . .), σi 1 agents u1, u2, . . . , uσi 1, such that every uj (j [σi 1]) is adjacent to vj by an edge of weight 2i 2. Let yi be the number of agents that A adds to C1 in phase i. It follows that σi = σi 1 + yi and yi σi 1 2i 1. First of all, notice that A cannot stop adding new agents to the unique component, because otherwise it would be not competitive, given that the weights of edges are geometrically increasing. Let k be an integer whose value will be suitably chosen at the end of the proof. Let k k be the first phase after phase k such that yk 1. Let h k be an integer such that σ2 h αh h2 210 , whose existence is guaranteed by Lemma 4.1. The adversary continues until the end of phase h. Clearly, σi = Pi j=1 yj. It can be easily checked that, after phase i, the measure of the solution of A is Pi j=1 yj2j 2 σi . On the other hand, there is another coalition structure C1, . . . , Cσi 1 in which each edge added by the adversary in phase i constitutes a separate coalition. The fractional weight of this solution is σi 12i 2 2 . Therefore, OPT σi 12i 2 2 . Given that σi+1 2σi, we obtain OPT σi2i 1 8 . Thus, at the end of phase i we have A σ2 i 2i 1 8 Pi j=1 yj2j 2 = σ2 i 2i 1 4 Pi j=1 yj2j 1 = σ2 i 4 Pi j=1 yj2j i = σ2 i 4αi , where αi = Pi j=1 yj 2j i . In particular, at the end of phase h, recalling that W = 2h 2, we have A σ2 h 4αh h2 212 = (log W + 2)2 212 > log2 W Combining with our assumption about the competitive ratio of A, we get (A + b)r OPT > Alog2 W 212 , which implies log2 W A b + 1. We get a contradiction by noting that, since r = o(log2 W), the ratio log2 W 212r is unbounded. 4.2 Bounded Coalition Size In this section we analyze the Max FW-CSG problem when the coalition size is bounded by α. On the Online Coalition Structure Generation Problem 4.2.1 Unweighted Graphs For the case of unweighted graphs, we are able to prove that algorithm Maximal Matching provides the best possible competitive ratio of 4α 1 α . Theorem 4.6 proves the lower bound. The proof is very similar to the one of Theorem 4.3. For the sake of completeness, in the following we provide a self-contained proof. Theorem 4.6 Given any ϵ > 0, there exists no 4α 1 α ϵ -competitive deterministic online algorithm for Max FW-CSG, even in unweighted graphs. Proof: Let us assume, by the way of contradiction, that A is a 4α 1 α ϵ -competitive deterministic online algorithm with an additive term b > 0. First of all, we show that, for every non-negative integer k, there is an adversary that causes the output of A to be a matching of k edges, i.e. k coalitions of two agents and n 2k singleton coalitions. In fact, there exists an adversary that causes A to add a coalition of two agents given that the current output is a matching of ℓedges, thus causing the output to be a matching of ℓ+ 1 edges: The adversary issues at most 3ℓ+ 8b + 1 couple of agents connected by an edge (i.e, in each couple there are two agents incident to only the edge connecting them) until A puts the two agents of a same couple in one coalition. We have to show that this must happen. Assume, by contradiction, that A does not put the two agents of any couple in one coalition. On the one hand, the output of A is a matching with ℓedges, thus A = ℓ/2. On the other hand, a possible coalition structure consists of a matching with ℓ+ 3ℓ+ 8b + 1 = 4ℓ+ 8b + 1 edges. Therefore, OPT 4ℓ+8b+1 2 > 2ℓ+ 4b. Then, OPT 4 α 1 2 + b = A + b, a contradiction. We conclude that A must add an edge to its output to augment it to a matching of ℓ+ 1 agents. The adversary chooses an integer k 1 to be determined later. In the first stage, the adversary causes the output of A to be a matching with k edges. Let C1, . . . , Ck be the coalitions of A consisting of two edges. These coalitions will possibly grow in the second stage. At any given point during the execution of A we denote by Fi the first four agents of Ci, or Fi = Ci if |Ci| < 4. Notice that also sets Fi can grow during the second stage. Also, F def = k i=1Fi. At the beginning of the second stage we have |F| = 2k, and by definition, |F| 4k. The adversary issues a new agent adjacent only to some agent u of F where u is chosen from F in a round robin manner. The adversary stops when every agent of F has α 1 neighbors outside of F. Since |F| is bounded, F will not grow after a certain point. After at most 4k(α 1) steps every agent of F will have α 1 neighbors not in F and the adversary will stop. Let k2, k3, k4 be the number of coalitions with 2, 3 and at least 4 agents, respectively. Clearly, k2 + k3 + k4 = k. We have A 1 3k3 + k4, since the solution consists of k2 matchings, k3 trees with 3 vertices and k4 trees (of at least 4 vertices). On the other hand, there is a solution that consists of |F| stars, each of which contains α vertices. Therefore, letting γ = α 1 α , we have that OPT (2k2 + 3k3 + 4k4) 1 1 α = γ(2k2 + 3k3 + 4k4). Notice also that c = 4γ ϵ. Flammini, Monaco, Moscardelli, Shalom, & Zaks We conclude OPT 4γ ϵ A γ(2k2 + 3k3 + 4k4) ϵ 2(4γ ϵ)(k2 + k3 + k4) = ϵ 2(4γ ϵ)k, where the last inequality holds because, since γ > 0 and ϵ > 0, we obtain that i) 2γ 4γ ϵ 1 ϵ 2(4γ ϵ), ii) 3γ 4γ ϵ 2 3 ϵ 2(4γ ϵ), and iii) 4γ 4γ ϵ 1 ϵ 2(4γ ϵ). Therefore, if the adversary chooses k such that ϵ 2(4γ ϵ)k > b, a contradiction arises and the claim follows. The following theorem provides a matching upper bound to Theorem 4.6. Its proof exploits and refines arguments introduced in the proof of Lemma 1 by Bil o et al. (2018). Theorem 4.7 Algorithm Maximal Matching is a 4α 1 α -competitive deterministic online algorithm for Max FW-CSG in unweighted graphs. Proof: Let C be the coalition structure returned by Maximal Matching. A vertex cover V C V is associated with C: V C is such that all agents being endpoints of the edges contained in the maximal matching belong to V C. Clearly, V C is a vertex cover because otherwise there should exist an edge of G that could be added to the matching, contradicting its maximality. Let C be an optimal solution for the considered instance of Max FW-CSG. In the remaining of the proof we prove that w F (C ) α . In fact, since |V C| = 4w F (C), the claim follows. Define V C = N \ V C. Let C i (i [k]) be a coalition of C . Partition the agents of C i in two sets: XV C i = C i V C and XV C i = C i V C. We distinguish between two cases: XV C i = ; it follows that C i V C. Therefore, since V C is an independent set, w F (C i ) = 0. XV C i = ; in this case the total number of edges in C i is at most |XV C i ||XV C i | + 1 2|XV C i |(|XV C i | 1). In fact (see Figure 6), all the possible edges may be present in C i among any agent in XV C i and any agent in XV C i (being at most |XV C i ||XV C i |), and between any couple of agents in XV C i (being at most 1 2|XV C i |(|XV C i | 1)), while no edge can be present between agents in XV C i (because XV C i is an independent set). It follows that the contribution of coalition C i to w F (C ) is w F (C i ) |XV C i ||XV C i | + 1 2|XV C i |(|XV C i | 1) |XV C i | + |XV C i | = |XV C i ||XV C i | + 1 2|XV C i | 1 2 |XV C i | + |XV C i | . On the Online Coalition Structure Generation Problem Figure 6: Bounding the total number of edges in C i . Solid edges represent the ones belonging to the computed maximal matching, while dashed edges are the ones belonging to C i but not belonging to the solution returned by Maximal Matching. Dividing by |XV C i | we obtain w F (C i ) |XV C i | |XV C i |+ 1 2 |XV C i | 1 2 |XV C i |+|XV C i | α 1 α because |XV C i | + |XV C i | α and |XV C i | 1. By summing over all indices i [k], we obtain P i [k]:XV C i = w F (C i ) P i [k]:XV C i = w F (C i ) P i [k]:XV C i = |XV C i | max i [k]:XV C i = w F (C i ) |XV C i | α 1 4.2.2 Weighted Graphs From Theorem 4.2, we know that, for any α 2, Maximal Matching is strictly 4Wcompetitive for general weights. It is not difficult to show that this bound is asymptotically tight, even when all the weights are positive. Theorem 4.8 The competitive ratio of any deterministic online algorithm for Max FW-CSG is Ω(W) even when all weights are positive. Proof: Let A be any deterministic online algorithm for Max FW-CSG with an additive term b. Consider the online input that is supplied to A by the following adversary. The adversary releases a star v1, v2, . . . centered at v1 until A creates its second coalition C2 = {vj} or the star is sufficiently large. The weights are such that wvj+1,v1 wvj,v1 for every Flammini, Monaco, Moscardelli, Shalom, & Zaks j > 1. By setting W = wvj,v1, we have that OPT W 2 . On the other hand A = o(W) in both cases, i.e. either the star is sufficiently large, or the heaviest edge is not taken by A. Therefore, the competitive ratio of A is at least OPT o(W) = Ω(W). 4.3 Bounded Number of Coalitions In this section we consider the case where the number of coalitions is bounded by some k 2, the case of k = 1 being trivial. 4.3.1 General Weights By exploiting arguments similar to the ones used in the proofs of Theorem 3.3 and Theorem 3.4, it is possible to prove the following results. Theorem 4.9 There exists no deterministic competitive algorithm for Max FW-CSG for any k 2. Proof: Suppose, by the way of contradiction, that A is a r-competitive algorithm for Max FW-CSG with an additive term b, i.e. A OPT r b for some b 0, with r being either constant or a function of n. The adversary releases an independent set of at most k + 1 agents until A puts two agents vi, vj in the same coalition. Then it releases an agent adjacent to only vi and vj with edges of weights 2br + 1 and (2br + 1) respectively. Then, regardless of the decisions of A, we have A = 0. On the other hand, one can form a coalition consisting of vi together with the last agent, and form a second coalition from the remaining agents which constitute an independent set. Thus, OPT = 2br+1 2 > br implying A = 0 < OPT r b, a contradiction. In the following theorem, it is shown that the strict competitive ratio remains unbounded even when W = 1. Theorem 4.10 There exists no deterministic strictly competitive algorithm for Max FW-CSG for any k 2, even when W = 1. Proof: Suppose, by the way of contradiction, that A is a r-competitive algorithm A for Max FW-CSG, i.e. A OPT r , with r being either constant or a function of n. The adversary releases an independent set of at most k + 1 vertices until A puts two agents vi, vj in the same coalition. Then it releases an agent adjacent to only vi and vj with edges of weights 1 and 1 respectively. Then, regardless of the decisions of A, we have A = 0. On the other hand, one can form a coalition consisting of vi together with the last agent, and form a second coalition from the remaining agents which constitute an independent set. Thus, OPT = 1 2 implying A = 0 < OPT r , a contradiction. On the Online Coalition Structure Generation Problem 4.3.2 Positive Weights Observation 1 For positive weights, Grand Coalition is n 2 -competitive. In fact, Grand Coalition = P e E(G) w(e) n , and OPT P e E(G) w(e) 2 , since the weight of any edge is shared by at least its two endpoints. Theorem 4.11 Given any ϵ > 0, there exists no deterministic online algorithm for Max FW-CSG having competitive ratio n 2 ϵ, for any k 2 and even when all weights are positive. Proof: Let us assume, by the way of contradiction, that A is a r-competitive deterministic online algorithm for Max FW-CSG with r = n 2 ϵ and an additive term b > 0. Consider the online input that is supplied to A by the following adversary. The adversary releases a star v1, v2, . . . centered at v1. The weights are such that wvj+1,v1 wvj,v1, for every j > 1. In particular, let oj+1 = Pj i=2 wvi,v1 be the sum of the weights of the edges viv1, for i = 2, . . . , j, then we set wvj+1,v1 > oj+1(n 2ϵ)+bn(n 2ϵ) 2ϵ . Notice that, by the definition of wvj+1,v1, for any j > 1 the following holds: 2 n 2 ϵ = wvj+1,v1 n 2ϵ > wvj+1,v1 + oj+1 Let us call C1 the coalition where algorithm A puts agent v1. If, at some step j, A puts the agent vj into a different coalition than C1, then the adversary stops. In this case, we get that the optimum has value at least wvj,v1 2 (by creating a coalition containing only vj and v1). Therefore r b wvj,v1 2(n 2 ϵ) b > oj(n 2ϵ) + b(n2 2nϵ (4ϵ(n 2 ϵ)) n 2 ϵ ϵ2 > oj n 1 = A, a contradiction. Finally, if algorithm A puts all agents into coalition C1, we have that r b wvn,v1 2(n 2 ϵ) b > wvn,v1 + on n + b b = wvn,v1 + on where the second inequality holds by (6). Therefore, since a contradiction arises also in this case, the claim follows. 5. Conclusion and Open Problems In this paper we have considered the problem of partitioning agents into coalitions in an online fashion. Given that previous work on CSG mainly assumes that all the information on the input is known at the beginning, this work may be considered as a fundamental step towards more realistic CSG models: Further steps, for instance considering some degree of uncertainty regarding the weight of edges, deserve future research in order to model CSG scenarios in an increasingly realistic way. Flammini, Monaco, Moscardelli, Shalom, & Zaks We have presented close upper and lower bounds for the competitive ratio in various scenarios, while considering two natural coalition value functions: the value of a coalition is defined as the sum of the weights of its edges or as the sum of the weights of its edges divided by its size. There are few problems left open in the considered scenarios: for instance, it would be interesting to provide a lower bound to the non-strict competitive ratio for Max W-CSG and Max FW-CSG in the case of bounded number of coalitions and unweighted graphs. It is worth remarking that, although our model considers undirected graphs (having undirected edges), dealing with directed graphs (having directed arcs) would not make the problem richer or more interesting. In fact, given that we are not considering individual utilities of the nodes but global utilities of the coalitions, if we replace every couple of arcs being between two nodes in the opposite directions with a single edge having as weight the sum of their weights and every remaining directed arc with an edge having the same weight, we obtain an equivalent problem in our (undirected) setting1. We expect that our study will initiate more research along the same lines. An interesting research direction is that of considering more involved coalition value functions, depending on specific applications. For instance, we might consider that there are also costs associated with each coalition, or other costs taking into account the topological properties of the subgraphs induced by the coalitions, like for instance the diameter, the average distance between the agents, measures depending on the centrality indices in social networks, etc. Recent work about such measures has been presented by Balliu, Flammini, and Olivetti (2017), Balliu, Flammini, Melideo, and Olivetti (2019). Moreover, it is worth to extend this research to the case where the coalition structure can be modified by migrating agents from coalition to coalition by paying some penalty as in the setting considered by Augustine et al. (2016). Furthermore, one might consider cases where agents can also leave the graph as in the setting considered by Dinitz (2008) and in general CSG in dynamic environments (de O. Ramos, Burguillo, & Bazzan, 2014). Finally, it would be interesting to understand whether randomized algorithms can achieve significantly better performance than deterministic ones, or specifically designed deterministic algorithm can provide better expected performances when executed on graphs in which connections between nodes obey to some given probabilistic law. To this respect, a model deserving further research is the scale-free network considered by Albert and Barab asi (2002), in which a network is incrementally built (in an online fashion) by adding new nodes such that the degree distribution follows a power law. Acknowledgments 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) 1. Notice that, in the case of general weights, the parameter W has to be obtained by scaling the new weights of the undirected edges so that the minimum edge weight is 1. On the Online Coalition Structure Generation Problem Albert, R., & Barab asi, A.-l. (2002). Statistical mechanics of complex networks. Rev. Mod. Phys, 74(1), 47 97. Augustine, J., Avin, C., Liaee, M., Pandurangan, G., & Rajaraman, R. (2016). Information spreading in dynamic networks under oblivious adversaries. In Proceedings of the 30th International Symposium on Distributed Computing, (DISC), pp. 399 413. Aziz, H., Brandt, F., & Seedig, H. (2011). Stable partitions in additively separable hedonic games. In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 183 190. Aziz, H., Gaspers, S., Gudmundsson, J., Mestre, J., & Taubig, H. (2015). Welfare maximization in fractional hedonic games. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), pp. 461 467. Aziz, H., Brandl, F., Brandt, F., Harrenstein, P., Olsen, M., & Peters, D. (2019). Fractional hedonic games. ACM Trans. Economics and Comput., 7(2), 6:1 6:29. Aziz, H., & de Keijzer, B. (2011). Complexity of coalition structure generation. In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS, pp. 191 198. Bachrach, Y., Kohli, P., Kolmogorov, V., & Zadimoghaddam, M. (2013). Optimal coalition structure generation in cooperative graph games. In Proceedings of the 27th AAAI Conference on Artificial Intelligence (AAAI), pp. 81 87. Ballester, C. (2004). Np-completeness in hedonic games. Games and Economic Behavior, 49(1), 1 30. Balliu, A., Flammini, M., & Olivetti, D. (2017). On pareto optimality in social distance games. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pp. 349 355. Balliu, A., Flammini, M., Melideo, G., & Olivetti, D. (2019). On non-cooperativeness in social distance games. Journal of Artificial Intelligence Research, 66, 625 653. Banerjee, S., Konishi, H., & S onmez, T. (2001). Core in a simple coalition formation game. Social Choice and Welfare, 18, 135 153. Bil o, V., Fanelli, A., Flammini, M., Monaco, G., & Moscardelli, L. (2018). Nash stable outcomes in fractional hedonic games: Existence, efficiency and computation. Journal of Artificial Intelligence Research, 62, 315 371. Bil o, V., Fanelli, A., Flammini, M., Monaco, G., & Moscardelli, L. (2019). Optimality and nash stability in additive separable generalized group activity selection problems. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI), pp. 102 108. Bistaffa, F., & Farinelli, A. (2018). A COP model for graph-constrained coalition formation. Journal of Artificial Intelligence Research, 62, 133 153. Bogomolnaia, A., & Jackson, M. O. (2002). The stability of hedonic coalition structures. Games and Economic Behavior, 38(2), 201 230. Flammini, Monaco, Moscardelli, Shalom, & Zaks Borodin, A., & El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cambridge University Press. Brandl, F., Brandt, F., & Strobel, M. (2015). Fractional hedonic games: individual and group stability. In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems, (AAMAS), pp. 1219 1227. Buchbinder, N., Feldman, M., Filmus, Y., & Garg, M. (2020). Online submodular maximization: beating 1/2 made simple. Math. Program., 183(1), 149 169. Carosi, R., Monaco, G., & Moscardelli, L. (2019). Local core stability in simple symmetric fractional hedonic games. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 574 582. Chalkiadakis, G., Elkind, E., Markakis, E., Polukarov, M., & Jennings, N. R. (2010). Cooperative games with overlapping coalitions. Journal of Artificial Intelligence Research, 39, 179 216. Dang, V. D., & Jennings, N. R. (2004). Generating coalition structures with finite bound from the optimal guarantees. In Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 564 571. de O. Ramos, G., Burguillo, J. C., & Bazzan, A. L. C. (2014). Dynamic constrained coalition formation among electric vehicles. J. Braz. Comput. Soc., 20(1), 8:1 8:15. Deng, X., & Papadimitriou, C. H. (1994). On the complexity of cooperative solution concepts. Mathematics of Operations Research, 12, 257 266. Dinitz, M. (2008). Online, dynamic, and distributed embeddings of approximate ultrametrics. In Proceedings of the 22nd International Symposium on Distributed Computing (DISC), pp. 152 166. Dr eze, J. H., & Greenberg, J. (1980). Hedonic coalitions: optimality and stability. Econometrica, 48(4), 987 1003. Dutta, A., Dasgupta, P., Baca, J., & Nelson, C. A. (2013). A bottom-up search algorithm for dynamic reformation of agent coalitions under coalition size constraints. In Proceedings of the IEEE/WIC/ACM International Conferences on Intelligent Agent Technology (IAT), pp. 329 336. Elkind, E., Fanelli, A., & Flammini, M. (2020). Price of pareto optimality in hedonic games. Artificial Intelligence, 288, 103357. Fanelli, A., Monaco, G., & Moscardelli, L. (2021). Relaxed core stability in fractional hedonic games. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI), pp. 182 188. Fiat, A., & Woeginger, G. J. (Eds.). (1998). Online Algorithms, The State of the Art (the book grow out of a Dagstuhl Seminar, June 1996), Vol. 1442 of Lecture Notes in Computer Science. Springer. Flammini, M., Kodric, B., Monaco, G., & Zhang, Q. (2021). Strategyproof mechanisms for additively separable and fractional hedonic games. Journal of Artificial Intelligence Research, 70, 1253 1279. On the Online Coalition Structure Generation Problem Flammini, M., Monaco, G., Moscardelli, L., Shalom, M., & Zaks, S. (2018). Online coalition structure generation in graph games. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS), pp. 1353 1361. Mauro, N. D., Basile, T. M. A., Ferilli, S., & Esposito, F. (2010). Coalition structure generation with GRASP. In Proceedings of the 14th International Conference on Artificial Intelligence: Methodology, Systems, Applications (AIMSA), pp. 111 120. Monaco, G., Moscardelli, L., & Velaj, Y. (2019). On the performance of stable outcomes in modified fractional hedonic games with egalitarian social welfare. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 873 881. Monaco, G., Moscardelli, L., & Velaj, Y. (2020). Stable outcomes in modified fractional hedonic games. Autonomous Agents and Multi-Agent Systems, 34(1), 4. Myerson, R. B. (1977). Graphs and cooperation in games. Math. Oper. Res., 2(3), 225 229. Nguyen, T. D., & Zick, Y. (2018). Resource based cooperative games: Optimization, fairness and stability. In Proceedings of the 11th International Symposium on Algorithmic Game Theory (SAGT), Vol. 11059 of Lecture Notes in Computer Science, pp. 239 244. Springer. Olsen, M. (2009). Nash stability in additively separable hedonic games and community structures. Theory of Computing Systems, 45(4), 917 925. Rahwan, T., & Jennings, N. R. (2008). An improved dynamic programming algorithm for coalition structure generation. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1417 1420. Rahwan, T., Michalak, T. P., Wooldridge, M., & Jennings, N. R. (2012). Anytime coalition structure generation in multi-agent systems with positive or negative externalities. Artificial Intelligence, 186, 95 122. Rahwan, T., Michalak, T. P., Wooldridge, M., & Jennings, N. R. (2015). Coalition structure generation: A survey. Artificial Intelligence, 229, 139 174. Rahwan, T., Ramchurn, S. D., Jennings, N. R., & Giovannucci, A. (2009). An anytime algorithm for optimal coalition structure generation. Journal of Artificial Intelligence Research, 34, 521 567. Rothkopf, M. H., Pekec, A., & Harstad, R. M. (1998). Computationally manageable combinatorial auctions. Management Science, 44(8), 1131 1147. Sandholm, T., Larson, K., Andersson, M., Shehory, O., & Tohm e, F. (1999). Coalition structure generation with worst case guarantees. Artificial Intelligence, 111(1-2), 209 238. Sen, S., & Dutta, P. S. (2000). Searching for optimal coalition structures. In Proceedings of the 4th International Conference on Multi-Agent Systems (ICMAS), pp. 287 292. Shehory, O., & Kraus, S. (1998). Methods for task allocation via agent coalition formation. Artificial Intelligence, 101(1-2), 165 200. Shin, D., & Shin, Y. (2011). Why do people play social network games?. Comput. Hum. Behav., 27(2), 852 861. Flammini, Monaco, Moscardelli, Shalom, & Zaks Voice, T., Polukarov, M., & Jennings, N. R. (2012). Coalition structure generation over graphs. Journal of Artificial Intelligence Research, 45, 165 196. Zick, Y., Markakis, E., & Elkind, E. (2014). Arbitration and stability in cooperative games with overlapping coalitions. Journal of Artificial Intelligence Research, 50, 847 884.