Heterogeneous Multiagent Task Allocation via Cooperative Exchange Strategies for Equilibrium-Improving: A Potential Game Framework
针对异构任务和智能体的资源分配问题，提出基于势博弈的联盟形成模型，证明纳什均衡效率下界为e/(2e-1)，并设计惯性对数线性学习算法结合合作交换机制，提升全局效用，适用于灾害救援等动态场景。
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.