Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Nonconvex Nash Games with Side Constraints

Optimization

Speaker: Professor Jong-Shi Pang, University of Ilinois
Location: 1147 MSB
Start time: Mon, Dec 5 2011, 4:10PM

This lecture develops an optimization-based theory for the existence and uniqueness of equilibria of a non-cooperative game wherein the selfish players' optimization problems are nonconvex and there are side constraints and associated price clearance to be satisfied by the equilibria.   A new concept of equilibrium for such a nonconvex game, which we term a "quasi-Nash equilibrium" (QNE), is introduced as a solution of the variational inequality (VI) obtained by aggregating the first-order optimality conditions of the players' problems while retaining the convex constraints (if any) in the defining set of the VI.  Under a second-order sufficiency condition from nonlinear programming, a quasi-Nash equilibrium becomes a local Nash equilibrium of the game.  Uniqueness of a QNE is established using a degree-theoretic proof.  Under a key boundedness property of the Karush-Kuhn-Tucker multipliers, we establish the single-valuednesse 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 a NE of such a game and provide a matrix-theoretic condition for the convergence of the algorithm.  Two applications of the results are presented: one application 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 pertains to a cognitive radio paradigm in a signal processing game that extends much of the recent work in this area where the joint sensing, detection, and power allocation are all combined in one game-theoretic framework.