{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,22]],"date-time":"2026-07-22T13:24:15Z","timestamp":1784726655887,"version":"3.55.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,2,18]],"date-time":"2020-02-18T00:00:00Z","timestamp":1581984000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,2,18]],"date-time":"2020-02-18T00:00:00Z","timestamp":1581984000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["17H01790"],"award-info":[{"award-number":["17H01790"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2020,4]]},"abstract":"Abstract<\/jats:title>How to form effective coalitions is an important issue in multi-agent systems. Coalition Structure Generation ($${{\\mathsf {CSG}}}$$<\/jats:tex-math>CSG<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>) is a fundamental problem whose formalization can encompass various applications related to multi-agent cooperation.$${{\\mathsf {CSG}}}$$<\/jats:tex-math>CSG<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>involves partitioning a set of agents into coalitions such that the social surplus (i.e., the sum of the values of all coalitions) is maximized. In traditional$${\\mathsf {CSG}}$$<\/jats:tex-math>CSG<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we are guaranteed that all coalitions will be successfully established, that is, the attendance rate of each agent for joining any coalition is assumed to be 1.0. Having the real world in mind, however, it is natural to consider the uncertainty of agents\u2019 availabilities, e.g., an agent might be available only two or three days a week because of his\/her own schedule. Probabilistic Coalition Structure Generation ($${{\\mathsf {PCSG}}}$$<\/jats:tex-math>PCSG<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>) is an extension of$${\\mathsf {CSG}}$$<\/jats:tex-math>CSG<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>where the attendance type of each agent is considered. The aim of this problem is to find the optimal coalition structure which maximizes the sum of the expected values of all coalitions. In$${\\mathsf {PCSG}}$$<\/jats:tex-math>PCSG<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, since finding the optimal coalition structure easily becomes intractable, it is important to consider approximation algorithms, i.e., to consider a trade-off between the quality of the returned solution and tractability. In this paper, a formal framework for$${\\mathsf {PCSG}}$$<\/jats:tex-math>PCSG<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is introduced. Approximation algorithms for$${\\mathsf {PCSG}}$$<\/jats:tex-math>PCSG<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>called Bounded Approximation Algorithm based on Attendance Types ($${{\\mathsf {BAAAT}}}$$<\/jats:tex-math>BAAAT<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>) and Involved$${\\mathsf {BAAAT}}$$<\/jats:tex-math>BAAAT<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>($${{\\mathsf {IBAAAT}}}$$<\/jats:tex-math>IBAAAT<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>) are then presented. We prove a priori bounds on the quality of the solution returned by$${\\mathsf {BAAAT}}$$<\/jats:tex-math>BAAAT<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$${\\mathsf {IBAAAT}}$$<\/jats:tex-math>IBAAAT<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>with respect to the optimum and perform experimental evaluations on a number of benchmarks.<\/jats:p>","DOI":"10.1007\/s10458-020-09449-8","type":"journal-article","created":{"date-parts":[[2020,2,18]],"date-time":"2020-02-18T11:04:03Z","timestamp":1582023843000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Two approximation algorithms for probabilistic coalition structure generation with quality bound"],"prefix":"10.1007","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7305-0194","authenticated-orcid":false,"given":"Kouki","family":"Matsumura","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bojana","family":"Kodric","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tenda","family":"Okimoto","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Katsutoshi","family":"Hirayama","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,2,18]]},"reference":[{"key":"9449_CR1","doi-asserted-by":"crossref","unstructured":"Bachrach, Y., Kohli, P., Kolmogorov, V., & Zadimoghaddam, M. (2013). Optimal coalition structure generation in cooperative graph games. In Proceedings of 27th AAAI conference on artificial intelligence (pp. 81\u201387)","DOI":"10.1609\/aaai.v27i1.8653"},{"issue":"1","key":"9449_CR2","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.ejor.2014.01.039","volume":"237","author":"EK Burke","year":"2014","unstructured":"Burke, E. K., & Curtois, T. (2014). New approaches to nurse rostering benchmark instances. European Journal of Operational Research, 237(1), 71\u201381.","journal-title":"European Journal of Operational Research"},{"issue":"3","key":"9449_CR3","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/s10458-010-9157-y","volume":"24","author":"G Chalkiadakis","year":"2012","unstructured":"Chalkiadakis, G., & Boutilier, C. (2012). Sequentially optimal repeated coalition formation under uncertainty. Autonomous Agents and Multi-Agent Systems, 24(3), 441\u2013484.","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"issue":"6\u20137","key":"9449_CR4","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1016\/j.artint.2006.01.005","volume":"170","author":"V Conitzer","year":"2006","unstructured":"Conitzer, V., & Sandholm, T. W. (2006). Complexity of constructing solutions in the core based on synergies among coalitions. Artificial Intelligence, 170(6\u20137), 607\u2013619.","journal-title":"Artificial Intelligence"},{"key":"9449_CR5","unstructured":"Dang, V. D., Dash, R. K., Rogers, A., & Jennings, N. R. (2006). Overlapping coalition formation for efficient data fusion in multi-sensor networks. In Proceedings of 21st national conference on artificial intelligence (pp. 635\u2013640)"},{"key":"9449_CR6","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/978-3-642-32723-0_27","volume":"83","author":"P Dasgupta","year":"2013","unstructured":"Dasgupta, P., & Cheng, K. (2013). Robust multi-robot team formations using weighted voting games. Distributed Autonomous Robotic Systems, 83, 373\u2013387.","journal-title":"Distributed Autonomous Robotic Systems"},{"key":"9449_CR7","first-page":"1","volume-title":"Frontiers in water resource economics. Natural Resource Management and Policy","author":"A Dinar","year":"2006","unstructured":"Dinar, A., Moretti, S., Patrone, F., & Zara, S. (2006). Application of stochastic cooperative games in water resources. In R. U. Goetz & D. Berga (Eds.), Frontiers in water resource economics. Natural Resource Management and Policy (pp. 1\u201320). Boston, MA: Springer."},{"key":"9449_CR8","first-page":"273","volume":"2","author":"PF Faye","year":"2015","unstructured":"Faye, P. F., Aknine, S., Sene, M., & Shehory, O. (2015). Dynamic coalitions formation in dynamic uncertain environments. WI-IAT, 2, 273\u2013276.","journal-title":"WI-IAT"},{"key":"9449_CR9","doi-asserted-by":"crossref","unstructured":"Ieong, S., & Shoham, Y. (2005) Marginal contribution nets: A compact representation scheme for coalitional games. In Proceedings of 6th ACM conference on electronic commerce (pp. 193\u2013202)","DOI":"10.1145\/1064009.1064030"},{"key":"9449_CR10","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations.\u00a0The IBM Research Symposia Series","author":"RM Karp","year":"1972","unstructured":"Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller, J. W. Thatcher & J. D. Bohlinger (Eds.), Complexity of computer computations.\u00a0The IBM Research Symposia Series (pp. 85\u2013103). Boston, MA: Springer."},{"key":"9449_CR11","doi-asserted-by":"crossref","unstructured":"Kraus, S., Shehory, O., & Taase, G. (2003). Coalition formation with uncertain heterogeneous information. In Proceedings of 2nd international joint conference on autonomous agents and multiagent systems (pp. 1\u20138)","DOI":"10.1145\/860575.860577"},{"issue":"1","key":"9449_CR12","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1080\/095281300146290","volume":"12","author":"KS Larson","year":"2000","unstructured":"Larson, K. S., & Sandholm, T. W. (2000). Anytime coalition structure generation: An average case study. Journal of Experimental and Theoretical Artificial Intelligence, 12(1), 23\u201342.","journal-title":"Journal of Experimental and Theoretical Artificial Intelligence"},{"key":"9449_CR13","doi-asserted-by":"crossref","unstructured":"Matsumura, K., Okimoto, T., & Hirayama, K. (2018) Bounded approximate algorithm for probabilistic coalition structure generation. In Proceedings of 21st international conference on principles and practice of multi-agent systems (pp. 123\u2013139)","DOI":"10.1007\/978-3-030-03098-8_8"},{"key":"9449_CR14","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.artint.2015.09.006","volume":"230","author":"T Michalak","year":"2016","unstructured":"Michalak, T., Rahwan, T., Elkind, E., Wooldridge, M., & Jennings, N. R. (2016). A hybrid exact algorithm for complete set partitioning. Artificial Intelligence, 230, 14\u201350.","journal-title":"Artificial Intelligence"},{"key":"9449_CR15","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1613\/jair.1549","volume":"23","author":"R Nair","year":"2005","unstructured":"Nair, R., & Tambe, M. (2005). Hybrid BDI-POMDP framework for multiagent teaming. Journal of Artificial Intelligence Research, 23, 367\u2013420.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9449_CR16","unstructured":"Okimoto, T., Ribeiro, T., Bouchabou, D., & Inoue, K. (2016). Mission oriented robust multi-team formation and its application to robot rescue simulation. In Proceedings of 25th international joint conference on artificial intelligence (pp. 454\u2013460)"},{"key":"9449_CR17","unstructured":"Okimoto, T., Schwind, N., Clement, M., Ribeiro, T., Inoue, K., & Marquis, P. (2015) How to form a task-oriented robust team. In Proceedings of 14th international conference on autonomous agents and multiagent systems (pp. 395\u2013403)"},{"key":"9449_CR18","unstructured":"Rahwan, T., & Jennings, N. R. (2008). Coalition structure generation: Dynamic programming meets anytime optimization. In Proceedings of 23rd AAAI conference on artificial intelligence (pp. 156\u2013161)"},{"key":"9449_CR19","unstructured":"Rahwan, T., & Jennings, N. R. (2008) An improved dynamic programming algorithm for coalition structure generation. In Proceedings of 7th international joint conference on autonomous agents and multiagent systems (pp. 1417\u20131420)"},{"key":"9449_CR20","unstructured":"Rahwan, T., Michalak, T., & Jennings, N. R. (2012). A hybrid algorithm for coalition structure generation. In Proceedings of 26th AAAI conference on artificial intelligence (pp. 1443\u20131449)"},{"key":"9449_CR21","unstructured":"Rahwan, T., Ramchurn, S., Dang, V. D., Giovannucci, A., & Jennings, N. R. (2007). Anytime optimal coalition structure generation. In Proceedings of 2nd national conference on artificial intelligence (pp. 1184\u20131190)"},{"key":"9449_CR22","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1613\/jair.2695","volume":"34","author":"T Rahwan","year":"2009","unstructured":"Rahwan, T., Ramchurn, S. D., Jennings, N. R., & Giovannucci, A. (2009). An anytime algorithm for optimal coalition structure generation. Journal of Artificial Intelligence Research, 34, 521\u2013567.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9449_CR23","unstructured":"Sandholm, T. W. (1993). An implementation of the contract net protocol based on marginal cost calculations. In Proceedings of 11th national conference on artificial intelligence (pp. 295\u2013308)"},{"issue":"1\u20132","key":"9449_CR24","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0004-3702(99)00036-3","volume":"111","author":"TW Sandholm","year":"1999","unstructured":"Sandholm, T. W., Larson, K., Andersson, M., Shehory, O., & Tohm\u00e9, F. (1999). Coalition structure generation with worst case guarantees. Artificial Intelligence, 111(1\u20132), 209\u2013238.","journal-title":"Artificial Intelligence"},{"issue":"1\u20132","key":"9449_CR25","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0004-3702(97)00030-1","volume":"94","author":"TW Sandholm","year":"1997","unstructured":"Sandholm, T. W., & Lesser, V. R. (1997). Coalitions among computationally bounded agents. Artificial Intelligence, 94(1\u20132), 99\u2013137.","journal-title":"Artificial Intelligence"},{"key":"9449_CR26","unstructured":"Schwind, N., Okimoto, T., Inoue, K., Hirayama, K., Lagniez, J. M., & Marquis, P. (2018). Probabilistic coalition structure generation. In Proceedings of 16th international conference on principles of knowledge representation and reasoning (pp. 663\u2013664)"},{"key":"9449_CR27","unstructured":"Service, T. C., & Adams, J. A. (2010). Anytime dynamic programming for coalition structure generation. In Proceedings of 9th international joint conference on autonomous agents and multiagent systems (pp. 1411\u20131412)"},{"key":"9449_CR28","doi-asserted-by":"crossref","unstructured":"Service, T. C., & Adams, J. A. (2010). Approximate coalition structure generation. In Proceedings of 24th AAAI conference on artificial intelligence (pp. 854\u2013859)","DOI":"10.1609\/aaai.v24i1.7636"},{"issue":"4","key":"9449_CR29","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/s10458-018-9386-z","volume":"32","author":"S Ueda","year":"2018","unstructured":"Ueda, S., Iwasaki, A., Conitzer, V., Ohta, N., Sakurai, Y., & Yokoo, M. (2018). Coalition structure generation in cooperative games with compact representations. Autonomous Agents and Multi-Agent Systems, 32(4), 503\u2013533.","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"key":"9449_CR30","doi-asserted-by":"crossref","unstructured":"Ueda, S., Iwasaki, A., Yokoo, M., Silaghi, M. C., Hirayama, K., & Matsui, T. (2010) Coalition structure generation based on distributed constraint optimization. In Proceedings of 24th AAAI conference on artificial intelligence (pp. 197\u2013203)","DOI":"10.1609\/aaai.v24i1.7552"},{"key":"9449_CR31","unstructured":"Ueda, S., Kitaki, M., Iwasaki, A., & Yokoo, M. (2011). Concise characteristic function representations in coalitional games based on agent types. In Proceedings of 22nd international joint conference on artificial intelligence (pp. 393\u2013399)"},{"issue":"1","key":"9449_CR32","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1080\/09528130410001710792","volume":"16","author":"JM Vidal","year":"2004","unstructured":"Vidal, J. M. (2004). The effects of co-operation on multiagent search in task-oriented domains. Journal of Experimental and Theoretical Artificial Intelligence, 16(1), 5\u201318.","journal-title":"Journal of Experimental and Theoretical Artificial Intelligence"},{"issue":"4","key":"9449_CR33","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF01935053","volume":"26","author":"DY Yeh","year":"1986","unstructured":"Yeh, D. Y. (1986). A dynamic programming approach to the complete set partitioning problem. BIT Computer Science and Numerical Mathematics, 26(4), 467\u2013474.","journal-title":"BIT Computer Science and Numerical Mathematics"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-020-09449-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10458-020-09449-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-020-09449-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,15]],"date-time":"2022-10-15T21:27:16Z","timestamp":1665869236000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10458-020-09449-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,18]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["9449"],"URL":"https:\/\/doi.org\/10.1007\/s10458-020-09449-8","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,18]]},"assertion":[{"value":"18 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"25"}}