Optimising Social Welfare in Multi-Resource Threshold Task Games

Fatma R. Habib*, Maria Polukarov, Enrico H. Gerding

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingOther chapter contributionpeer-review

3 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationPRIMA 2017
Subtitle of host publicationPrinciples and Practice of Multi-Agent Systems - 20th International Conference, Proceedings
PublisherSpringer Verlag
Number of pages17
Volume10621 LNAI
ISBN (Print)9783319691305
Publication statusE-pub ahead of print - 5 Oct 2017
Event20th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2017 - Nice, France
Duration: 30 Oct 20173 Nov 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10621 LNAI
ISSN (Print)03029743
ISSN (Electronic)16113349


Conference20th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2017


  • Coalition formation
  • Cooperative games
  • Overlapping coalitions


Dive into the research topics of 'Optimising Social Welfare in Multi-Resource Threshold Task Games'. Together they form a unique fingerprint.

Cite this