Coalitional Structure Generation in Skill Games

We consider optimizing the coalition structure in Coalitional Skill Games (CSGs), a succinct representation of coalitional games (Bachrach and Rosenschein 2008). In CSGs, the value of a coalition depends on the tasks its members can achieve. The tasks require various skills to complete them, and agents may have different skill sets. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that CSGs can represent any characteristic function, and consider optimal coalition structure generation in this representation. We provide hardness results, showing that in general CSGs, as well as in very restricted versions of them, computing the optimal coalition structure is hard. On the positive side, we show that the problem can be reformulated as constraint satisfaction on a hyper graph, and present an algorithm that finds the optimal coalition structure in polynomial time for instances with bounded tree-width and number of tasks.