Generalized Nash Equilibrium Problems with Mixed-Integer Variables
share
We consider generalized Nash equilibrium problems (GNEPs) with non-convex strategy spaces and non-convex cost functions. This general class of games includes the important case of games with mixed-integer variables for which only a few results are known in the literature. We present a new approach to characterize equilibria via a convexification technique using the Nikaido-Isoda function. To any given instance I of the GNEP, we derive a convexified instance I^conv and show that every feasible strategy profile for I is an equilibrium if and only if it is an equilibrium for I^conv and the convexified cost functions coincide with the initial ones. Based on this general result we identify important classes of GNEPs which allow us to reformulate the equilibrium problem via standard optimization problems. 1. First, quasi-linear GNEPs are introduced where for fixed strategies of the opponent players, the cost function of every player is linear and the convex hull of the respective strategy space is polyhedral. For this game class we reformulate the equilibrium problem for I^conv as a standard (non-linear) optimization problem. 2. Secondly, we study GNEPs with joint constraint sets. We introduce the new class of projective-closed GNEPs for which we show that I^conv falls into the class of jointly convex GNEPs. As an important application, we show that general GNEPs with shared binary sets {0,1}^k are projective-closed. 3. Thirdly, we discuss the class of quasi-separable GNEPs in which roughly speaking the players' cost functions depend on their own strategy only. We show that they admit a special structure leading to a characterization of equilibria via solutions of a convex optimization problem. 4. Finally, we present numerical results regarding the computation of equilibria for a class of quasi-linear and projective-closed GNEPs.
READ FULL TEXT