King's College London

Research portal

Optimising Social Welfare in Multi-Resource Threshold Task Games

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

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

Original languageEnglish
Title of host publicationPRIMA 2017
Subtitle of host publicationPrinciples and Practice of Multi-Agent Systems - 20th International Conference, Proceedings
PublisherSpringer Verlag
Pages110-126
Number of pages17
Volume10621 LNAI
ISBN (Print)9783319691305
DOIs
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

Conference

Conference20th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2017
CountryFrance
CityNice
Period30/10/20173/11/2017

Links

King's Authors

Research outputs

Abstract

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.

View graph of relations

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454