An Adaptive Collaborative Neurodynamic Approach to Compute Nash Equilibrium in Normal-Form Games

Abstract

The Nash Equilibrium (NE), one of the elegant and fundamental concepts in game theory, plays a crucial part within various fields, including engineering and computer science. However, efficiently computing an NE in normal-form games remains a significant challenge, particularly for large-scale problems. In contrast to widely applied simplicial and homotopy methods, this paper designs a novel Adaptive Collaborative Neurodynamic Approach (ACNA), which for the first time guarantees both exact and global NE computation for general $N$-player normal-form games with mixed strategies, where the payoff functions are non-convex and the pseudo-gradient is non-monotone. Additionally, leveraging the adaptive penalty method, the ACNA ensures its state enters the constraint set in finite time, which avoids the second-order sufficiency conditions required by Lagrangian methods, and the computationally complicated penalty parameter estimation needed by exact penalty methods. Furthermore, by incorporating the particle swarm algorithm, it is demonstrated that the ACNA achieves global convergence to an exact NE with probability one. At last, a simulation is conducted to validate the effectiveness of the proposed approach.