UC San Diego

The Generalized Nash Equilibrium Problem (GNEP) is a kind of game to find strategies for a group of players such that each player’s objective function is optimized, given other players’ strategies. If all the objective and constraining functions involved are polynomials, we call the problem a Generalized Nash Equilibrium Problem of Polynomials (GNEPP). When the constraining functions of each player are independent of other player’s strategies, the GNEP is called a (standard) Nash Equilibrium Problem (NEP). The GNEP is said to be convex if each player’s optimization is a convex optimization problem, given other players’ strategies.

For nonconvex Nash equilibrium problems that are given by polynomial functions, we formulate efficient polynomial optimization problems for computing Nash equilibria. We show that under generic assumptions, the method can find one or even all Nash equilibria if they exist, or detect the nonexistence of Nash equilibria. For convex GNEPPs, we introduce rational and parametric expressions for Lagrange multipliers to formulate polynomial optimization for computing Generalized Nash Equilibria (GNEs). We prove that under some specific assumptions, the method can find a GNE if there exists one, or detect the nonexistence of GNEs. Numerical experiments are presented to show the efficiency of the methods. The Moment-SOS hierarchy of semidefinite relaxations is used to solve the polynomial optimization.

Moreover, we study the Gauss-Seidel method for solving the nonconvex GNEPPs. We give a certificate for a class of GNEPPs such that the Gauss-Seidel method is guaranteed to converge, and the numerical experiments show that the Gauss-Seidel method can solve many GNEPPs efficiently.