Payoff Distribution Strategy of Overlapping Coalitions for Concurrent Multiple Tasks
GUI Haixia1,2 , JIANG Jianguo1, ZHANG Guofu1
1.School of Computer and Information, Hefei University of Technology, Hefei 230009 2.School of Economics and Management, Anhui University of Science and Technology, Huainan 232001
Abstract：Payoff distribution of overlapping coalitions is a difficult topic in multi-agent systems. A payoff distribution strategy of overlapping coalitions for concurrent multiple tasks is proposed in this paper. Based on the idea of more abilities for more works, multiple concurrent tasks are dispatched in parallel by proportional allocation. Meanwhile, the payoff of overlapping coalitions is distributed according to the results of task dispatch. Then, a sufficient and necessary condition that one agent satisfies the principle of non-reducing utility when joining multiple coalitions is deduced. Finally, the effectiveness of the proposed method is proved by an example, and a comparative analysis between the proposed strategy and the serial utility allocation is carried out. The result shows that when a new agent applies for joining coalitions, the proposed strategy can satisfy the condition of non-reducing utility more easily and it has better timeliness.
[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 Coalitional Games. Artificial Intelligence, 2009, 173(1): 45-79. [3] MANVI S S, KAKKASAGERI M S. Multicast Routing in Mobile Ad Hoc Networks by Using a Multiagent System. Information Sciences, 2008, 178(6): 1611-1628. [4] 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. [5] ZOLEZZI J M, RUDNICK H. Transmission Cost Allocation by Cooperative Games and Coalition Formation. IEEE Trans on Power Systems, 2002, 17(4): 1008-1015. [6] ERLI G, TAKAHASI K, CHEN L N, et al. Transmission Expansion Cost Allocation Based on Cooperative Game Theory for Congestion Relief. International Journal of Electrical Power & Energy Systems, 2005, 27(1): 61-67. [7] ZHANG G F, JIANG J G, SU Z P, et al. Searching for Overlapping Coalitions in Multiple Virtual Organizations. Information Sciences, 2010, 180(17): 3140-3156. [8] CRISPIM J, REGO N, DE SOUSA J P. Stochastic Partner Selection for Virtual Enterprises: A Chance-Constrained Approach. International Journal of Production Research, 2015, 53(12): 3661-3677. [9] HAN Z, POOR H V. Coalition Games with Cooperative Transmi-ssion: A Cure for the Curse of Boundary Nodes in Selfish Packet-Forwarding Wireless Networks. IEEE Trans on Communications, 2009, 57(1): 203-213. [10] 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. [11] 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. [12] JAMES A. Optimisation, Security, Privacy and Trust in e-Business Systems. Journal of Computer and Systems Sciences, 2015, 81(6): 941-942. [13] 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. [14] VIG L, ADAMS J A. Multi-robot Coalition Formation. IEEE Trans on Robotics, 2006, 22(4): 637-649. [15] SEOW K T, SIM K M, KWEK S Y C. Coalition Formation for Resource Coallocation Using BDI Assignment Agents. IEEE Trans on Systems, Man and Cybernetics (Applications and Reviews), 2007, 37(4): 682-693. [16] KULKARNI A J, TAI K. Probability Collectives: A Multi-agent Approach for Solving Combinatorial Optimization Problems. Applied Soft Computing, 2010, 10(3): 759-771. [17] SERVICE T, ADAMS J. Randomized Coalition Structure Generation. Artificial Intelligence, 2011, 175(16/17): 2061-2074. [18] RAHWAN T, RAMCHURN S D, JENNINGS N R, et al. An Anytime Algorithm for Optimal Coalition Structure Generation. Journal of Artificial Intelligence Research, 2009, 34: 521-567. [19] VOICE T, POLUKAROV M, JENNINGS N R. Coalition Structure Generation over Graphs. Journal of Artificial Intelligence Research, 2012, 45(1): 165-196. [20] RAHWAN T, MICHALAK T, WOOLDRIDGE M, et al. Anytime Coalition Structure Generation in Multi-agent Systems with Positive or Negative Externalities. Artificial Intelligence, 2012, 186: 95-122. [21] RAHWAN T, JENNINGS N R. An Algorithm for Distributing Coalitional Value Calculations among Cooperating Agents. Artificial Intelligence, 2007, 171(8/9): 535-567. [22] RAHWAN T, JENNINGS N R. Distributing Coalitional Value Calculations among Cooperative Agents // Proc of the 20th National Conference on Artificial Intelligence. Pittsburgh, USA, 2005, I: 152-157. [23] 蒋建国,张国富,夏 娜,等.一种基于理性Agent的任务求解联盟形成策略.自动化学报, 2008, 34(4): 478-481. (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.) [24] AIRIAU S, SEN S. A Fair Payoff Distribution for Myopic Rational Agents // Proc of the 8th International Conference on Autonomous Agents and Multi-agent Systems. Budapest, Hungary, 2009, II: 1305-1306. [25] ROTH A E. The Shapley Value. Cambridge, UK: Cambridge University Press, 1988. [26] 罗 翊,石纯一.Agent协作求解中形成联盟的行为策略.计算机学报, 1997, 20(11): 961-965. (LUO Y, SHI C Y. The Behavior Strategy to form Coalition in Agent Cooperative Problem-Solving. Chinese Journal of Computers, 1997, 20(11): 961-965.) [27] 蒋建国,夏 娜,于春华.基于能力向量发挥率和拍卖的联盟形成策略.电子学报, 2004, 32(12): 215-217. (JIANG J G, XIA N, YU C H. The Coalition Formation Strategy Based on Capability Vector Contribution-Rate and Auction. Acta Electronica Sinica, 2004, 32(12): 215-217.) [28] 夏 娜,蒋建国,于春华,等.一种基于利益均衡的联盟形成策略.控制与决策, 2005, 20(12): 1426-1428, 1433. (XIA N, JIANG J G, YU C H, et al.A Coalition Formation Stra-tegy Based on Benefit Equilibrium. Control and Decision, 2005, 20(12): 1426-1428, 1433.) [29] ZICK Y, ELKIND E. Arbitrators in Overlapping Coalition Formation Games // Proc of the 10th International Conference on Autonomous Agents and Multiagent Systems. Taibei, China, 2011, I: 55-62. [30] CHALKIADAKIS G, ELKIND E, MARKAKIS E, et al. Overla-pping Coalition Formation // Proc of the 4th International Workshop on Internet and Network Economics. Shanghai, China, 2008: 307-321. [31] ZICK Y, CHALKIADAKIS G, ELKIND E. Overlapping Coalition Formation Games: Charting the Tractability Frontier [C/OL]. [2015-06-30]. http:// www.ifaamas.org/Proceedings/aamas2012/papers/1E-4.pdf. [32] CHALKIADAKIS G, ELKIND E, MARKAKIS E, et al. Cooperative Games with Overlapping Coalitions. Journal of Artificial Intelligence Research, 2010, 39: 179-216. [33] 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, USA, 2012: 1506-1512. [34] ZICK Y. Stability and Arbitration in Cooperative Games with Overlapping Coalitions [C/OL]. [2015-06-30]. http: // www.ifaamas. org/Proceedings/aamas2012/papers/DC-24.pdf. [35] LIN C F, HU S L. Multi-task Overlapping Coalition Parallel Formation Algorithm // Proc of the 6th International Joint Conference on Auto-nomous Agents and Multiagent Systems. Honolulu, USA, 2007: 1252-1254. [36] 张国富,周 鹏,苏兆品,等.基于讨价还价的重叠联盟效用划分策略.模式识别与人工智能, 2014, 27(10): 930-938. (ZHANG G F, ZHOU P, SU Z P, et al. A Payoff Distribution Strategy for Overlapping Coalitions Based on Bargaining. Pattern Recognition and Artificial Intelligence, 2014, 27(10): 930-938.) [37] XIA C M, HOWELL J. Loop Status Monitoring and Fault Localisa-tion. Journal of Process Control, 2003, 13(7): 679-691. [38] 熊义杰.现代博弈论基础.北京:国防工业出版社, 2010. (Xiong Y J. Modern Game Theory. Beijing, China: National Defense Industry Press, 2010.)
2016, Vol. 29 
