Forming Coalitions and Facilitating Relationships for Completing Tasks in Social Networks

We consider the problem of computing effective coalition structures in situations where the coalitions that can be formed and the value of these coalitions is determined by a social network, indicating the strength of relationships between agents. We assume that a central organizer desires to build coalition structures to carry out a given set of tasks, and that it is possible for this central organizer to create new relationships between agents, although such relationship-building is assumed to incur some cost. Within this model, we investigate the problem of computing coalition structures that maximize social welfare, and the problem of computing core-stable coalition structures. In addition to giving some general results on these problems, we identify tractable instances of the problems, and present algorithms for these cases.