Abstract: Game theory is an important research branch of operations research. It can also be seen as a mathematical optimization method for solving the optimization problem of optimal strategies corresponding to multiple individuals or groups under certain constraints. Game theory currently has a wide application background in many fields such as political economy, social management science, and national defense and military. In its application, it can be divided into cooperative game problems and noncooperative game problems based on whether the players cooperate or not. The noncooperative game problem studies how people utilize the optimal strategy to maximize their benefits in a situation where interests are mutually constrained. The Nash equilibrium theory has important applications in noncooperative game problems. Nash equilibrium indicates that each participant has a finite number of strategies and allows for mixed strategies, and the Nash equilibrium point must exist. The Nash equilibrium problem of noncooperative games has broad application prospects in the current information age. In the fields of artificial intelligence and new generation mobile communication technology, Nash equilibrium problems based on large-scale intelligence have been extensively proposed, and the research on noncooperative game problem is of great significance. Complementary problems are also a kind of optimization problems with a wide range of mathematical and operational research applications. The theories and methods of complementary problems are widely applied to various related fields, such as economic equilibrium problems, optimal control problems and related field. With the arrival of the big data era, tensor, as high-dimensional arrays, is used to expand the high-dimensional of matrix. In recent years, tensors have been widely used in fields such as multidimensional image processing and complex data analysis. As combining research of complementary and tensor, the research on tensor complementarity problem has developed rapidly. And the concepts of tensor eigenvalue complementarity problem and stochastic tensor complementarity problem have been proposed. The research on tensor complementarity problem has made significant progress in terms of solution set properties and error bound analysis. The proposal of various structural tensors has laid a theoretical foundation for the study of tensor complementarity problem in game problem and sparse solution problem. Conjugate gradient method, as an important optimization method, has the characteristics of simple structure, small computational storage, and global convergence. Since it was accepted, it has been widely applied in solving large-scale equations, large-scale unconstrained optimization problems, and other related optimization problems. In recent years, the application of first-order methods with low computational complexity, fast solving, and moderate accuracy in solving machine learning has become increasingly widespread. As an important class of first-order methods, conjugate gradient methods will attract widespread research attention again.
In this paper, a smoothing modified Hestenes-Stiefel(HS) conjugate gradient method is proposed to solve the multi-person noncooperative games problem. The general model of multi-person noncooperative game is transformed into a tensor complementarity problem, further into a non-smooth equation system by using complementarity function, and then smoothed. Finally, it is equivalent to an unconstrained optimization problem. The proposed method can randomly select initial points, and has the characteristics of high stability and small storage, making it an effective method for solving non-cooperative game problems with multiple players. At the end of the paper, numerical examples and conclusions are presented, and numerical results of the effectiveness for the proposed method are presented in the numerical examples section.

Key words: multi-person noncooperative games, Nash equilibrium, tensor complementarity problem, smoothing NHS conjugate gradient method, global convergence

摘要： 针对多人非合作博弈问题,提出了一种光滑修正Hestenes-Stiefel(HS)共轭梯度算法。通过将多人非合作博弈的一般模型转化为张量互补问题并利用互补函数将其转为非光滑方程系统,再对其进行光滑化处理,最终等价转换为求解无约束优化问题。提出的算法可以对初始点进行随机选取,同时该算法具有稳定性高,存储量小的特点,是求解多人非合作博弈问题的一种有效算法。文中最后给出了数值算例与结论,数值算例部分给出了表明所提算法有效性的结果。

关键词: 多人非合作博弈, 纳什均衡, 张量互补问题, 光滑NHS共轭梯度算法, 全局收敛