Heterogeneous Multiagent Task Allocation via Cooperative Exchange Strategies for Equilibrium-Improving: A Potential Game Framework

Task allocation in multiagent systems is a critical challenge due to the heterogeneity of tasks and agents, where tasks have varying resource requirements and agents possess differing resource supplies. During execution, agents' resources deplete while tasks' requirements dynamically decrease. This problem has broad applications, such as optimally deploying UAVs equipped with diverse medical supplies in disaster rescue scenarios to minimize casualties. To address this, this article proposes a coalition formation game model, formulated as a potential game. We theoretically prove the submodularity of both the coalition utility function and the global utility function. Based on this submodularity, we establish that the efficiency lower bound of any Nash equilibrium in the proposed game model is given by $e / (2e-1)$ , significantly outperforming the 50% bound reported in prior studies. Furthermore, we introduce an inertia-based log-linear learning algorithm enhanced with a multiagent cooperative exchange mechanism, which enables the system to escape from suboptimal equilibria and improve global utility. In addition, we extend the algorithm to accommodate local communication constraints and dynamic allocation scenarios. Extensive experimental evaluations demonstrate that our proposed method achieves superior performance across diverse scenarios compared to existing algorithms.