Abstract
Cooperative game theory studied the Coalition Structure Generation (CSG) problem in a characteristic function form, where each coalition is associated with a value. Given n agents, there are \(2^n-1\) coalitions. Hence, in the CSG problem, given a set of \(2^n-1\) coalitions, each associated with a value, we have to find a maximal valued disjoint set of coalitions with the same union as the whole set. The first best approximation ratio obtainable in \(O(2^n)\) time is \(\frac{2}{n}\) from the optimal [8]. Later, Adams et al. [1] presented an algorithm which is capable of generating a solution with a value of \(\frac{2}{3}\) of the optimal in \(O(\sqrt{n}2.83^n)\) time, a solution with a value \(\frac{1}{2}\) of the optimal in \(O(\sqrt{n}2.59^n)\) time and a \(\frac{1}{8}\) approximation in \(O(2^n)\) time. This paper sheds new light on the CSG problem by exploiting the combinatorics and symmetry and proposes an approximate halfway dynamic programming (HDP) algorithm with time complexity \(O(2^{\frac{3n}{2}})\approx O(2.83^n)\) with an approximation ratio of \(1-\frac{4}{n}\).
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.
If n is even, it picks coalitions of size n/2, n is odd, it chooses the coalitions of size \(\lceil \frac{n}{2}\rceil \) and \(\lceil \frac{n}{2}\rceil -1\).
References
Adams, J., et al.: Approximate coalition structure generation. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence, pp. 854–859. AAAI (2010)
Larson, K.S., Sandholm, T.W.: Anytime coalition structure generation: an average case study. J. Exp. Theor. Artif. Intell. 12(1), 23–42 (2000)
Michalak, T., Rahwan, T., Elkind, E., Wooldridge, M., Jennings, N.R.: A hybrid exact algorithm for complete set partitioning. Artif. Intell. 230, 14–50 (2016)
Rahwan, T., Jennings, N.R.: An improved dynamic programming algorithm for coalition structure generation. In: AAMAS, vol. 3, pp. 1417–1420 (2008)
Rahwan, T., Michalak, T.P., Jennings, N.R.: A hybrid algorithm for coalition structure generation. In: AAAI, pp. 1443–1449 (2012)
Rahwan, T., Ramchurn, S.D., Dang, V.D., Giovannucci, A., Jennings, N.R.: Anytime optimal coalition structure generation. In: AAAI, vol. 7, pp. 1184–1190 (2007)
Rahwan, T., Ramchurn, S.D., Jennings, N.R., Giovannucci, A.: An anytime algorithm for optimal coalition structure generation. J. Artif. Intell. Res. 34, 521–567 (2009)
Sandholm, T., Larson, K., Andersson, M., Shehory, O., Tohmé, F.: Coalition structure generation with worst case guarantees. Artif. Intell. 111(1), 209–238 (1999)
Travis, S.: Coalition structure generation in characteristic function games. Ph.D. thesis, Graduate School of Vanderbilt University (2012)
Acknowledgments
The research presented in this article is funded by “Visvesvaraya PhD Scheme for Electronics & IT”, grant no: PhD-MLA/4(29)/2015-16. Samir Aknine was supported by Univ. Lyon 1.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Narayan, C., Samir, A., Animesh, D. (2019). Leveraging Symmetric Relations for Approximation Coalition Structure Generation. In: Baldoni, M., Dastani, M., Liao, B., Sakurai, Y., Zalila Wenkstern, R. (eds) PRIMA 2019: Principles and Practice of Multi-Agent Systems. PRIMA 2019. Lecture Notes in Computer Science(), vol 11873. Springer, Cham. https://doi.org/10.1007/978-3-030-33792-6_27
Download citation
DOI: https://doi.org/10.1007/978-3-030-33792-6_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-33791-9
Online ISBN: 978-3-030-33792-6
eBook Packages: Computer ScienceComputer Science (R0)