Optimising Social Welfare in Practical Cooperative Settings

Abstract

The coalition structure generation (CSG) problem is a fundamental topic in multi-agent systems and cooperative game theory. It treats scenarios in which cooperative agents strive to maximise the sum of their utilities known as the social welfare. Existing research addressing the CSG problem has focused on settings where an agent’s participation is restricted to one coalition, while little research has been done on overlapping coalition formation games (OCF-Gs). OCF-Gs, introduced by Chalkiadakis et al., allow agents to join multiple coalitions. More specifically, Chalkiadakis et al. defined threshold task games (TTGs), to represent overlapping coalitions of agents in a task based environment. In essence, every agent is endowed with a certain amount of a resource and is allowed to contribute to multiple tasks represented as coalitions. However, the TTG model makes the simplifying assumption that the environment consists of only one type of resource. As the first contribution in this thesis, we introduce MR-TTGs (multiple-resource threshold task games), an extension of TTGs that models environments with multiple resources. Furthermore, for our second contribution, we solve the CSG problem for MR-TTGs. To this end, we present two reductions of the CSG problem on MR-TTGs to two different variants of the knapsack problem. We then propose two anytime branch and bound algorithm for solving these reductions. Moreover, work on CSG studies a very general setting where coalition structures of all sizes are feasible. However, in certain scenarios, it is desirable to specify the size (cardinality) of a coalition structure depending on the availability of some resource. The number of rooms or vehicles available, for example, influences the number of coalitions in a coalition structure. For our third contribution, we propose an algorithm to address the problem of cardinality constrained CSG. The running time of the algorithm is small for large coalition structure sizes. Moreover, the approximation ratio was less than 1.006 for all instances. Furthermore, most of the literature on CSG focused on settings where the coalition values are given. However, in many settings, obtaining the optimal coalition values require complex computations. As a result, in order to utilise existing CSG algorithm, one needs to calculate the values of all coalitions beforehand. We ran a couple of problems of 25 agents in this setting and it took 3 days to solve each problem using CPLEX. To circumvent expensive calculations, for our fourth contribution, we utilise interval cooperative games to substitute coalition values with approximate ones. More specifically, we prove that the resulting coalition structure is within β^2 of the optimal, where β is the approximation ratio of the values used in the interval model. Additionally, empirical evaluation of our proposed approach output solutions that are within β of the optimal.