Forming k coalitions and facilitating relationships in social networks

We show that, when the number of coalitions, k, is fixed and there are not many negative edges, it is possible to find the coalition structure that maximizes the social welfare in polynomial time. Furthermore, an organizer can efficiently find the optimal set of edges to add to the network, and we experimentally demonstrate the effectiveness of this approach. In addition, we show that in our setting even when k is fixed and there are not many negative edges, finding a member of the core is intractable. However, we provide a heuristic for efficiently finding a member of the core that also guarantees a social welfare within a factor of 1/2 of the optimal social welfare. We also show that checking whether a given coalition structure is a member of the core can be done in polynomial time. Finally, we consider the problem faced by an organizer who would like to add edges to the network in order to stabilize a specific coalition structure core: we show that this problem is intractable.