{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T14:01:46Z","timestamp":1760709706449,"version":"3.41.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2018,9,11]],"date-time":"2018-09-11T00:00:00Z","timestamp":1536624000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"JSPS KAKENHI","award":["JP16K00304","JP17K00307"],"award-info":[{"award-number":["JP16K00304","JP17K00307"]}]},{"name":"Youth Innovation Research Group of Sichuan Province","award":["2015TD0020"],"award-info":[{"award-number":["2015TD0020"]}]},{"name":"the Ministry of Education in China Project of Humanities and Social Sciences","award":["17YJCZH260"],"award-info":[{"award-number":["17YJCZH260"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2019,1]]},"DOI":"10.1007\/s10601-018-9295-4","type":"journal-article","created":{"date-parts":[[2018,9,11]],"date-time":"2018-09-11T04:23:17Z","timestamp":1536639797000},"page":"25-55","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Improved WPM encoding for coalition structure generation under MC-nets"],"prefix":"10.1007","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6548-2256","authenticated-orcid":false,"given":"Xiaojuan","family":"Liao","sequence":"first","affiliation":[]},{"given":"Miyuki","family":"Koshimura","sequence":"additional","affiliation":[]},{"given":"Kazuki","family":"Nomoto","sequence":"additional","affiliation":[]},{"given":"Suguru","family":"Ueda","sequence":"additional","affiliation":[]},{"given":"Yuko","family":"Sakurai","sequence":"additional","affiliation":[]},{"given":"Makoto","family":"Yokoo","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,9,11]]},"reference":[{"key":"9295_CR1","unstructured":"Alviano, M., Dodaro, C., Ricca, F. (2015). A maxsat algorithm using cardinality constraints of bounded size. In IJCAI (pp. 2677\u20132683)."},{"key":"9295_CR2","unstructured":"Argelich, J., Li, C.M., Many, F., Planes, J. (2016). Max-sat 2016: Eleventh max-sat evaluation. http:\/\/maxsat.ia.udl.cat\/introduction\/ ."},{"key":"9295_CR3","volume-title":"Handbook of satisfiability, Vol. 185","author":"A Biere","year":"2009","unstructured":"Biere, A., Heule, M., van Maaren, H. (2009). Handbook of satisfiability Vol. 185. Amsterdam: IOS press."},{"issue":"6","key":"9295_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2200\/S00355ED1V01Y201107AIM016","volume":"5","author":"G Chalkiadakis","year":"2011","unstructured":"Chalkiadakis, G., Elkind, E., Wooldridge, M. (2011). Computational aspects of cooperative game theory. Synthesis Lectures on Artificial Intelligence and Machine Learning, 5(6), 1\u2013168.","journal-title":"Synthesis Lectures on Artificial Intelligence and Machine Learning"},{"issue":"6-7","key":"9295_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-7), 607\u2013619.","journal-title":"Artificial Intelligence"},{"key":"9295_CR6","unstructured":"Cook, S.A. (1971). The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing (pp. 151\u2013158). New York : ACM."},{"issue":"5","key":"9295_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/cpe.3969","volume":"29","author":"F Cruz","year":"2017","unstructured":"Cruz, F., Espinosa, A., Moure, J.C., Cerquides, J., Rodriguez-Aguilar, J.A., Svensson, K., Ramchurn, S.D. (2017). Coalition structure generation problems: optimization and parallelization of the idp algorithm in multicore systems. Concurrency and Computation: Practice and Experience, 29(5), 1\u201320.","journal-title":"Concurrency and Computation: Practice and Experience"},{"key":"9295_CR8","unstructured":"Davies, J., & Bacchus, F. (2013). Exploiting the power of mip solvers in maxsat. In International conference on theory and applications of satisfiability testing (pp. 166\u2013181). Berlin: Springer."},{"issue":"4","key":"9295_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"},{"issue":"1","key":"9295_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.V. (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":"9295_CR11","unstructured":"Hussin, A., & Fatima, S. (2016). Heuristic methods for optimal coalition structure generation. In Multi-agent systems and agreement technologies (pp. 124\u2013139). Berlin: Springer."},{"key":"9295_CR12","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 (pp. 193\u2013202). New York: ACM."},{"key":"9295_CR13","doi-asserted-by":"crossref","first-page":"95","DOI":"10.3233\/SAT190091","volume":"8","author":"M Koshimura","year":"2012","unstructured":"Koshimura, M., Zhang, T., Fujita, H., Hasegawa, R. (2012). Qmaxsat: a partial max-sat solver. Journal on Satisfiability, Boolean Modeling and Computation, 8, 95\u2013100.","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"9295_CR14","doi-asserted-by":"crossref","first-page":"59","DOI":"10.3233\/SAT190075","volume":"7","author":"D Le Berre","year":"2010","unstructured":"Le Berre, D., & Parrain, A. (2010). The sat4j library, release 2.2, system description. Journal on Satisfiability, Boolean Modeling and Computation, 7, 59\u201364.","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"issue":"1","key":"9295_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dss.2009.12.002","volume":"49","author":"C Li","year":"2010","unstructured":"Li, C., Sycara, K., Scheller-Wolf, A. (2010). Combinatorial coalition formation for multi-item group-buying with heterogeneous customers. Decision Support Systems, 49(1), 1\u201313.","journal-title":"Decision Support Systems"},{"issue":"1","key":"9295_CR16","first-page":"613","volume":"185","author":"CM Li","year":"2009","unstructured":"Li, C.M., & Many\u00e0, F. (2009). Maxsat, hard and soft constraints. Frontiers in Artificial Intelligence & Applications, 185(1), 613\u2013631.","journal-title":"Frontiers in Artificial Intelligence & Applications"},{"key":"9295_CR17","unstructured":"Liao, X., Koshimura, M., Fujita, H., Hasegawa, R. (2012). Solving the coalition structure generation problem with maxsat. In 2012 IEEE 24th international conference on Tools with artificial intelligence (ICTAI), (Vol. 1 pp. 910\u2013915). Piscataway: IEEE."},{"issue":"7","key":"9295_CR18","doi-asserted-by":"publisher","first-page":"1812","DOI":"10.1587\/transinf.E97.D.1812","volume":"97","author":"X Liao","year":"2014","unstructured":"Liao, X., Koshimura, M., Fujita, H., Hasegawa, R. (2014). Extending maxsat to solve the coalition structure generation problem with externalities based on agent relations. IEICE Transactions on Information and Systems, 97(7), 1812\u20131821.","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"7","key":"9295_CR19","doi-asserted-by":"publisher","first-page":"1781","DOI":"10.1587\/transinf.E97.D.1781","volume":"97","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, 97(7), 1781\u20131789.","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"6","key":"9295_CR20","doi-asserted-by":"publisher","first-page":"1136","DOI":"10.1007\/s11390-016-1688-5","volume":"31","author":"Y Liu","year":"2016","unstructured":"Liu, Y., Zhang, G.F., Su, Z.P., Yue, F., Jiang, J.G. (2016). Using computational intelligence algorithms to solve the coalition structure generation problem in coalitional skill games. Journal of Computer Science and Technology, 31(6), 1136\u20131150.","journal-title":"Journal of Computer Science and Technology"},{"key":"9295_CR21","unstructured":"Michalak, T., Marciniak, D., Szamotulski, M., Rahwan, T., Wooldridge, M., McBurney, P., Jennings, N.R. (2010). A logic-based representation for coalitional games with externalities. In Proceedings of the 9th international conference on autonomous agents and multiagent systems: volume 1-Volume 1, International Foundation for Autonomous Agents and Multiagent Systems (pp. 125\u2013132)."},{"issue":"C","key":"9295_CR22","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(C), 14\u201350.","journal-title":"Artificial Intelligence"},{"issue":"2","key":"9295_CR23","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1287\/opre.1120.1139","volume":"61","author":"E Moreno-Centeno","year":"2013","unstructured":"Moreno-Centeno, E., & Karp, R.M. (2013). The implicit hitting set approach to solve combinatorial optimization problems with an application to multigenome alignment. Operations Research, 61(2), 453\u2013468.","journal-title":"Operations Research"},{"key":"9295_CR24","unstructured":"Ohta, N., Conitzer, V., Ichimura, R., Sakurai, Y., Iwasaki, A., Yokoo, M. (2009). Coalition structure generation utilizing compact characteristic function representations. In International Conference on Principles and Practice of Constraint Programming (pp. 623\u2013638). Berlin: Springer."},{"key":"9295_CR25","unstructured":"Rahwan, T., & Jennings, N.R. (1417). An improved dynamic programming algorithm for coalition structure generation. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems-Volume 3, International Foundation for Autonomous Agents and Multiagent Systems."},{"key":"9295_CR26","doi-asserted-by":"crossref","unstructured":"Rahwan, T., Michalak, T.P., Elkind, E., Faliszewski, P., Sroka, J., Wooldridge, M., Jennings, N.R. (2011). Constrained coalition formation. In AAAI, (Vol. 11 pp. 719\u2013725).","DOI":"10.1609\/aaai.v25i1.7888"},{"key":"9295_CR27","unstructured":"Rahwan, T., Michalak, T.P., Jennings, N.R. (2012). A hybrid algorithm for coalition structure generation. In AAAI (pp. 1443\u20131449)."},{"key":"9295_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":"9295_CR29","unstructured":"Saikko, P., Berg, J., J\u00e4rvisalo, M. (2016). Lmhs: a sat-ip hybrid maxsat solver. In International conference on theory and applications of satisfiability testing (pp. 539\u2013546). Berlin: Springer."},{"key":"9295_CR30","unstructured":"Saikko, P., Wallner, J.P., J\u00e4rvisalo, M. (2016). Implicit hitting set algorithms for reasoning beyond np. In KR (pp. 104\u2013113)."},{"issue":"6","key":"9295_CR31","doi-asserted-by":"publisher","first-page":"1121","DOI":"10.1587\/transinf.2014FOP0007","volume":"98","author":"M Sakai","year":"2015","unstructured":"Sakai, M., & Nabeshima, H. (2015). Construction of an robdd for a pb-constraint in band form and related techniques for pb-solvers. IEICE Transactions on Information and Systems, 98(6), 1121\u20131127.","journal-title":"IEICE Transactions on Information and Systems"},{"issue":"1-2","key":"9295_CR32","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-2), 165\u2013200.","journal-title":"Artificial intelligence"},{"key":"9295_CR33","doi-asserted-by":"crossref","unstructured":"Skibski, O., Michalewski, H., Nag\u00f3rko, A., Michalak, T.P., Dowell, A.J., Rahwan, T., Wooldridge, M. (2016). Non-utilitarian coalition structure generation. In ECAI (pp. 1738\u20131739).","DOI":"10.3233\/978-1-61499-672-9-1738"},{"key":"9295_CR34","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-Volume 2, International Foundation for Autonomous Agents and Multiagent Systems (pp. 795\u2013804)."},{"key":"9295_CR35","doi-asserted-by":"publisher","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. https:\/\/doi.org\/10.1007\/s10458-018-9386-z .","DOI":"10.1007\/s10458-018-9386-z"},{"key":"9295_CR36","unstructured":"Yang, G., Esmailpour, A., Cao, Y., Nasser, N. (2016). A novel coalitional structure generation algorithm for interference mitigation in small cell networks. In Global communications conference (GLOBECOM), 2016 IEEE (pp. 1\u20134). Piscataway: IEEE."},{"issue":"4","key":"9295_CR37","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"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-018-9295-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-018-9295-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-018-9295-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T01:54:23Z","timestamp":1751853263000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-018-9295-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,11]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["9295"],"URL":"https:\/\/doi.org\/10.1007\/s10601-018-9295-4","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"type":"print","value":"1383-7133"},{"type":"electronic","value":"1572-9354"}],"subject":[],"published":{"date-parts":[[2018,9,11]]},"assertion":[{"value":"11 September 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}