Problem Research And Distributed Algorithm Design Based On Non-cooperative Game

Game theory is a discipline that studies the strategies utilized by relevant parties in games played under specific constraints between multiple individuals or teams.Currently,as game theory is increasingly applied in fields such as economics,operations research,and engineering,research results on various types of game problems continue to emerge.Non-cooperative games are one type of game problem,with the most important research problem being Nash equilibrium.As game networks gradually increase in size,the requirements for computing power and efficiency in solving Nash equilibrium problems are becoming increasingly high.Traditional centralized algorithms require a central node and have disadvantages such as poor robustness,low efficiency,and limited practicality.Distributed algorithms,which are based on a ”decentralized” concept and do not require a central node,have characteristics such as a large number of intelligent agents,fast optimization convergence speed,versatile algorithm application scenarios,and low resource utilization,making them widely applied in optimization and artificial intelligence fields in recent years.With the wide application of game problem in many fields,its problem model becomes more and more complex,and more and more factors or conditions need to be considered.Therefore,it is an important challenge to design efficient algorithms for the generalized Nash equilibrium(GNE)problems in non-cooperative games.The traditional centralized algorithm can not adapt to the current complex problems.Based on the advantages of distributed algorithms,this paper designs distributed algorithms to solve the GNE problem in non-cooperative games.Specifically,we first analyze the generalized Nash equilibrium problem model in non-cooperative games and aggregative games,considering local feasible sets and globally shared coupled affine constraints.We then obtain the Karush-Kuhn-Tucker(KKT)conditions of the problem model using the primal-dual method.Simultaneously,we analyze the variational form of the problem model,establish a connection between the KKT conditions of the variational inequality and the original problem,and finally design a distributed algorithm based on the KKT conditions of the variational problem.The specific contents include the following three aspects:(1)For general non-cooperative game models,two distributed primal-dual proximal gradient algorithms are designed for the cases of complete decision information and partial decision information,respectively.Both algorithms use edge-based consensus on undirected connected graphs.Additionally,local constant step sizes and local relaxation parameters are adopted in both algorithms to effectively avoid conservative parameter selection.It is worth noting that in the theoretical analysis of the algorithms,we use more general Lipschitz continuity and strong monotonicity assumptions,make the algorithm fully distributed.Under certain necessary assumptions,the convergence of the algorithm is proven.(2)For the GNE problem in aggregative games,we also consider a model with local feasible sets and global shared coupled affine constraints for each agent.A distributed primal-dual operator splitting algorithm is designed.The characteristic of aggregative games is the existence of an aggregation structure in the objective function.Therefore,aggregative games are a type of partial decision information game.In the algorithm design,we introduce local estimation for the aggregation information,so each agent only needs to estimate the aggregation information locally,which allows for the use of only local information in computation.This algorithm uses fewer computational resources and is more suitable for large-scale networks.(3)In terms of theoretical analysis,inspired by the theory of monotone operators and averaging operators,we have established a convergence analysis framework for the distributed algorithm.In the theoretical analysis,we first split the operator and analyze its properties separately.Based on some necessary assumptions,we prove that the operator is a monotone operator or an averaging operator,and under the condition that the step size is less than the explicit upper bound,we prove the convergence of the algorithm.This provides an effective reference for subsequent work.In summary,this paper builds on existing research to address the GNE problem in non-cooperative games and a class of aggregative games,using the primal-dual,proximal operator,and operator splitting methods to design distributed algorithms.The results of this study will provide valuable references for the research on GNE problems and the design of distributed algorithms.