Finding the Largest Successful Coalition under the Strict Goal Preferences of Agents

Su, Zhaopin1,2,3,4; Zhang, Guofu1,2,3,4; Yue, Feng1,2,3,4; He, Jindong1,2,3,4; Li, Miqing5; Li, Bin6; Yao, Xin5,7

2020-09

10.1145/3412370

ACM T AUTON ADAP SYS   影响因子和分区

1556-4665

1556-4703

Coalition formation has been a fundamental form of resource cooperation for achieving joint goals in multiagent systems. Most existing studies still focus on the traditional assumption that an agent has to contribute its resources to all the goals, even if the agent is not interested in the goal at all. In this article, a natural extension of the traditional coalitional resource games (CRGs) is studied from both theoretical and empirical perspectives, in which each agent has uncompromising, personalized preferences over goals. Specifically, a new CRGs model with agents' strict preferences for goals is presented, in which an agent is willing to contribute its resources only to the goals that are in its own interest set. The computational complexity of the basic decision problems surrounding the successful coalition is reinvestigated. The results suggest that these problems in such a strict preference way are complex and intractable. To find the largest successful coalition for possible computation reduction or potential parallel processing, a flow-network-based exhaust algorithm, called FNetEA, is proposed to achieve the optimal solution. Then, to solve the problem more efficiently, a hybrid algorithm, named 2D-HA, is developed to find the approximately optimal solution on the basis of genetic algorithm, two-dimensional (2D) solution representation, and a heuristic for solution repairs. Through extensive experiments, the 2D-HA algorithm exhibits the prominent ability to provide reassurances that the optimal solution could be found within a reasonable period of time, even in a super-large-scale space.

Coalitional resource games goal preferences of agents successful coalition network flows genetic algorithm heuristic

SCI ; EI

英语

其他

National Natural Science Foundation of China[61573125] ; Anhui Provincial Key Research and Development Program[202004d07020011] ; MOE (Ministry of Education in China) Project of Humanities and Social Sciences[19YJC870021][18YJC870025] ; Shenzhen Peacock Plan[KQTD2016112514355531] ; Fundamental Research Funds for the Central Universities[PA2020GDKC0015][PA2019GDQT0008][PA2019GDPK0072]

Computer Science

Computer Science, Artificial Intelligence ; Computer Science, Information Systems ; Computer Science, Theory & Methods

WOS:000575714500003

ASSOC COMPUTING MACHINERY

20204209349073

Multi agent systems ; Software agents ; Complex networks ; Optimal systems

Computer Systems and Equipment:722 ; Systems Science:961

Web of Science

1.Hefei Univ Technol, Minist Educ, Key Lab Knowledge Engn Big Data, Hefei, Peoples R China
2.Hefei Univ Technol, Sch Comp Sci & Informat Engn, Hefei, Peoples R China
3.Hefei Univ Technol, Intelligent Interconnected Syst Lab Anhui Prov, Hefei 230009, Peoples R China
4.Hefei Univ Technol, Anhui Prov Key Lab Ind Safety & Emergency Technol, Hefei, Peoples R China
5.Univ Birmingham, Sch Comp Sci, CERCIA, Birmingham, W Midlands, England
6.Univ Sci & Technol China, Sch Informat Sci & Technol, Hefei, Peoples R China
7.Southern Univ Sci & Technol, Dept Comp Sci & Engn, Shenzhen Key Lab Computat Intelligence, Shenzhen, Peoples R China

Su, Zhaopin,Zhang, Guofu,Yue, Feng,et al. Finding the Largest Successful Coalition under the Strict Goal Preferences of Agents[J]. ACM T AUTON ADAP SYS,2020,14(4).

Su, Zhaopin.,Zhang, Guofu.,Yue, Feng.,He, Jindong.,Li, Miqing.,...&Yao, Xin.(2020).Finding the Largest Successful Coalition under the Strict Goal Preferences of Agents.ACM T AUTON ADAP SYS,14(4).

Su, Zhaopin,et al."Finding the Largest Successful Coalition under the Strict Goal Preferences of Agents".ACM T AUTON ADAP SYS 14.4(2020).