First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems

The Nash equilibrium problem (NEP) [Nash, 1950, 1951] is a central topic in mathematics, economics and computer science. NEP problems have begun to play an important role in machine learning as researchers begin to focus on decisions, incentives and the dynamics of multi-agent learning. In a classical NEP, the payoff to each player depends upon the strategies chosen by all, but the domains from which the strategies are to be chosen for each player are independent of the strategies chosen by other players. The goal is to arrive at a joint optimal outcome where no player can do better by deviating unilaterally [Osborne and Rubinstein, 1994, Myerson, 2013]. The generalized Nash equilibrium problem (GNEP) is a natural generalization of an NEP where the choice of an action by one agent affects both the payoff and the domain of actions of all other agents [Arrow and Debreu, 1954]. Its introduction in the 1950's provided the foundation for a rigorous theory of economic equilibrium [Debreu, 1952, Arrow and Debreu, 1954, Debreu, 1959]. More recently, the GNEP problem has emerged as a powerful paradigm in a range of engineering applications involving noncooperative games. In particular, in the survey of Facchinei and Kanzow [2010a], three general classes of problems were developed in detail: the abstract model of general equilibrium, power allocation in a telecommunication system, and environmental pollution control.