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.     

Strong stability of Nash equilibria in load balancing games

We study strong stability of Nash equilibria in load balancing games of m(m 2)identical servers,in which every job chooses one of the m servers and each job wishes to minimize its cost,given by the workload of the server it chooses.A Nash equilibrium(NE)is a strategy profile that is resilient to unilateral deviations.Finding an NE in such a game is simple.However,an NE assignment is not stable against coordinated deviations of several jobs,while a strong Nash equilibrium(SNE)is.We study how well an NE approximates an SNE.Given any job assignment in a load balancing game,the improvement ratio(IR)of a deviation of a job is defined as the ratio between the pre-and post-deviation costs.An NE is said to be aρ-approximate SNE(ρ1)if there is no coalition of jobs such that each job of the coalition will have an IR more thanρfrom coordinated deviations of the coalition.While it is already known that NEs are the same as SNEs in the 2-server load balancing game,we prove that,in the m-server load balancing game for any given m 3,any NE is a(5/4)-approximate SNE,which together with the lower bound already established in the literature yields a tight approximation bound.This closes the final gap in the literature on the study of approximation of general NEs to SNEs in load balancing games.To establish our upper bound,we make a novel use of a graph-theoretic tool.     

Nonzero-sum games for continuous-time Markov chains with unbounded transition and average payoff rates

This paper attempts to study two-person nonzero-sum games for denumerable continuous-time Markov chains determined by transition rates,with an expected average criterion.The transition rates are allowed to be unbounded,and the payoff functions may be unbounded from above and from below.We give suitable conditions under which the existence of a Nash equilibrium is ensured.More precisely,using the socalled "vanishing discount" approach,a Nash equilibrium for the average criterion is obtained as a limit point of a sequence of equilibrium strategies for the discounted criterion as the discount factors tend to zero.Our results are illustrated with a birth-and-death game.     

A note on a generalized network flow model for manufacturing process

Manufacturing network flow （MNF） is a generalized network model that overcomes the limitation of an ordinary network flow in modeling more complicated manufacturing scenarios, in particular the synthesis of different materials into one product and/or the distilling of one type of material into many different products. Though a network simplex method for solving a simplified version of MNF has been outlined in the literature, more research work is still needed to give a complete answer whether some classical duality and optimality results of the classical network flow problem can be extended in MNF. In this paper, we propose an algorithmic method for obtaining an initial basic feasible solution to start the existing network simplex algorithm, and present a network-based approach to checking the dual feasibility conditions. These results are an extension of those of the ordinary network flow problem.     

Modified block iterative method for solving convex feasibility problem,equilibrium problems and variational inequality problems

The purpose of this paper is by using the modified block iterative method to propose an algorithm for finding a common element in the intersection of the set of common fixed points of an infinite family of quasi-φ-asymptotically nonexpansive and the set of solutions to an equilibrium problem and the set of solutions to a variational inequality. Under suitable conditions some strong convergence theorems are established in 2-uniformly convex and uniformly smooth Banach spaces. As applications we utilize the results presented in the paper to solving the convex feasibility problem (CFP) and zero point problem of maximal monotone mappings in Banach spaces. The results presented in the paper improve and extend the corresponding results announced by many authors.     

AN EFFICIENT MOVING MESH METHOD FOR A MODEL OF TURBULENT FLOW IN CIRCULAR TUBES

This paper presents an efficient moving problem with an optimal control constrained mesh method to solve a nonlinear singular condition. The physical problem is governed by a new model of turbulent flow in circular tubes proposed by Luo et al. using Prandtl＇s mixing-length theory. Our algorithm is formed by an outer iterative algorithm for handling the optimal control condition and an inner adaptive mesh redistribution algorithm for solving the singular governing equations. We discretize the nonlinear problem by using a upwinding approach, and the resulting nonlinear equations are solved by using the Newton- Raphson method. The mesh is generated and the grid points are moved by using the arc-length equidistribution principle. The numerical results demonstrate that proposed algorithm is effective in capturing the boundary layers associated with the turbulent model.     

Decomposition of two classes of structural models

The conditional independence structure of a common probability measure is a structural model. In this paper, we solve an open problem posed by Studeny [Probabilistic Conditional Independence Structures, Theme 9, p. 206]. A new approach is proposed to decompose a directed acyclic graph and its optimal properties are studied. We interpret this approach from the perspective of the decomposition of the corresponding conditional independence model and provide an algorithm for identifying the maximal prime subgraphs in a directed acyclic graph.     

Stability vs. optimality in selfish ring routing

We study asymmetric atomic selfish routing in ring networks, which has diverse practical applications in network design and analysis. We are concerned with minimizing the maximum latency of source-destination node-pairs over links with linear latencies. We show that there exists an optimal solution that is a 9-approximate Nash equilibrium, significantly improving the existing upper bound of 54 on the instability factor. We present fast implementation of the best response dynamics for computing a Nash equilibrium. Furthermore, we perform empirical study on the price of stability, narrowing the gap between the lower and upper bounds to 0.7436.     

AN EXTRAGRADIENT METHOD FOR RELAXED COCOERCIVE VARIATIONAL INEQUALITY AND EQUILIBRIUM PROBLEMS

The purpose of this paper is to investigate the problem of finding the common element of the set of common fixed points of a countable family of nonexpansive mappings, the set of an equilibrium problem and the set of solutions of the variational inequality prob- lem for a relaxed cocoercive and Lipschitz continuous mapping in Hilbert spaces. Then, we show that the sequence converges strongly to a common element of the above three sets under some parameter controlling conditions, which are connected with Yao, Liou, Yao[17], Takahashi[12] and many others.     

A note on economic equilibrium and financial networks

Nagurney （1999） used variational inequalities to study economic equilibrium and financial networks and applied the modified projection method to solve the problem. In this paper, we formulate the problem as a nonlinear complementarity problem. The complementarity model is just the KKT condition for the model of Nagurney （1999）. It is a simpler model than that of Nagurney （1999）. We also establish sufficient conditions for existence and uniqueness of the equilibrium pattern, which are weaker than those in Nagurney （]999）. Finally, we apply a smoothing Newton-type algorithm to solve the problem and report some numerical results.     

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.     

Optimization reformulations of the generalized Nash equilibrium problem using regularized indicator Nikaidô–Isoda function

In this paper, we extend the literature by adapting the Nikaidô–Isoda function as an indicator function termed as regularized indicator Nikaidô–Isoda function, and this is demonstrated to guarantee existence of a solution. Using this function, we present two constrained optimization reformulations of the generalized Nash equilibrium problem (GNEP for short). The first reformulation characterizes all the solutions of GNEP as global minima of the optimization problem. Later this approach is modified to obtain the second optimization reformulation whose global minima characterize the normalized Nash equilibria. Some numerical results are also included to illustrate the behaviour of the optimization reformulations.     

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.     

Restricted generalized Nash equilibria and controlled penalty algorithm

The generalized Nash equilibrium problem (GNEP) is a generalization of the standard Nash equilibrium problem, in which each player’s strategy set may depend on the rival players’ strategies. The GNEP has recently drawn much attention because of its capability of modeling a number of interesting conflict situations in, for example, an electricity market and an international pollution control. However, a GNEP usually has multiple or even infinitely many solutions, and it is not a trivial matter to choose a meaningful solution from those equilibria. The purpose of this paper is two-fold. First we present an incremental penalty method for the broad class of GNEPs and show that it can find a GNE under suitable conditions. Next, we formally define the restricted GNE for the GNEPs with shared constraints and propose a controlled penalty method, which includes the incremental penalty method as a subprocedure, to compute a restricted GNE. Numerical examples are provided to illustrate the proposed approach.     

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

Partial penalization for the solution of generalized Nash equilibrium problems

In this paper we reformulate the generalized Nash equilibrium problem (GNEP) as a nonsmooth Nash equilibrium problem by means of a partial penalization of the difficult coupling constraints. We then propose a suitable method for the solution of the penalized problem and we study classes of GNEPs for which the penalty approach is guaranteed to converge to a solution. In particular, we are able to prove convergence for an interesting class of GNEPs for which convergence results were previously unknown.     

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

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

Optimization reformulations of the generalized Nash equilibrium problem using Nikaido-Isoda-type functions

We consider the generalized Nash equilibrium problem which, in contrast to the standard Nash equilibrium problem, allows joint constraints of all players involved in the game. Using a regularized Nikaido-Isoda-function, we then present three optimization problems related to the generalized Nash equilibrium problem. The first optimization problem is a complete reformulation of the generalized Nash game in the sense that the global minima are precisely the solutions of the game. However, this reformulation is nonsmooth. We then modify this approach and obtain a smooth constrained optimization problem whose global minima correspond to so-called normalized Nash equilibria. The third approach uses the difference of two regularized Nikaido-Isoda-functions in order to get a smooth unconstrained optimization problem whose global minima are, once again, precisely the normalized Nash equilibria. Conditions for stationary points to be global minima of the two smooth optimization problems are also given. Some numerical results illustrate the behaviour of our approaches.     

Parametrized variational inequality approaches to generalized Nash equilibrium problems with shared constraints

We consider the generalized Nash equilibrium problem (GNEP), in which each player’s strategy set may depend on the rivals’ strategies through shared constraints. A practical approach to solving this problem that has received increasing attention lately entails solving a related variational inequality (VI). From the viewpoint of game theory, it is important to find as many GNEs as possible, if not all of them. We propose two types of parametrized VIs related to the GNEP, one price-directed and the other resource-directed. We show that these parametrized VIs inherit the monotonicity properties of the original VI and, under mild constraint qualifications, their solutions yield all GNEs. We propose strategies to sample in the parameter spaces and show, through numerical experiments on benchmark examples, that the GNEs found by the parametrized VI approaches are widely distributed over the GNE set.