Linear–quadratic stochastic two-person nonzero-sum differential games: Open-loop and closed-loop Nash equilibria

In this paper, we consider a linear–quadratic stochastic two-person nonzero-sum differential game. Open-loop and closed-loop Nash equilibria are introduced. The existence of the former is characterized by the solvability of a system of forward–backward stochastic differential equations, and that of the latter is characterized by the solvability of a system of coupled symmetric Riccati differential equations. Sometimes, open-loop Nash equilibria admit a closed-loop representation, via the solution to a system of non-symmetric Riccati equations, which could be different from the outcome of the closed-loop Nash equilibria in general. However, it is found that for the case of zero-sum differential games, the Riccati equation system for the closed-loop representation of an open-loop saddle point coincides with that for the closed-loop saddle point, which leads to the conclusion that the closed-loop representation of an open-loop saddle point is the outcome of the corresponding closed-loop saddle point as long as both exist. In particular, for linear–quadratic optimal control problem, the closed-loop representation of an open-loop optimal control coincides with the outcome of the corresponding closed-loop optimal strategy, provided both exist.     

Establishing Nash equilibrium of the manufacturer–supplier game in supply chain management

We study a game model of multi-leader and one-follower in supply chain optimization where n suppliers compete to provide a single product for a manufacturer. We regard the selling price of each supplier as a pre-determined parameter and consider the case that suppliers compete on the basis of delivery frequency to the manufacturer. Each supplier's profit depends not only on its own delivery frequency, but also on other suppliers' frequencies through their impact on manufacturer's purchase allocation to the suppliers. We first solve the follower's (manufacturer's) purchase allocation problem by deducing an explicit formula of its solution. We then formulate the n leaders' (suppliers') game as a generalized Nash game with shared constraints, which is theoretically difficult, but in our case could be solved numerically by converting to a regular variational inequality problem. For the special case that the selling prices of all suppliers are identical, we provide a sufficient and necessary condition for the existence and uniqueness of the Nash equilibrium. An explicit formula of the Nash equilibrium is obtained and its local uniqueness property is proved.     

A Shared-Constraint Approach to Multi-Leader Multi-Follower Games

Multi-leader multi-follower games are a class of hierarchical games in which a collection of leaders compete in a Nash game constrained by the equilibrium conditions of another Nash game amongst the followers. The resulting equilibrium problem with equilibrium constraints is complicated by nonconvex agent problems and therefore providing tractable conditions for existence of global or even local equilibria has proved challenging. Consequently, much of the extant research on this topic is either model specific or relies on weaker notions of equilibria. We consider a modified formulation in which every leader is cognizant of the equilibrium constraints of all leaders. Equilibria of this modified game contain the equilibria, if any, of the original game. The new formulation has a constraint structure called shared constraints, and our main result shows that if the leader objectives admit a potential function, the global minimizers of the potential function over this shared constraint are equilibria of the modified formulation. We provide another existence result using fixed point theory that does not require potentiality. Additionally, local minima, B-stationary, and strong-stationary points of this minimization problem are shown to be local Nash equilibria, Nash B-stationary, and Nash strong-stationary points of the corresponding multi-leader multi-follower game. We demonstrate the relationship between variational equilibria associated with this modified shared-constraint game and equilibria of the original game from the standpoint of the multiplier sets and show how equilibria of the original formulation may be recovered. We note through several examples that such potential multi-leader multi-follower games capture a breadth of application problems of interest and demonstrate our findings on a multi-leader multi-follower Cournot game.     

分布参数最优控制的边界元共轭梯度算法

研究了一类线性椭圆型分布参数最优控制问题的数值解算法.得到最优控制对应的最优性方程组,在凸性条件下,证明了最优控制的唯一存在性问题.将最优控制问题化为以控制函数和状态函数为局中人的递阶式(Stackelberg)非合作对策问题,其平衡点是最优控制的解.进一步得到求平衡点的边界元共轭梯度算法.最后,研究算法中边界元离散的误差估计,以算例验证该算法.     

Minimal and locally minimal games and game forms

By Shapley’s (1964) theorem, a matrix game has a saddle point whenever each of its 2×2 subgames has one. In other words, all minimal saddle point free (SP-free) matrices are of size 2×2. We strengthen this result and show that all locally minimal SP-free matrices also are of size 2×2. In other words, if A is a SP-free matrix in which a saddle point appears after deleting an arbitrary row or column then A is of size 2×2. Furthermore, we generalize this result and characterize the locally minimal Nash equilibrium free (NE-free) bimatrix games.Let us recall that a two-person game form is Nash-solvable if and only if it is tight [V. Gurvich, Solution of positional games in pure strategies, USSR Comput. Math. and Math. Phys. 15 (2) (1975) 74-87]. We show that all (locally) minimal non-tight game forms are of size 2×2. In contrast, it seems difficult to characterize the locally minimal tight game forms (while all minimal ones are just trivial); we only obtain some necessary and some sufficient conditions. We also recall an example from cooperative game theory: a maximal stable effectivity function that is not self-dual and not convex.     

On the Selection of One Feedback Nash Equilibrium in Discounted Linear-Quadratic Games

We study a selection method for a Nash feedback equilibrium of a one-dimensional linear-quadratic nonzero-sum game over an infinite horizon. By introducing a change in the time variable, one obtains an associated game over a finite horizon T > 0 and with free terminal state. This associated game admits a unique solution which converges to a particular Nash feedback equilibrium of the original problem as the horizon T goes to infinity.     

三群体2×2×2非对称演化博弈稳定性分析

针对目前三方演化博弈的稳定性研究不足这一问题,利用复制动态方程构建了一般化的三维动力系统,首先讨论了单群体策略演化趋势,接着根据李雅普诺夫稳定性理论分析了系统的渐进稳定性,并结合单群体策略的演化趋势对系统稳定性作了深入研究。研究表明:严格纯策略纳什均衡是ESS,不严格纯策略纳什均衡是线性策略收敛(自定义概念),所有类型的混合策略纳什均衡均为鞍点,共同划分了ESS的吸引域,并证明了零特征值非ESS定理,以及ESS不共边定理,在此基础上给出了N维双策略系统中ESS的最多个数。最后,设计了六组经典算例,首先结合研究结果分析了算例,接着对算例进行系统仿真,仿真结果与理论分析一致,为演化博弈的进一步研究提供借鉴与启发。     

On the implementation of the L-Nash bargaining solution in two-person bargaining games

The “Nash program” initiated by Nash (Econometrica 21:128–140, 1953) is a research agenda aiming at representing every axiomatically determined cooperative solution to a game as a Nash outcome of a reasonable noncooperative bargaining game. The L-Nash solution first defined by Forgó (Interactive Decisions. Lecture Notes in Economics and Mathematical Systems, vol 229. Springer, Berlin, pp 1–15, 1983) is obtained as the limiting point of the Nash bargaining solution when the disagreement point goes to negative infinity in a fixed direction. In Forgó and Szidarovszky (Eur J Oper Res 147:108–116, 2003), the L-Nash solution was related to the solution of multiciteria decision making and two different axiomatizations of the L-Nash solution were also given in this context. In this paper, finite bounds are established for the penalty of disagreement in certain special two-person bargaining problems, making it possible to apply all the implementation models designed for Nash bargaining problems with a finite disagreement point to obtain the L-Nash solution as well. For another set of problems where this method does not work, a version of Rubinstein’s alternative offer game (Econometrica 50:97–109, 1982) is shown to asymptotically implement the L-Nash solution. If penalty is internalized as a decision variable of one of the players, then a modification of Howard’s game (J Econ Theory 56:142–159, 1992) also implements the L-Nash solution.     

A dual approach to primal degeneracy

The Revised Primal Simplex algorithm, in its simplest form, has no defence against degeneracy. Various forms of the perturbation method are usually effective, but most offer no guarantee of avoiding all degeneracy, and can lead to numerical difficulties. This paper presents a method that avoids cycling and circling by taking a dual approach.The degenerate subproblem consists of all the original variables, but only the degenerate transformed constraints. The current primal objective, which may be mixed, is used. This subproblem may be solved using the dual simplex algorithm, starting from the current dual infeasible solution, and with a zero dual objective. If the dual algorithm terminates optimally then the whole problem is optimal (subject to primal feasibility). Otherwise the final solution provides a non-basic direction which improves the value of the mixed primal objective and moves away from the degenerate vertex. A purification algorithm then renders the solution basic and further improves the mixed objective.     

A mixed finite element method with Lagrange multipliers for nonlinear exterior transmission problems

Summary. We apply a mixed finite element method to numerically solve a class of nonlinear exterior transmission problems in R ² with inhomogeneous interface conditions. Besides the usual unknowns required for the dual-mixed method, which include the gradient of the temperature in this nonlinear case, our approach makes use of the trace of the outer solution on the transmission boundary as a suitable Lagrange multiplier. In addition, we use a boundary integral operator to reduce the original transmission problem on the unbounded region into a nonlocal one on a bounded domain. In this way, we are lead to a two-fold saddle point operator equation as the resulting variational formulation. We prove that the continuous formulation and the associated Galerkin scheme defined with Raviart-Thomas spaces are well posed, and derive the a-priori estimates and the corresponding rate of convergence. Then, we introduce suitable local problems and deduce first an implicit reliable and quasi-efficient a-posteriori error estimate, and then a fully explicit reliable one. Finally, several numerical results illustrate the effectivity of the explicit estimate for the adaptive computation of the discrete solutions. Mathematics Subject Classification (2000): 65N30, 65N38, 65N22, 65F10This research was partially supported by CONICYT-Chile through the FONDAP Program in Applied Mathematics, and by the Dirección de Investigación of the Universidad de Concepción through the Advanced Research Groups Program.     

Dynamic pricing with uncertain production cost: An alternating-move approach

This article studies a two-firm dynamic pricing model with random production costs. The firms produce the same perishable products over an infinite time horizon when production (or operation) costs are random. In each period, each firm determines its price and production levels based on its current production cost and its opponent’s previous price level. We use an alternating-move game to model this problem and show that there exists a unique subgame perfect Nash equilibrium in production and pricing decisions. We provide a closed-form solution for the firm’s pricing policy. Finally, we study the game in the case of incomplete information, when both or one of the firms do not have access to the current prices charged by their opponents.     

Local controllability of a 1-D Schrödinger equation

We consider a nonrelativistic charged particle in a 1-D box of potential. This quantum system is subject to a control, which is a uniform electric field. It is represented by a complex probability amplitude solution of a Schrödinger equation. We prove the local controllability of this nonlinear system around the ground state. Our proof uses the return method, a Nash–Moser implicit function theorem and moment theory.     

Two noncooperative games between a coalition and its surrounding in a class of n-person games with constant sum

A cooperative game engendered by a noncooperative n-person game (the master game) in which any subset of n players may form a coalition playing an antagonistic game against the residual players (the surrounding) that has a (Nash equilibrium) solution, is considered, along with another noncooperative game in which both a coalition and its surrounding try to maximize their gains that also possesses a Nash equilibrium solution. It is shown that if the master game is the one with constant sum, the sets of Nash equilibrium strategies in both above-mentioned noncooperative games (in which a coalition plays with (against) its surrounding) coincide.     

Finding all pure strategy Nash equilibria in a planar location game

In this paper, we deal with a planar location-price game where firms first select their locations and then set delivered prices in order to maximize their profits. If firms set the equilibrium prices in the second stage, the game is reduced to a location game for which pure strategy Nash equilibria are studied assuming that the marginal delivered cost is proportional to the distance between the customer and the facility from which it is served. We present characterizations of local and global Nash equilibria. Then an algorithm is shown in order to find all possible Nash equilibrium pairs of locations. The minimization of the social cost leads to a Nash equilibrium. An example shows that there may exist multiple Nash equilibria which are not minimizers of the social cost.     

An efficient numerical method for preconditioned saddle point problems

In this paper, we consider the solution of linear systems of saddle point type by a preconditioned numerical method. We first transform the original linear system into two sub-systems with small size by a preconditioning strategy, then employ the conjugate gradient (CG) method to solve the linear system with a SPD coefficient matrix, and a splitting iteration method to solve the other sub-system, respectively. Numerical experiments show that the new method can achieve faster convergence than several effective preconditioners published in the recent literature in terms of total runtime and iteration steps.     

On an augmented Lagrangian-based preconditioning of Oseen type problems

The paper deals with a general framework for constructing preconditioners for saddle point matrices, in particular as arising in the discrete linearized Navier-Stokes equations (Oseen’s problem). We utilize the so-called augmented Lagrangian framework, where the original linear system of equations is first transformed to an equivalent one, which latter is then solved by a preconditioned iterative solution method.     

A polynomial-time method to compute all Nash equilibria solutions of a general two-person inspection game

We consider a two-person nonzero-sum simultaneous inspection game that takes place at multiple sites. The inspector has a limited inspection resource. She needs to decide which sites to inspect, and with how much effort, while adhering also to local restrictions on the permitted inspections levels at the sites. The inspectee has several employees who work on his behalf. He needs to decide how to distribute them across the sites, and how they should act there. Computation of Nash equilibria is challenging for this sort of games. Still, we develop a linear-time algorithm that determines all Nash equilibria solutions of the game, and provide explicit (easily computable) expressions for all possible Nash equilibria. We then derive some managerial insights by applying the algorithm to several examples, and examining the Nash equilibria, including an outcome that an increase in the inspection resource may induce the inspectee to cooperate more at sites without increasing the inspection levels at them.     

A Qualitative Characterization of Symmetric Open-Loop Nash Equilibria in Discounted Infinite Horizon Differential Games

The local stability, steady state comparative statics, and local comparative dynamics of symmetric open-loop Nash equilibria for the ubiquitous class of discounted infinite horizon differential games are investigated. It is shown that the functional forms and values of the parameters specified in a differential game are crucial in determining the local stability of a steady state and, in turn, the steady state comparative statics and local comparative dynamics. A simple sufficient condition for a steady state to be a local saddle point is provided. The power and reach of the results are demonstrated by applying them to two well-known differential games.     

Feedback saddle point solution of counterterror measures and economic growth game

In this paper, the feedback Nash equilibrium solutions of the differential game between counterterror measures and economic growth are investigated. The Hamilton–Jacobi–Isaacs (HJI) equation is used to obtain the feedback saddle point of this zero-sum game. Moreover, the characteristics of the feedback strategies for the government and terrorist organization as well as their relationships with both resource states are analyzed.