[1]任子仪,童向荣.约束条件下联盟生成研究进展[J].智能系统学报,2019,14(3):413-422.[doi:10.11992/tis.201804054]
REN Ziyi,TONG Xiangrong.Research progress of constrained coalition formation[J].CAAI Transactions on Intelligent Systems,2019,14(3):413-422.[doi:10.11992/tis.201804054]
点击复制
REN Ziyi,TONG Xiangrong.Research progress of constrained coalition formation[J].CAAI Transactions on Intelligent Systems,2019,14(3):413-422.[doi:10.11992/tis.201804054]
约束条件下联盟生成研究进展
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
14
期数:
2019年第3期
页码:
413-422
栏目:
综述
出版日期:
2019-05-05
- Title:
- Research progress of constrained coalition formation
- Keywords:
- coalition structure; social welfare; coalition formation; constraint; characteristic function; coalition structure graph; coalition game; dynamic programming
- 分类号:
- TP18
- 摘要:
- 联盟生成是在多Agent系统的研究中最为重要的挑战之一。如何对Agent进行划分使所得社会福利最大化是当前面临的主要问题。假设每个Agent都具有理性和自利性的特性，为了追求自身的利益最大化而选择和其他的Agent进行联合，进而使整个系统实现利益的最大化。目前，联盟生成问题有很大的计算挑战，即使在进行联盟的时候添加了约束条件，也需要新的算法来更快更有效地解决该问题。本文主要对约束条件下的联盟生成的研究进行综述，主要包括4部分：最坏情况有限界联盟生成、动态规划联盟生成求精确最优解、联盟生成求近似最优解和约束条件下联盟生成求最优解。
- Abstract:
- Coalition formation is one of the most important challenges in the research of multiagent systems. Currently, our main problem is how to divide Agent to maximize the social welfare. We assume that each Agent possesses the characteristics of rationality and self-interest to maximize its own interests. An Agent integrates with another Agent, which also maximizes the interest of the whole system. At present, the coalition formation problem presents notable computational challenges. If constraints are added during the coalition process, new algorithms are needed to solve the problem more rapidly and effectively. This paper mainly summarizes the study of coalition structure generation under constraint conditions. This paper comprises four parts:the coalition structure generation with the worst case guaranteed, the use of the dynamic programming to find the exact optimal solution, the near-optimal solution after formation of the coalition structure, and the optimal solution to the constrained coalition formation.
- 参考文献/References:
-
[1] AZIZ H. Multiagent systems:algorithmic, game-theoretic, and logical foundations by Y. Shoham and K. Leyton-Brown Cambridge University Press, 2008[J]. ACM SIGACT news, 2010, 41(1):34-37.
[2] WOOLDRIDGE M. Computational aspects of cooperative game theory[C]//Proceedings of the 5th KES International Conference on Agent and Multi-Agent Systems:Technologies and Applications. Manchester, UK, 2011.
[3] ELKIND E, RAHWAN T, JENNINGS N R. Computational coalition formation[M]. Cambridge:MIT Press, 2013:329-380.
[4] OSBORNE M J, RUBINSTEIN A. A course in game theory[M]. Cambridge:MIT Press, 1994.
[5] VON NEUMANN J, MORGENSTERN O. Theory of games and economic behavior[M]. Princeton:Princeton University Press, 1972.
[6] WOOLDRIDGE M, BUSSMANN S, KLOSTERBERG M. Production sequencing as negotiation[C]//Proceedings of the First International Conference on the Practical Application of Intelligent Agents and Multi-Agent Technology. London, UK, 1996:709-726.
[7] SANDHOLM T, SIKKA S, NORDEN S. Algorithms for optimizing leveled commitment contracts[C]//Proceedings of the 16th International Joint Conference on Artifical Intelligence. Stockholm, Sweden, 1999:535-540.
[8] RAHWAN T, MICHALAK T P, WOOLDRIDGE M, et al. Coalition structure generation:a survey[J]. Artificial intelligence, 2015, 229:139-174.
[9] ZHU Han, POOR H V. Coalition games with cooperative transmission:a cure for the curse of boundary nodes in selfish packet-forwarding wireless networks[C]//Proceedings of the 5th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks and Workshops. Limasso, Cyprus, 2009:1-8.
[10] KHAN Z, LEHTOM?KI J, LATVA-AHO M, et al. On selfish and altruistic coalition formation in cognitive radio networks[C]//Proceedings of the 2010 Fifth International Conference on Cognitive Radio Oriented Wireless Networks and Communications. Cannes, France, 2010:1-5.
[11] LI Cuihong, SYCARA K, SCHELLER-WOLF A. Combinatorial coalition formation for multi-item group-buying with heterogeneous customers[J]. Decision support systems, 2010, 49(1):1-13.
[12] MANOOCHEHRI H E, WENKSTERN R Z. Dynamic coalition structure generation for autonomous connected vehicles[C]//Proceedings of 2017 IEEE International Conference on Agents. Beijing, China, 2017:21-26.
[13] SLESS L, HAZON N, KRAUS S, et al. Forming k coalitions and facilitating relationships in social networks[J]. Artificial intelligence, 2018, 259:217-245.
[14] SLESS L, HAZON N, KRAUS S, et al. Forming coalitions and facilitating relationships for completing tasks in social networks[C]//Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems. Paris, France, 2014:261-268.
[15] SANDHOLM T, LARSON K, ANDERSSON M, et al. Coalition structure generation with worst case guarantees[J]. Artificial intelligence, 1999, 111(1/2):209-238.
[16] YEH D Y. A dynamic programming approach to the complete set partitioning problem[J]. BIT numerical mathematics, 1986, 26(4):467-474.
[17] DANG T T, FRANKOVIE B, BUDINNSKA I. Create agent’s coalition based on a dynamic programming approach[C]//Proceedings of the 15th European Conference on Artificial Intelligence, Workshop "Agent Technologies and Logistics". Lyon, France, 2002:16-24.
[18] GRECO G, GUZZO A. Constrained coalition formation on valuation structures:formal framework, applications, and islands of tractability[J]. Artificial intelligence, 2017, 249:19-46.
[19] 童向荣, 张伟. 动态联盟收益值的再励学习[J]. 计算机工程与应用, 2006, 42(6):85-87 TONG Xiangrong, ZHANG Wei. Reinforcement learning for the value of dynamic coalition[J]. Computer engineering and application, 2006, 42(6):85-87
[20] DEAN T, BODDY M. An analysis of time-dependent planning[C]//Proceedings of the 7th National Conference on Artificial Intelligence. St. Paul, Brazil, 1988:49-54.
[21] BRUALDI R A. 组合数学[M]. 冯舜玺, 译. 5版. 北京:机械工业出版社, 2012:180-186. BRUALDI R A. Introductory combinatorics[M]. FENG Shunxi, trans. 5th ed. Beijing:China Machine Press, 2012:180-186.
[22] KARP R M. Reducibility among combinatorial problems[C]//Complexity of Computer Computations. New York, USA, 1972:85-103.
[23] HASTAD J. Clique is hard to approximate within n1-ε[J]. Acta mathematica, 1999, 182(1):105-142.
[24] SANDHOLM T. An algorithm for optimal winner determination in combinatorial auction[C]//Proceedings of the Sixteenth International joint conference on artificial intelligence. Stockholm, Sweden, 1999:542-547.
[25] LINIAL N. Game-theoretic aspects of computing[M]//AUMANN R J, HART S. Handbook of Game Theory with Economic Applications. Amsterdam, Netherlands:Elsevier, 1994:1339-1395.
[26] LARSON K S, SANDHOLM T W. Anytime coalition structure generation:an average case study[J]. Journal of experimental & theoretical artificial intelligence, 2000, 12(1):23-42.
[27] 胡山立, 石纯一. 一种任一时间联盟结构生成算法[J]. 软件学报, 2001, 12(5):729-734 HU Shanli, SHI Chunyi. An anytime coalition structure generation algorithm[J]. Journal of software, 2001, 12(5):729-734
[28] 胡山立, 石纯一. 给定限界要求的联盟结构生成[J]. 计算机学报, 2001, 24(11):1185-1190 HU Shanli, SHI Chunyi. Coalition structure generation with given required bound[J]. Chinese journal of computers, 2001, 24(11):1185-1190
[29] DANG V D, JENNINGS N R. Generating coalition structures with finite bound from the optimal guarantees[C]//Proceedings of 3rd International Joint Conference on Autonomous Agents and Multiagent Systems. New York, USA, 2004:564-571.
[30] ROTHKOPF M H, PEKE? A, HARSTAD R M. Computationally manageable combinational auctions[J]. Management science, 1998, 44(8):1131-1147.
[31] 刘惊雷, 童向荣, 张伟. 一种快速构建最优联盟结构的方法[J]. 计算机工程与应用, 2006, 42(4):35-37, 44 LIU Jinglei, TONG Xiangrong, ZHANG Wei. A kind of method for quick constructing optimal coalition structure[J]. Computer engineering and applications, 2006, 42(4):35-37, 44
[32] RAHWAN T, MICHALAK T P, ELKIND E, et al. Constrained coalition formation[C]//Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. San Francisco, USA, 2011:719-725.
[33] 张新良, 石纯一. 多Agent联盟结构动态生成算法[J]. 软件学报, 2007, 18(3):574-581 ZHANG Xinliang, SHI Chunyi. A dynamic formation algorithm of multi-agent coalition structure[J]. Journal of software, 2007, 18(3):574-581
[34] RAHWAN T, RAMCHURN S D, DANG V D, et al. Near-optimal anytime coalition structure generation[C]//Proceedings of the 20th International Joint Conference on Artificial Intelligence. Hyderabad, India, 2007:2365-2371.
[35] ALBIZURI M J, AURRECOECHEA J, ZARZUELO J M. Configuration values:extensions of the coalitional Owen value[J]. Games and economic behavior, 2006, 57(1):1-17.
[36] RAHWAN T, JENNINGS N R. Distributing coalitional value calculations among cooperative agents[C]//Proceedings of the 20th National Conference on Artificial Intelligence. Pittsburgh, Pennsylvania, 2005:152-157.
[37] FRANKOVI B, DANG T, BUDINSKá I. Agents’ coalitions based on a dynamic programming approach[J]. Acta polytechnica hungarica, 2008, 5(2):5-21.
[38] IEONG S, SHOHAM Y. Marginal contribution nets:a compact representation scheme for coalitional games[C]//Proceedings of the 6th ACM Conference on Electronic Commerce. Vancouver, BC, Canada, 2005:193-202.
备注/Memo
收稿日期:2018-04-26。
基金项目:国家自然科学基金项目（61572418）；山东省科技发展计划项目（2016GGX109004）.
作者简介:任子仪,女,1994年生,硕士研究生,主要研究方向为联盟结构生成和数据挖掘;童向荣,男,1975年生,教授,博士,主要研究方向为多Agent系统、分布式人工智能、数据挖掘。主持国家自然科学基金面上项目2项,山东省自然科学基金1项。发表学术论文50余篇。
通讯作者:童向荣.E-mail:txr@ytu.edu.cn
更新日期/Last Update:
1900-01-01