Lightweight Log-Linear Learning With Neighborhood Search for Equilibrium Selection in Finite Potential Games
针对动作集大的有限势博弈，提出一种轻量级对数线性动力学，通过邻域搜索生成候选动作集，避免遍历全部动作，在异步和独立更新规则下证明渐近收敛，并通过多卫星任务分配问题验证其求解时间优势。
In this article, we consider the problem of equilibrium selection in multiplayer finite potential games with large-size action sets. Traditional learning approaches often require players to traverse the entire action set to evaluate the utility of each action, which can be computationally intensive and inefficient. To overcome this limitation, we leverage the idea of neighborhood search into the game-theoretical learning process for the first time by generating neighborhood candidate action sets for exploration and evaluation. As such, we propose a lightweight log-linear dynamics for efficient equilibrium selection in finite potential games. Asymptotic convergence is proved under both asynchronous and independent revision rules with the help of resistance tree theory. Furthermore, through the multisatellite cooperative task allocation (MSCTA) problem, we elaborate on how to encode the players’ actions and how to generate the neighborhood structure. Simulation results demonstrate that the proposed method significantly outperforms the existing game-theoretic learning methods, notably in terms of solution time.