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 solving generalized Nash equilibrium problems via optimization

This paper deals with the generalized Nash equilibrium problem (GNEP), i.e. a noncooperative game in which the strategy set of each player, as well as his payoff function, depends on the strategies of all players. We consider an equivalent optimization reformulation of GNEP using a regularized Nikaido–Isoda function so that solutions of GNEP coincide with global minima of the optimization problem. We then propose a derivative-free descent type method with inexact line search to solve the equivalent optimization problem and we prove that our algorithm is globally convergent. The convergence analysis is not based on conditions guaranteeing that every stationary point of the optimization problem is a solution of GNEP. Finally, we present the performance of our algorithm on some examples.     

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.     

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.     

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.     

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.     

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).     

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.     

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.     

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.     

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.     

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

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

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.     

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.     

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.     

Competitive newsvendor problems with the same Nash and Stackelberg solutions

Consider two newsvendors: (i) they compete satisfying substitutable demands searching Nash equilibrium or (ii) one is the leader deciding first, the other responds optimally playing a Stackelberg game. The leader profits more than she does in (i). We present conditions under which the leader's profit does not improve from (i) to (ii).     

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.