Design And Analysis Of Distributed Multi-agent Game Algorithm Under Coupling Constraints

Multi-agent game is a hot topic in distributed algorithm research.There are many applications in resource allocation,strategy formulation and automatic control,especially in market pricing model and smart grid design.In terms of theoretical analysis,the main objective of multi-agent game is to solve its Nash equilibrium.In Nash equilibrium,the strategies of all agents reach equilibrium and cannot gain more benefits by changing their own strategies.When solving Nash equilibrium,most of the current researches focus on the expansion of game problems,game network design and algorithm acceleration.However,there are still some areas to be improved:on the one hand,the multi-agent game still tends to choose undirected graph in the communication network structure,which brings narsh equirements to the application of network graph;On the other hand,distributed game algorithms generally adopt fixed step size.Although the range of step size is given,the appropriate step size selection method is not given,which makes step size selection a big problem in practical application.In view of the above problems,this thesis carries out two aspects of research:1.For the multi-agent game problem with coupling constraints,a completely distributed Nash equilibrium search algorithm,namely Generalized Pseudo-gradient(GPG)algorithm is proposed.It allows dynamics to ensure convergence in unbalanced digraph,and of course it is also convergent in undirected graph.After that,this thesis also extends it to the intermittent communication network,and allows the convergence of the algorithm under the condition of intermittent communication.It reduces the burden on the communication link to a certain extent.This allows more changes in communication networks,including the scalability of digraphs and the multiplexing of communication links.In theoretical analysis,the forward and backward splitting method which is an operator analysis method,is used to cut the algorithm into various operators.After this,the monotonicity of each partial operator in weighted Hilbert space is guaranteed by adding the left PF(Perron Frobenius)eigenvector.In addition,by setting a preprocessing matrix,the algorithm is finally transformed into two composite operators.By analyzing the nonexpansion of the composite operators,the convergence conditions can be obtained.This thesis choose Nash-Cournot game to show the results.The GPG algorithm is compared with a fully distributed algorithm proposed in the previous studies.Afterwards,the simulation diagram of the influence of intermittent communication on the convergence of the algorithm is given.2.For the multi-agent game problem in time-varying networks,an adaptive step size algorithm is proposed.In order to achieve better descent effect,this thesis uses a method to estimate the step size of Newton descent method to obtain BB step size,which specifically uses the secant equation method.However,in the time-varying networks,the range of step size will change with the change of communication network,so this thesis designs a time-varying shrinkage parameter to compress BB step size in a small range.It ensures that the step size has a better convergence effect on the algorithm as much as possible.The time-varying shrinkage parameter is related to the singular value of adjacency matrix.In addition,this thesis also adapts this algorithm to the game with coupling constraints,and changes the shirinkage parameter into a scalar closely related to the constraints.Whether in unconstrained or coupled constrained games,the algorithm based on BB step size proposed in this thesis can converge to the same Nash equilibrium point in each time-varying network,which is also explained in the theoretical analysis.It is not necessary to assume that the game problem has the same Nash equilibrium point in the undirected graph at all times.This thesis compares the convergence results of BB step algorithm with Armijo step algorithm and fixed step algorithm,which shows that the algorithm proposed in this thesis has advantages in time-varying networks.