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. © 2020 ACM.
|ACM Transactions on Autonomous and Adaptive Systems
|Published - 31 Dec 2019
Bibliographical noteZ. Su and G. Zhang contributed equally to this research. This work was supported in part by the National Natural Science Foundation of China under Grant No. 61573125, in part by the Anhui Provincial Key Research and Development Program under Grant No. 202004d07020011, in part by the MOE (Ministry of Education in China) Project of Humanities and Social Sciences under Grants No. 19YJC870021 and No. 18YJC870025, in part by the Shenzhen Peacock Plan under Grant No. KQTD2016112514355531, and in part by the Fundamental Research Funds for the Central Universities under Grants No. PA2020GDKC0015, No. PA2019GDQT0008, and No. PA2019GDPK0072.
- Coalitional resource games
- Genetic algorithm
- Goal preferences of agents
- Network flows
- Successful coalition