一类纳什均衡问题的求解算法

The method for a class of Nash equilibrium game

随着纳什均衡问题被应用到多个领域,其求解算法也得到了越来越多的关注。但鉴于纳什均衡是由一系列优化问题组成的复杂系统,经典的约束优化算法不能被直接应用于求解该问题中,导致求解该问题的困难。对于一类效用函数是强凸的纳什均衡问题,利用Nikaido-Isoda函数将其转化为一类与之完全等价的光滑约束优化问题进行求解是一种有效途径。本文在纳什均衡问题效用函数的梯度具有强单调性这一假设条件下给出求解此类问题的Nikaido-Isoda算法并证明该算法具有全局收敛性。最后,通过求解两类经典纳什均衡问题,验证了该算法的可行性和有效性。

The Nash equilibrium game has been applied to many fields,the algorithm for the problem has attracted much attention in recent years.But since the Nash equilibrium game is a complex system composed by a series of optimization problems,the standard optimization method cannot be directly used for the problem,this leads to the difficulty of solving it.For a class of Nash equilibrium games with strongly convex payoff functions,using the Nikaido-Isoda function to transform the Nash equilibrium game into a smooth constraint optimization problem is an effective method to solve the Nash equilibrium game.Based on the gradient strongly monotonity of the Nash equilibrium payoff function,we present a Nikaido-Isoda algorithm for the game and the global convergence of the algorithm is proved.Finally,by solving two kinds of standard Nash equilibrium problems,the feasibility and effectiveness of the Nikaido-Isoda algorithm are verified.