Back to search

University of Southampton

Optimising social welfare in practical cooperative settings

Abstract

dc:description.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. (2010), allow agents to join multiple coalitions. More specifically, Chalkiadakis et al. (2010) defined threshold task games (TTGs), to represent overlapping coalitions of agents in a taskbased 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 iv 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.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Habib, Fatma R.
Advisor dc:contributor.advisor
  • Gerding, Enrico
ORCID person:identifier.orcid

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Habib, Fatma R.. Optimising social welfare in practical cooperative settings. doctoral thesis, 2020.