Nonsmooth optimization reformulations characterizing all solutions of jointly convex generalized Nash equilibrium problems

Generalized Nash equilibrium problems (GNEPs) allow, in contrast to standard Nash equilibrium problems, a dependence of the strategy space of one player from the decisions of the other players. In this paper, we consider jointly convex GNEPs which form an important subclass of the general GNEPs. Based on a regularized Nikaido-Isoda function, we present two (nonsmooth) reformulations of this class of GNEPs, one reformulation being a constrained optimization problem and the other one being an unconstrained optimization problem. While most approaches in the literature compute only a so-called normalized Nash equilibrium, which is a subset of all solutions, our two approaches have the property that their minima characterize the set of all solutions of a GNEP. We also investigate the smoothness properties of our two optimization problems and show that both problems are continuous under a Slater-type condition and, in fact, piecewise continuously differentiable under the constant rank constraint qualification. Finally, we present some numerical results based on our unconstrained optimization reformulation.     

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.     

Sufficient conditions to compute any solution of a quasivariational inequality via a variational inequality

We define the concept of reproducible map and show that, whenever the constraint map defining the quasivariational inequality (QVI) is reproducible then one can characterize the whole solution set of the QVI as a union of solution sets of some variational inequalities (VI). By exploiting this property, we give sufficient conditions to compute any solution of a generalized Nash equilibrium problem (GNEP) by solving a suitable VI. Finally, we define the class of pseudo-Nash equilibrium problems, which are (not necessarily convex) GNEPs whose solutions can be computed by solving suitable Nash equilibrium problems.     

Split equilibrium problems for related games and applications to economic theory

ABSTRACT

In this paper we introduce the concept of split Nash equilibrium problems associated with two related noncooperative strategic games. Then we apply the Fan-KKM theorem to prove the existence of solutions to split Nash equilibrium problems of related noncooperative strategic games, in which the strategy sets of the players are nonempty closed and convex subsets in Banach spaces. As an application of this existence to economics, an example is provided that studies the existence of split Nash equilibrium of utilities of two related economies. As applications, we study the existence of split Nash equilibrium in the dual (playing twice) extended Bertrand duopoly model of price competition.     

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.     

Computing equilibria of Cournot oligopoly models with mixed-integer quantities

We consider Cournot oligopoly models in which some variables represent indivisible quantities. These models can be addressed by computing equilibria of Nash equilibrium problems in which the players solve mixed-integer nonlinear problems. In the literature there are no methods to compute equilibria of this type of Nash games. We propose a Jacobi-type method for computing solutions of Nash equilibrium problems with mixed-integer variables. This algorithm is a generalization of a recently proposed method for the solution of discrete so-called “2-groups partitionable” Nash equilibrium problems. We prove that our algorithm converges in a finite number of iterations to approximate equilibria under reasonable conditions. Moreover, we give conditions for the existence of approximate equilibria. Finally, we give numerical results to show the effectiveness of the proposed method.     

On the computation of all solutions of jointly convex generalized Nash equilibrium problems

Jointly convex generalized Nash equilibrium problems are the most studied class of generalized Nash equilibrium problems. For this class of problems it is now clear that a special solution, called variational or normalized equilibrium, can be computed by solving a variational inequality. However, the computation of non-variational equilibria is more complex and less understood and only very few methods have been proposed so far. In this note we consider a new approach for the computation of non-variational solutions of jointly convex problems and compare our approach to previous proposals.     

The existence of solutions for the system of generalized vector quasi-equilibrium problems

In this paper, we study the system of generalized vector quasi-equilibrium problems which includes as special cases the system of generalized vector equilibrium problems and the system of vector quasi-equilibrium problems, and establish the existence result for its solutions by means of the Kakutani–Fan–Glicksberg fixed points theorem. As special cases, we also derive the existence results for weakly Pareto–Nash equilibrium points for multiobjective generalized game problems and multiobjective game problems.     

Stochastic Variational Inequality Approaches to the Stochastic Generalized Nash Equilibrium with Shared Constraints

In this paper, we consider the generalized Nash equilibrium with shared constraints in the stochastic environment, and we call it the stochastic generalized Nash equilibrium. The stochastic variational inequalities are employed to solve this kind of problems, and the expected residual minimization model and the conditional value-at-risk formulations defined by the residual function for the stochastic variational inequalities are discussed. We show the risk for different kinds of solutions for the stochastic generalized Nash equilibrium by the conditional value-at-risk formulations. The properties of the stochastic quadratic generalized Nash equilibrium are shown. The smoothing approximations for the expected residual minimization formulation and the conditional value-at-risk formulation are employed. Moreover, we establish the gradient consistency for the measurable smoothing functions and the integrable functions under some suitable conditions, and we also analyze the properties of the formulations. Numerical results for the applications arising from the electricity market model illustrate that the solutions for the stochastic generalized Nash equilibrium given by the ERM model have good properties, such as robustness, low risk and so on.     

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.     

Some interesting properties of maximin strategies

Since the seminal paper of Nash (1950) game theoretic literature has focused mostly on equilibrium and not on maximin (minimax) strategies. We study the properties of these strategies in non-zero-sum strategic games that possess (completely) mixed Nash equilibria. We find that under certain conditions maximin strategies have several interesting properties, some of which extend beyond 2-person strategic games. In particular, for n-person games we specify necessary and sufficient conditions for maximin strategies to yield the same expected payoffs as Nash equilibrium strategies. We also show how maximin strategies may facilitate payoff comparison across Nash equilibria as well as refine some Nash equilibrium strategies.     

Identification of classes of differential games for which the open loop is a degenerate feedback Nash equilibrium

In general, it is clear that open-loop Nash equilibrium and feedback Nash equilibrium do not coincide. In this paper, we study the structure of differential games and develop a technique using which we can identify classes of games for which the open-loop Nash equilibrium is a degenerate feedback equilibrium. This technique clarifies the relationship between the assumptions made on the structure of the game and the resultant equilibrium.The author would like to thank E. Dockner, A. Mehlmann, and an anonymous referee for helpful comments.     

一种n人静态博弈纯策略纳什均衡存在性判别法

本首先给出了n人静态博弈纯策略纳什均衡存在的充要条件。然后给出n人静态博弈纯策略纳什均衡存在性的一种判别方法。最后在判别纯策略纳什均衡存在的条件下，给出判定该静态博弈存在多少纯策略纳什均衡以及哪些纯策略组合是纯策略纳什均衡(解)的方法。     

Nash equilibrium based fairness

There are several approaches of sharing resources among users. There is a noncooperative approach wherein each user strives to maximize its own utility. The most common optimality notion is then the Nash equilibrium. Nash equilibria are generally Pareto inefficient. On the other hand, we consider a Nash equilibrium to be fair as it is defined in a context of fair competition without coalitions (such as cartels and syndicates). We show a general framework of systems wherein there exists a Pareto optimal allocation that is Pareto superior to an inefficient Nash equilibrium. We consider this Pareto optimum to be ??Nash equilibrium based fair.?? We further define a ??Nash proportionately fair?? Pareto optimum. We then provide conditions for the existence of a Pareto-optimal allocation that is, truly or most closely, proportional to a Nash equilibrium. As examples that fit in the above framework, we consider noncooperative flow-control problems in communication networks, for which we show the conditions on the existence of Nash-proportionately fair Pareto optimal allocations.     

Systems of quasi-variational relations with applications

In this paper, we introduce a system of quasi-variational relations (in short, SQVR) and present several examples which show that it is a very general and unified model of several problems. We establish the existence of solutions of SQVP, in general, and several other problems, in particular. As an application of our results, we derive maximal element theorems and a collectively fixed point theorem for a family of multivalued maps. As further applications, we study Ky Fan type inequality / inclusion problem for vector valued bifunctions which includes constrained Nash equilibrium problem as a special case. We also present a common fixed point theorem for a family of multivalued maps. The results of this paper improve and generalize several known results on (system of) quasi-equilibrium problems, (system of) quasi-variational inclusions, constrained Nash equilibrium problem, collectively fixed point theorem and KKM type theorems for a family of multivalued maps. Our results also contain several results which appeared in recent literature.     

Variational Inequality Formulation of a Class of Multi-Leader-Follower Games

The multi-leader-follower game can be looked on as a generalization of the Nash equilibrium problem and the Stackelberg game, which contains several leaders and a number of followers. Recently, the multi-leader-follower game has been drawing more and more attention, for example, in electricity power markets. However, when we formulate a general multi-leader-follower game as a single-level game, it will give rise to a lot of problems, such as the lack of convexity and the failure of constraint qualifications. In this paper, to get rid of these difficulties, we focus on a class of multi-leader-follower games that satisfy some particular, but still reasonable assumptions, and show that these games can be formulated as ordinary Nash equilibrium problems, and then as variational inequalities. We establish some results on the existence and uniqueness of a leader-follower Nash equilibrium. We also present illustrative numerical examples from an electricity power market model.     

System of nonsmooth variational inequalities with applications

In this paper, we consider a system of vector variational inequalities and a system of nonsmooth variational inequalities defined by means of Clarke directional derivative. We also consider the Nash equilibrium problem with vector pay-offs and its scalarized form. We present some relations among these systems and problems. The existence results for a solution of system of nonsmooth variational inequalities are given. As a consequence, we derive an existence result for a solution of Nash equilibrium problem with vector pay-offs.     

System of Generalized Vector Quasi-Equilibrium Problems with Applications to Fixed Point Theorems for a Family of Nonexpansive Multivalued Mappings

In this paper, we establish the existence theorems of the generalized vector quasi-equilibrium problems. From some existence theorem, we establish fixed point theorems for a family of lower semicontinuous or nonexpansive multivalued mappings. We also obtain the existence theorems of system of mixed generalized vector variational-like inequalities and existence theorems of the Debreu vector equilibrium problems and the Nash vector equilibrium problems.     

Fictitious play with incomplete learning

In this paper, we consider a case that a game is played repeatedly in an incomplete learning process where each player updates his belief only in the learning periods rather than all the stages. For fictitious play process with incomplete learning, we discuss the absorbability of Nash equilibriums and the consistency of utilities in a finite game and discuss the convergence in a 2×2 game with an identical learning-period set. The main results for incomplete learning models are that, if it is uniformly played, a strict Nash equilibrium is absorbing in a fictitious play process; a fictitious play has the property of utility consistency if it exhibits infrequent switches and players learn frequently enough; a 2×2 game with an identical learning-period set has fictitious play property that any fictitious process for the game converges to equilibrium provided that players learn frequently enough.