{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T14:00:00Z","timestamp":1760709600809,"version":"3.37.3"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,4,30]],"date-time":"2018-04-30T00:00:00Z","timestamp":1525046400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2018,4,30]],"date-time":"2018-04-30T00:00:00Z","timestamp":1525046400000},"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":"publisher","award":["15K16058","26280081"],"award-info":[{"award-number":["15K16058","26280081"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["24220003"],"award-info":[{"award-number":["24220003"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s10458-018-9386-z","type":"journal-article","created":{"date-parts":[[2018,4,30]],"date-time":"2018-04-30T09:14:34Z","timestamp":1525079674000},"page":"503-533","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Coalition structure generation in cooperative games with compact representations"],"prefix":"10.1007","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1677-1585","authenticated-orcid":false,"given":"Suguru","family":"Ueda","sequence":"first","affiliation":[]},{"given":"Atsushi","family":"Iwasaki","sequence":"additional","affiliation":[]},{"given":"Vincent","family":"Conitzer","sequence":"additional","affiliation":[]},{"given":"Naoki","family":"Ohta","sequence":"additional","affiliation":[]},{"given":"Yuko","family":"Sakurai","sequence":"additional","affiliation":[]},{"given":"Makoto","family":"Yokoo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,4,30]]},"reference":[{"key":"9386_CR1","unstructured":"Aziz, H., & de\u00a0Keijzer, B. (2011). Complexity of coalition structure generation. In Proceedings of the 10th international conference on autonomous agents and multiagent systems (AAMAS) (pp. 191\u2013198)."},{"key":"9386_CR2","unstructured":"Bistaffa, F., Farinelli, A., Cerquides, J., Rodr\u00edguez-Aguilar, J. A., & Ramchurn, S. D. (2014). Anytime coalition structure generation on synergy graphs. In Proceedings of the 13th international conference on autonomous agents and multi-agent systems (AAMAS) (pp. 13\u201320)."},{"key":"9386_CR3","doi-asserted-by":"publisher","DOI":"10.1002\/9780471225294","volume-title":"Building and solving mathematical programming models in engineering and science","author":"E Castillo","year":"2001","unstructured":"Castillo, E., Conejo, A. J., Pedregal, P., Garcia, R., & Alguacil, N. (2001). Building and solving mathematical programming models in engineering and science. New York: Wiley."},{"key":"9386_CR4","doi-asserted-by":"crossref","unstructured":"Chalkiadakis, G., Elkind, E., & Wooldridge, M. (2011). Computational aspects of cooperative game theory. Morgan and Claypool Publishers.","DOI":"10.2200\/S00355ED1V01Y201107AIM016"},{"key":"9386_CR5","unstructured":"Conitzer, V., & Sandholm, T. (2004). Computing shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. In Proceedings of the 19th national conference on artificial intelligence (AAAI) (pp. 219\u2013225)."},{"issue":"6","key":"9386_CR6","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), 607\u2013619.","journal-title":"Artificial Intelligence"},{"key":"9386_CR7","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 the 21st national conference on artificial intelligence (AAAI) (pp. 635\u2013640)."},{"issue":"2","key":"9386_CR8","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"},{"issue":"4","key":"9386_CR9","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1002\/malq.200810021","volume":"55","author":"E Elkind","year":"2009","unstructured":"Elkind, E., Goldberg, L. A., Goldberg, P. W., & Wooldridge, M. (2009). A tractable and expressive class of marginal contribution nets and its applications. Mathematical Logic Quarterly, 55(4), 362\u2013376.","journal-title":"Mathematical Logic Quarterly"},{"key":"9386_CR10","unstructured":"Gillies, D. (1953). Some theorems on n-person games. Ph.D. thesis, Princeton University."},{"issue":"12\u201313","key":"9386_CR11","doi-asserted-by":"publisher","first-page":"1877","DOI":"10.1016\/j.artint.2011.06.002","volume":"175","author":"G Greco","year":"2011","unstructured":"Greco, G., Malizia, E., Palopoli, L., & Scarcello, F. (2011). On the complexity of core, kernel, and bargaining set. Artificial Intelligence, 175(12\u201313), 1877\u20131910.","journal-title":"Artificial Intelligence"},{"key":"9386_CR12","unstructured":"Greco, G., Malizia, E., Palopoli, L., & Scarcello, F. (2011). On the complexity of the core over coalition structures. In Proceedings of the 22nd international joint conference on artificial intelligence (IJCAI) (pp. 216\u2013221)."},{"key":"9386_CR13","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J. (1999). Clique is hard to approximate within $$n^{1-\\epsilon }$$. Acta Mathematica, 182, 105\u2013142.","journal-title":"Acta Mathematica"},{"key":"9386_CR14","doi-asserted-by":"crossref","unstructured":"Ieong, S., & Shoham, Y. (2005). Marginal contribution nets: A compact representation scheme for coalitional games. In Proceedings of the 6th ACM conference on electronic commerce (ACM EC) (pp. 193\u2013202).","DOI":"10.1145\/1064009.1064030"},{"key":"9386_CR15","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.artint.2015.01.001","volume":"222","author":"A Iwasaki","year":"2015","unstructured":"Iwasaki, A., Ueda, S., Hashimoto, N., & Yokoo, M. (2015). Finding core for coalition structure utilizing dual solution. Artificial Intelligence, 222, 49\u201366.","journal-title":"Artificial Intelligence"},{"key":"9386_CR16","doi-asserted-by":"crossref","unstructured":"Leyton-Brown, K., Pearson, M., & Shoham, Y. (2000). Towards a universal test suite for combinatorial auction algorithms. In ACM EC (pp. 66\u201376).","DOI":"10.1145\/352871.352879"},{"key":"9386_CR17","unstructured":"Li, Y., & Conitzer, V. (2014). Complexity of stability-based solution concepts in multi-issue and mc-net cooperative games. In Proceedings of the 13th international conference on autonomous agents and multi-agent systems (AAMAS) (pp. 581\u2013588)."},{"key":"9386_CR18","unstructured":"Liao, X., Koshimura, M., Fujita, 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 (pp. 910\u2013915)."},{"issue":"3","key":"9386_CR19","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1287\/moor.3.3.189","volume":"3","author":"N Megiddo","year":"1978","unstructured":"Megiddo, 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":"9386_CR20","unstructured":"Michalak, T. P., Marciniak, D., Szamotulski, M., Rahwan, T., Wooldridge, M., McBurney, P., et al. (2010). A logic-based representation for coalitional games with externalities. In Proceedings of the 9th international conference on autonomous agents and multiagent systems (AAMAS) (pp. 125\u2013132)."},{"key":"9386_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":"9386_CR22","doi-asserted-by":"crossref","unstructured":"Modi, P. J., Shen, W. M., Tambe, M., & Yokoo, M. (2003). An asynchronous complete method for distributed constraint optimization. In Proceedings of the 2nd international conference on autonomous agents and multiagent systems (AAMAS) (pp. 161\u2013168).","DOI":"10.1145\/860575.860602"},{"issue":"1","key":"9386_CR23","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF01770871","volume":"6","author":"RB Myerson","year":"1977","unstructured":"Myerson, R. B. (1977). Values of games in partition function form. International Journal of Game Theory, 6(1), 23\u201331.","journal-title":"International Journal of Game Theory"},{"key":"9386_CR24","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 15th international conference on principles and practice of constraint programming (CP) (pp. 623\u2013638).","DOI":"10.1007\/978-3-642-04244-7_49"},{"key":"9386_CR25","unstructured":"Rahwan, T., & Jennings, N. R. (2008). An improved dynamic programming algorithm for coalition structure generation. In Proceedings of the 7th international conference on autonomous agents and multiagent systems (AAMAS) (pp. 1417\u20131420)."},{"key":"9386_CR26","doi-asserted-by":"crossref","unstructured":"Rahwan, T., Michalak, T. P., Elkind, E., Faliszewski, P., Sroka, J., Wooldridge, M., et al. (2011). Constrained coalition formation. In AAAI.","DOI":"10.1609\/aaai.v25i1.7888"},{"key":"9386_CR27","unstructured":"Rahwan, T., Michalak, T. P., Jennings, N. R., Wooldridge, M., & McBurney, P. (2009). Coalition structure generation in multi-agent systems with positive and negative externalities. In Proceedings of the 21st international joint conference on artificial intelligence (IJCAI) (pp. 257\u2013263)."},{"key":"9386_CR28","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"},{"key":"9386_CR29","doi-asserted-by":"crossref","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 (JAIR), 34, 521\u2013567.","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"issue":"1\u20132","key":"9386_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0004-3702(01)00159-X","volume":"135","author":"T Sandholm","year":"2002","unstructured":"Sandholm, T. (2002). Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135(1\u20132), 1\u201354.","journal-title":"Artificial Intelligence"},{"issue":"1\u20132","key":"9386_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":"1\u20132","key":"9386_CR32","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0004-3702(97)00030-1","volume":"94","author":"T Sandholm","year":"1997","unstructured":"Sandholm, T., & Lesser, V. R. (1997). Coalitions among computationally bounded agents. Artificial Intelligence, 94(1\u20132), 99\u2013137.","journal-title":"Artificial Intelligence"},{"issue":"6","key":"9386_CR33","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":"9386_CR34","unstructured":"Shapley, L. S. (1953). A value for n-person games. In Contributions to the theory of games (pp. 307\u2013317). Princeton: Princeton University Press."},{"key":"9386_CR35","doi-asserted-by":"crossref","unstructured":"Skibski, O., Michalak, T. P., Sakurai, Y., Wooldridge, M., & Yokoo, M. (2015). A graphical representation for games in partition function form. In Proceedings of the 29th AAAI conference on artificial intelligence (AAAI) (pp. 1036\u20131042).","DOI":"10.1609\/aaai.v29i1.9306"},{"issue":"1","key":"9386_CR36","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"},{"key":"9386_CR37","unstructured":"Tran-Thanh, L., Nguyen, T., Rahwan, T., Rogers, A., & Jennings, N. R. (2013). An efficient vector-based representation for coalitional games. In Proceedings of the 23rd international joint conference on artificial intelligence (IJCAI) (pp. 383\u2013389)."},{"key":"9386_CR38","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 Proceedings of the 11th international conference on autonomous agents and multiagent systems (AAMAS) (pp. 795\u2013804)."},{"key":"9386_CR39","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 the 24th AAAI conference on artificial intelligence (AAAI) (pp. 197\u2013203).","DOI":"10.1609\/aaai.v24i1.7552"},{"key":"9386_CR40","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 22nd international joint conference on artificial intelligence (IJCAI) (pp. 393\u2013399)."},{"key":"9386_CR41","volume-title":"Approximation algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V. V. (2001). Approximation algorithms. Berlin: Springer."},{"key":"9386_CR42","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1613\/jair.3715","volume":"45","author":"T Voice","year":"2012","unstructured":"Voice, T., Polukarov, M., & Jennings, N. R. (2012). Coalition structure generation over graphs. Journal of Artificial Intelligence Research (JAIR), 45, 165\u2013196.","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"9386_CR43","unstructured":"Voice, T., Ramchurn, S. D., & Jennings, N. R. (2012). On coalition formation with sparse synergies. In Proceedings of the 11th international conference on autonomous agents and multiagent systems (AAMAS) (pp. 223\u2013230)."},{"issue":"4","key":"9386_CR44","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 Numerical Mathematics, 26(4), 467\u2013474.","journal-title":"BIT Numerical Mathematics"},{"key":"9386_CR45","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D. (2007). Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing, 3, 103\u2013128.","journal-title":"Theory of Computing"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10458-018-9386-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-018-9386-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-018-9386-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,2]],"date-time":"2023-09-02T10:10:19Z","timestamp":1693649419000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10458-018-9386-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,30]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["9386"],"URL":"https:\/\/doi.org\/10.1007\/s10458-018-9386-z","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"type":"print","value":"1387-2532"},{"type":"electronic","value":"1573-7454"}],"subject":[],"published":{"date-parts":[[2018,4,30]]},"assertion":[{"value":"30 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}