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. The work of Christain Kanzow has been partially supported by the program “Identification, Optimization and Control with Applications in Modern Technologies” of the Elite Network of Bavaria, Germany.     

On generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables

ABSTRACT

We define and discuss different enumerative methods to compute solutions of generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables. We propose both branch-and-bound methods based on merit functions for the mixed-integer game, and branch-and-prune methods that exploit the concept of dominance to make effective cuts. We show that under mild assumptions the equilibrium set of the game is finite and we define an enumerative method to compute the whole of it. We show that our branch-and-prune method can be suitably modified in order to make a general equilibrium selection over the solution set of the mixed-integer game. We define an application in economics that can be modelled as a Nash game with linear coupling constraints and mixed-integer variables, and we adapt the branch-and-prune method to efficiently solve it.     

A best-response approach for equilibrium selection in two-player generalized Nash equilibrium problems

ABSTRACT

In this paper, we propose a best-response approach to select an equilibrium in a two-player generalized Nash equilibrium problem. In our model we solve, at each of a finite number of time steps, two independent optimization problems. We prove that convergence of our Jacobi-type method, for the number of time steps going to infinity, implies the selection of the same equilibrium as in a recently introduced continuous equilibrium selection theory. Thus the presented approach is a different motivation for the existing equilibrium selection theory, and it can also be seen as a numerical method. We show convergence of our numerical scheme for some special cases of generalized Nash equilibrium problems with linear constraints and linear or quadratic cost functions.     

On differentiability properties of player convex generalized Nash equilibrium problems

Abstract

This article studies differentiability properties for a reformulation of a player convex generalized Nash equilibrium problem as a constrained and possibly nonsmooth minimization problem. By using several results from parametric optimization we show that, apart from exceptional cases, all locally minimal points of the reformulation are differentiability points of the objective function. This justifies a numerical approach which basically ignores the possible nondifferentiabilities.     

A half-space projection method for solving generalized Nash equilibrium problems

The generalized Nash equilibrium problem (GNEP) is an n-person noncooperative game in which each player’s strategy set depends on the rivals’ strategy set. In this paper, we presented a half-space projection method for solving the quasi-variational inequality problem which is a formulation of the GNEP. The difference from the known projection methods is due to the next iterate point in this method is obtained by directly projecting a point onto a half-space. Thus, our next iterate point can be represented explicitly. The global convergence is proved under the minimal assumptions. Compared with the known methods, this method can reduce one projection of a vector onto the strategy set per iteration. Numerical results show that this method not only outperforms the known method but is also less dependent on the initial value than the known method.     

An improved two-step method for solving generalized Nash equilibrium problems

The generalized Nash equilibrium problem (GNEP) is a noncooperative game in which the strategy set of each player, as well as his payoff function, depend on the rival players strategies. As a generalization of the standard Nash equilibrium problem (NEP), the GNEP has recently drawn much attention due to its capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international pollution control. In this paper, we propose an improved two-step (a prediction step and a correction step) method for solving the quasi-variational inequality (QVI) formulation of the GNEP. Per iteration, we first do a projection onto the feasible set defined by the current iterate (prediction) to get a trial point; then, we perform another projection step (correction) to obtain the new iterate. Under certain assumptions, we prove the global convergence of the new algorithm. We also present some numerical results to illustrate the ability of our method, which indicate that our method outperforms the most recent projection-like methods of Zhang et al. (2010).     

On generalized Nash games and variational inequalities

We show that for a large class of problems a generalized Nash equilibrium can be calculated by solving a variational inequality. We analyze what solutions are found by this reduction procedure and hint at possible applications.     

求解随机广义纳什均衡问题的样本均值方法

研究随机广义纳什均衡问题.给出了随机广义纳什均衡问题变分不等式形式的再定式.利用期望残差最小化方法,获得了求解该问题的一种新的模型.并通过拟蒙特卡罗方法给出了该模型的求解方法.     

惩罚框架下求解广义Nash均衡问题的分解算法

广义Nash均衡问题(GNEP),是非合作博弈论中一类重要的问题,它在经济学、管理科学和交通规划等领域有着广泛的应用.本文主要提出一种新的惩罚算法来求解一般的广义Nash均衡问题,并根据罚函数的特殊结构,采用交替方向法求解子问题.在一定的条件下,本文证明新算法的全局收敛性.多个数值例子的试验结果表明算法是可行的,并且是有效的.     

Mathematical programs with multiobjective generalized Nash equilibrium problems in the constraints

This paper considers a class of mathematical programs that include multiobjective generalized Nash equilibrium problems in the constraints. Little research can be found in the literature although it has some interesting applications. We present a single level reformulation for this kind of problems and show their equivalence in terms of global and local minimizers. We find that the reformulation is a special case of the so-called mathematical program with equilibrium constraints which is extensively studied in the literature.     

Generalized Nash equilibrium problem, variational inequality and quasiconvexity

It is well known that the generalized Nash equilibrium problem, a model for multi-leader–follower games, can be reformulated as a quasivariational inequality. We show that, in fact, a reformulation in terms of a variational inequality can be obtained in the general setting of quasiconvex nondifferentiable decision functions. An existence result is deduced.     

Numerical solutions to coupled-constraint (or generalised Nash) equilibrium problems

This paper is about games where the agents face constraints in the combined strategy space (unlike in standard games where the action sets are defined separately for each player) and about computational methods for solutions to such games. The motivation examples for such games include electricity generation problems with transmission capacity constraints, environmental management to control pollution and internet switching to comply to buffers of bounded capacity. In each such problem a regulator may aim at compliance to standards or quotas through taxes or charges. The relevant solution concept for these games has been known under several names like generalised Nash equilibrium, coupled constraint equilibrium and more. Existing numerical methods converging to such an equilibrium will be explained. Application examples of use of NIRA, which is a suite of Matlab routines that implement one of the methods, will be provided.      

On generalized operator quasi-equilibrium problems

In this paper, we will introduce the generalized operator equilibrium problem and generalized operator quasi-equilibrium problem which generalize the operator equilibrium problem due to Kazmi and Raouf [K.R. Kazmi, A. Raouf, A class of operator equilibrium problems, J. Math. Anal. Appl. 308 (2005) 554-564] into multi-valued and quasi-equilibrium problems. Using a Fan-Browder type fixed point theorem in [S. Park, Foundations of the KKM theory via coincidences of composites of upper semicontinuous maps, J. Korean Math. Soc. 31 (1994) 493-519] and an existence theorem of equilibrium for 1-person game in [X.-P. Ding, W.K. Kim, K.-K. Tan, Equilibria of non-compact generalized games with L^∗-majorized preferences, J. Math. Anal. Appl. 164 (1992) 508-517] as basic tools, we prove new existence theorems on generalized operator equilibrium problem and generalized operator quasi-equilibrium problem which includes operator equilibrium problems.     

Privacy impact on generalized Nash equilibrium in peer-to-peer electricity market

We consider a peer-to-peer electricity market, where agents hold private information that they might not want to share. The problem is modeled as a noncooperative communication game, which takes the form of a Generalized Nash Equilibrium Problem, where the agents determine their randomized reports to share with the other market players, while anticipating the form of the peer-to-peer market equilibrium. In the noncooperative game, each agent decides on the deterministic and random parts of the report, such that (a) the distance between the deterministic part of the report and the truthful private information is bounded and (b) the expectation of the privacy loss random variable is bounded. This allows each agent to change her privacy level. We characterize the equilibrium of the game, prove the uniqueness of the Variational Equilibria and provide a closed form expression of the privacy price. Numerical illustrations are presented on the 14-bus IEEE network.     

On generalized vector equilibrium problems

In this paper, we study the generalized vector equilibrium problems in real Hausdorff topological vector space settings. The concepts of weak solutions and strong solutions are introduced. Several new results of existence for the weak solutions and strong solutions of generalized vector equilibrium problems are derived. The new results extend and modify various existence theorems for similar problems.     

The system of generalized vector equilibrium problems with applications

In this paper, we introduce the system of generalized vector equilibrium problems which includes as special cases the system of generalized implicit vector variational inequality problems, the system of generalized vector variational and variational-like inequality problems and the system of vector equilibrium problems. By using a maximal element theorem, we establish existence results for a solution of these systems. As an application, we derive existence results for a solution of a more general Nash equilibrium problem for vector-valued functions.     

Finding a Nash equilibrium in noncooperativeN-person games by solving a sequence of linear stationary point problems

In this paper we present an algorithm for finding a Nash equilibrium in a noncooperative normal formN-person game. More generally, the algorithm can be applied for solving a nonlinear stationary point problem on a simplotope, being the Cartesian product of several simplices. The algorithm solves the problem by solving a sequence of linear stationary point problems. Each problem in the sequence is solved in a finite number of iterations. Although the overall convergence cannot be proved, the method performs rather well. Computational results suggest that this algorithm performs at least as good as simplicial algorithms do.For the special case of a bi-matrix game (N=2), the algorithm has an appealing game-theoretic interpretation. In that case, the problem is linear and the algorithm always finds a solution. Furthermore, the equilibrium found in a bi-matrix game is perfect whenever the algorithm starts from a strategy vector at which all actions are played with positive probability.This research is part of the VF-program Co-operation and Competition, which has been approved by the Netherlands Ministery of Education and Sciences.     

Viscosity approximation methods for generalized equilibrium problems and fixed point problems

The purpose of this paper is to investigate the problem of finding a common element of the set of solutions of a generalized equilibrium problem (for short, GEP) and the set of fixed points of a nonexpansive mapping in the setting of Hilbert spaces. By using well-known Fan-KKM lemma, we derive the existence and uniqueness of a solution of the auxiliary problem for GEP. On account of this result and Nadler’s theorem, we propose an iterative scheme by the viscosity approximation method for finding a common element of the set of solutions of GEP and the set of fixed points of a nonexpansive mapping. Furthermore, it is proven that the sequences generated by this iterative scheme converge strongly to a common element of the set of solutions of GEP and the set of fixed points of a nonexpansive mapping.     

On the generalized vector equilibrium problems

In this paper, generalized vector equilibrium problems are studied and some existence theorems of solutions for these problems in the setting of topological vector spaces are proved. Sufficient conditions for the set of solutions to be compact and convex are given. Our results improve some recent results in this field.     

An existence result for generalized vector equilibrium problems without pseudomonotonicity

In this work, we introduce and study a class of generalized vector equilibrium problems for multifunctions which includes a number of generalized vector variational inequality problems and generalized vector variational-like inequality problems as special cases. By using the KKM–Fan theorem and Nadler’s result, we prove an existence theorem for solutions for this class of generalized vector equilibrium problems in Banach spaces. Applications to generalized vector variational-like inequalities are given.