图联盟结构核的求解算法
|
摘要
联盟结构核是人工智能领域中的一个重要研究内容,特别是生成满足核要求的联盟结构及其分配,是当前主要的研究任务。传统算法存在一些缺陷,比如假定所有联盟可生成且联盟利益满足超加性,忽视外部环境对生成联盟的限制作用。采用约束图作为联盟生成的约束条件,按劳分配作为初始分配方案,谈判集、稳定成本作为分配调整方案,设计SCP(stable core programming)算法生成联盟结构核,使得生成的联盟结构核可以满足所有处于联盟状态Agent的最大利益期望,保证联盟结构的稳定性。
The research of coalitional structure core is an important part in the field of artificial intelligence. Especially, the research of generating the coalitional structure and its distribution that can meet the core requirement is the present primary mission. Traditional algorithms use different methods to create the coalitions, but they still have some shortcomings, for example, assuming that all coalitions can be generated and satisfy the super-additivity, ignoring the restriction of external environment on the formation of coalition. The constraint graph is used as the constraint condition of the coalition generation, the distribution according to work is taken as the initial allocation scheme, and the bargaining set and the stable cost are taken as the allocation adjustment scheme, this paper designs the SCP(stable core programming) algorithm to generate the core of coalitional structure. As an algorithm to solve the stable situation of coalitions and the core of coalitional game, it can meet the best interest expectations of all agents in coalitions and guarantees the stability of coalitional structure.
The research of coalitional structure core is an important part in the field of artificial intelligence. Especially, the research of generating the coalitional structure and its distribution that can meet the core requirement is the present primary mission. Traditional algorithms use different methods to create the coalitions, but they still have some shortcomings, for example, assuming that all coalitions can be generated and satisfy the super-additivity, ignoring the restriction of external environment on the formation of coalition. The constraint graph is used as the constraint condition of the coalition generation, the distribution according to work is taken as the initial allocation scheme, and the bargaining set and the stable cost are taken as the allocation adjustment scheme, this paper designs the SCP(stable core programming) algorithm to generate the core of coalitional structure. As an algorithm to solve the stable situation of coalitions and the core of coalitional game, it can meet the best interest expectations of all agents in coalitions and guarantees the stability of coalitional structure.
引文
[1]Iwasaki A,Ueda S,Hashimoto N,et al.Finding core for coalition structure utilizing dual solution[J].Artificial Intelligence,2015,222(5):49-66.
[2]Chalkiadakis G,Greco G,Markakis E.Characteristic function games with restricted agent interactions:core-stability and coalition structures[J].Artificial Intelligence,2016,232(1):76-113.
[3]Tan Chunqiao.Shapley value for n persons games with interval fuzzy coalition based on Choquet extension[J].Journal of Systems Engineering,2010,25(4):451-458.
[4]Rahwan T,Jennings N R.An improved dynamic programming algorithm for coalition structure generation[C]//Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems,Estoril,May 12-16,2008.New York:ACM,2008:1417-1420.
[5]Billera L J.Some theorems on the core of an n-person game without side-payments[J].SIAM Journal on Applied Mathematics,1970,18(3):567-579.
[6]Schmeidler D.The nucleolus of a characteristic function game[J].SIAM Journal on Applied Mathematics,1969,17(6):1163-1170.
[7]Myerson R B.Graphs and cooperation in games[J].Mathematics of Operations Research,1977,2(3):225-229.
[8]Skibski O,Michalak T P,Rahwan T,et al.Algorithms for the Shapley and Myerson values in graph-restricted games[C]//Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems,Paris,May 5-9,2014.New York:ACM,2014:197-204.
[9]Michalak T P,Rahwan T,Szczepanski P L,et al.Computational analysis of connectivity games with applications to the investigation of terrorist networks[C]//Proceedings of the 23rd International Joint Conference on Artificial Intelligence,Beijing,Aug 3-9,2013.Menlo Park:AAAI,2014:293-301.
[10]de Weerdt M,Zhang Yingqian,Klos T.Multiagent task allocation in social networks[J].Autonomous Agents and MultiAgent Systems,2012,25(1):46-86.
[11]Yeh D Y.A dynamic programming approach to the complete set partitioning problem[J].BIT Numerical Mathematic,1986,26(4):467-474.
[12]Xu Guangbin,Liu Jinglei.The optimal coalition structure generation with the constrained number of coalition[J].Journal of Nanjing University:Natural Sciences,2015,51(4):601-613.
[13]Yang Xiangfeng,Gao Jinwu.Uncertain core for coalitional game with uncertain payoffs[J].Journal of Uncertain Systems,2014,8(1):13-21.
[14]Guan Baichun.New interpretation of distribution according to one.s performance-an explanation of innovation pursuit[J].Theory Journal,2005(3):35-39.
[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]Breton M L,Owen G,Weber S.Strongly balanced cooperative games[J].International Journal of Game Theory,1992,20(4):419-427.
[17]Scarf H E.The core of an N person game[J].Econometrica,1965,35(1):50-69.
[18]Voice T,Polukarov M,Jennings N R.Coalition structure generation over graphs[J].Journal of Artificial Intelligence Research,2012,45(1):165-195.
[19]Bachrach Y,Meir R,Jung K,et al.Coalitional structure generation in skill games[C]//Proceedings of the 24th AAAIConference on Artificial Intelligence,Atlanta,Jul 11-15,2010.Menlo Park:AAAI,2011:703-708.
[20]Aumann R J,Maschler M.The bargaining set for cooperative games[J].Advances in Game Theory,1964,52(1):443-476.
[21]Bachrach Y,Elkind E,Meir R,et al.The cost of stability in coalitional games[C]//LNCS 5814:Proceedings of the 2nd International Symposium on Algorithmic Game Theory,Paphos,Oct 18-20,2009.Berlin,Heidelberg:Springer,2009:122-134.
[22]Aurangzeb M,Lewis F L.Internal structure of coalitions in competitive and altruistic graphical coalitional games[J].Automatica,2014,50(2):335-348.
[3]谭春桥.基于Choquet延拓具有区间模糊联盟n人对策的Shapley值[J].系统工程学报,2010,25(4):451-458.
[12]徐广斌,刘惊雷.带有联盟个数约束的最优联盟结构生成[J].南京大学学报:自然科学,2015,51(4):601-613.
[14]关柏春.按劳分配新论——一种追求变革的解说[J].理论学刊,2005(3):35-39.
[2]Chalkiadakis G,Greco G,Markakis E.Characteristic function games with restricted agent interactions:core-stability and coalition structures[J].Artificial Intelligence,2016,232(1):76-113.
[3]Tan Chunqiao.Shapley value for n persons games with interval fuzzy coalition based on Choquet extension[J].Journal of Systems Engineering,2010,25(4):451-458.
[4]Rahwan T,Jennings N R.An improved dynamic programming algorithm for coalition structure generation[C]//Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems,Estoril,May 12-16,2008.New York:ACM,2008:1417-1420.
[5]Billera L J.Some theorems on the core of an n-person game without side-payments[J].SIAM Journal on Applied Mathematics,1970,18(3):567-579.
[6]Schmeidler D.The nucleolus of a characteristic function game[J].SIAM Journal on Applied Mathematics,1969,17(6):1163-1170.
[7]Myerson R B.Graphs and cooperation in games[J].Mathematics of Operations Research,1977,2(3):225-229.
[8]Skibski O,Michalak T P,Rahwan T,et al.Algorithms for the Shapley and Myerson values in graph-restricted games[C]//Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems,Paris,May 5-9,2014.New York:ACM,2014:197-204.
[9]Michalak T P,Rahwan T,Szczepanski P L,et al.Computational analysis of connectivity games with applications to the investigation of terrorist networks[C]//Proceedings of the 23rd International Joint Conference on Artificial Intelligence,Beijing,Aug 3-9,2013.Menlo Park:AAAI,2014:293-301.
[10]de Weerdt M,Zhang Yingqian,Klos T.Multiagent task allocation in social networks[J].Autonomous Agents and MultiAgent Systems,2012,25(1):46-86.
[11]Yeh D Y.A dynamic programming approach to the complete set partitioning problem[J].BIT Numerical Mathematic,1986,26(4):467-474.
[12]Xu Guangbin,Liu Jinglei.The optimal coalition structure generation with the constrained number of coalition[J].Journal of Nanjing University:Natural Sciences,2015,51(4):601-613.
[13]Yang Xiangfeng,Gao Jinwu.Uncertain core for coalitional game with uncertain payoffs[J].Journal of Uncertain Systems,2014,8(1):13-21.
[14]Guan Baichun.New interpretation of distribution according to one.s performance-an explanation of innovation pursuit[J].Theory Journal,2005(3):35-39.
[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]Breton M L,Owen G,Weber S.Strongly balanced cooperative games[J].International Journal of Game Theory,1992,20(4):419-427.
[17]Scarf H E.The core of an N person game[J].Econometrica,1965,35(1):50-69.
[18]Voice T,Polukarov M,Jennings N R.Coalition structure generation over graphs[J].Journal of Artificial Intelligence Research,2012,45(1):165-195.
[19]Bachrach Y,Meir R,Jung K,et al.Coalitional structure generation in skill games[C]//Proceedings of the 24th AAAIConference on Artificial Intelligence,Atlanta,Jul 11-15,2010.Menlo Park:AAAI,2011:703-708.
[20]Aumann R J,Maschler M.The bargaining set for cooperative games[J].Advances in Game Theory,1964,52(1):443-476.
[21]Bachrach Y,Elkind E,Meir R,et al.The cost of stability in coalitional games[C]//LNCS 5814:Proceedings of the 2nd International Symposium on Algorithmic Game Theory,Paphos,Oct 18-20,2009.Berlin,Heidelberg:Springer,2009:122-134.
[22]Aurangzeb M,Lewis F L.Internal structure of coalitions in competitive and altruistic graphical coalitional games[J].Automatica,2014,50(2):335-348.
[3]谭春桥.基于Choquet延拓具有区间模糊联盟n人对策的Shapley值[J].系统工程学报,2010,25(4):451-458.
[12]徐广斌,刘惊雷.带有联盟个数约束的最优联盟结构生成[J].南京大学学报:自然科学,2015,51(4):601-613.
[14]关柏春.按劳分配新论——一种追求变革的解说[J].理论学刊,2005(3):35-39.