Iterative Algorithms for Equilibrium Problems

We consider equilibrium problems in the framework of the formulation proposed by Blum and Oettli, which includes variational inequalities, Nash equilibria in noncooperative games, and vector optimization problems, for instance, as particular cases. We show that such problems are particular instances of convex feasibility problems with infinitely many convex sets, but with additional structure, so that projection algorithms for convex feasibility can be modified in order to improve their convergence properties, mainly achieving global convergence without either compactness or coercivity assumptions. We present a sequential projections algorithm with an approximately most violated constraint control strategy, and two variants where exact orthogonal projections are replaced by approximate ones, using separating hyperplanes generated by subgradients. We include full convergence analysis of these algorithms.     

Smoothing approach to Nash equilibrium formulations for a class of equilibrium problems with shared complementarity constraints

The equilibrium problem with equilibrium constraints (EPEC) can be looked on as a generalization of Nash equilibrium problem (NEP) and the mathematical program with equilibrium constraints (MPEC) whose constraints contain a parametric variational inequality or complementarity system. In this paper, we particularly consider a special class of EPECs where a common parametric P-matrix linear complementarity system is contained in all players?? strategy sets. After reformulating the EPEC as an equivalent nonsmooth NEP, we use a smoothing method to construct a sequence of smoothed NEPs that approximate the original problem. We consider two solution concepts, global Nash equilibrium and stationary Nash equilibrium, and establish some results about the convergence of approximate Nash equilibria. Moreover we show some illustrative numerical examples.     

Convergence of the Approximation Scheme to American Option Pricing via the Discrete Morse Semiflow

We consider the approximation scheme to the American call option via the discrete Morse semiflow, which is a minimizing scheme of a time semi-discretized variational functional. In this paper we obtain a rate of convergence of approximate solutions and the convergence of approximate free boundaries. We mainly apply the theory of variational inequalities and that of viscosity solutions to prove our results.     

State-constrained optimal control of nonlinear elliptic variational inequalities

An optimization control problem for systems described by abstract variational inequalities with state constraints is considered. The solvability of this problem is proved. The problem is approximated by the penalty method. The convergence of this method is proved. Necessary conditions of optimality for the approximation problem are obtained. Its solution is an approximate optimal control of the initial problem.     

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.     

Solution smoothness of ill-posed equations in Hilbert spaces: four concepts and their cross connections

Numerical solution of ill-posed operator equations requires regularization techniques. The convergence of regularized solutions to the exact solution can be usually guaranteed, but to also obtain estimates for the speed of convergence one has to exploit some kind of smoothness of the exact solution. We consider four such smoothness concepts in a Hilbert space setting: source conditions, approximate source conditions, variational inequalities, and approximate variational inequalities. Besides some new auxiliary results on variational inequalities the equivalence of the last three concepts is shown. In addition, it turns out that the classical concept of source conditions and the modern concept of variational inequalities are connected via Fenchel duality.     

Remarks on existence and uniqueness of Cournot–Nash equilibria in the non-potential case

This article is devoted to various methods (optimal transport, fixed-point, ordinary differential equations) to obtain existence and/or uniqueness of Cournot–Nash equilibria for games with a continuum of players with both attractive and repulsive effects. We mainly address separable situations but for which the game does not have a potential, contrary to the variational framework of Blanchet and Carlier (Optimal transport and Cournot–Nash equilibria, 2012). We also present several numerical simulations which illustrate the applicability of our approach to compute Cournot–Nash equilibria.     

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.     

Nested monotony for variational inequalities over product of spaces and convergence of iterative algorithms

The auxiliary problem principle has been proposed by the first author as a framework to describe and analyze iterative algorithms such as gradient as well as decomposition/coordination algorithms for optimization problems (Refs. 1–3) and variational inequalities (Ref. 4). The key assumption to prove the global and strong convergence of such algorithms, as well as of most of the other algorithms proposed in the literature, is the strong monotony of the operator involved in the variational inequalities. In this paper, we consider variational inequalities defined over a product of spaces and we introduce a new property of strong nested monotony, which is weaker than the ordinary overall strong monotony generally assumed. In some sense, this new concept seems to be a minimal requirement to insure convergence of the algorithms alluded to above. A convergence theorem based on this weaker assumption is given. Application of this result to the computation of Nash equilibria can be found in another paper (Ref. 5).This research has been supported by the Centre National de la Recherche Scientifique (ATP Complex Technological Systems) and by the Centre National d'Etudes des Télécommunications (Contract 83.5B.034.PAA).     

A numerical approach to optimization problems with variational inequality constraints

Optimization problems with variational inequality constraints are converted to constrained minimization of a local Lipschitz function. To this minimization a non-differentiable optimization method is used; the required subgradients of the objective are computed by means of a special adjoint equation. Besides tests with some academic examples, the approach is applied to the computation of the Stackelberg—Cournot—Nash equilibria and to the numerical solution of a class of quasi-variational inequalities.Corresponding author.     

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.     

α-Well-posedness for Nash Equilibria and For Optimization Problems with Nash Equilibrium Constraints

We present the concepts of α-well-posedness for parametric noncooperative games and for optimization problems with constraints defined by parametric Nash equilibria. We investigate some classes of functions that ensure these types of well-posedness and the connections with α-well-posedness for variational inequalities and optimization problems with variational inequality constraints.     

Semidefinite programming for min–max problems and games

We consider two min–max problems (1) minimizing the supremum of finitely many rational functions over a compact basic semi-algebraic set and (2) solving a 2-player zero-sum polynomial game in randomized strategies with compact basic semi-algebraic sets of pure strategies. In both problems the optimal value can be approximated by solving a hierarchy of semidefinite relaxations, in the spirit of the moment approach developed in Lasserre (SIAM J Optim 11:796–817, 2001; Math Program B 112:65–92, 2008). This provides a unified approach and a class of algorithms to compute Nash equilibria and min–max strategies of several static and dynamic games. Each semidefinite relaxation can be solved in time which is polynomial in its input size and practice on a sample of experiments reveals that few relaxations are needed for a good approximation (and sometimes even for finite convergence), a behavior similar to what was observed in polynomial optimization.     

Computing pure Nash and strong equilibria in bottleneck congestion games

Bottleneck congestion games properly model the properties of many real-world network routing applications. They are known to possess strong equilibria—a strengthening of Nash equilibrium to resilience against coalitional deviations. In this paper, we study the computational complexity of pure Nash and strong equilibria in these games. We provide a generic centralized algorithm to compute strong equilibria, which has polynomial running time for many interesting classes of games such as, e.g., matroid or single-commodity bottleneck congestion games. In addition, we examine the more demanding goal to reach equilibria in polynomial time using natural improvement dynamics. Using unilateral improvement dynamics in matroid games pure Nash equilibria can be reached efficiently. In contrast, computing even a single coalitional improvement move in matroid and single-commodity games is strongly NP-hard. In addition, we establish a variety of hardness results and lower bounds regarding the duration of unilateral and coalitional improvement dynamics. They continue to hold even for convergence to approximate equilibria.     

Existence, uniqueness and approximation of the solution of an ode with (infinitely many) state-dependent impulses via fixed mesh galerkin formulation

A fixed mesh variational formulation is used to establish existence and uniqueness of the solution of ordinary differential equations with (infinitely many) state-dependent impulses on the right-hand side. This approach gives a natural numerical scheme to approximate the solution. The convergence of the approximation is proved and its asymptotic order obtained.     

On the approximation and the optimization of plates

This work is devoted to the study of simply supported and of clamped plates together with related variational inequalitiesand optimization problems. We introduce a new unitary approach based on distributed optimal control problems governed by second order elliptic boundary value problems and their penalization. This approach gives the possibility to approximate the solution via piecewise linear continuous finite elements and is simpler than other methods considered in the literature.The convergence with respect to the penalization parameter (?) is proved under very general assumptions.

In order to solve the obtained control problems, optimization procedures of steepest descent type are considered. Relevantnumerical examples illustrate the applicability of the proposed methods.     

Identification of Efficient Subgame-Perfect Nash Equilibria in a Class of Differential Games1

We present a method for the characterization of subgame-perfect Nash equilibria being Pareto efficient in a class of differential games. For that purpose, we propose a new approach based on new necessary and sufficient conditions for computing subgame-perfect Nash equilibria.     

Nash Equilibria,Variational Inequalities,and Dynamical Systems

In this paper, we introduce some relationships between Nash equilibria, variational equilibria, and dynamical equilibria for noncooperative games.     

Iterative methods for variational and complementarity problems

In this paper, we study both the local and global convergence of various iterative methods for solving the variational inequality and the nonlinear complementarity problems. Included among such methods are the Newton and several successive overrelaxation algorithms. For the most part, the study is concerned with the family of linear approximation methods. These are iterative methods in which a sequence of vectors is generated by solving certain linearized subproblems. Convergence to a solution of the given variational or complementarity problem is established by using three different yet related approaches. The paper also studies a special class of variational inequality problems arising from such applications as computing traffic and economic spatial equilibria. Finally, several convergence results are obtained for some nonlinear approximation methods.This research was based on work supported by the National Science Foundation under grant ECS-7926320.     

kth Order convergence for a semilinear elliptic boundary value problem in the divergence form

The convergence problem of approximate solutions for a semilinear elliptic boundary value problem in the divergence form is studied. By employing the method of quasilinearization, a sequence of approximate solutions converging with the kth (k ? 2) order convergence to a weak solution for a semilinear elliptic problem is obtained via the variational approach.