第3期 任子仪，等：约束条件下联盟生成研究进展 ·421· {a1Aa2Aa3}→2 ory[M].Cambridge:MIT Press,1994 {a1Λa2Λa3}→2 [5]VON NEUMANN J,MORGENSTERN O.Theory of {a1Aa2Aa3}→2 games and economic behavior[M].Princeton:Princeton {a1Λa2∧a3}→5 University Press.1972 {a3Aas}→0 {a2Aa4}→0 [6]WOOLDRIDGE M.BUSSMANN S.KLOSTERBERG M. 根据给定的规则，v({a1,a1,a1)=2。 Production sequencing as negotiation[C]//Proceedings of the First International Conference on the Practical Applica- 定理5令h≥0是一个固定自然数，T=<N,v> tion of Intelligent Agents and Multi-Agent Technology. 是一个博弈，其中v是独立于不相交成员的评估 London,UK,1996:709-726. 函数，交互图D所构成的树的高大于h。令 [7]SANDHOLM T,SIKKA S,NORDEN S.Algorithms for σ=<D,S,a,B,x,y>,则(T,σ)的联盟结构生成的值 optimizing leveled commitment contracts[C]//Proceed- 可以在多项式时间内解决。 ings of the 16th International Joint Conference on Artifical 约束满足问题具有较强的灵活性，能够进行 Intelligence.Stockholm,Sweden,1999:535-540. 推广解决文献[32]中提到的约束问题。 [8]RAHWAN T,MICHALAK T P,WOOLDRIDGE M,et al. Coalition structure generation:a survey[J].Artificial intel- 7结束语 ligence,.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[Cl//Proceed- 本文针对这一问题进行了全面的综述：1)搜索空 ings of the 5th International Symposium on Modeling and 间的不同表示：2)动态规划算法的时候来解决这 Optimization in Mobile,Ad Hoc and Wireless Networks 个问题；3)使用近似最优来代替最优解；4)使用 and Workshops.Limasso,Cyprus,2009:1-8. 评估的方法，主要是添加了约束条件。所有的这 [10]KHAN Z,LEHTOMAKI J,LATVA-AHO M,et al.On selfish and altruistic coalition formation in cognitive ra- 些结构都是以一种独立的方式展示出来的。 dio networks[C]//Proceedings of the 2010 Fifth Interna- 但是，在现有联盟生成的研究中，大多数是 tional Conference on Cognitive Radio Oriented Wireless 以Agent之间具有相同的协商资源和态度为前提 Networks and Communications.Cannes,France,2010 的，只考虑了协商中的相同性，却忽略了协商中 1-5. 的异质性。在未来的工作中，可以考虑将协商的 [11]LI Cuihong,SYCARA K,SCHELLER-WOLF A.Com- 异质性与约束联盟中的评估结构相结合。 binatorial coalition formation for multi-item group-buy- 同时，在约束K-means聚类算法的启发下，可 ing with heterogeneous customers[J].Decision support systems,.2010,491):1-13. 以将一般形式的无法连接的约束进行合理操作后 [12]MANOOCHEHRI H E,WENKSTERN R Z.Dynamic 有理性地加入到评估结构中。另外，可以进行扩 coalition structure generation for autonomous connected 展，将允许联盟生成的概率使用先验知识进行检 vehicles[C]//Proceedings of 2017 IEEE International 验或者将Agent之间的动态相互信任添加到联盟 Conference on Agents.Beijing,China,2017:21-26. 生成的过程中。 [13]SLESS L,HAZON N,KRAUS S,et al.Forming k coali- tions and facilitating relationships in social networks[J] 参考文献： Artificial intelligence.2018.259:217-245. [14]SLESS L.HAZON N.KRAUS S.et al.Forming coali- [1]AZIZ H.Multiagent systems:algorithmic,game-theoretic, tions and facilitating relationships for completing tasks in and logical foundations by Y.Shoham and K.Leyton- social networks[Cl//Proceedings of the 2014 Internation- Brown Cambridge University Press,2008[J].ACM al Conference on Autonomous Agents and Multi-Agent SIGACT news,2010.41(1):34-37. Systems.Paris,France,2014:261-268. [2]WOOLDRIDGE M.Computational aspects of cooperative [15]SANDHOLM T,LARSON K,ANDERSSON M,et al. game theory[C]//Proceedings of the 5th KES International Coalition structure generation with worst case guarantees Conference on Agent and Multi-Agent Systems:Technolo- [J].Artificial intelligence,1999,111(1/2):209-238. gies and Applications.Manchester,UK,2011. [16]YEH D Y.A dynamic programming approach to the com- [3]ELKIND E,RAHWAN T,JENNINGS N R.Computation- plete set partitioning problem[J].BIT numerical mathem- al coalition formation[M].Cambridge:MIT Press,2013: atics,1986,26(4):467-474. 329-380. [17]DANG TT,FRANKOVIE B,BUDINNSKA I.Create [4]OSBORNE M J,RUBINSTEIN A.A course in game the- agent's coalition based on a dynamic programming ap-{a1 ∧a2 ∧ ¬a3} → 2 {¬a1 ∧a2 ∧a3} → 2 {a1 ∧ ¬a2 ∧a3} → 2 {a1 ∧a2 ∧a3} → 5 {a3 ∧a5} → 0 {a2 ∧a4} → 0 根据给定的规则， v({a1,a1,a1}) = 2。 h ⩾ 0 Γ =< N，v > v D σ= < D,S,α, β, x, y > (Γ,σ) 定理5 令 是一个固定自然数， 是一个博弈，其中 是独立于不相交成员的评估 函数，交互图 所构成的树的高大 于 h。 令 ，则 的联盟结构生成的值 可以在多项式时间内解决。 约束满足问题具有较强的灵活性，能够进行 推广解决文献[32]中提到的约束问题。 7 结束语 联盟结构生成问题中如何能够更快更精确地 进行优化整体性能对于研究人员一直都是挑战。 本文针对这一问题进行了全面的综述：1) 搜索空 间的不同表示；2) 动态规划算法的时候来解决这 个问题；3) 使用近似最优来代替最优解；4) 使用 评估的方法，主要是添加了约束条件。所有的这 些结构都是以一种独立的方式展示出来的。 但是，在现有联盟生成的研究中，大多数是 以 Agent 之间具有相同的协商资源和态度为前提 的，只考虑了协商中的相同性，却忽略了协商中 的异质性。在未来的工作中，可以考虑将协商的 异质性与约束联盟中的评估结构相结合。 同时，在约束 K-means 聚类算法的启发下，可 以将一般形式的无法连接的约束进行合理操作后 有理性地加入到评估结构中。另外，可以进行扩 展，将允许联盟生成的概率使用先验知识进行检 验或者将 Agent 之间的动态相互信任添加到联盟 生成的过程中。 参考文献： 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. [1] WOOLDRIDGE M. Computational aspects of cooperative game theory[C]//Proceedings of the 5th KES International Conference on Agent and Multi-Agent Systems: Technolo￾gies and Applications. Manchester, UK, 2011. [2] ELKIND E, RAHWAN T, JENNINGS N R. Computation￾al coalition formation[M]. Cambridge: MIT Press, 2013: 329–380. [3] [4] OSBORNE M J, RUBINSTEIN A. A course in game the￾ory[M]. Cambridge: MIT Press, 1994. VON NEUMANN J, MORGENSTERN O. Theory of games and economic behavior[M]. Princeton: Princeton University Press, 1972. [5] WOOLDRIDGE M, BUSSMANN S, KLOSTERBERG M. Production sequencing as negotiation[C]// Proceedings of the First International Conference on the Practical Applica￾tion of Intelligent Agents and Multi-Agent Technology. London, UK, 1996: 709–726. [6] SANDHOLM T, SIKKA S, NORDEN S. Algorithms for optimizing leveled commitment contracts[C]// Proceed￾ings of the 16th International Joint Conference on Artifical Intelligence. Stockholm, Sweden, 1999: 535–540. [7] RAHWAN T, MICHALAK T P, WOOLDRIDGE M, et al. Coalition structure generation: a survey[J]. Artificial intel￾ligence, 2015, 229: 139–174. [8] 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]// Proceed￾ings of the 5th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks and Workshops. Limasso, Cyprus, 2009: 1–8. [9] KHAN Z, LEHTOMÄKI J, LATVA-AHO M, et al. On selfish and altruistic coalition formation in cognitive ra￾dio networks[C]//Proceedings of the 2010 Fifth Interna￾tional Conference on Cognitive Radio Oriented Wireless Networks and Communications. Cannes, France, 2010: 1–5. [10] LI Cuihong, SYCARA K, SCHELLER-WOLF A. Com￾binatorial coalition formation for multi-item group-buy￾ing with heterogeneous customers[J]. Decision support systems, 2010, 49(1): 1–13. [11] 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. [12] SLESS L, HAZON N, KRAUS S, et al. Forming k coali￾tions and facilitating relationships in social networks[J]. Artificial intelligence, 2018, 259: 217–245. [13] SLESS L, HAZON N, KRAUS S, et al. Forming coali￾tions and facilitating relationships for completing tasks in social networks[C]// Proceedings of the 2014 Internation￾al Conference on Autonomous Agents and Multi-Agent Systems. Paris, France, 2014: 261–268. [14] SANDHOLM T, LARSON K, ANDERSSON M, et al. Coalition structure generation with worst case guarantees [J]. Artificial intelligence, 1999, 111(1/2): 209–238. [15] YEH D Y. A dynamic programming approach to the com￾plete set partitioning problem[J]. BIT numerical mathem￾atics, 1986, 26(4): 467–474. [16] DANG T T, FRANKOVIE B, BUDINNSKA I. Create agent’s coalition based on a dynamic programming ap- [17] 第 3 期 任子仪，等：约束条件下联盟生成研究进展 ·421·