A Payoff Distribution Strategy for Overlapping Coalitions Based on Bargaining
ZHANG Guo-Fu1,2, ZHOU Peng1, SU Zhao-Pin1,2, YANG Ren-Zhi1, JIANG Jian-Guo1,2
1.School of Computer and Information, Hefei University of Technology, Heifei 230009 2.Engineering Research Center of Safety Critical Industrial Measurement and Control Technology, Ministry of Education, Hefei University of Technology, Hefei 230009
Abstract In multi-agent system (MAS), payoff distribution for overlapping coalitions is a difficult problem in overlapping coalition formation (OCF). In this paper, the possible resource conflicts in OCF are discussed firstly, then some important characteristics of the OCF model are deduced. Based on those results, the strategy of bargaining is introduced to allocate tasks to agents in coalitions, and the payoff of coalitions is distributed according to the principle of non-reducing utility. Finally, the analysis of a specific example shows the feasibility of the proposed method.
[1] Service T C, Adams J A. Coalition Formation for Task Allocation: Theory and Algorithms. Autonomous Agents and Multi-agent Systems, 2011, 22(2): 225-248 [2] Agotnes T, van der Hoek W, Wooldridge M. Reasoning about Coa-litional Games. Artificial Intelligence, 2009, 173(1): 45-79 [3] Michalak T, Tyrowicz J, McBurney P, et al. Exogenous Coalition Formation in the e-Marketplace Based on Geographical Proximity. Electronic Commerce Research and Applications, 2009, 8(4): 203-223 [4] Argoneto P, Renna P. Production Planning, Negotiation and Coalition Integration: A New Tool for an Innovative e-Business Model. Robotics and Computer-Integrated Manufacturing, 2010, 26(1): 1-12 [5] Han Z, Poor H V. Coalition Games with Cooperative Transmission: A Cure for the Curse of Boundary Nodes in Selfish Packet-Forwarding Wireless Networks. IEEE Trans on Communications, 2009, 57(1): 203-213 [6] Saad W, Han Z, Basar T, et al. Hedonic Coalition Formation for Distributed Task Allocation among Wireless Agents. IEEE Trans on Mobile Computing, 2011, 10(9): 1327-1344 [7] Chen J, Sun D. Coalition-Based Approach to Task Allocation of Multiple Robots with Resource Constraints. IEEE Trans on Automation Science and Engineering, 2012, 9(3): 516-528 [8] Liang X N, Xiao Y. Studying Bio-inspired Coalition Formation of Robots for Detecting Intrusions Using Game Theory. IEEE Trans on Systems, Man, and Cybernetics: Part B, 2010, 40(3): 683-693 [9] Park H, van der Schaar M. Coalition-Based Resource Negotiation for Multimedia Applications in Informationally Decentralized Networks. IEEE Trans on Multimedia, 2009, 11(4): 765-779 [10] Zhao H V, Lin W S, Liu K J R. Cooperation and Coalition in Multimedia Fingerprinting Colluder Social Networks. IEEE Trans on Multimedia, 2012, 14(3): 717-733 [11] Saad W, Han Z, Basar T, et al. Distributed Coalition Formation Games for Secure Wireless Transmission. Mobile Networks and Applications, 2011, 16(2): 231-245 [12] Huang Y W, Moulin P. On the Saddle-Point Solution and the Large-Coalition Asymptotics of Fingerprinting Games. IEEE Trans on Information Forensics and Security, 2012, 7(1): 160-175 [13] Liu J L, Zhang W, Tong X R, et al. O(2.983n) Time Complexity Algorithm for Optimal Coalition Structure Generation. Journal of Software, 2011, 22(5): 938-950 (in Chinese) (刘惊雷,张 伟,童向荣,等.一种O(2.983n)时间复杂度的最优联盟结构生成算法.软件学报, 2011, 22(5): 938-950) [14] Su Z P, Jiang J G, Xia N, et al. An Evaluation Method for Agent Coalition Based on D-S Evidence Theory. Pattern Recognition and Artificial Intelligence, 2007, 20(5): 624-629 (in Chinese) (苏兆品,蒋建国,夏 娜,等.一种基于D-S证据理论的Agent联盟评价方法.模式识别与人工智能, 2007, 20(5): 624-629) [15] Rahwan T, Jennings N R. An Algorithm for Distributing Coalitional Value Calculations among Cooperating Agents. Artificial Intelligence, 2007, 171(8/9): 535-567 [16] Rahwan T, Jennings N R. Distributing Coalitional Value Calculations among Cooperative Agents // Proc of the 20th National Conference on Artificial Intelligence. Pittsburgh, USA, 2005: 152-157 [17] Jiang J G, Zhang G F, Xia N, et al. A Task Oriented Coalition Formation Strategy Based on Rational Agents. Acta Automatica Sinica, 2008, 34(4): 478-481 (in Chinese) (蒋建国,张国富,夏 娜,等.一种基于理性Agent的任务求解联盟形成策略.自动化学报, 2008, 34(4): 478-481) [18] Airiau S, Sen S. A Fair Payoff Distribution for Myopic Rational Agents // Proc of the 8th International Conference on Autonomous Agents and Multiagent Systems. Budapest, Hungary, 2009, II: 1305-1306 [19] Chalkiadakis G, Elkind E, Markakis E, et al. Cooperative Games with Overlapping Coalitions. Journal of Artificial Intelligence Research, 2010, 39: 179-216 [20] Zick Y, Markakis E, Elkind E. Stability via Convexity and LP Duality in OCF Games // Proc of the 26th AAAI Conference on Artificial Intelligence. Toronto, Canada, 2012: 1506-1512 [21] Zhang G F, Jiang J G, Lu C H, et al. A Revision Algorithm for Invalid Encodings in Concurrent Formation of Overlapping Coalitions. Applied Soft Computing, 2011, 11(2): 2164-2172 [22] Zhang G F, Zhou P, Jiang J G, et al. An Algorithm for Overla- pping Coalition Formation Based on Virtual Coalition. Acta Electronica Sinica, 2012, 40(1): 121-127 (in Chinese) (张国富,周 鹏,蒋建国,等.基于虚拟联盟的重叠联盟形成算法.电子学报, 2012, 40(1): 121-127) [23] Sun X L, Li R. Integer Programming. Beijing, China: Science Press, 2010 (in Chinese) (孙小玲,李 端.整数规划.北京:科学出版社, 2010) [24] Xiong Y J. Modern Game Theory. Beijing, China: National Defense Industry Press, 2010 (in Chinese) (熊义杰.现代博弈论基础.北京:国防工业出版社, 2010)
2014, Vol. 27 
