{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,22]],"date-time":"2026-07-22T13:24:14Z","timestamp":1784726654701,"version":"3.55.0"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2018,11,3]],"date-time":"2018-11-03T00:00:00Z","timestamp":1541203200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000857","name":"Loughborough University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000857","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":[[2019,3]]},"DOI":"10.1007\/s10458-018-9398-8","type":"journal-article","created":{"date-parts":[[2018,11,3]],"date-time":"2018-11-03T03:09:41Z","timestamp":1541214581000},"page":"35-83","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Computing optimal coalition structures in polynomial time"],"prefix":"10.1007","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6068-2942","authenticated-orcid":false,"given":"Shaheen","family":"Fatima","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Wooldridge","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,11,3]]},"reference":[{"key":"9398_CR1","doi-asserted-by":"crossref","unstructured":"Aziz, H., & de Keijzer, B. (2011). Complexity of coalition structure generation. In Proceedings of the 10th international joint conference on AAMAS (pp. 191\u2013198).","DOI":"10.65109\/KVYX5768"},{"key":"9398_CR2","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":"9398_CR3","doi-asserted-by":"crossref","unstructured":"Banerjee, B., & Kraemer, L. (2010). Coalition structure generation in multi-agent systems with mixed externalities. In Proceedings of AAMAS (pp. 175\u2013182).","DOI":"10.65109\/GRTP2392"},{"issue":"7","key":"9398_CR4","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":"9398_CR5","doi-asserted-by":"crossref","unstructured":"Bitar, E., Baeyens, E., Khargonekar, P., Varaiya, P., & Poolla, K. (2012). Optimal sharing of quantity risk for a coalition of wind power producers facing nodal prices. In Proceedings of the 31st IEEE American control conference (pp. 4438\u20134445).","DOI":"10.1109\/ACC.2012.6315524"},{"key":"9398_CR6","volume-title":"Scheduling algorithms","author":"P Brucker","year":"2007","unstructured":"Brucker, P. (2007). Scheduling algorithms. Berlin: Springer."},{"key":"9398_CR7","doi-asserted-by":"publisher","DOI":"10.2200\/S00355ED1V01Y201107AIM016","volume-title":"Computational aspects of cooperative game theory","author":"G Chalkiadakis","year":"2011","unstructured":"Chalkiadakis, G., Elkind, E., & Wooldridge, M. (2011). Computational aspects of cooperative game theory. San Rafael: Morgan & Claypool."},{"key":"9398_CR8","first-page":"381","volume":"27","author":"V Conitzer","year":"2006","unstructured":"Conitzer, V., & Sandholm, T. (2006). Complexity of constructing solutions in the core based on synergies among coalitions. AI Journal, 27, 381\u2013417.","journal-title":"AI Journal"},{"key":"9398_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-4871-0","volume-title":"Cooperative game theory and applications","author":"I Curiel","year":"1997","unstructured":"Curiel, I. (1997). Cooperative game theory and applications. Berlin: Springer."},{"key":"9398_CR10","volume-title":"Asymptotic methods in analysis","author":"N Bruijn de","year":"1988","unstructured":"de Bruijn, N. (1988). Asymptotic methods in analysis. Illinois: Dover."},{"issue":"6","key":"9398_CR11","doi-asserted-by":"publisher","first-page":"1413","DOI":"10.3982\/ECTA7224","volume":"76","author":"G Clippel De","year":"2008","unstructured":"De Clippel, G., & Serrano, R. (2008). Marginal contributions and externalities in the value. Econometrica, 76(6), 1413\u20131436.","journal-title":"Econometrica"},{"key":"9398_CR12","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-540-33876-5_13","volume-title":"Multiagent based supply chain management","author":"A Fink","year":"2006","unstructured":"Fink, A. (2006). Supply chain coordination by means of automated negotiations between autonomous agents. In B. Chaib-draa & J. Muller (Eds.), Multiagent based supply chain management (pp. 351\u2013372). Berlin: Springer."},{"key":"9398_CR13","doi-asserted-by":"crossref","unstructured":"Garg, J., Mehta, R., & Vazirani, V. (2014). Dichotomies in equilibrium computation and complementary pivot algorithms for a new class of non-separable utility functions. In Proceedings of STOC.","DOI":"10.1145\/2591796.2591863"},{"key":"9398_CR14","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, 203\u2013213.","journal-title":"IEEE Transactions on Communications"},{"key":"9398_CR15","volume-title":"Automated negotiation in multi-agent based electronic business: Negotiation in business-to-business transactions in supply chain management for multi-agent based electronic business","author":"G Huq","year":"2010","unstructured":"Huq, G. (2010). Automated negotiation in multi-agent based electronic business: Negotiation in business-to-business transactions in supply chain management for multi-agent based electronic business. Muller: VDM Verlag Dr."},{"key":"9398_CR16","doi-asserted-by":"crossref","unstructured":"Ieong, S., & Shoham, Y. (2005). Marginal contribution nets: A compact representation scheme for coalitional games. In Proceedings of the ACM Conference on Electronic Commerce (pp. 193\u2013202).","DOI":"10.1145\/1064009.1064030"},{"key":"9398_CR17","unstructured":"Keinanen, H. (2009). Simulated annealing for multi-agent coalition formation. In Proceedings of the Third KES international symposium on agent and multiagent systems: Technologies and applications KES-AMSTA (pp. 30\u201339)."},{"key":"9398_CR18","unstructured":"Lin, C. (1975). Corporate tax structures and a special class of set partitioning problems. PhD thesis, Case Western Reserve University."},{"issue":"4","key":"9398_CR19","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1287\/mnsc.25.4.405","volume":"25","author":"C Lin","year":"1979","unstructured":"Lin, C., & Salkin, H. (1979). Aggregation of subsidiary firms for minimal unemployment compensation payments via integer programming. Management Science, 25(4), 405\u2013408.","journal-title":"Management Science"},{"key":"9398_CR20","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0166-218X(83)90069-0","volume":"6","author":"C Lin","year":"1983","unstructured":"Lin, C., & Salkin, H. (1983). An efficient algorithm for the complete set partitioning problem. Discrete Applied Mathematics, 6, 149\u2013156.","journal-title":"Discrete Applied Mathematics"},{"key":"9398_CR21","unstructured":"Di Mauro, N., Basile, T., Ferilli, S., & Esposito, F. (2010). Coalition structure generation with grasp. In Proceedings of the fourteenth international conference on AI: Methodology, systems and applications (pp. 111\u2014120)."},{"key":"9398_CR22","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":"9398_CR23","doi-asserted-by":"crossref","unstructured":"Michalak, T., Sroka, J., Rahwan, T., Wooldridge, M., McBurney, P., & Jennings, N. (2010). A distributed algorithm for anytime coalition structure generation. In Proceedings of AAMAS (pp. 17\u2013114).","DOI":"10.65109\/BHAT3920"},{"key":"9398_CR24","first-page":"1","volume-title":"Multiagent based supply chain management","author":"T Moyaux","year":"2006","unstructured":"Moyaux, T., Chaib-draa, B., & D\u2019Amours, S. (2006). Supply chain management and multiagent systems: An overview. In B. Chaib-draa & J. Muller (Eds.), Multiagent based supply chain management (pp. 1\u201327). Berlin: Springer."},{"key":"9398_CR25","volume-title":"Scheduling: Theory, algorithms and systems","author":"M Pinedo","year":"2008","unstructured":"Pinedo, M. (2008). Scheduling: Theory, algorithms and systems. Berlin: Springer."},{"key":"9398_CR26","doi-asserted-by":"crossref","unstructured":"Rahwan, T., & Jennings, N.\u00a0R. (2008). An improved dynamic programming algorithm for coalition structure generation. In In Proceedings of the seventh international joint conference on autonomous agents and multiagent systems (pp. 1417\u20131420).","DOI":"10.65109\/XSMA8286"},{"key":"9398_CR27","unstructured":"Rahwan, T., Michalak, T., Jennings, N.R., Wooldridge, M., & McBurney, P. (2009). Coalition structure generation in multi-agent systems with positive and negative externalities. In In Proceedings of the 21st international joint conference on AI."},{"key":"9398_CR28","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":"9398_CR29","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":"9398_CR30","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199207954.001.0001","volume-title":"A game-theoretic perspective on coalition formation","author":"D Ray","year":"2007","unstructured":"Ray, D. (2007). A game-theoretic perspective on coalition formation. Oxford: Oxford University Press."},{"issue":"5","key":"9398_CR31","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1080\/00029890.1964.11992270","volume":"71","author":"G Rota","year":"1964","unstructured":"Rota, G. (1964). The number of partitions of a set. American Mathematical Monthly, 71(5), 498\u2013504.","journal-title":"American Mathematical Monthly"},{"issue":"8","key":"9398_CR32","doi-asserted-by":"publisher","first-page":"1131","DOI":"10.1287\/mnsc.44.8.1131","volume":"44","author":"M Rothkopf","year":"1998","unstructured":"Rothkopf, M., Pekec, A., & Harstad, R. (1998). Computationally manageable combinatorial auctions. Management Science, 44(8), 1131\u20131147.","journal-title":"Management Science"},{"key":"9398_CR33","first-page":"1","volume":"135","author":"T Sandholm","year":"2002","unstructured":"Sandholm, T. (2002). Algorithm for optimal winner determination in combinatorial auctions. AI Journal, 135, 1\u201354.","journal-title":"AI Journal"},{"key":"9398_CR34","first-page":"209","volume":"111","author":"T Sandholm","year":"1999","unstructured":"Sandholm, T., Larson, K., Anderson, A., Shehory, O., & Tohme, F. (1999). Coalition structure generation with worst case guarantees. AI Journal, 111, 209\u2013238.","journal-title":"AI Journal"},{"key":"9398_CR35","doi-asserted-by":"crossref","unstructured":"Sen, S., & Dutta, P. (2000). Searching for optimal coalition structures. In Proceedings of ICMAS (pp. 286\u2013292).","DOI":"10.1109\/ICMAS.2000.858465"},{"key":"9398_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10458-010-9124-7","volume":"23","author":"T. Service and J. Adams","year":"2011","unstructured":"T. Service and J. Adams. (2011). Constant factor approximation algorithms for coalition structure generation. Journal of Autonomous Agents and MultiAgent Systems, 23, 1\u201317.","journal-title":"Journal of Autonomous Agents and MultiAgent Systems"},{"issue":"1\u20132","key":"9398_CR37","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 Journal, 101(1\u20132), 165\u2013200.","journal-title":"Artificial Intelligence Journal"},{"issue":"12","key":"9398_CR38","doi-asserted-by":"publisher","first-page":"1104","DOI":"10.1109\/TC.1980.1675516","volume":"C\u201329","author":"R Smith","year":"1980","unstructured":"Smith, R. (1980). The contract net protocol: High level communication and control in a distributed problem solver. IEEE Transactions on Computers, C\u201329(12), 1104\u20131113.","journal-title":"IEEE Transactions on Computers"},{"key":"9398_CR39","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780199563074.001.0001","volume-title":"Introduction to metric and topological spaces","author":"W Sutherland","year":"2009","unstructured":"Sutherland, W. (2009). Introduction to metric and topological spaces. Oxford: Oxford University Press."},{"key":"9398_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$$ n -Person games in partition function form. Naval Research Logistics Quarerly, 10, 281\u2013298.","journal-title":"Naval Research Logistics Quarerly"},{"key":"9398_CR41","doi-asserted-by":"crossref","unstructured":"Ueda, S., Iwasaki, A., & Yokoo, M. (2010). Coalition structure generation based on distributed constraint optimization. In Proceedings of AAAI (pp. 155\u2013168).","DOI":"10.1609\/aaai.v24i1.7552"},{"key":"9398_CR42","doi-asserted-by":"crossref","unstructured":"Ueda, S., Iwasaki, A., & Yokoo, M. (2011). Concise characteristic function representations in coalitional games based on agent types. In Proceedings of IJCAI (pp. 393\u2013399).","DOI":"10.65109\/NRFX1652"},{"issue":"4","key":"9398_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 Numerical Mathematics, 26(4), 467\u2013474.","journal-title":"BIT Numerical Mathematics"},{"key":"9398_CR44","first-page":"80","volume-title":"The endogenous formation of economic coalitions","author":"S Yi","year":"2003","unstructured":"Yi, S. (2003). Endogenous formation of economic coalitions: A survey on the partition function approach. In C. Carraro (Ed.), The endogenous formation of economic coalitions (pp. 80\u2013127). London: Edward Elgar."}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-018-9398-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10458-018-9398-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-018-9398-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T23:19:44Z","timestamp":1775258384000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10458-018-9398-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,3]]},"references-count":44,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2019,3]]}},"alternative-id":["9398"],"URL":"https:\/\/doi.org\/10.1007\/s10458-018-9398-8","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,3]]},"assertion":[{"value":"3 November 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}