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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 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.
References
Akçay, Y., Li, H., Xu, S.H.: Greedy algorithm for the general multidimensional knapsack problem. Ann. Oper. Res. 150(1), 17–29 (2007)
Aumann, R.J., Dreze, J.H.: Cooperative games with coalition structures. Int. J. Game Theor. 3(4), 217–237 (1974)
Bachrach, Y., Meir, R., Jung, K., Kohli, P.: Coalitional structure generation in skill games. In: AAAI, vol. 10, pp. 703–708 (2010)
Bachrach, Y., Rosenschein, J.S.: Coalitional skill games. In: AAMAS, vol. 2, 1023–1030 (2008)
Bing, H., Leblet, J., Simon, G.: Hard multidimensional multiple choice knapsack problems, an empirical study. Comput. Oper. Res. 37(1), 172–181 (2010)
Chalkiadakis, G., Elkind, E., Markakis, E., Polukarov, M., Jennings, N.R.: Cooperative games with overlapping coalitions. JAIR 39(1), 179–216 (2010)
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)
Dang, V.D., Jennings, N.R.: Coalition structure generation in task-based settings. In: ECAI, pp. 210–214 (2006)
Dantzig, G.B.: Discrete-variable extremum problems. Oper. Res. 5(2), 266–288 (1957)
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)
Dobson, G.: Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Math. Oper. Res. 7(4), 515–531 (1982)
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)
Habib, F.R., Polukarov, M., Gerding, E.H.: Optimising social welfare in multi-resource threshold task games: Appendix (2017). https://eprints.soton.ac.uk/413650/
Pisinger, D.: A fast algorithm for strongly correlated knapsack problems. Discrete Appl. Math. 89(1–3), 197–212 (1998)
Pisinger, D.: Where are the hard knapsack problems? Comput. Oper. Res. 32(9), 2271–2284 (2005)
Sbihi, A.: A best first search exact algorithm for the multiple-choice multidimensional knapsack problem. J. Comb. Optim. 13(4), 337–351 (2007)
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)
Shehory, O., Kraus, S.: Formation of overlapping coalitions for precedence-ordered task-execution among autonomous agents. In: ICMAS, pp. 330–337 (1996)
Shehory, O., Kraus, S.: Methods for task allocation via agent coalition formation. Artif. Intell. 101(1–2), 165–200 (1998)
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)
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)
Wooldridge, M., Dunne, P.E.: On the computational complexity of coalitional resource games. J. Artif. Intell. 170(10), 835–871 (2006)
Zanakis, S.H.: Heuristic 0–1 linear programming: an experimental comparison of three methods. Manag. Sci. 24(1), 91–104 (1977)
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)
Zick, Y., Chalkiadakis, G., Elkind, E.: Overlapping coalition formation games: charting the tractability frontier. In: AAMAS, vol. 2, pp. 787–794 (2012)
Zick, Y., Elkind, E.: Arbitrators in overlapping coalition formation games. In: AAMAS, vol. 1, pp. 55–62 (2011)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Habib, F.R., Polukarov, M., Gerding, E.H. (2017). Optimising Social Welfare in Multi-Resource Threshold Task Games. In: An, B., Bazzan, A., Leite, J., Villata, S., van der Torre, L. (eds) PRIMA 2017: Principles and Practice of Multi-Agent Systems. PRIMA 2017. Lecture Notes in Computer Science(), vol 10621. Springer, Cham. https://doi.org/10.1007/978-3-319-69131-2_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-69131-2_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-69130-5
Online ISBN: 978-3-319-69131-2
eBook Packages: Computer ScienceComputer Science (R0)