[Home]
[
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Generalized Nash Equilibrium Problems of Polynomials
Xindong Tang
UCSD
Abstract:
The Generalized Nash Equilibrium Problem (GNEP) is a kind of games 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 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 nonexistence of GNEs. Numerical experiments are presented to show the efficiency of the methods. The Moment-SOS hierarchy of semidefinite relaxations are 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.
Tuesday, April 20, 2021
11:00AM Zoom ID 939 3177 8552
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Directors:
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Xindong Tang
UCSD
Abstract:
The Generalized Nash Equilibrium Problem (GNEP) is a kind of games 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 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 nonexistence of GNEs. Numerical experiments are presented to show the efficiency of the methods. The Moment-SOS hierarchy of semidefinite relaxations are 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.
Tuesday, April 20, 2021
11:00AM Zoom ID 939 3177 8552