This paper designs a distributed algorithm to seek generalized Nash equilibria of a robust game with uncertain coupled constraints.Due to the uncertainty of parameters in set constraints,the authors aim to find a gene...This paper designs a distributed algorithm to seek generalized Nash equilibria of a robust game with uncertain coupled constraints.Due to the uncertainty of parameters in set constraints,the authors aim to find a generalized Nash equilibrium in the worst case.However,it is challenging to obtain the exact equilibria directly because the parameters are from general convex sets,which may not have analytic expressions or are endowed with high-dimensional nonlinearities.To solve this problem,the authors first approximate parameter sets with inscribed polyhedrons,and transform the approximate problem in the worst case into an extended certain game with resource allocation constraints by robust optimization.Then the authors propose a distributed algorithm for this certain game and prove that an equilibrium obtained from the algorithm induces anε-generalized Nash equilibrium of the original game,followed by convergence analysis.Moreover,resorting to the metric spaces and the analysis on nonlinear perturbed systems,the authors estimate the approximation accuracy related toεand point out the factors influencing the accuracy ofε.展开更多
A vector space structure is proposed for the set of finite games with fixed numbers of players and strategies for each players.Two statical equivalences are used to reduce the dimension of finite games.Under the vecto...A vector space structure is proposed for the set of finite games with fixed numbers of players and strategies for each players.Two statical equivalences are used to reduce the dimension of finite games.Under the vector space structure the subspaces of exact and weighted potential games are investigated.Formulas are provided to calculate them.Then the finite evolutionary games(EGs)are considered.Strategy profile dynamics is obtained using different strategy updating rules(SURs).Certain SURs,which assure the convergence of trajectories to pure Nash equilibriums,are investigated.Using the vector space structure,the projection of finite games to the subspace of exact(or weighted)potential games is considered,and a simple formula is given to calculate the projection.The convergence of near potential games to anε-equilibrium is studied.Further more,the Lyapunov function of EGs is defined and its application to the convergence of EGs is presented.Finally,the near potential function for an EG is defined,and it is proved that if the near potential function of an EG is a Lyapunov function,the EG will converge to a pure Nash equilibrium.Some examples are presented to illustrate the results.展开更多
基金supported partly by the National Key R&D Program of China under Grant No.2018YFA0703800the Strategic Priority Research Program of Chinese Academy of Sciences under Grant No.XDA27000000the National Natural Science Foundation of China under Grant Nos.61873262 and 61733018。
文摘This paper designs a distributed algorithm to seek generalized Nash equilibria of a robust game with uncertain coupled constraints.Due to the uncertainty of parameters in set constraints,the authors aim to find a generalized Nash equilibrium in the worst case.However,it is challenging to obtain the exact equilibria directly because the parameters are from general convex sets,which may not have analytic expressions or are endowed with high-dimensional nonlinearities.To solve this problem,the authors first approximate parameter sets with inscribed polyhedrons,and transform the approximate problem in the worst case into an extended certain game with resource allocation constraints by robust optimization.Then the authors propose a distributed algorithm for this certain game and prove that an equilibrium obtained from the algorithm induces anε-generalized Nash equilibrium of the original game,followed by convergence analysis.Moreover,resorting to the metric spaces and the analysis on nonlinear perturbed systems,the authors estimate the approximation accuracy related toεand point out the factors influencing the accuracy ofε.
基金supported by the National Key Research and Development Program of China under Grant No.2016YFB0901902the National Natural Science Foundation of China under Grant Nos.61573344,61333001,61733018,and 61374168
基金supported partly by the National Natural Science Foundation of China under Grant Nos.61273013,61333001,61104065,and 61374168
文摘A vector space structure is proposed for the set of finite games with fixed numbers of players and strategies for each players.Two statical equivalences are used to reduce the dimension of finite games.Under the vector space structure the subspaces of exact and weighted potential games are investigated.Formulas are provided to calculate them.Then the finite evolutionary games(EGs)are considered.Strategy profile dynamics is obtained using different strategy updating rules(SURs).Certain SURs,which assure the convergence of trajectories to pure Nash equilibriums,are investigated.Using the vector space structure,the projection of finite games to the subspace of exact(or weighted)potential games is considered,and a simple formula is given to calculate the projection.The convergence of near potential games to anε-equilibrium is studied.Further more,the Lyapunov function of EGs is defined and its application to the convergence of EGs is presented.Finally,the near potential function for an EG is defined,and it is proved that if the near potential function of an EG is a Lyapunov function,the EG will converge to a pure Nash equilibrium.Some examples are presented to illustrate the results.