Forming k coalitions and facilitating relationships in social networks

In this paper we relax two common assumptions that are made when studying coalition formation. The first is that any number of coalitions can be formed; the second is that any possible coalition can be formed. We study a model of coalition formation where the value depends on a social network and exactly k coalitions must be formed. Additionally, in this context we present a new problem for an organizer that would like to introduce members of the social network to each other in order to increase the social welfare or to stabilize a coalition structure. 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.