Optimising Social Welfare in Multi-Resource Threshold Task Games

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

doi:10.1007/978-3-319-69131-2_7

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 proceeding › Other chapter contribution › peer-review

3 Citations (Scopus)

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.

Original language	English
Title of host publication	PRIMA 2017
Subtitle of host publication	Principles and Practice of Multi-Agent Systems - 20th International Conference, Proceedings
Publisher	Springer Verlag
Pages	110-126
Number of pages	17
Volume	10621 LNAI
ISBN (Print)	9783319691305
DOIs	https://doi.org/10.1007/978-3-319-69131-2_7
Publication status	E-pub ahead of print - 5 Oct 2017
Event	20th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2017 - Nice, France Duration: 30 Oct 2017 → 3 Nov 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10621 LNAI
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Conference

Conference	20th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2017
Country/Territory	France
City	Nice
Period	30/10/2017 → 3/11/2017

Keywords

Coalition formation
Cooperative games
Overlapping coalitions

Access to Document

10.1007/978-3-319-69131-2_7

https://eprints.soton.ac.uk/414358/

Cite this

Habib, F. R., Polukarov, M., & Gerding, E. H. (2017). Optimising Social Welfare in Multi-Resource Threshold Task Games. In PRIMA 2017: Principles and Practice of Multi-Agent Systems - 20th International Conference, Proceedings (Vol. 10621 LNAI, pp. 110-126). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10621 LNAI). Springer Verlag. Advance online publication. https://doi.org/10.1007/978-3-319-69131-2_7

Habib, Fatma R. ; Polukarov, Maria ; Gerding, Enrico H. / Optimising Social Welfare in Multi-Resource Threshold Task Games. PRIMA 2017: Principles and Practice of Multi-Agent Systems - 20th International Conference, Proceedings. Vol. 10621 LNAI Springer Verlag, 2017. pp. 110-126 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{a23446d52ecb4b1b86991c1eac177b45,

title = "Optimising Social Welfare in Multi-Resource Threshold Task Games",

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.",

keywords = "Coalition formation, Cooperative games, Overlapping coalitions",

author = "Habib, {Fatma R.} and Maria Polukarov and Gerding, {Enrico H.}",

year = "2017",

month = oct,

day = "5",

doi = "10.1007/978-3-319-69131-2_7",

language = "English",

isbn = "9783319691305",

volume = "10621 LNAI",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "110--126",

booktitle = "PRIMA 2017",

address = "Germany",

note = "20th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2017 ; Conference date: 30-10-2017 Through 03-11-2017",

}

Habib, FR, Polukarov, M & Gerding, EH 2017, Optimising Social Welfare in Multi-Resource Threshold Task Games. in PRIMA 2017: Principles and Practice of Multi-Agent Systems - 20th International Conference, Proceedings. vol. 10621 LNAI, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10621 LNAI, Springer Verlag, pp. 110-126, 20th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2017, Nice, France, 30/10/2017. https://doi.org/10.1007/978-3-319-69131-2_7

Optimising Social Welfare in Multi-Resource Threshold Task Games. / Habib, Fatma R.; Polukarov, Maria; Gerding, Enrico H.
PRIMA 2017: Principles and Practice of Multi-Agent Systems - 20th International Conference, Proceedings. Vol. 10621 LNAI Springer Verlag, 2017. p. 110-126 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10621 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Other chapter contribution › peer-review

TY - CHAP

T1 - Optimising Social Welfare in Multi-Resource Threshold Task Games

AU - Habib, Fatma R.

AU - Polukarov, Maria

AU - Gerding, Enrico H.

PY - 2017/10/5

Y1 - 2017/10/5

N2 - 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.

AB - 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.

KW - Coalition formation

KW - Cooperative games

KW - Overlapping coalitions

UR - http://www.scopus.com/inward/record.url?scp=85034239381&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-69131-2_7

DO - 10.1007/978-3-319-69131-2_7

M3 - Other chapter contribution

AN - SCOPUS:85034239381

SN - 9783319691305

VL - 10621 LNAI

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 110

EP - 126

BT - PRIMA 2017

PB - Springer Verlag

T2 - 20th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2017

Y2 - 30 October 2017 through 3 November 2017

ER -

Habib FR, Polukarov M, Gerding EH. Optimising Social Welfare in Multi-Resource Threshold Task Games. In PRIMA 2017: Principles and Practice of Multi-Agent Systems - 20th International Conference, Proceedings. Vol. 10621 LNAI. Springer Verlag. 2017. p. 110-126. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). Epub 2017 Oct 5. doi: 10.1007/978-3-319-69131-2_7

Optimising Social Welfare in Multi-Resource Threshold Task Games

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Optimising social welfare in multi-resource threshold task games: Appendix

Cite this