Strategically supported cooperation in dynamic games with coalition structures

The problem of strategic stability of long-range cooperative agreements in dynamic games with coalition structures is investigated. Based on imputation distribution procedures, a general theoretical framework of the differential game with a coalition structure is proposed. A few assumptions about the deviation instant for a coalition are made concerning the behavior of a group of many individuals in certain dynamic environments.From these, the time-consistent cooperative agreement can be strategically supported by ε-Nash or strong ε-Nash equilibria. While in games in the extensive form with perfect information, it is somewhat surprising that without the assumptions of deviation instant for a coalition, Nash or strong Nash equilibria can be constructed.     

Generalized Krasnoselskii–Mann-type iterations for nonexpansive mappings in Hilbert spaces

The Krasnoselskii–Mann iteration plays an important role in the approximation of fixed points of nonexpansive operators; it is known to be weakly convergent in the infinite dimensional setting. In this present paper, we provide a new inexact Krasnoselskii–Mann iteration and prove weak convergence under certain accuracy criteria on the error resulting from the inexactness. We also show strong convergence for a modified inexact Krasnoselskii–Mann iteration under suitable assumptions. The convergence results generalize existing ones from the literature. Applications are given to the Douglas–Rachford splitting method, the Fermat–Weber location problem as well as the alternating projection method by John von Neumann.     

A procedure for finding Nash equilibria in bi-matrix games

In this paper we consider the computation of Nash equilibria for noncooperative bi-matrix games. The standard method for finding a Nash equilibrium in such a game is the Lemke-Howson method. That method operates by solving a related linear complementarity problem (LCP). However, the method may fail to reach certain equilibria because it can only start from a limited number of strategy vectors. The method we propose here finds an equilibrium by solving a related stationary point problem (SPP). Contrary to the Lemke-Howson method it can start from almost any strategy vector. Besides, the path of vectors along which the equilibrium is reached has an appealing game-theoretic interpretation. An important feature of the algorithm is that it finds a perfect equilibrium when at the start all actions are played with positive probability. Furthermore, we can in principle find all Nash equilibria by repeated application of the algorithm starting from different strategy vectors.This author is financially supported by the Co-operation Centre Tilburg and Eindhoven Universities, The Netherlands.     

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

On generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables

ABSTRACT

We define and discuss different enumerative methods to compute solutions of generalized Nash equilibrium problems with linear coupling constraints and mixed-integer variables. We propose both branch-and-bound methods based on merit functions for the mixed-integer game, and branch-and-prune methods that exploit the concept of dominance to make effective cuts. We show that under mild assumptions the equilibrium set of the game is finite and we define an enumerative method to compute the whole of it. We show that our branch-and-prune method can be suitably modified in order to make a general equilibrium selection over the solution set of the mixed-integer game. We define an application in economics that can be modelled as a Nash game with linear coupling constraints and mixed-integer variables, and we adapt the branch-and-prune method to efficiently solve it.     

Some projection-like methods for the generalized Nash equilibria

A generalized Nash game is an m-person noncooperative game in which each player’s strategy depends on the rivals’ strategies. Based on a quasi-variational inequality formulation for the generalized Nash game, we present two projection-like methods for solving the generalized Nash equilibria in this paper. It is shown that under certain assumptions, these methods are globally convergent. Preliminary computational experience is also reported.     

A Combined Relaxation Method for a Class of Nonlinear Variational Inequalities

In this paper, we describe a class of combined relaxation methods for the non strictly monotone nonlinear variational inequality problem, which involves a max-type convex function. This method is readily implementable and attains a linear rate of convergence under certain additional assumptions.     

解变分不等式问题的混合方法

By using Fukushima‘s differentiable merit function,Taji,Fukushima and Ibaraki have given a globally convergent modified Newton method for the strongly monotone variational inequality problem and proved their method to be quadratically convergent under certain assumptions in 1993. In this paper a hybrid method for the variational inequality problem under the assumptions that the mapping F is continuously differentiable and its Jacobian matrix F(x) is positive definite for all x∈S rather than strongly monotone and that the set S is nonempty, polyhedral,closed and convex is proposed. Armijo-type line search and trust region strategies as well as Fukushima‘s differentiable merit function are incorporated into the method. It is then shown that the method is well defined and globally convergent and that,under the same assumptions as those of Taji et al. ,the method reduces to the basic Newton method and hence the rate of convergence is quadratic. Computational experiences show the efficiency of the proposed method.     

A new class of hybrid extragradient algorithms for solving quasi-equilibrium problems

Generalized Nash equilibrium problems are important examples of quasi-equilibrium problems. The aim of this paper is to study a general class of algorithms for solving such problems. The method is a hybrid extragradient method whose second step consists in finding a descent direction for the distance function to the solution set. This is done thanks to a linesearch. Two descent directions are studied and for each one several steplengths are proposed to obtain the next iterate. A general convergence theorem applicable to each algorithm of the class is presented. It is obtained under weak assumptions: the pseudomonotonicity of the equilibrium function and the continuity of the multivalued mapping defining the constraint set of the quasi-equilibrium problem. Finally some preliminary numerical results are displayed to show the behavior of each algorithm of the class on generalized Nash equilibrium problems.     

Convergence analysis of generalized nonlinear inexact Uzawa algorithm for stabilized saddle point problems

This paper deals with a modified nonlinear inexact Uzawa (MNIU) method for solving the stabilized saddle point problem. The modified Uzawa method is an inexact inner-outer iteration with a variable relaxation parameter and has been discussed in the literature for uniform inner accuracy. This paper focuses on the general case when the accuracy of inner iteration can be variable and the convergence of MNIU with variable inner accuracy, based on a simple energy norm. Sufficient conditions for the convergence of MNIU are proposed. The convergence analysis not only greatly improves the existing convergence results for uniform inner accuracy in the literature, but also extends the convergence to the variable inner accuracy that has not been touched in literature. Numerical experiments are given to show the efficiency of the MNIU algorithm.     

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.     

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.     

Improving fairness in ambulance planning by time sharing

Most literature on the ambulance location problem aims to maximize coverage, i.e., the fraction of people that can be reached within a certain response time threshold. Such a problem often has one optimum, but several near-optimal solutions may exist. These may have a similar overall performance but provide different coverage for different regions. This raises the question: are we making ‘arbitrary’ choices in terms of who gets coverage and who does not? In this paper we propose to share time between several good ambulance configurations in the interest of fairness. We argue that the Bernoulli–Nash social welfare measure should be used to evaluate the fairness of the system. Therefore, we formulate a nonlinear optimization model that determines the fraction of time spent in each configuration to maximize the Bernoulli–Nash social welfare. We solve this model in a case study for an ambulance provider in the Netherlands, using a combination of simulation and optimization. Furthermore, we analyze how the Bernoulli–Nash optimal solution compares to the maximum-coverage solution by formulating and solving a multi-objective optimization model.     

A Bidding Game with Heterogeneous Players

A one-sided limit order book is modeled as a noncooperative game for several players. Agents offer various quantities of an asset at different prices, competing to fulfill an incoming order, whose size is not known a priori. Players can have different payoff functions, reflecting different beliefs about the fundamental value of the asset and probability distribution of the random incoming order. In a previous paper, the existence of a Nash equilibrium was established by means of a fixed point argument. The main issue discussed in the present paper is whether this equilibrium can be obtained from the unique solution to a two-point boundary value problem, for a suitable system of discontinuous ordinary differential equations. Some additional assumptions are introduced, which yield a positive answer. In particular, this is true when there are exactly two players, or when all players assign the same exponential probability distribution to the incoming order. In both of these cases, we also prove that the Nash equilibrium is unique. A counterexample shows that these assumptions cannot be removed, in general.     

Exponential energy decay of solutions for a system of viscoelastic wave equations of Kirchhoff type with strong damping

The initial boundary value problem for a system of viscoelastic wave equations of Kirchhoff type with strong damping is considered. We prove that, under suitable assumptions on relaxation functions and certain initial data, the decay rate of the solutions energy is exponential.     

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.     

Optimal long-time $L_p}(0,T)$ stability and semidiscrete error estimates for the Volterra formulation of the linear quasistatic viscoelasticity problem

The purpose of this article is to show how the solution of the linear quasistatic (compressible) viscoelasticity problem, written in Volterra form with fading memory, may be sharply bounded in terms of the data if certain physically reasonable assumptions are satisfied. The bounds are derived by making precise assumptions on the memory term which then make it possible to avoid the Gronwall inequality, and use instead a comparison theorem which is more sensitive to the physics of the problem. Once the data-stability estimates are established we apply the technique also to deriving a priori error bounds for semidiscrete finite element approximations. Our bounds are derived for viscoelastic solids and fluids under the small strain assumption in terms of the eigenvalues of a certain matrix derived from the stress relaxation tensor. For isotropic materials we can be explicit about the form of these bounds, while for the general case we give a formula for their computation.     

Theoretical and numerical comparison of relaxation methods for mathematical programs with complementarity constraints

Mathematical programs with equilibrium constraints (MPECs) are difficult optimization problems whose feasible sets do not satisfy most of the standard constraint qualifications. Hence MPECs cause difficulties both from a theoretical and a numerical point of view. As a consequence, a number of MPEC-tailored solution methods have been suggested during the last decade which are known to converge under suitable assumptions. Among these MPEC-tailored solution schemes, the relaxation methods are certainly one of the most prominent class of solution methods. Several different relaxation schemes are available in the meantime, and the aim of this paper is to provide a theoretical and numerical comparison of these schemes. More precisely, in the theoretical part, we improve the convergence theorems of several existing relaxation methods. There, we also take a closer look at the properties of the feasible sets of the relaxed problems and show which standard constraint qualifications are satisfied for these relaxed problems. Finally, the numerical comparison is based on the MacMPEC test problem collection.     

The auction algorithm for the transportation problem

The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. This paper generalizes the auction algorithm to solve linear transportation problems. The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem. Computational results show that this modified version of the auction algorithm is very efficient for certain types of transportation problems.     

Feedback Nash equilibria in a problem of optimal fishery management

The paper deals with a problem of optimal management of a common-property fishery, modelled as a two-player differential game. Under nonclassical assumptions on harvest rates and utilities, a feedback Nash equilibrium is determined, using a bionomic equilibrium concept. Later on, this assumption is relaxed and a feedback Nash equilibrium is established under minimal hypotheses.