Optimising Social Welfare in Multi-Resource Threshold Task Games

In this paper, we introduce a discrete model for overlapping coalition formation called the multi-resource threshold task game (MR-TTG), which generalises the model introduced in [6]. Furthermore, we define the coalition structure generation (CSG) Problem for MR-TTGs. Towards the efficient solution of CSG problems for MR-TTGs, we provide two reductions to the well-known knapsack problems: the bounded multidimensional knapsack problem and the multiple-choice multidimensional knapsack problem. We then propose two branch and bound algorithms to compare between these reductions. Empirical evaluation shows that the latter reduction is more efficient in solving difficult instances of the problem.