›› 2016, Vol. 31 ›› Issue (6): 1136-1150.doi: 10.1007/s11390-016-1688-5

Special Issue: Artificial Intelligence and Pattern Recognition; Theory and Algorithms

• Regular Paper • Previous Articles     Next Articles

Using Computational Intelligence Algorithms to Solve the Coalition Structure Generation Problem in Coalitional Skill Games

Yang Liu1, Guo-Fu Zhang1,2*, Member, IEEE, Zhao-Pin Su1,2, Member, IEEE, Feng Yue1,3, Jian-Guo Jiang1,2, Senior Member, CCF   

  1. 1 School of Computer and Information, Hefei University of Technology, Hefei 230009, China;
    2 Intelligent Manufacturing Institute, Hefei University of Technology, Hefei 230009, China;
    3 Department of Science and Technology Management, Hefei University of Technology, Hefei 230009, China
  • Received:2015-07-15 Revised:2016-06-17 Online:2016-11-05 Published:2016-11-05
  • Supported by:

    This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 61573125 and 61371155, and the Anhui Provincial Natural Science Foundation of China under Grant Nos. 1608085MF131, 1508085MF132, and 1508085QF129.

Coalitional skill games (CSGs) are a simple model of cooperation in an uncertain environment where each agent has a set of skills that are required to accomplish a variety of tasks and each task requires a set of skills to be completed,but each skill is very hard to be quantified and can only be qualitatively expressed.Thus far,many computational questions surrounding CSGs have been studied.However,to the best of our knowledge,the coalition structure generation problem (CSGP),as a central issue of CSGs,is extremely challenging and has not been well solved.To this end,two different computational intelligence algorithms are herein evaluated:binary particle swarm optimization (BPSO) and binary differential evolution (BDE).In particular,we develop the two stochastic search algorithms with two-dimensional binary encoding and corresponding heuristic for individual repairs.After that,we discuss some fundamental properties of the proposed heuristic.Finally,we compare the improved BPSO and BDE with the state-of-the-art algorithms for solving CSGP in CSGs.The experimental results show that our algorithms can find the same near optimal solutions with the existing approaches but take extremely short time,especially under the large problem size.

[1] Khan M A, Turgut D, Bölöni L. Optimizing coalition formation for tasks with dynamically evolving rewards and nondeterministic action effects. Autonomous Agents and MultiAgent Systems, 2011, 22(3):415-438.

[2] Ye D, Zhang M, Sutanto D. Self-adaptation-based dynamic coalition formation in a distributed agent network:A mechanism and a brief survey. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(5):1042-1051.

[3] Li C, Sycara K, Scheller-Wolf A. Combinatorial coalition formation for multi-item group-buying with heterogeneous customers. Decision Support Systems, 2010, 49(1):1-13.

[4] Liao S S, Zhang J D, Lau R et al. Coalition formation based on marginal contributions and the Markov process. Decision Support Systems, 2014, 57(1):355-363.

[5] Ke G Y, Bookbinder J H, Kilgour D M. Coordination of transportation and quantity discount decisions, with coalition formation. International Journal of Production Research, 2014, 52(17):5115-5130.

[6] Saad W, Han Z, Ba?ar T et al. Hedonic coalition formation for distributed task allocation among wireless agents. IEEE Transactions on Mobile Computing, 2011, 10(9):1327- 1344.

[7] Guerrero J, Oliver G. Multi-robot coalition formation in real-time scenarios. Robotics and Autonomous Systems, 2012, 60(10):1295-1307.

[8] Liu A, Li Q, Huang L et al. Coalitional game for community-based autonomous web services cooperation. IEEE Transactions on Services Computing, 2013, 6(3):387-399.

[9] Service T C, Adams J A. Constant factor approximation algorithms for coalition structure generation. Autonomous Agents and Multi-Agent Systems, 2011, 23(1):1-17.

[10] 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.

[11] Zick Y, Chalkiadakis G, Elkind E. Overlapping coalition formation games:Charting the tractability frontier. In Proc. the 11th International Conference on Autonomous Agents and Multiagent Systems, June 2012, pp.787-794.

[12] Zick Y, Markakis E, Elkind E. Arbitration and stability in cooperative games with overlapping coalitions. Journal of Artificial Intelligence Research, 2014, 50:847-884.

[13] Dunne P E, Kraus S, Manisterski E et al. Solving coalitional resource games. Artificial Intelligence, 2010, 174(1):20-50.

[14] Chitnis R, Hajiaghayi M, Liaghat V. Parameterized complexity of problems in coalitional resource games. In Proc. the 25th AAAI Conference on Artificial Intelligence, August 2011, pp.620-625.

[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] Airiau S, Sen S.A fair payoff distribution for myopic rational agents. In Proc. the 8th International Joint Conference on Autonomous Agents and Multiagent Systems, May 2009, pp.1305-1306.

[17] Chalkiadakis G, Markakis E, Boutilier C. Coalition formation under uncertainty:Bargaining equilibria and the Bayesian core stability concept. In Proc. the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, May 2007, pp.412-419.

[18] Chalkiadakis G, Boutilier C. Sequentially optimal repeated coalition formation under uncertainty. Autonomous Agents and Multi-Agent Systems, 2012, 24(3):441-484.

[19] Kenari S M S, Jahan M V, Jalali M. Multi-skill agents coalition formation under skill uncertainty. In Proc. International Symposium on Artificial Intelligence and Signal Processing, June 2011, pp.89-96.

[20] Sridhar U, Mandyam S.Capability-weighted group utility maximizer for network coalitional games under uncertainty. In Proc. IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, August 2012, pp.613-617.

[21] Bachrach Y, Rosenschein J S.Coalitional skill games. In Proc. the 7th International Conference on Autonomous Agents and Multiagent Systems, May 2008, pp.1023-1030.

[22] Bachrach Y, Parkes D C, Rosenschein J S.Computing cooperative solution concepts in coalitional skill games. Artificial Intelligence, 2013, 204:1-21.

[23] Aziz H, Brandt F, Harrenstein P. Monotone cooperative games and their threshold versions. In Proc. the 9th International Conference on Autonomous Agents and Multiagent Systems, May 2010, pp.1107-1114.

[24] Aziz H, De Keijzer B. Complexity of coalition structure generation. In Proc. the 10th International Conference on Autonomous Agents and Multiagent Systems, May 2011, pp.191-198.

[25] Tran-Thanh L, Nguyen T D, Rahwan T et al. An efficient vector-based representation for coalitional games. In Proc. the 23rd International Joint Conference on Artificial Intelligence, August 2013, pp.383-389.

[26] Wu D, Cai Y, Wang J. A coalition formation framework for transmission scheme selection in wireless sensor networks. IEEE Transactions on Vehicular Technology, 2011, 60(6):2620-2630.

[27] Akkarajitsakul K, Hossain E, Niyato D. Coalition-based cooperative packet delivery under uncertainty:A dynamic bayesian coalitional game. IEEE Transactions on Mobile Computing, 2013, 12(2):371-385.

[28] Blankenburg B, He M, Klusch M et al. Risk-bounded formation of fuzzy coalitions among service agents. In Proc. the 10th International Workshop on Cooperative Information Agents, September 2006, pp.332-346.

[29] Wei G, Vasilakos A V, Zheng Y et al. A game-theoretic method of fair resource allocation for cloud computing services. The Journal of Supercomputing, 2010, 54(2):252-269.

[30] Niyato D, Vasilakos A V, Zhu K. Resource and revenue sharing with coalition formation of cloud providers:Game theoretic approach. In Proc. the 11th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, May 2011, pp.215-224.

[31] Huang B, Gao C, Chen L. Partner selection in a virtual enterprise under uncertain information about candidates. Expert Systems with Applications, 2011, 38(9):11305-11310.

[32] Rahimi M R, Venkatasubramanian N, Vasilakos A V. MuSIC:Mobility-aware optimal service allocation in mobile cloud computing. In Proc. the 6th IEEE International Conference on Cloud Computing, June 28-July 3, 2013, pp.75-82.

[33] Sheng Q Z, Qiao X, Vasilakos A V et al. Web services composition:A decade's overview. Information Sciences, 2014, 280:218-238.

[34] Khan M A, Tembine H, Vasilakos A V. Game dynamics and cost of learning in heterogeneous 4G networks. IEEE Journal on Selected Areas in Communications, 2012, 30(1):198-213.

[35] Duarte P B F, Fadlullah Z M, Vasilakos A V et al. On the partially overlapped channel assignment on wireless mesh network backbone:A game theoretic approach. IEEE Journal on Selected Areas in Communications, 2012, 30(1):119-127.

[36] Wang C Y, Ko C H, Wei H Y et al. A botingbased Femtocell downlink cell-breathing control mechanism. IEEE/ACM Transactions on Networking, 2016, 24(1):85-98.

[37] Dutta A, Dasgupta P, Baca J et al. SearchUCSG:A fast coalition structure search algorithm for modular robot reconfiguration under uncertainty. Robotica, 2014, 32(2):225-244.

[38] Roh J H, Shahidehpour M, Wu L. Market-based generation and transmission planning with uncertainties. IEEE Transactions on Power Systems, 2009, 24(3):1587-1598.

[39] Bachracht Y, Meir R, Jung K et al. Coalitional structure generation in skill games. In Proc. the 24th AAAI Conference on Artificial Intelligence, July 2010, pp.703-708.

[40] Nguyen T D. A fast approximation algorithm for solving the complete set packing problem. European Journal of Operational Research, 2014, 237(1):62-70.

[41] Sen S, Dutta P. Search for optimal coalition structures. In Proc. the 4th International Conference on Multi-Agent Systems, July 2000, pp.287-292.

[42] Yang J, Luo Z. Coalition formation mechanism in multiagent systems based on genetic algorithms. Applied Soft Computing, 2007, 7(2):561-568.

[43] Keinänen H. Simulated annealing for multi-agent coalition formation. In Proc. the 3rd KES International Symposium on Agent and Multi-Agent Systems-Technologies and Applications, June 2009, pp.30-39.

[44] Kennedy J, Eberhart R C. A discrete binary version of the particle swarm algorithm. In Proc. IEEE International Conference on Systems, Man, and Cybernetics, October 1997, pp.4104-4108.

[45] Pampará G, Engelbrecht A P, Franken N. Binary differential evolution. In Proc. IEEE International Conference on Evolutionary Computation, July 2006, pp.1873-1879.

[46] Pedrasa M A A, Spooner T D, MacGill I F. Scheduling of demand side resources using binary particle swarm optimization. IEEE Transactions on Power Systems, 2009, 24(3):1173-1181.

[47] Cao R F, Wang X C, Wu Z K et al. A parallel Markov cerebrovascular segmentation algorithm based on statistical model. Journal of Computer Science and Technology, 2016, 31(2):400-416.

[48] Du H Z, Xia N, Jiang J G et al. A Monte Carlo enhanced PSO algorithm for optimal QoM in multi-channel wireless networks. Journal of Computer Science and Technology, 2013, 28(3):553-563.

[49] He R J, Yang Z Y. Differential evolution with adaptive mutation and parameter control using Lévy probability distribution. Journal of Computer Science and Technology, 2012, 27(5):1035-1055.

[50] Lu X F, Tang K. Classification- and regression-assisted differential evolution for computationally expensive problems. Journal of Computer Science and Technology, 2012, 27(5):1024-1034.

[51] Kennedy J, Eberhart R C. Particle swarm optimization. In Proc. IEEE International Conference on Neural Networks, November 1995, pp.1942-1948.

[52] Storn R, Price K. Differential evolution-A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization, 1997, 11(4):341-359.

[53] Altman D G, Machin D, Bryant T N et al. Statistics with Confidence:Confidence Intervals and Statistical Guidelines. London, England:BMJ Books, 2000.

[54] Elkind E, Chalkiadakis G, Jennings N R. Coalition structures in weighted voting games. In Proc. the 18th European Conference on Artificial Intelligence, July 2008, pp.393-397.

[55] Deng X, Papadimitriou C H. On the complexity of cooperative solution concepts. Mathematics of Operations Research, 1994, 19(2):257-266.

[56] Voice T, Polukarov M, Jennings N R. Coalition structure generation over graphs. Journal of Artificial Intelligence Research, 2012, 45(1):165-196.

[57] Bachrach Y, Kohli P, Kolmogorov V et al. Optimal coalition structure generation in cooperative graph games. In Proc. the 27th AAAI Conference on Artificial Intelligence, July 2013, pp.81-87.

[58] Kalai E, Zemel E. Totally balanced games and games of flow. Mathematics of Operations Research, 1982, 7(3):476-478.

[59] Bachrach Y, Rosenschein J S.Power in threshold network flow games. Autonomous Agents and Multi-Agent Systems, 2009, 18(1):106-132.

[60] Xia N, Jiang J, Hu C. Solution to agent coalition problem using improved ant colony optimization algorithm. In Proc. IEEE/WIC/ACM International Conference on Intelligent Agent Technology, September 2004, pp.475-478.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .
[10] Li Minghui;. CAD System of Microprogrammed Digital Systems[J]. , 1987, 2(3): 226 -235 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved