There are a few studies that focus on solution methods for finding a Nash equilibrium of zero-sum games. We discuss the use of Karmarkar’s interior point method to solve the Nash equilibrium problems of a zero-sum ga...There are a few studies that focus on solution methods for finding a Nash equilibrium of zero-sum games. We discuss the use of Karmarkar’s interior point method to solve the Nash equilibrium problems of a zero-sum game, and prove that it is theoretically a polynomial time algorithm. We implement the Karmarkar method, and a preliminary computational result shows that it performs well for zero-sum games. We also mention an affine scaling method that would help us compute Nash equilibria of general zero-sum games effectively.展开更多
In this paper, the optimal variational generalized Nash equilibrium(v-GNE) seeking problem in merely monotone games with linearly coupled cost functions is investigated, in which the feasible strategy domain of each a...In this paper, the optimal variational generalized Nash equilibrium(v-GNE) seeking problem in merely monotone games with linearly coupled cost functions is investigated, in which the feasible strategy domain of each agent is coupled through an affine constraint. A distributed algorithm based on the hybrid steepest descent method is first proposed to seek the optimal v-GNE. Then, an accelerated algorithm with relaxation is proposed and analyzed, which has the potential to further improve the convergence speed to the optimal v-GNE. Some sufficient conditions in both algorithms are obtained to ensure the global convergence towards the optimal v-GNE. To illustrate the performance of the algorithms, numerical simulation is conducted based on a networked Nash-Cournot game with bounded market capacities.展开更多
文摘There are a few studies that focus on solution methods for finding a Nash equilibrium of zero-sum games. We discuss the use of Karmarkar’s interior point method to solve the Nash equilibrium problems of a zero-sum game, and prove that it is theoretically a polynomial time algorithm. We implement the Karmarkar method, and a preliminary computational result shows that it performs well for zero-sum games. We also mention an affine scaling method that would help us compute Nash equilibria of general zero-sum games effectively.
基金supported by the National Natural Science Foundation of China(Basic Science Center Program)(61988101)the Joint Fund of Ministry of Education for Equipment Pre-research (8091B022234)+3 种基金Shanghai International Science and Technology Cooperation Program (21550712400)Shanghai Pilot Program for Basic Research (22TQ1400100-3)the Fundamental Research Funds for the Central UniversitiesShanghai Artifcial Intelligence Laboratory。
文摘In this paper, the optimal variational generalized Nash equilibrium(v-GNE) seeking problem in merely monotone games with linearly coupled cost functions is investigated, in which the feasible strategy domain of each agent is coupled through an affine constraint. A distributed algorithm based on the hybrid steepest descent method is first proposed to seek the optimal v-GNE. Then, an accelerated algorithm with relaxation is proposed and analyzed, which has the potential to further improve the convergence speed to the optimal v-GNE. Some sufficient conditions in both algorithms are obtained to ensure the global convergence towards the optimal v-GNE. To illustrate the performance of the algorithms, numerical simulation is conducted based on a networked Nash-Cournot game with bounded market capacities.
