Robust Dynamic Programming in N Players Uncertain Differential Games

1Introduction

Differential games stand as a suitable framework for modelling strategic interaction between different agents (known as players), where each of them is looking for the minimization or, equivalently, the maximization of his individual criterion (Engwerda, 2005; Başar and Olsder, 1999). In such a multi-player scenario, none of the players is allowed to maximize his profits or objectives at the expense of the rest of the players. Therefore, the solution of the game is given in a form of “equilibrium of forces”.

Among different types of solutions, the so called Nash equilibrium is the most extensively used in the game theory literature. In this solution none of the players can improve their criteria by unilaterally deviating from their Nash strategy; therefore, no player has an incentive to change his decision. When the full state information is available to all the players to realize their decision strategy in each point of time, this is called a feedback Nash equilibrium (Engwerda, 2005; Başar and Olsder, 1999; Friedman, 1971). In order to find such feedback strategies, the optimal control tools are applied, specifically an equivalent N players form of the Hamilton–Jacobi–Bellman equation is required to be solved for each of the players. In the case of the non-cooperative Nash equilibrium solution framework, each player deals with a single criterion optimization problem (the standard optimal control problem), with the actions of the remaining players taking fixed equilibrium values.

Although the notion of robustness is such an important feature in the control theory, there are not many studies of dynamic games that are affected by some sort of uncertainties or disturbances. Some recent developments on this topic can be mentioned. Jiménez-Lizárraga and Poznyak (2007) presented a notion of open loop Nash equilibrium (OLNE) where the parameters of the game are within a finite set and the solution is given in terms of the worst-case scenario, that is, the result of the application of certain control input (in terms of the cost function value) is associated with the worst or least favourable value of the unknown parameter. The article of Jank and Kun (2002) shows also an OLNE and derives conditions for the existence and uniqueness of a worst case Nash equilibrium (WCNE); however, in this case they considered that the uncertainty belongs to a Hilbert functional space and enters adding up into the time derivative of the state variables. A similar problem is considered in a quite recent work (Engwerda, 2017), where the author shows that the WCNE can be derived by finding an ONLE of an associated differential game with 2N initial state constraints, the author derives necessary and sufficient conditions for the solution of the finite time problem. The work of Jungers et al. (2008) deals with a game with polytopic uncertainties that reformulated the problem as a nonconvex coupling between semi-definite programming to find the Nash type controls. Other related approaches include: using the Nash strategy to design robust controls for linear systems (Chen and Zhou, 2001). Another way to deal with uncertainties is to view them as an exogenous input (a fictitious player) (Chen et al., 1997). In the work of van den Broek et al. (2003) the definition of equilibria is extended to deal with two cases: a soft-constrained formulation whose basis is given by Jank and Kun (2002), where the fictitious player is introduced in the criteria via a weighting matrix.

In this work, inspired in the works of Jank and Kun (2002) and Engwerda (2005, 2017), we analyse a deterministic N-player non-zero sum Differential Game case, considering finite, as well as infinite, time horizon in the performance index and a L2 perturbation which is considered as a fictitious player trying to maximize the cost of each i-th player.

Assuming the player has access to the full state information, we are interested in finding a type of robust feedback Nash strategies, that guarantee a robust equilibrium when the players consider the worst case of the perturbation with respect to their own point of view. To that end, a set of robust form of the HJB equations are introduced; each of these equations compute not only the minimum of the i-th player control; but the maximum or worst case uncertainty from his point of view; resulting in a min-max form of the known HJB equations for a N players game. To the best of the authors’ knowledge, using such a robust HJB equation has not been considered before to find a robust feedback Nash equilibrium in linear quadratic deterministic games, which stand as an important case to study. To summarize, the contributions of this work are as follows:

The development of this paper is as follows. In Section 2 we state, formally, the general problem of a differential game and the conditions for the Robust Nash Equilibrium to exist. Then, in Section 3 we define the dynamics of the problem analysed and the type of functional cost we have to minimize for a finite time horizon problem, we also state a theorem based on dynamic programming to find the robust controls for each player. In Section 4 we analyse the case of infinite time horizon. Finally, Section 5 follows with a numerical example. The purpose of this last section is to show how to apply the formulas obtained in Sections 3–4 and then compare our results against a finite time differential game which does not consider perturbation in the solution of the problem, which is the common problem treated, but the system itself is affected by some sort of perturbation.

2Problem Statement

In this section we exploit the principle of dynamic programming in order to find all the robust feedback Nash equilibrium strategies for each player of a Non-zero sum uncertain differential game. We begin by presenting the general sufficient conditions for such a robust equilibrium to exist. Towards that end, consider the following N-person uncertain differential game with initial pair (s,y)∈[0,T]×Rn×1 described by the following initial value problem

Throughout the article we shall use the next notations:

3Finite Time Horizon N Players Linear Affine Quadratic Differential Game

Once the general conditions for the existence of a robust feedback Nash equilibrium in an uncertain differential game are established, we turn now to the special case of the linear affine quadratic differential games (LAQDG). In this section we consider the case where the time horizon is finite, that is, T<+∞. The game is played by N participants which are trying to minimize certain loss inflicted by a disturbance, besides, the functional cost of the game is restricted by the corresponding differential equation. Therefore, in this section we assume that:

For the linear affine dynamics given in (14), equation (12) can be rewritten as follows:

The proof of this theorem is presented in Appendix A.

4Infinite Time Horizon Case

In this section we consider the same linear affine quadratic game when the time horizon is infinite. As the case analysed in the last section, the players are trying to minimize certain loss inflicted by a disturbance, besides, the functional cost of the game is restricted by a differential equation which considers an affine term. In this type of game the functional cost is given by:

To find the solution to this problem the completion of the square method is developed in Poznyak (2008) and the following theorem is stated.

The proof of this theorem is found in Appendix A.

5Numerical Example: A Differential Game Model for a Vertical Marketing System with Demand Fluctuation and Seasonal Prices

Consider a noncooperative game in a two-echelon supply chain established between two chain agents (Dockner et al., 2000; Jørgensen, 1986); a single supplier (called the manufacturer) and a single distributor (called the retailer). The manufacturer is in charge of selling a product type to a single retailer over a period of time T at the price p1(t). The retailer is in charge of distributing and marketing that product, at a price p2(t)=p1(t)+r2(t), where r2(t) represents the profit margin gained by the retailer at time t per each unit sold. In this case, let us set r2=0.2p1.

The dynamic of the game is established by both players searching for a Nash equilibrium in their coordination contract, and furthermore facing some source of uncertainties. For this particular case assume that the retailer deals with a demand that evolves exogenously over time, with the quantity sold per time unit, d, depending not only on price p1, but also on the time t elapsed, d=d(p,t). The exogenous change in demand presented here is due to seasonal fluctuations. Under such enviroment, the profit equations for each players are J1 and J2 with the following quadratic structure:

Fig. 1

Price vs Perturbed demand.

Fig. 2

Riccati differential equation player 1 (manufacturer).

Fig. 3

Riccati differential equation player 2 (retailer).

Fig. 4

Comparison between manufacturer produced units ( u1), units demanded by the retailer ( u2), and units left in the manufacturer stock x1.

According to the game equations (1) and (2), N=2. We used the Matlab software to solve numerically backward in time (21), thus obtaining the corresponding robust Nash equilibrium strategies for each player. The results of such numerical solution are shown in figures (Figs. 2, 3). In Fig. 1 are depicted the perturbed demand and the manufacturer price. Figure 4 shows the behaviour of decision variables from each player, and the state equation from the manufacturer ( u1 production manufacturer’s rate, u2 purchasing retailer’s rate, and manufacturer’s inventory). Through this figure we can compare the different outputs, for instance, we observe that products left in the manufacturer’s stock basically are close to zero. In fact, this figure shows the advantages of better coordination between the different chain agents, in order to reduce bullwip effect. Since, the manufacturer and the retailer share information about customer demand, the produced goods from the manufacturer and the purchased goods from the retailer are deriving in similar behaviour.

Also, since there are no restrictions for the states of a given stage in the chain we can see that, at times, we are going to have negative values for this variable. For example, between t=8 and t=16, the units left in stock get a negative value, this only means that the manufacturer has backlogged units. However, we can appreciate that the amount of this backlogged units is minimum. Also for the closing of the season, between t=20 and t=25 it is better for the manufacturer only to have backlogged units. Once we get a Nash equilibrium, any deviation from the output policies would result in a loss for the manufacturer or the retailer.