{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,10,30]],"date-time":"2022-10-30T04:41:39Z","timestamp":1667104899678},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,4,19]],"date-time":"2022-04-19T00:00:00Z","timestamp":1650326400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,19]],"date-time":"2022-04-19T00:00:00Z","timestamp":1650326400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2022,10]]},"abstract":"Abstract<\/jats:title>For cooperative games with externalities, the problem of optimally partitioning a set of players into disjoint exhaustive coalitions is called coalition structure generation<\/jats:italic>, and is a fundamental computational problem in multi-agent systems. Coalition structure generation is, in general, computationally hard and a large body of work has therefore investigated the development of efficient solutions for this problem. However, the existing methods are mostly limited to deterministic environments. In this paper, we focus attention on uncertain environments. Specifically, we define probabilistically monotone partition function games<\/jats:italic>, a subclass of the well-known partition function games<\/jats:italic> in which we introduce uncertainty. We provide a constructive proof that an exact optimum can be found using a greedy approach, present an algorithm for finding an optimum, and analyze its time complexity.<\/jats:p>","DOI":"10.1007\/s10458-022-09555-9","type":"journal-article","created":{"date-parts":[[2022,4,20]],"date-time":"2022-04-20T05:04:36Z","timestamp":1650431076000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimal coalition structures for probabilistically monotone partition function games"],"prefix":"10.1007","volume":"36","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-6068-2942","authenticated-orcid":false,"given":"Shaheen","family":"Fatima","sequence":"first","affiliation":[]},{"given":"Michael","family":"Wooldridge","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,19]]},"reference":[{"key":"9555_CR1","unstructured":"Aziz, H., & de\u00a0Keijzer, B. (2011). Complexity of coalition structure generation. In Proceedings of the 10th international joint conference on AAMAS, pp. 191\u2013198."},{"key":"9555_CR2","doi-asserted-by":"publisher","first-page":"562","DOI":"10.1016\/j.geb.2013.08.006","volume":"82","author":"H Aziz","year":"2013","unstructured":"Aziz, H., Brandt, F., & Harrenstein, P. (2013). Pareto optimality in coalition formation. Games and Economic Behavior, 82, 562\u2013581.","journal-title":"Games and Economic Behavior"},{"key":"9555_CR3","doi-asserted-by":"crossref","unstructured":"Bachrach, Y., Meir, R., Jung, K., & Kohli, P. (2010). Coalitional structure generation in skill games. In Proceedings of AAAI, pp. 703\u2013708.","DOI":"10.1609\/aaai.v24i1.7620"},{"key":"9555_CR4","unstructured":"Banerjee, B., & Kraemer, L. (2010). Coalition structure generation in multi-agent systems with mixed externalities. In Proceedings of AAMAS, pp. 175\u2013182."},{"issue":"7","key":"9555_CR5","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1080\/00029890.1934.11987615","volume":"41","author":"ET Bell","year":"1934","unstructured":"Bell, E. T. (1934). Exponential numbers. The American Mathematical Monthly, 41(7), 411\u2013419.","journal-title":"The American Mathematical Monthly"},{"key":"9555_CR6","doi-asserted-by":"crossref","unstructured":"Chalkiadakis, G., Elkind, E., & Wooldridge, M. (2011). Computational aspects of cooperative game theory. Morgan & Claypool.","DOI":"10.1007\/978-3-031-01558-8"},{"key":"9555_CR7","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, 441\u2013484.","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"issue":"1","key":"9555_CR8","first-page":"179","volume":"39","author":"G Chalkiadakis","year":"2010","unstructured":"Chalkiadakis, G., Elkind, E., Markakis, E., & Jennings, N. (2010). Cooperative games with overlapping coalitions. Journal of AI Research, 39(1), 179\u2013216.","journal-title":"Journal of AI Research"},{"key":"9555_CR9","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1137\/0131029","volume":"31","author":"A Charnes","year":"1976","unstructured":"Charnes, A., & Granot, D. (1976). Coalitional and chance-constrained solutions to $$n$$-person games I. SIAM Journal of Applied Mathematics, 31, 358\u2013367.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"9555_CR10","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1287\/opre.25.6.1013","volume":"25","author":"A Charnes","year":"1977","unstructured":"Charnes, A., & Granot, D. (1977). Coalitional and chance-constrained solutions to $$n$$-person games II. Operations Research, 25, 1013\u20131019.","journal-title":"Operations Research"},{"key":"9555_CR11","doi-asserted-by":"crossref","unstructured":"Curiel, I. (1997). Cooperative game theory and applications. B. V: Springer.","DOI":"10.1007\/978-1-4757-4871-0"},{"key":"9555_CR12","unstructured":"Dang, V., Dash, R., Rogers, A., & Jennings, N. (2006). Overlapping coalition formation for efficient data fusion in multi-sensor networks. In Proceedings of the 21st National Conference on artificial intelligence (AAAI), pp. 635\u2013640."},{"key":"9555_CR13","unstructured":"de Bruijn, N. (1988). Asymptotic methods in analysis. Dover."},{"key":"9555_CR14","doi-asserted-by":"publisher","unstructured":"Dinar, A., Moretti, S., Patrone, F., & Zara, S. (2006). Application of stochastic cooperative games in water resources. In R.\u00a0Goetz, D.\u00a0Berga (Eds.) Frontiers in water resource economics. Natural Resource Management and Policy, vol.\u00a029. Springer. https:\/\/doi.org\/10.1007\/0-387-30056-2_1","DOI":"10.1007\/0-387-30056-2_1"},{"key":"9555_CR15","doi-asserted-by":"crossref","unstructured":"Epstein, D., & Bazzan, A. (2013). Distributed coalition structure generation with positive and negative externalities. In 16th Proceedings of Portugese conference on AI, pp. 408\u2013419. Springer.","DOI":"10.1007\/978-3-642-40669-0_35"},{"issue":"3","key":"9555_CR16","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1093\/comjnl\/31.3.283","volume":"31","author":"MC Er","year":"1988","unstructured":"Er, M. C. (1988). A fast algorithm for generating set partitions. The Computer Journal, 31(3), 283\u2013284.","journal-title":"The Computer Journal"},{"key":"9555_CR17","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s10458-018-9398-8","volume":"33","author":"S Fatima","year":"2019","unstructured":"Fatima, S., & Wooldridge, M. (2019). Computing optimal coalition structures in polynomial time. Journal of Autonomous Agents and Multiagent Systems, 33, 35\u201383.","journal-title":"Journal of Autonomous Agents and Multiagent Systems"},{"key":"9555_CR18","doi-asserted-by":"crossref","unstructured":"Fink, A. (2006). Supply chain coordination by means of automated negotiations between autonomous agents. In B.\u00a0Chaib-draa, J.\u00a0Muller (Eds.) Multiagent based supply chain management, pp. 351\u2013372. Springer.","DOI":"10.1007\/978-3-540-33876-5_13"},{"key":"9555_CR19","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10951-019-00630-w","volume":"23","author":"S Gawiejnowicz","year":"2020","unstructured":"Gawiejnowicz, S. (2020). A review of four decades of time-dependent scheduling: Main results, new topics, and open problems. Journal of Scheduling, 23, 3\u201347.","journal-title":"Journal of Scheduling"},{"key":"9555_CR20","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s10951-008-0064-x","volume":"11","author":"V Gordon","year":"2008","unstructured":"Gordon, V., Potts, C., Strusevich, V., & Whitehead, J. (2008). Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation. Journal of Scheduling, 11, 357\u2013370.","journal-title":"Journal of Scheduling"},{"key":"9555_CR21","unstructured":"Graham, R., Knuth, D., & Patashnik, O. (1994). Concrete mathematics. Addison Wesley."},{"key":"9555_CR22","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1287\/moor.17.4.792","volume":"17","author":"D Granot","year":"1992","unstructured":"Granot, D., & Granot, F. (1992). On some network flow games. Mathematics of Operations Research, 17, 792\u2013841.","journal-title":"Mathematics of Operations Research"},{"key":"9555_CR23","doi-asserted-by":"crossref","unstructured":"Habib, F., Polukarov, M., & Gerding, E. (2017). Optimising social welfare in multi-resource threshold task games. In Proceedings of principles and practice of multi-agent systems \u2013 20th international conference.","DOI":"10.1007\/978-3-319-69131-2_7"},{"key":"9555_CR24","doi-asserted-by":"publisher","unstructured":"Matsumara, K., Kodric., B., Okimoto, T., & Hirayama, K. (2020). Two approximation algorithms for probabilistic coalition structure generation with quality bound. Journal of Autonomous Agents and Multiagent Systems, 34(Article number: 25). https:\/\/doi.org\/10.1007\/s10458-020-09449-8.","DOI":"10.1007\/s10458-020-09449-8"},{"key":"9555_CR25","first-page":"139","volume":"230","author":"T Michalak","year":"2016","unstructured":"Michalak, T., Rahwan, T., Elkind, E., & Wooldridge, M. (2016). A hybrid exact algorithm for complete set partitioning. AI Journal, 230, 139\u2013174.","journal-title":"AI Journal"},{"key":"9555_CR26","doi-asserted-by":"crossref","unstructured":"Moyaux, T., Chaib-draa, B., & D\u2019Amours, S. (2006). Supply chain management and multiagent systems: An overview. In B.\u00a0Chaib-draa, J.\u00a0Muller (Eds.) Multiagent based supply chain management, pp. 1\u201327. Springer.","DOI":"10.1007\/978-3-540-33876-5_1"},{"key":"9555_CR27","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF01770871","volume":"6","author":"R Myerson","year":"1977","unstructured":"Myerson, R. (1977). Values of games in partition function form. International Journal of Game Theory, 6, 23\u201331.","journal-title":"International Journal of Game Theory"},{"key":"9555_CR28","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1006\/game.1994.1008","volume":"6","author":"A Nowak","year":"1994","unstructured":"Nowak, A., & Radzik, T. (1994). The shapley value for $$n$$-person games in generalized characteristic function form. Games and Economic Behavior, 6, 150\u2013161.","journal-title":"Games and Economic Behavior"},{"key":"9555_CR29","doi-asserted-by":"publisher","unstructured":"Pr\u00e4ntare, F., & Heintz, F. (2020). An anytime algorithm for optimal simultaneous coalition structure generation and assignment. Journal of Autonomous Agents and Multiagent Systems, 34. https:\/\/doi.org\/10.1007\/s10458-020-09450-1.","DOI":"10.1007\/s10458-020-09450-1"},{"key":"9555_CR30","unstructured":"Rahwan, T., & Jennings, N. R. (2008). An improved dynamic programming algorithm for coalition structure generation. In Proceedings of the seventh international joint conference on autonomous agents and multiagent systems, pp. 1417\u20131420."},{"key":"9555_CR31","first-page":"521","volume":"34","author":"T Rahwan","year":"2009","unstructured":"Rahwan, T., Ramchurn, S., Jennings, N., & Giovanucci, A. (2009). An anytime algorithm for optimal coalition structure generation. Journal of AI Research, 34, 521\u2013567.","journal-title":"Journal of AI Research"},{"key":"9555_CR32","first-page":"95","volume":"186","author":"T Rahwan","year":"2012","unstructured":"Rahwan, T., Michalak, T., Wooldridge, M., & Jennings, N. (2012). Anytime coalition structure generation in multi-agent systems with positive or negative externalities. AI Journal, 186, 95\u2013122.","journal-title":"AI Journal"},{"key":"9555_CR33","first-page":"139","volume":"229","author":"T Rahwan","year":"2015","unstructured":"Rahwan, T., Michalak, T., Wooldridge, M., & Jennings, N. (2015). Coalition structure generation: A survey. AI Journal, 229, 139\u2013174.","journal-title":"AI Journal"},{"key":"9555_CR34","doi-asserted-by":"crossref","unstructured":"Ray, D. (2007). A game-theoretic perspective on coalition formation. Oxford University Press.","DOI":"10.1093\/acprof:oso\/9780199207954.001.0001"},{"key":"9555_CR35","first-page":"209","volume":"111","author":"T Sandholm","year":"1999","unstructured":"Sandholm, T., Larson, K., Andersson, A., Shehory, O., & Tohm\u00e9, F. (1999). Coalition structure generation with worst case guarantees. AI Journal, 111, 209\u2013238.","journal-title":"AI Journal"},{"key":"9555_CR36","doi-asserted-by":"crossref","unstructured":"Shapley, L. (1953). A value for $$n$$-person games. In: H.\u00a0Kuhn, A.\u00a0Tucker (Eds.) Contributions to the theory of games, volume II, pp. 307\u2013317. Princeton University Press.","DOI":"10.1515\/9781400881970-018"},{"key":"9555_CR37","unstructured":"Shrot, T., Auman, Y., & Kraus, S. (2010). On agent types in coalition formation problems. In Proceedings of AAMAS, pp. 757\u2013764."},{"key":"9555_CR38","doi-asserted-by":"crossref","unstructured":"Suijs, J., Waegenaere, A., & Borm, P. (1998). Stochastic cooperative games in insurance. Insurance: Mathematics and Economics, 22(3\u20134), 209\u2013228.","DOI":"10.1016\/S0167-6687(97)00038-3"},{"key":"9555_CR39","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-1190-4","volume-title":"Scheduling theory: Single-stage systems","author":"V Tanaev","year":"1994","unstructured":"Tanaev, V., Gordon, V., & Shafransky, Y. (1994). Scheduling theory: Single-stage systems. Dordrecht: Kluwer."},{"key":"9555_CR40","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1002\/nav.3800100126","volume":"10","author":"R Thrall","year":"1963","unstructured":"Thrall, R., & Lucas, W. (1963). $$n$$-person games in partition function form. Naval Research Logistics Quarerly, 10, 281\u2013298.","journal-title":"Naval Research Logistics Quarerly"},{"key":"9555_CR41","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. Journal of Autonomous Agents and Multiagent Systems, 32, 503\u2013533.","journal-title":"Journal of Autonomous Agents and Multiagent Systems"},{"issue":"4","key":"9555_CR42","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 Numerical Mathematics, 26(4), 467\u2013474.","journal-title":"BIT Numerical Mathematics"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-022-09555-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10458-022-09555-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-022-09555-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T12:48:49Z","timestamp":1667047729000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10458-022-09555-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,19]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["9555"],"URL":"https:\/\/doi.org\/10.1007\/s10458-022-09555-9","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,19]]},"assertion":[{"value":"15 March 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"27"}}