·422· 智能系统学报 第14卷 proach[Cl//Proceedings of the 15th European Conference tationally manageable combinational auctions[J].Man- on Artificial Intelligence,Workshop "Agent Technolo- agement science,1998,448):1131-1147. gies and Logistics".Lyon,France.2002:16-24. [31]刘惊雷，童向荣，张伟.一种快速构建最优联盟结构的 [18]GRECO G,GUZZO A.Constrained coalition formation 方法.计算机工程与应用，2006,42(4)：35-37,44. on valuation structures:formal framework,applications, LIU Jinglei,TONG Xiangrong,ZHANG Wei.A kind of and islands of tractability[J].Artificial intelligence,2017. method for quick constructing optimal coalition 249:19-46. structure[J].Computer engineering and applications, [19]童向荣，张伟.动态联盟收益值的再励学习.计算机 2006,42(4:35-37,44. 工程与应用，2006.42(6)：85-87. [32]RAHWAN T.MICHALAK T P.ELKIND E,et al.Con- TONG Xiangrong,ZHANG Wei.Reinforcement learn- strained coalition formation[C]//Proceedings of the ing for the value of dynamic coalition[.Computer en- Twenty-Fifth AAAI Conference on Artificial Intelligence. gineering and application,2006,42(6):85-87. San Francisco,USA,2011:719-725. [20]DEAN T,BODDY M.An analysis of time-dependent [33]张新良，石纯一.多Agent联盟结构动态生成算法]， planning[Cl//Proceedings of the 7th National Conference 软件学报，2007,18(3574-581. on Artificial Intelligence.St.Paul,Brazil,1988:49-54. ZHANG Xinliang,SHI Chunyi.A dynamic formation al- [21]BRUALDI R A.组合数学M).冯舜玺，译.5版.北京： gorithm of multi-agent coalition structure[J].Journal of 机械工业出版社，2012：180-186. software,2007,18(3):574-581. BRUALDI R A.Introductory combinatorics[M].FENG [34]RAHWAN T.RAMCHURN S D.DANG V D.et al. Shunxi,trans.5th ed.Beijing:China Machine Press, Near-optimal anytime coalition structure generation[C]// 2012:180-186. Proceedings of the 20th International Joint Conference on [22]KARP R M.Reducibility among combinatorial Artificial Intelligence.Hyderabad,India,2007: problems[C]//Complexity of Computer Computations. 2365-2371. New York,USA,1972:85-103. [35]ALBIZURI M J.AURRECOECHEA J.ZARZUELO J [23]HASTAD J.Clique is hard to approximate withinn[]. M.Configuration values:extensions of the coalitional Acta mathematica,1999,182(1):105-142. Owen value[J].Games and economic behavior,2006. [24]SANDHOLM T.An algorithm for optimal winner de- 57(1)1-17. termination in combinatorial auction[Cl//Proceedings of [36]RAHWAN T,JENNINGS N R.Distributing coalitional the Sixteenth International joint conference on artificial value calculations among cooperative agents[C]//Pro- intelligence.Stockholm,Sweden,1999:542-547 ceedings of the 20th National Conference on Artificial In- [25]LINIAL N.Game-theoretic aspects of computing[M]// telligence.Pittsburgh,Pennsylvania,2005:152-157. AUMANN R J,HART S.Handbook of Game Theory [37]FRANKOVI B,DANG T,BUDINSKA I.Agents'coali- with Economic Applications.Amsterdam,Netherlands: tions based on a dynamic programming approach[J].Acta Elsevier,1994:1339-1395. polytechnica hungarica,2008,5(2):5-21. [26]LARSON K S.SANDHOLM T W.Anytime coalition [38]IEONG S,SHOHAM Y.Marginal contribution nets:a structure generation:an average case study[J].Journal of compact representation scheme for coalitional games[Cl// experimental theoretical artificial intelligence,2000, Proceedings of the 6th ACM Conference on Electronic 12(1:23-42. Commerce.Vancouver,BC,Canada,2005:193-202. [27刀胡山立，石纯一.一种任一时间联盟结构生成算法) 软件学报.2001.12(5)：729-734. 作者简介： HU Shanli,SHI Chunyi.An anytime coalition structure 任子仪，女，1994年生，硕士研究 generation algorithm[J].Journal of software,2001,12(5): 生，主要研究方向为联盟结构生成和 729-734. 数据挖掘。 [28]胡山立，石纯一.给定限界要求的联盟结构生成刀.计 算机学报，2001,2411)少1185-1190. HU Shanli,SHI Chunyi.Coalition structure generation with given required bound[J].Chinese journal of com- puters,,2001,24(11):1185-1190. 童向荣，男，1975年生.教授，博 [29]DANG V D,JENNINGS N R.Generating coalition struc- 士，主要研究方向为多Agent系统、分 tures with finite bound from the optimal guarantees[C]// 布式人工智能、数据挖掘。主持国家自 Proceedings of 3rd International Joint Conference on 然科学基金面上项目2项，山东省自 Autonomous Agents and Multiagent Systems.New York. 然科学基金1项。发表学术论文50余篇。 USA,2004:564-571 [30]ROTHKOPF M H,PEKEC A,HARSTAD R M.Compu-proach[C]//Proceedings of the 15th European Conference on Artificial Intelligence, Workshop “Agent Technolo￾gies and Logistics”. Lyon, France, 2002: 16–24. GRECO G, GUZZO A. Constrained coalition formation on valuation structures: formal framework, applications, and islands of tractability[J]. Artificial intelligence, 2017, 249: 19–46. [18] 童向荣, 张伟. 动态联盟收益值的再励学习[J]. 计算机 工程与应用, 2006, 42(6): 85–87. TONG Xiangrong, ZHANG Wei. Reinforcement learn￾ing for the value of dynamic coalition[J]. Computer en￾gineering and application, 2006, 42(6): 85–87. [19] 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. [20] 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. [21] KARP R M. Reducibility among combinatorial problems[C]// Complexity of Computer Computations. New York, USA, 1972: 85–103. [22] HASTAD J. Clique is hard to approximate within n 1-ε[J]. Acta mathematica, 1999, 182(1): 105–142. [23] SANDHOLM T. An algorithm for optimal winner de￾termination in combinatorial auction[C]// Proceedings of the Sixteenth International joint conference on artificial intelligence. Stockholm, Sweden, 1999: 542–547. [24] 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. [25] 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. [26] 胡山立, 石纯一. 一种任一时间联盟结构生成算法[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. [27] 胡山立, 石纯一. 给定限界要求的联盟结构生成[J]. 计 算机学报, 2001, 24(11): 1185–1190. HU Shanli, SHI Chunyi. Coalition structure generation with given required bound[J]. Chinese journal of com￾puters, 2001, 24(11): 1185–1190. [28] DANG V D, JENNINGS N R. Generating coalition struc￾tures 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. [29] [30] ROTHKOPF M H, PEKEČ A, HARSTAD R M. Compu￾tationally manageable combinational auctions[J]. Man￾agement science, 1998, 44(8): 1131–1147. 刘惊雷, 童向荣, 张伟. 一种快速构建最优联盟结构的 方法[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. [31] RAHWAN T, MICHALAK T P, ELKIND E, et al. Con￾strained coalition formation[C]//Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence. San Francisco, USA, 2011: 719–725. [32] 张新良, 石纯一. 多 Agent 联盟结构动态生成算法[J]. 软件学报, 2007, 18(3): 574–581. ZHANG Xinliang, SHI Chunyi. A dynamic formation al￾gorithm of multi-agent coalition structure[J]. Journal of software, 2007, 18(3): 574–581. [33] 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. [34] 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. [35] RAHWAN T, JENNINGS N R. Distributing coalitional value calculations among cooperative agents[C]// Pro￾ceedings of the 20th National Conference on Artificial In￾telligence. Pittsburgh, Pennsylvania, 2005: 152–157. [36] FRANKOVI B, DANG T, BUDINSKÁ I. Agents’ coali￾tions based on a dynamic programming approach[J]. Acta polytechnica hungarica, 2008, 5(2): 5–21. [37] 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. [38] 作者简介： 任子仪，女，1994 年生，硕士研究 生，主要研究方向为联盟结构生成和 数据挖掘。 童向荣，男，1975 年生，教授，博 士，主要研究方向为多 Agent 系统、分 布式人工智能、数据挖掘。主持国家自 然科学基金面上项目 2 项，山东省自 然科学基金1项。发表学术论文50余篇。 ·422· 智 能 系 统 学 报 第 14 卷