NONCONVEX GAMES WITH SIDE CONSTRAINTS.

This paper develops an optimization-based theory for the existence and uniqueness of equilibria of a noncooperative game wherein the selfish players' optimization problems are nonconvex and there are side constraints and an associated price clearance to be satisfied by the equilibria. A new concept of equilibrium for such a noncouvex game, which we term a "quasi-Nash equilibrium" (QNE), is introduced as a solution of the variation inequality (VI) obtained by aggregating the first order optimality conditions of the players' problems while retaining the convex constraints (if any) ill the defining set of the VI. Under a second-order sufficiency condition from nonlinear programming, a QNE becomes a local Nash equilibrium of the game. Uniqueness of a QNE is established using a degree-theoretic proof. Under a key bounded ness property of the Karush-Kuhn-Tucker multipliers of the nonconvex constraints and the positive definiteness of the Hessians of the players' Lagrangian functions, we establish the single-valuedness of the players' best-response maps, from which the existence of a Nash equilibrium (NE) of the nonconvex game follows. We also present a distributed algorithm for computing an NE of such a game and provide a matrix-theoretic condition for the convergence of the algorithm. An application is presented that pertains to a special multi-leader follower game wherein the nonconvexity is due to the followers' equilibrium conditions in the leaders' optimization problems. Another application to a cognitive radio paradigm in a signal processing game is described in detail in [G. Scutari and J.S. Pang, IEEE Trans. Inform. Theory, submitted; J.S. Pang and G. Scutari, Joint IEEE Trans. Signal Process, submitted]. [ABSTRACT FROM AUTHOR]