[1]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]
Copy

Research progress of constrained coalition formation

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 14 Number of periods: 2019 3 Page number: 413-422 Column: 综述 Public date: 2019-05-05
Title:
Research progress of constrained coalition formation
Author(s):
REN Ziyi;  TONG Xiangrong
School of Computer and Control Engineering, Yantai University, Yantai 264005, China
Keywords:
coalition structure; social welfare; coalition formation; constraint; characteristic function; coalition structure graph; coalition game; dynamic programming
CLC:
TP18
DOI:
10.11992/tis.201804054
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.
Similar References:

Memo

-

Last Update: 1900-01-01

Copyright © CAAI Transactions on Intelligent Systems