Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Handling Heterogeneous Disagreements Through Abstract Argumentation (Extended Abstract) Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Optimising Social Welfare in Multi-Resource Threshold Task Games

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

Published in: PRIMA 2017: Principles and Practice of Multi-Agent Systems

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Reachability and Expectation in Gossiping
next chapter Speed up Automated Mechanism Design by Sampling Worst-Case Profiles: An Application to Competitive VCG Redistribution Mechanism for Public Project Problem
Footnotes
1
A coalition structure is defined as a list rather than a set because different partial coalitions can have the same weights of agents’ contributions.
 
Literature
1.
Akçay, Y., Li, H., Xu, S.H.: Greedy algorithm for the general multidimensional knapsack problem. Ann. Oper. Res. 150(1), 17–29 (2007)MathSciNetCrossRefMATH
2.
3.
Bachrach, Y., Meir, R., Jung, K., Kohli, P.: Coalitional structure generation in skill games. In: AAAI, vol. 10, pp. 703–708 (2010)
4.
Bachrach, Y., Rosenschein, J.S.: Coalitional skill games. In: AAMAS, vol. 2, 1023–1030 (2008)
5.
Bing, H., Leblet, J., Simon, G.: Hard multidimensional multiple choice knapsack problems, an empirical study. Comput. Oper. Res. 37(1), 172–181 (2010)MathSciNetCrossRefMATH
6.
Chalkiadakis, G., Elkind, E., Markakis, E., Polukarov, M., Jennings, N.R.: Cooperative games with overlapping coalitions. JAIR 39(1), 179–216 (2010)MathSciNetMATH
7.
Dang, V.D., Dash, R.K., Rogers, A., Jennings, N.R.: Overlapping coalition formation for efficient data fusion in multi-sensor networks. In: AAAI, pp. 635–640 (2006)
8.
Dang, V.D., Jennings, N.R.: Coalition structure generation in task-based settings. In: ECAI, pp. 210–214 (2006)
9.
10.
Di, B., Wang, T., Song, L., Han, Z.: Incentive mechanism for collaborative smartphone sensing using overlapping coalition formation games. In: GLOBECOM, pp. 1705–1710 (2013)
11.
Dobson, G.: Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Math. Oper. Res. 7(4), 515–531 (1982)MathSciNetCrossRefMATH
12.
Gillies, D.B.: Solutions to general non-zero-sum games. In: Tucker, A.W., Luce, R.D. (eds.) Contributions to the Theory of Games, vol. 4, pp. 47–85. Princeton University Press, Princeton (1959)
13.
14.
15.
16.
Sbihi, A.: A best first search exact algorithm for the multiple-choice multidimensional knapsack problem. J. Comb. Optim. 13(4), 337–351 (2007)MathSciNetCrossRefMATH
17.
Shapley, L.S.: A value for \(n\)-person games. In: Tucker, A.W., Kuhn, H.W. (eds.) Contributions to the Theory of Games, vol. 2, pp. 307–317. Princeton University Press, Princeton (1953)
18.
Shehory, O., Kraus, S.: Formation of overlapping coalitions for precedence-ordered task-execution among autonomous agents. In: ICMAS, pp. 330–337 (1996)
19.
20.
Tran-Thanh, L., Nguyen, T.D., Rahwan, T., Rogers, A., Jennings, N.R.: An efficient vector-based representation for coalitional games. In: AAAI, pp. 383–389 (2013)
21.
Wang, T., Song, L., Han, Z., Saad, W.: Overlapping coalitional games for collaborative sensing in cognitive radio networks. In: WCNC, pp. 4118–4123. IEEE (2013)
22.
Wooldridge, M., Dunne, P.E.: On the computational complexity of coalitional resource games. J. Artif. Intell. 170(10), 835–871 (2006)MathSciNetCrossRefMATH
23.
24.
Zhang, Z., Song, L., Han, Z., Saad, W.: Coalitional games with overlapping coalitions for interference management in small cell networks. IEEE Trans. Wirel. Commun. 13(5), 2659–2669 (2014)CrossRef
25.
Zick, Y., Chalkiadakis, G., Elkind, E.: Overlapping coalition formation games: charting the tractability frontier. In: AAMAS, vol. 2, pp. 787–794 (2012)
26.
Zick, Y., Elkind, E.: Arbitrators in overlapping coalition formation games. In: AAMAS, vol. 1, pp. 55–62 (2011)
Metadata
Title
Optimising Social Welfare in Multi-Resource Threshold Task Games
Authors
Fatma R. Habib
Maria Polukarov
Enrico H. Gerding
Copyright Year
2017
Book
PRIMA 2017: Principles and Practice of Multi-Agent Systems

Print ISBN: 978-3-319-69130-5

Electronic ISBN: 978-3-319-69131-2

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-69131-2_7

Premium Partner

    Image Credits