Some Projection-like Methods For The Generalized Nash Equilibria

Game theory is the theory of decision making which widely used in social and economic aspects. Nash equilibrium game is a very important game.This article is a review,which is mainly about Nash equilibrium game on a special case:generalized Nash equilibrium game.The GNE game can be defined as follows:Let N is the set of n players, where n is finite. Xi(?) Rm is the strategy set of player i, X=Πj∈NXj (?) Rnm,and XN\i=Πj∈n,j±i Xj。Let Ki:XN\i�'Xi be a point-to-set mapping which represents the ability of players j≠i to affect the feasible strategies of player i. Let the utility function for player i be represented by the function u':grKi�'R, where grKi denotes the graph of the mapping K'. Let K denote the mapping formed from the K', (?)i∈N, i.e., for all x∈X, K(x)=Πi∈N Ki(xN\i), where xN\i represents the vector x with the i-th subvector xi removed. The generalized Nash equilibria game is thus defined by the data{Xi, K', u'}i∈N , and an equilibrium of this game is defined as a point x*= (x*1, x*2,...,x*n)∈X such that x*i∈Ki(x*N\i) Vi∈N, ui(x*)< ui(xi,x*N\i) (?)xi∈Ki(x*N\i) i∈N.In words, x* is a GNE.According to the approach that Nash equilibrium into a variational inequality, Harker solves the generalized Nash equilibrium by turning it into a quasi-variational inequality.The QVI formulation of the GNE game is:find x*∈K(x*) such thatΣ-▽xiui(x*i, x*N\i)T(xi-x*i)≥0 (?)x∈K(x*), i∈N or F(x*)T(x-x*)≥0 (?)x∈K(x*)This paper summarized of some existence conditions for solutions of quasi-variational inequality,and made preparations for the following Noor's proiection-like methods. Then we focuse on the related concepts of proiection-like methods. For a given nonempty closed convex setΩin Rn,the orthogonal projection from Rn ontoΩis defined by PΩ(x)=argmin{||x-y|||y∈Ω}, x∈Rn.Then,following the definition of projection,we summarized the nature and definitions associated with the projective algorithms,including monotone,continuous,expansion and so on.Finally,we review the iterative steps of the algorithm in Jianzhong Zhang.Firstly the simple iteration method in Noor is given:let u∈K(u), un+1=m(un)+PK(un-ρ∧(Tun-f)-m(un)),where p satisfy the following conditions: 0＜ρ＜(α+(?))/β2,α＞2β(?),γ≤1/2Then,Li Jing improved Noor's steps of the algorithm and its convergence theorem has been given.Algorithm 4.1Step 1:Take x0∈K(x0).Let k=0.Step 2:If rK(xk)(xk)=0 then stop.Otherwise,let xk+1=PK(xk)(xk-λF(xk)),Finally,the two iterative projection-like algorithm in Jianzhong Zhang's papers are de-scribed in detail.Algorithm 4.2Step 1 Given constants y>0,1∈(0,1),u∈(0,1),and p∈(0,2).Take X-1∈X.Choose arbitrarily an x0∈K(X-1).Set k=0.Step 2 If rK(xk)(xk)=0 then stop.Otherwise,let xk=PK(xk)(xk-αkF(xk)),where ak=γlmk and mk is the smallest nonnegative integer m,such thatαk〈F(xk)-F(xk),xk-xk〉≤u||xk-xk||2Step 3 Set Xk+1=PK(xk)(xk-βk(xk-xk+αkF(xk))),whereβk is given byβk=ρ(1-u)||xk-xk||2/||xk-xk+αkF(xk)||2Step 4 Set k:=k+1 and go to Step 2.Algorithm 4.3Step 1 Given contants l∈(0,1),u∈(0,1),andρ∈(0,2).Take x0∈X。Set k=0。Step 2 If rK(xk)(xk)=0 then stop.Otherwise,let zk=PK(xk)(xk-F(xk)), yk=(1-αK)xk+αkzk,whereαk=lmK and mk is the smallest nonnegative integer m,such that〈F(xk)-F((1-lm)xk+lmzk),xk-zk〉≤u||xk-zk||2.Step 3 Set xk+1=PK(xk)(xk-βkdk), where dk andβk are given by dk=xk-zk+F(yk)/ ak andβk=ρ(1-u)||xk-zk||2/||dk||2,Step 4 Set k:=k+1 and go to Step 2.These two algorithms in Zhang Jianzhong's paper all have strengths and weaknesses. In the example in,we clearly see that these two algorithms are effective and can obtain the generalized Nash equilibrium.But when we change the different starting points,the number of iterations in Algorithm 4.2 was significantly less than the number in Algorithm 4.3.This shows that the line search to obtain the step size of the Algorithm 4.2 made it more accurate. However,when we observe the CPU time of two algorithms,we find that Algorithm 4.3 calculate faster than Algorithm 4.2.More iterations,the more obvious advantages of algo-rithm 4.2,it means that Algorithm 4.3 is more efficient than Algorithm 4.2 on the computer. Therefore,we can not simply evaluate the pros and cons of these two algorithms in Zhang Jianzhong.Which method is more suitable and more efficient should be determined on their specific situation in practice.