{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:16:00Z","timestamp":1740122160990,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,3,24]],"date-time":"2021-03-24T00:00:00Z","timestamp":1616544000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,24]],"date-time":"2021-03-24T00:00:00Z","timestamp":1616544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2021,4]]},"DOI":"10.1007\/s10458-021-09498-7","type":"journal-article","created":{"date-parts":[[2021,3,24]],"date-time":"2021-03-24T08:03:36Z","timestamp":1616573016000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the computation of probabilistic coalition structures"],"prefix":"10.1007","volume":"35","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7972-5984","authenticated-orcid":false,"given":"Nicolas","family":"Schwind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tenda","family":"Okimoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katsumi","family":"Inoue","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katsutoshi","family":"Hirayama","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Marie","family":"Lagniez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"Marquis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,24]]},"reference":[{"key":"9498_CR1","unstructured":"Chalkiadakis, G., & Boutilier, C. (2004). Bayesian reinforcement learning for coalition formation under uncertainty. In Proceedings of the third international conference on autonomous agents and multiagent systems (AAMAS\u201904) (pp. 1090\u20131097)."},{"key":"9498_CR2","unstructured":"Chalkiadakis, G., & Boutilier, C. (2007). Coalitional bargaining with agent type uncertainty. In Proceedings of the twentieth international joint conference on artificial intelligence (IJCAI\u201907) (pp. 1227\u20131232)."},{"issue":"3","key":"9498_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"},{"key":"9498_CR4","doi-asserted-by":"crossref","unstructured":"Chalkiadakis, G., Elkind, E., & Wooldridge, M. (2011). Computational aspects of cooperative game theory. Morgan & Claypool Publishers.","DOI":"10.2200\/S00355ED1V01Y201107AIM016"},{"issue":"6\u20137","key":"9498_CR5","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. (2006). Complexity of constructing solutions in the core based on synergies among coalitions. Artificial Intelligence, 170(6\u20137), 607\u2013619.","journal-title":"Artificial Intelligence"},{"issue":"2","key":"9498_CR6","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.19.2.257","volume":"19","author":"X Deng","year":"1994","unstructured":"Deng, X., & Papadimitriou, C. H. (1994). On the complexity of cooperative solution concepts. Mathematics of Operations Research, 19(2), 257\u2013266.","journal-title":"Mathematics of Operations Research"},{"key":"9498_CR7","doi-asserted-by":"crossref","unstructured":"Doherty, P., Michalak, T., Sroka, J., & Sza\u0142as, A. (2011). Contextual coalitional games. In Proceedings of the fourth Indian conference on logic and its applications (ICLA\u201911) (pp. 65\u201378).","DOI":"10.1007\/978-3-642-18026-2_7"},{"key":"9498_CR8","doi-asserted-by":"crossref","unstructured":"Faye, P.F., Aknine, S., Sene, M., & Shehory, O. (2015). Dynamic coalitions formation in dynamic uncertain environments. In IEEE\/WIC\/ACM international conference on web intelligence and intelligent agent technology (WI-IAT\u201915) (pp. 273\u2013276).","DOI":"10.1109\/WI-IAT.2015.86"},{"key":"9498_CR9","unstructured":"Gillies, D. (1953). Some theorems on n-person games. Ph.D. thesis, Princeton University."},{"issue":"1","key":"9498_CR10","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1109\/TCOMM.2009.0901.060661","volume":"57","author":"Z Han","year":"2009","unstructured":"Han, Z., & Poor, H. (2009). Coalition games with cooperative transmission: A cure for the curse of boundary nodes in selfish packet-forwarding wireless networks. IEEE Transactions on Communications, 57(1), 203\u2013213.","journal-title":"IEEE Transactions on Communications"},{"key":"9498_CR11","doi-asserted-by":"crossref","unstructured":"Ieong, S., & Shoham, Y. (2005). Marginal contribution nets: a compact representation scheme for coalitional games. In Proceedings of the sixth ACM conference on electronic commerce (EC\u201905) (pp. 193\u2013202).","DOI":"10.1145\/1064009.1064030"},{"key":"9498_CR12","unstructured":"Ieong, S., & Shoham, Y. (2008). Bayesian coalitional games. In Proceedings of the twenty-third AAAI conference on artificial intelligence (AAAI\u201908) (pp. 95\u2013100)."},{"key":"9498_CR13","doi-asserted-by":"crossref","unstructured":"Khan, Z., Lehtomaki, J., Latva-aho, M., & DaSilva, L. A. (2010). On selfish and altruistic coalition formation in cognitive radio networks. In Proceedings of the fifth international conference on cognitive radio oriented wireless networks and communications (CROWNCOM\u201910) (pp. 1\u20135).","DOI":"10.4108\/ICST.CROWNCOM2010.9208"},{"key":"9498_CR14","doi-asserted-by":"crossref","unstructured":"Kraus, S., Shehory, O., & Taase, G. (2003). Coalition formation with uncertain heterogeneous information. In Proceedings of the second international conference on autonomous agents and multiagent systems (AAMAS\u201903) (pp. 1\u20138).","DOI":"10.1145\/860575.860577"},{"key":"9498_CR15","doi-asserted-by":"crossref","unstructured":"Li, Y., Albarghouthi, A., Kincaid, Z., Gurfinkel, A., & Chechik, M. (2014). Symbolic optimization with SMT solvers. In The forty-first annual ACM SIGPLAN-SIGACT symposium on principles of programming languages (POPL\u201914) (pp. 607\u2013618).","DOI":"10.1145\/2535838.2535857"},{"key":"9498_CR16","unstructured":"Liao, X., Koshimura, M., H. H., & Hasegawa, R. (2012). Solving the coalition structure generation problem with MaxSAT. In Proceedings of the IEEE 24th international conference on tools with artificial intelligence (ICTAI\u201912) (pp. 910\u2013915)."},{"issue":"7","key":"9498_CR17","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1587\/transinf.E97.D.1781","volume":"E97\u2013D5","author":"X Liao","year":"2014","unstructured":"Liao, X., Koshimura, M., Fujita, H., & Hasegawa, R. (2014). MaxSAT encoding for MC-Net-based coalition structure generation problem with externalities. IEICE Transactions on Information and Systems, E97\u2013D5(7), 1781\u20131789.","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"1","key":"9498_CR18","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10601-018-9295-4","volume":"24","author":"X Liao","year":"2019","unstructured":"Liao, X., Koshimura, M., Nomoto, K., Ueda, S., Sakurai, Y., & Yokoo, M. (2019). Improved WPM encoding for coalition structure generation under MC-nets. Constraints, 24(1), 25\u201355.","journal-title":"Constraints"},{"issue":"1","key":"9498_CR19","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10458-020-09449-8","volume":"34","author":"K Matsumura","year":"2020","unstructured":"Matsumura, K., Kodric, B., Okimoto, T., & Hirayama, K. (2020). Two approximation algorithms for probabilistic coalition structure generation with quality bound. Autonomous Agents Multi Agent Systems, 34(1), 25.","journal-title":"Autonomous Agents Multi Agent Systems"},{"issue":"3","key":"9498_CR20","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1287\/moor.3.3.189","volume":"3","author":"N Megido","year":"1978","unstructured":"Megido, N. (1978). Computational complexity of the game theory approach to cost allocation for a tree. Mathematics of Operations Research, 3(3), 189\u2013196.","journal-title":"Mathematics of Operations Research"},{"key":"9498_CR21","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/j.artint.2015.09.006","volume":"230","author":"TP Michalak","year":"2016","unstructured":"Michalak, T. P., 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":"9498_CR22","unstructured":"Ohta, N., Iwasaki, A., Yokoo, M., Maruono, K., Conitzer, V., & Sandholm, T. (2006). A compact representation scheme for coalitional games in open anonymous environments. In Proceedings of the twenty-first national conference on artificial intelligence (AAAI\u201906) (pp. 697\u2013702)."},{"key":"9498_CR23","doi-asserted-by":"crossref","unstructured":"Ohta, N., Conitzer, V., Ichimura, R., Sakurai, Y., Iwasaki, A., & Yokoo, M. (2009). Coalition structure generation utilizing compact characteristic function representations. In Proceedings of the fifteenth international conference on principles and practice of constraint programming (CP\u201909) (pp. 623\u2013638).","DOI":"10.1007\/978-3-642-04244-7_49"},{"key":"9498_CR24","doi-asserted-by":"crossref","unstructured":"Okimoto, T., Schwind, N., Demirovic, E., Inoue, K., & Marquis, P. (2018). Robust coalition structure generation. In Proceedings of the twenty-first international conference on principles and practice of multi-agent systems (PRIMA\u201918) (pp. 140\u2013157).","DOI":"10.1007\/978-3-030-03098-8_9"},{"key":"9498_CR25","unstructured":"Papadimitriou, C. M. (1994). Computational complexity. Addison-Wesley."},{"key":"9498_CR26","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":"9498_CR27","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/j.artint.2015.08.004","volume":"229","author":"T Rahwan","year":"2015","unstructured":"Rahwan, T., Michalak, T. P., Wooldridge, M., & Jennings, N. R. (2015). Coalition structure generation: A survey. Artificial Intelligence, 229, 139\u2013174.","journal-title":"Artificial Intelligence"},{"issue":"1","key":"9498_CR28","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/s10458-015-9286-4","volume":"30","author":"SD Ramchurn","year":"2016","unstructured":"Ramchurn, S. D., Wu, F., Jiang, W., Fischer, J. E., Reece, S., Roberts, S., et al. (2016). Human-agent collaboration for disaster response. Autonomous Agents and Multi-Agent Systems, 30(1), 82\u2013111.","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"issue":"7","key":"9498_CR29","doi-asserted-by":"publisher","first-page":"1131","DOI":"10.1287\/mnsc.44.8.1131","volume":"44","author":"MH Rothkopf","year":"1998","unstructured":"Rothkopf, M. H., Peke\u010d, A., & Harstad, R. M. (1998). Computationally manageable combinatorial auctions. Management Science, 44(7), 1131\u20131147.","journal-title":"Management Science"},{"issue":"5","key":"9498_CR30","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1109\/MSP.2009.000000","volume":"26","author":"W Saad","year":"2009","unstructured":"Saad, W., Han, Z., Debbah, M., Hjorungnes, A., & Basar, T. (2009). Coalitional game theory for communication networks. IEEE Signal Processing Magazine, 26(5), 77\u201397.","journal-title":"IEEE Signal Processing Magazine"},{"issue":"1\u20132","key":"9498_CR31","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S0004-3702(99)00036-3","volume":"111","author":"T Sandholm","year":"1999","unstructured":"Sandholm, T., 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":"6","key":"9498_CR32","doi-asserted-by":"publisher","first-page":"1163","DOI":"10.1137\/0117107","volume":"17","author":"D Schmeidler","year":"1969","unstructured":"Schmeidler, D. (1969). The nucleolus of a characteristic function game. SIAM Journal on Applied Mathematics, 17(6), 1163\u20131170.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"9498_CR33","unstructured":"Schwind, N., Okimoto, T., Inoue, K., Hirayama, K., Lagniez, J. M., & Marquis, P. (2018). Probabilistic coalition structure generation. In Proceedings of the sixteenth international conference on principles of knowledge representation and reasoning (KR\u201918) (pp. 663\u2013664)."},{"issue":"8","key":"9498_CR34","first-page":"307","volume":"2","author":"LS Shapley","year":"1953","unstructured":"Shapley, L. S. (1953). A value for n-person games. Contributions to the Theory of Games, 2(8), 307\u2013317.","journal-title":"Contributions to the Theory of Games"},{"issue":"1","key":"9498_CR35","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0004-3702(98)00045-9","volume":"101","author":"O Shehory","year":"1998","unstructured":"Shehory, O., & Kraus, S. (1998). Methods for task allocation via agent coalition formation. Artificial Intelligence, 101(1), 165\u2013200.","journal-title":"Artificial Intelligence"},{"key":"9498_CR36","unstructured":"Shrot, T., Aumann, Y., & Kraus, S. (2010). On agent types in coalition formation problems. In Proceedings of the ninth international conference on autonomous agents and multiagent systems (AAMAS\u201910) (pp. 757\u2013764)."},{"issue":"1","key":"9498_CR37","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/S0377-2217(97)00421-9","volume":"113","author":"J Suijs","year":"1999","unstructured":"Suijs, J., Borm, P., De Waegenaere, A., & Tijs, S. (1999). Cooperative games with stochastic payoffs. European Journal of Operational Research, 113(1), 193\u2013205.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"9498_CR38","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1002\/nav.3800100126","volume":"10","author":"RM Thrall","year":"1963","unstructured":"Thrall, R. M., & Lucas, W. F. (1963). N-person games in partition function form. Naval Research Logistics Quarterly, 10(1), 281\u2013298.","journal-title":"Naval Research Logistics Quarterly"},{"issue":"5","key":"9498_CR39","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"20","author":"S Toda","year":"1991","unstructured":"Toda, S. (1991). PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5), 865\u2013877.","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"9498_CR40","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1002\/malq.200810024","volume":"55","author":"J Uckelman","year":"2009","unstructured":"Uckelman, J., Chevaleyre, Y., Endriss, U., & Lang, J. (2009). Representing utility functions via weighted goals. Mathematical Logic Quarterly, 55(4), 341\u2013361.","journal-title":"Mathematical Logic Quarterly"},{"key":"9498_CR41","unstructured":"Ueda, S., Kitaki, M., Iwasaki, A., & Yokoo, M. (2011). Concise characteristic function representations in coalitional games based on agent types. In Proceedings of the tenth international conference on autonomous agents and multiagent systems (AAMAS\u201911) (pp. 1271\u20131272)."},{"key":"9498_CR42","unstructured":"Ueda, S., Hasegawa, T., Hashimoto, N., Ohta, N., Iwasaki, A., & Yokoo, M. (2012). Handling negative value rules in MC-net-based coalition structure generation. In International conference on autonomous agents and multiagent systems, AAMAS 2012, Valencia, Spain, June 4\u20138, 2012 (Vol. 3, pp. 795\u2013804)."},{"issue":"4","key":"9498_CR43","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF01935053","volume":"26","author":"D Yeh","year":"1986","unstructured":"Yeh, D. (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"},{"key":"9498_CR44","unstructured":"Zlotkin, G., & Rosenschein, J.S. (1989). Negotiation and task sharing among autonomous agents in cooperative domains. In Proceedings of the eleventh international joint conference on artificial intelligence (IJCAI\u201989) (pp. 912\u2013917)."}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-021-09498-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-021-09498-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-021-09498-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,21]],"date-time":"2021-04-21T09:48:14Z","timestamp":1618998494000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-021-09498-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,24]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["9498"],"URL":"https:\/\/doi.org\/10.1007\/s10458-021-09498-7","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"type":"print","value":"1387-2532"},{"type":"electronic","value":"1573-7454"}],"subject":[],"published":{"date-parts":[[2021,3,24]]},"assertion":[{"value":"9 March 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"14"}}