Generalized Nash Equilibrium Problems

The Generalized Nash Equilibrium Problem is an important model that has its roots in the economic sciences but is being fruitfully used in many different fields. In this survey paper we aim at discussing its main properties and solution algorithms, pointing out what could be useful topics for future research in the field.     

Gap Functions for Quasivariational Inequalities and Generalized Nash Equilibrium Problems

The gap function (or merit function) is a classic tool for reformulating a Stampacchia variational inequality as an optimization problem. In this paper, we adapt this technique for quasivariational inequalities, that is, variational inequalities in which the constraint set depends on the current point. Following Fukushima (J. Ind. Manag. Optim. 3:165–171, 2007), an axiomatic approach is proposed. Error bounds for quasivariational inequalities are provided and an application to generalized Nash equilibrium problems is also considered.     

求解一类广义Nash均衡问题

Generalized Nash equilibrium problem (GNEP) is an important model that has many applications in practice. However, a GNEP usually has multiple or even infinitely many Nash equilibrium points and it is not easy to choose a favorable solution from those equilibria. This paper considers a class of GNEP with some kind of separability. We first extend the so-called normalized equilibrium concept to the stationarity sense and then, we propose an approach to solve the normalized stationary points by reformulating the GNEP as a single optimization problem. We further demonstrate the proposed approach on a GNEP model in similar product markets.     

A Penalty Approach for Generalized Nash Equilibrium Problem

The generalized Nash equilibrium problem (GNEP) is a generalization of the standard Nash equilibrium problem (NEP),in which both the utility function and the strategy space of each player depend on the strategies chosen by all other players.This problem has been used to model various problems in applications.However,the convergent solution algorithms are extremely scare in the literature.In this paper,we present an incremental penalty method for the GNEP,and show that a solution of the GNEP can be found by solving a sequence of smooth NEPs.We then apply the semismooth Newton method with Armijo line search to solve latter problems and provide some results of numerical experiments to illustrate the proposed approach.     

Relaxation Methods for Generalized Nash Equilibrium Problems with Inexact Line Search

The generalized Nash equilibrium problem (GNEP) is an extension of the standard Nash game where, in addition to the cost functions, also the strategy spaces of each player depend on the strategies chosen by all other players. This problem is rather difficult to solve and there are only a few methods available in the literature. One of the most popular ones is the so-called relaxation method, which is known to be globally convergent under a set of assumptions. Some of these assumptions, however, are rather strong or somewhat difficult to understand. Here, we present a modified relaxation method for the solution of a certain class of GNEPs. The convergence analysis uses completely different arguments based on a certain descent property and avoids some of the technical conditions for the original relaxation method. Moreover, numerical experiments indicate that the modified relaxation method performs quite well on a number of different examples taken from the literature.     

How to Select a Solution in Generalized Nash Equilibrium Problems

We propose a new solution concept for generalized Nash equilibrium problems. This concept leads, under suitable assumptions, to unique solutions, which are generalized Nash equilibria and the result of a mathematical procedure modeling the process of finding a compromise. We first compute the favorite strategy for each player, if he could dictate the game, and use the best response on the others’ favorite strategies as starting point. Then, we perform a tracing procedure, where we solve parametrized generalized Nash equilibrium problems, in which the players reduce the weight on the best possible and increase the weight on the current strategies of the others. Finally, we define the limiting points of this tracing procedure as solutions. Under our assumptions, the new concept selects one reasonable out of typically infinitely many generalized Nash equilibria.     

Generalized Equilibrium Problems and Generalized Complementarity Problems

From a general minimax inequality or an abstract lopsided saddle-point theorem, we deduce general Karamardian-type equilibrium theorems and generalized complementarity theorems. Our new results extend a number of well-known earlier works of many authors.     

求解广义纳什均衡问题的指数型惩罚函数方法

本文利用指数型惩罚函数部分地惩罚耦合约束,从而将广义纳什均衡问题(GNEP)的求解转化为求解一系列光滑的惩罚纳什均衡问题 (NEP)。我们证明了若光滑的惩罚NEP序列的解序列的聚点处EMFCQ成立,则此聚点是 GNEP的一个解。进一步,我们把惩罚 NEP的KKT条件转化为一个非光滑方程系统,然后应用带有 Armijo 线搜索的半光滑牛顿法来求解此系统。最后,数值结果表明我们的指数型惩罚函数方法是有效的。     

α-Well-posedness for Nash Equilibria and For Optimization Problems with Nash Equilibrium Constraints

We present the concepts of α-well-posedness for parametric noncooperative games and for optimization problems with constraints defined by parametric Nash equilibria. We investigate some classes of functions that ensure these types of well-posedness and the connections with α-well-posedness for variational inequalities and optimization problems with variational inequality constraints.     

Error bounds,metric subregularity and stability in Generalized Nash Equilibrium Problems with nonsmooth payoff functions

In this paper, we study the calmness of a generalized Nash equilibrium problem (GNEP) with non-differentiable data. The approach consists in obtaining some error bound property for the KKT system associated with the generalized Nash equilibrium problem, and returning to the primal problem thanks to the Slater constraint qualification.     

Equilibrium Problems under Generalized Convexity and Generalized Monotonicity

Generalized convex functions preserve many valuable properties of mathematical programming problems with convex functions. Generalized monotone maps allow for an extension of existence results for variational inequality problems with monotone maps. Both models are special realizations of an abstract equilibrium problem with numerous applications, especially in equilibrium analysis (e.g., Blum and Oettli, 1994). We survey existence results for equilibrium problems obtained under generalized convexity and generalized monotonicity. We consider both the scalar and the vector case. Finally existence results for a system of vector equilibrium problems under generalized convexity are surveyed which have applications to a system of vector variational inequality problems. Throughout the survey we demonstrate that the results can be obtained without the rigid assumptions of convexity and monotonicity.     

Equilibrium Problems under Generalized Convexity and Generalized Monotonicity

Generalized convex functions preserve many valuable properties of mathematical programming problems with convex functions. Generalized monotone maps allow for an extension of existence results for variational inequality problems with monotone maps. Both models are special realizations of an abstract equilibrium problem with numerous applications, especially in equilibrium analysis (e.g., Blum and Oettli, 1994). We survey existence results for equilibrium problems obtained under generalized convexity and generalized monotonicity. We consider both the scalar and the vector case. Finally existence results for a system of vector equilibrium problems under generalized convexity are surveyed which have applications to a system of vector variational inequality problems. Throughout the survey we demonstrate that the results can be obtained without the rigid assumptions of convexity and monotonicity.     

Generalized Equilibrium Problems for Quasimonotone and Pseudomonotone Bifunctions

By using quasimonotone and pseudomonotone bifunctions, we derive sufficient conditions which include weak coercivity conditions for existence of equilibrium points. As a consequence, we improve some recent results on the existence of such solutions.     

Duality for Equilibrium Problems under Generalized Monotonicity

Duality is studied for an abstract equilibrium problem which includes, among others, optimization problems and variational inequality problems. Following different schemes, various duals are proposed and primal–dual relationships are established under certain generalized convexity and generalized monotonicity assumptions. In a primal–dual setting, existence results for a solution are derived for different generalized monotone equilibrium problems within each duality scheme.     

A Nonlinear Scalarization Function and Generalized Quasi-vector Equilibrium Problems

Scalarization method is an important tool in the study of vector optimization as corresponding solutions of vector optimization problems can be found by solving scalar optimization problems. In this paper we introduce a nonlinear scalarization function for a variable domination structure. Several important properties, such as subadditiveness and continuity, of this nonlinear scalarization function are established. This nonlinear scalarization function is applied to study the existence of solutions for generalized quasi-vector equilibrium problems. This paper is dedicated to Professor Franco Giannessi for his 68th birthday     

A Generalized Variational Principle and Its Application to Equilibrium Problems

In this paper, we prove a generalized Ekeland-type variational principle for bifunctions, by showing the existence of solution for some generalized optimization problems. In a particular case, from this result, we obtain a Zhong-type variational principle for bifunctions, which may be important from algorithmic point of view, because the solution can be localized in a sphere. Contrary to the standard literature, we are able to guarantee the existence of solution without assuming the triangle property.     

On Intrinsic Complexity of Nash Equilibrium Problems and Bilevel Optimization

In this article we study generalized Nash equilibrium problems (GNEP) and bilevel optimization side by side. This perspective comes from the crucial fact that both problems heavily depend on parametric issues. Observing the intrinsic complexity of GNEP and bilevel optimization, we emphasize that it originates from unavoidable degeneracies occurring in parametric optimization. Under intrinsic complexity, we understand the involved geometrical complexity of Nash equilibria and bilevel feasible sets, such as the appearance of kinks and boundary points, non-closedness, discontinuity and bifurcation effects. The main goal is to illustrate the complexity of those problems originating from parametric optimization and singularity theory. By taking the study of singularities in parametric optimization into account, the structural analysis of Nash equilibria and bilevel feasible sets is performed. For GNEPs, the number of players’ common constraints becomes crucial. In fact, for GNEPs without common constraints and for classical NEPs we show that—generically—all Nash equilibria are jointly nondegenerate Karush–Kuhn–Tucker points. Consequently, they are isolated. However, in presence of common constraints Nash equilibria will constitute a higher dimensional set. In bilevel optimization, we describe the global structure of the bilevel feasible set in case of a one-dimensional leader’s variable. We point out that the typical discontinuities of the leader’s objective function will be caused by follower’s singularities. The latter phenomenon occurs independently of the viewpoint of the optimistic or pessimistic approach. In case of higher dimensions, optimistic and pessimistic approaches are discussed with respect to possible bifurcation of the follower’s solutions.