Open access peer-reviewed chapter

Existence of Open Loop Equilibria for Disturbed Stackelberg Games

Written By

T.-P. Azevedo Perdicoúlis, G. Jank and P. Lopes dos Santos

Submitted: October 15th, 2019 Reviewed: March 20th, 2020 Published: May 11th, 2020

DOI: 10.5772/intechopen.92202

Chapter metrics overview

544 Chapter Downloads

View Full Metrics

Abstract

In this work, we derive necessary and sufficient conditions for the existence of an hierarchic equilibrium of a disturbed two player linear quadratic game with open loop information structure. A convexity condition guarantees the existence of a unique Stackelberg equilibria; this solution is first obtained in terms of a pair of symmetric Riccati equations and also in terms of a coupled of system of Riccati equations. In this latter case, the obtained equilibrium controls are of feedback type.

Keywords

  • differential games
  • linear quadratic
  • Riccati differential equations
  • Stackelberg equilibrium
  • worst-case disturbance

1. Introduction

The study of linear quadratic (LQ) games has been addressed by many authors [1, 2, 3, 4]. This type of games is often used as a benchmark to assess the game equilibrium strategies and its respective outcomes. In a disturbed differential game, each player calculates its strategy taking into account a worst-case unknown disturbance. In non-cooperative game theory, the concept of hierarchical or Stackelberg games is very important, since different applications in economics and engineering exist [1, 5]. This is also the case of gas networks where a hierarchy may be assigned to its controllable elements—compressors, sources, reductors, etc… Also, for this application, the modelling as a disturbed game makes a lot of sense, since the unknown offtakes of the network can be modelled as unknown disturbances. Further research on Stackelberg games can be found for instance in AbouKandil and Bertrand [6]; Medanic [7]; Yong [8]; Tolwinski [9].

No assumptions/constraints are made of the disturbance. To be easier to understand the hierarchical concept, we consider only two players. Therefore, we study a LQ game of two players with Open Loop (OL) information structure where the players choose its strategy according to a modified Stackelberg equilibrium. Player-1 is the follower and chooses its strategy after the nomination of the strategy of the leader. Player-2, the leader, chooses its strategy assuming rationality of the follower. Both players find their strategies assuming a worst-case disturbance.

In this work, we consider a finite time horizon, where for applications this is chosen according to the periodicity of the operation of the problem being studied.

The disturbed case of the representation of optimal equilibria for noncooperative games has been studied [10, 11] considering a Nash equilibrium. It is the aim of this paper to generalise the work of Jank and Kun to Stackelberg games and extend the results presented in Freiling and Jank [12]; Freiling et al. [13] to the disturbed case. To calculate the controls, we use a value function approach, appropriately guessed. Thence, we obtain sufficient conditions of existence of these controls and its representation in terms of the solution of certain Riccati equations. Furthermore, a feedback form of the worst-case Stackelberg equilibrium is obtained.

In a future paper, we expect to present analogous conditions using an operator approach.

In Section 2, we define the disturbed LQ game and define Stackelberg worst-case equilibrium. In Section 3, we derive sufficient conditions for the existence of a worst-case Stackelberg equilibrium under OL information structure and investigate how are these solutions related to certain Riccati differential equations. Section 4 concludes the paper and outlines some directions for future work.

Advertisement

2. Fundamental notions

We start with the concept of best reply:

Definition 2.1. (Best reply) Let ΓN be a N-player differential game. For i1N,

γiγ1γi1γi+1γNjiUj.

We say that γ˜i is the best reply against γi if

Jiγ1γi1γ˜iγi+1γNJiγ1γN

holds for any strategy γiUi. We denote the set of all best replies by Riγi.

We study games of quadratic criteria, defined in a finite time horizon t0tfR and subject to a linear dynamics, controlled players and also an unknown disturbance. Hereby also consider uj=γjtηj, where ηj is the information structure of Player-j. In this case, ηj,j=1,,N, is of OL type.

Definition 2.2. (Linear Quadratic (LQ) differential game) Let ΓN be an N player differential game finite time horizon T=t0tf. Suppose further that:

  1. the dynamics of the game are assumed to obey a linear differential equation

ẋt=Atxt+j=1NBjtujt+Ctwt,xt0=x0.E1

In this equation, tT, where the initial t0 and the final tf are finite and fixed, the state xt is an n dimension vector of continuous functions defined in T and with xtf=xf. The controls ui,i=1,,N, are square (Lebesgue) integrable and the mi dimension vector of continuous functions is also defined in T. Also, the disturbance wtLmT. The different matrices are of adequate dimension and with elements continuous in T.

  1. the performance criteria are of the form

Jiuiuiw=Kxtf+t0tfΨuiuiwdt.E2

where

Kxtf=xTtfKifxtfE3
Ψuiuiw=xTtQitxt+wTtPitwt+j=1NujTtRijtujt,E4

with symmetric matrices KifRn×n and symmetric, piecewise continuous and bounded matrix valued functions QitRn×n,RijtRmi×mj and PitRm×m,i=1,2,,N.

We observe that no cost functional is assigned to the disturbance term because no constraints can be applied on an “unpredictable” parameter. In what follows, we consider N=2. To extend the theory to N>2, since this is an hierarchical solution, we need to define the structure of the leaders and followers in the game. We can even have more than two hierachy levels. We assume that Player-2 is the leader and Player-1 is the follower.

The leader seeks a strategy u2t in OL information structure and announces it before the game starts. This strategy is found knowing how the follower reacts to his choices. The follower calculates its strategy as a best reply to the strategy announced by the leader.

Problem 2.1. Find the control uiUi,i=1,2, in T for which Jiuiuiw,i=1,2, is minimal when subject to constraints uit=γitηit,i=1,2, and (1) and considering a worst-case disturbance.

Consider Ui,i=1,2, the sets of functions such that (1) is solvable and Ji exists, with ui,i=1,2, in these conditions Ui,i=1,2,W are said the sets of admissible controls and disturbance, respectively.

Definition 2.3. (Stackelberg equilibrium) Let Γ2 be a 2-person differential game, we define the Stackelberg/worst-case equilibrium in two stages.

  1. A function ŵiuW is called the worst-case disturbance, from the point of view of the ith player belonging to the set of admissible controls, if

JiuiuiŵiJiuiuiw,i=1,2,E5

holds for each wW. There exists exactly one worst-case disturbance from the point of view of the ith player according to every set of controls.

  1. We say that the controls u1u2 form a worst-case Stackelberg equilibrium if

  1. The leader chooses u2 such that

maxγ1R1u2J2γ1u2ŵ2maxγ1R1u2J2γ1u2ŵ2

for all u2U2.

  1. The follower then chooses u1 such that

R1u2=u1J1u1u2ŵ1J1γ1u2ŵ1.

To guarantee the uniqueness of OL Stackelberg solutions, matrices are assumed to satisfy Kif0,Qi0,Rij>0,ij and Rii0,i,j=1,,N in T Simaan and Cruz [14].

In what follows, we drop the dependence of the parameters in t to reduce the length of the formulas.

Advertisement

3. Sufficient conditions for the existence of OL Stackelberg equilibria

In this section, we withdraw sufficient conditions for the existence of the worst-case Stackelberg equilibrium, using a value function approach.

A disturbed differential LQ game as defined in Definition 2.2 is said playable if there exists a unique Stackelberg worst-case equilibrium.

Theorem 3.1. Let the solution of the Riccati differential equation

Ė1=E1AATE1Q1+E1S1+T1E1,E1tf=K1f,E6

with S1=B1R111B1T and T1=CP11CT exist on T.

For any given admissible OL control of the leader, u2, define e1Rn,d1R by

ė1=E1S1+T1e12E1B2u2ATe1T,e1tf=0E7
ḋ1=u2TR12+e1TB2u2+14e1TS1+T1e1,d1tf=0.E8

Then, the following identity holds:

2J1u1u2=x0TE1t0x0+x0Te1t0+d1t0+t0tfz1tR112dt+t0tfztP12dt,E9

where z1R112=z1R11z1 with

z1=u1+R111B1TE1x+12e1

and zP12=zP1z with

z=w+P11CTE1x+12e1

and x a solution of (1).

Proof: The proof is similar to the analogous result for the non-disturbed case Freiling et al. [13].

Theorem 3.2. Let the solution E1 of (6) exist on T. Then the unique response of the follower to the leader’s OL strategy u2t is given by:

u1=R111B1TE1x+12e1,E10

where the maximum disturbance,

w1=P11CTE1x+12e1,E11

was considered. E1 and e1 are the solutions of (6)(7) and x is then the solution of

ẋ=AS1+T1E1x12S1+T1e1+B2u2,E12
xt0=x0.E13

The corresponding minimal costs then are

J10=2J1u1u2=x0TE1t0x0+x0Te1t0+d1t0.E14

Proof: We have that the unique OL response of the follower to the leader’s announced strategy u2(10) under worst-case disturbance (11), that we substitute in the trajectory (1) to obtain:

ẋ=AS1+T1E1x12S1+T1e1+B2u2.

The cost functional minimal value is obtained when we substitute in (9) the minimal control and themaximal disturbance.

Notice that J10u2 is not depending on u1. This, as a matter of fact, is only true if we consider OL information structure, since otherwise u2 would depend on the trajectory x and hence, via (1), also on u1. In OL Stackelberg games, the leader tries next to find an optimal OL control u2 that minimises J2u1u2u2 while u1u2 is defined by (10).

Theorem 3.3. Let the solution of the Riccati differential Eq. (6) and the solution of

Ė2=E2HHTE2Q+E2S+TE2,E2tf=K2f000,E15

with S21B1R111R21R111B1T,S2B2R221B2T and T2CP21CT. Also HAS1Q1E1T1AT,QQ200S21,SS2000 and TT2T2E1E1T2E1T2E1 exist in T, where E2R2n×2n. Also BB20m1×n.

For any given control u2 of the leader, define functions e2R3n,v1,vw,xRn and d2R in T by the following initial and terminal value problems:

ė2=HT+E2S+Te2,e2tf=0E16
ḋ2=14e2TS+Te2,d2tf=0E17
v̇1=Q1x+E1T1ATv1+E1Cw,v1t0=v10E18
ẋ=AxS1v1+B2u2+Cw,xt0=x0,E19

with v1E1+12e1.

Then, we obtain

u1=R111B1Tv1,w1=P11CTv1,

and the following identity

2J2u1u2w2=x0Tv10E2t0x0v10+x0Tv10e2t0+d2t0+t0tfz2R222dt+t0tfzP22dt,

where y=xv1,z2R222=z2R22z2 and

z2=u2+R221B2T0m1×nE2y+12e2

and 0mi×n,i=1,2 the mi×n dimensional zero matrix and zP22=zP2z and

z=w2+P21C1TE2y+12e2.

Proof: Consider (10): u1=R111B1TE1x+12e1v1. Then, differentiate v1 and substitute the derivatives into the obtained expression using (6), (7) and (8). Also, the optimal control u1 and disturbance w1 in (11). Hence:

v̇1=Q1xATv1,ẋ=AxS1v1+B2u2+Cw.

Hence defining HAS1Q1E1T1AT,BB2On×m2 and C1IE1C. We define yxv1 to write these two equations as: (??) as:

ẏ=Hy+Bu2+C1wE20

Next, we consider the following value function

V˜2t=V2tyt=yTE2y+e2Ty+d2E21

for some mappings E2:TR2n×2n,e2:TR2n, and d2:TR2, where E2 is symmetric for each tT.

We consider (21), where we substitute (20):

dV˜2dt=ddtyTE2y+e2Ty+d2=ẏTE2y+yTĖ2y+yTE2ẏ+ė2Ty+e2Tẏ+ḋ2+xTQ2x+u1TR21u1+u2TR22u2+wTP2wψ2=yTHT+u2TBTwTC1TE2y+yTĖ2y+yTE2Hy+Bu2+C1w+ė2Ty+e2THy+Bu2+C1w+ḋ2+yTQ200S21Qy+u2TR22u2+wTP2wψ2

Now we associate certain terms

=yTHTE2+Ė2+E2H+Qy+u2y2TR22u2y2+y2TR22u2+u2TR22y2y2TR22y2+wαTP2wα+wTP2α+αTP2wαTP2α+u2TBTE2y+BTe2+yTE2B+12e2TBu2+wTC1TE2y+C1Te2+yTE2C1+12e2TC1wė2T+e2THy+ḋ2ψ2

and furthermore

=yTHTE2+Ė2+E2H+Qyψ2+u2y2TR22u2y2y2TR22y2+wαTP2wααTP2α+u2TBTE2y+BT12e2+R22y2+yTE2B+12e2TBy2TR22u2+wTC1TE2y+C1T12e2+P2α+yTE2C1+12e2TC1αTP2wė2T+e2THy+ḋ2ψ2

Consider

R22y2+B2TOm2×nE2y+12e2=0

and also

C1TE2y+12e2+P2α=0

If R22>0 then y2=R221B2TOm2×nE2y+12e2. If P2>0 then α=P21C1E2y+12e2.

Define SS2000 and TT2T2E1E1T2E1T2E1. Substitute this y2 and α in the calculations:

=yTHTE2+Ė2+E2H+QE2S+TE2y+u2y2TR22u2y2+wαTP2wα+ė2T+e2THE2S+Ty+ḋ214e2TS+Te2ψ2

Considering:

HTE2+Ė2+E2H+QE2S+TE2=0ė2T+e2THe2TS+TE2=0ḋ214e2TS+Te2=0

that is

Ė2=HTE2E2HQ+E2S+TE2ė2=HT+E2S+Te2ḋ2=14e2TS+Te2

We end up with

dV˜2tdt=u2y2TR22u2y2+wαTP2wαψ2E22

Integrating yields:

V˜2tfV˜t=ttfu2y2TR22u2y2+wαTP2wαsttfψ2.

Further, we assume the mappings E2,e2,d2 to be chosen in such a way that the following terminal values hold:

E2tf=K2fe2tf=0d2tf=0

Then, we obtain V˜2tf=yTtfKyfytf and substituting:

V˜2t=yTtfKyfytfttfu2y2TR22u2y2+wαTP2wα+ttfψ2E23

Observe that the rhs of (23) does not depend of ut0t and the rls of (23) does not depend of u2ttf. Then considering now the infimal value, we recall that:

V2ty=infu2ttfttfψ2τŷτuτ+yTtfK2fytf

Now, we substitute this into (23) and consider the infimal values over all possible control functions in ttf:

V˜2t=infyTtfK2fytf+ttfψ2V2tyinfttfu2y2TR22u2y2+wαTP2wα

then we have:

V2ty=V˜t+infut,tfttfu2y2TR22u2y2+wαTP2wα

V2ty equals V˜2t if u2y20tT and wα=0. As the leader chooses his strategy assuming rationality of the follower and worst-case disturbance, the follower should take also the worst-case disturbance into account.

To conclude, consider t=t0 and hence:

V2t0y=V˜2t0+infut0,tft0tfu2y2TR22u2y2+wαTP2wα

Then from (21):

V2t0y=y0TE2t0y0+e2Tt0y0+d2t0+infut0,tft0tfu2y2TR22u2y2+wαTP2wα

Defining z2u2y2=u2+R221B2T0E2y+12e2 and zwα=w+P21C1E2y+12e2, we have:

V2t0y=y0TE2t0y0+e2Tt0y0+d2t0+t0tfz2R222+zP22dt

Now, we substitute y0=x0v10.

The leader may choose its best answer either by accounting directly for its worst-case disturbance or by considering that the follower knows that there is a worst-case disturbance. In this work, the leader takes the worst-case disturbance directly into account.

Notice that in the term

J20=x0Tv10E2t0x0v10,E24

x0,E2t0, do not depend on the choice of u1,u2. Since we shall study the situation for Player-2 when Player-1 applies his optimal response control defined in (10), we have to set v1=E1x+12e1. From (7), we can see that v1t0=v10 depends on e1t0 and hence also on u2.

In order to derive from Theorems (3.1) and (3.3) sufficient conditions for the existence of a unique worst-case Stackelberg equilibrium, we must get rid of the u2-dependence on v10. Therefore, we propose to restrict the set of admissible controls to functions representable in linear feedback form. This is what we do next.

Theorem 3.4. Let the solutions E1tRn×n,E2R2n×2n of (6) and (15) exist in T, respectively. Let further the coupled system of equations

K̇1=Q1K1AATK1+K1S1+T1K1+K1S2K2,E25
K̇2=Q2K2AATK2+Q1p+K2S1K1+K2S2+T2K2+K2T2E1p,E26
ṗ=pAS21K1+S1K2+AT1E1p+pS1K1+pS2+T2K2+pT2E1p,E27

admits a solution in T.

Then, there exists a unique open loop disturbed Stackelberg equilibrium in feedback synthesis which is given by

u1t=R111tB1TtK1txt,E28
u2t=R221tB2TtK2txt,E29

considering worst-case disturbamces wi and where xt is a solution of the closed loop equation

ẋ=AS1K1S2+T2K2T2E1px,xt0=x0.E30

The minimal cost for the follower, J10u2, is as in (14), and for the leader is

J20u1u2=12x0TInK1Tt0E2t0t0InK1t0x0+e2Tt0InK1t0x0+d2t0

where e2t0,d2t0 are determined by (16) and (17), respectively.

Proof: The proof is similar to the analogous result for the non-disturbed case [13].

From the convexity assumptions, it follows that S1,S,Q1,Q and E1tf,E2tf are all semidefinite. Therefore, as far as the convexity conditions hold, the standard Riccati matrix Eqs. (6) and (15) are globally solvable in tf [15].

It still remains the following questions to be answered (i) direct criteria for solvability of these equations if the convexity assumption is guaranteed as well as (ii) solvability of the coupled system of Eqs. (25)(27).

Actually, this system of equations can also be written as a single, nonsymmetric Riccati matrix differential equation. Hence:

K̇1K̇2ṗ=Q1Q20K1K2pA+AT000ATQ1S21S1AT1E1K1K2p+K1K2pS1+T1,S2,0K1K2pK1K2ptf=K1fK2f0.E31

As it can be easily observed, all these Riccati equations are of nonsymmetric type:

Ẇ=B21WB11+B22W+WB12W,Wtf=Wf,E32

where W is a matrix of order k×n whose coefficients are of adequate size. See AbouKandil et al. [16] for results on the existence of solution of Riccati equations.

Advertisement

4. Discussion and conclusions

High dimension problems appeal to the use of hierarchic and decentralised models as differential games. One example of these problems is large networks, as for instance the management and control of high pressure gas networks. Since this is a large dimension and geographically dispersed problem, a decentralised formulation captures the non-cooperative nature, and sometimes even antagonistic, of the different stake-holders in the network.

The network controllable elements can be seen as players that seek their best settings and then interact among themselves to check for network feasibility. The equilibrium sought by the players depends on the way the players are organised among themselves. It makes some sense to have some autonomous elements that run the network and others follow, as is the case of a main inlet point of a country, as it happens with the inlet of Sines in the portuguese network. The ultimate goal of the network is to meet customers’ demand at the lowest cost. As the main variation of the problem is due to the off-takes, these may be seen as perturbations to nominal consumption levels of a deterministic model.

Therefore, it makes some sense to view the gas transportation and distribution system as a disturbed Stackelberg game where the players play against a worst-case disturbance, that means a sudden change in weather conditions from one period of operation to the other. Neverthless, the theory is not ready, and also having in mind the development of algorithms, direct solution methods, and explicit solution representations need to be further investigated. In this work, we have obtained sufficient conditions for the existence of the solution of a 2-player game. However, direct criteria for solvability of this problem needs more work. Also, the solvability of the coupled system of Eqs. (25)(27) has to be further investigated. Also, we would like to solve the same problem using an operator approach.

Similarly to what we have done in the past for Nash games, we would like to study this problem considering the underlying dynamics as a repetitive process, that seems to be adequate to capture the behaviour seemingly periodic of the network. Also, the boundary control of the network depends on the type of strategy sought by the players. The structure of these versions of the problems need to be examined.

The obtained results, in every stage of the work, should be applied to a single pipe and ideally using some operational data. Furthermore, we expect to apply the work to a simple network, which is not exactly a straightforward extension.

Advertisement

Acknowledgments

I would like to thank the reviewer for his valuable suggestions.

This work has been financed by National Funds through the Portuguese funding agency, FCT – Fundao para a Cincia e a Tecnologia under project: (i) UID/EEA/00048/2019 for the first author and (ii) UID/EEA/50014/2019 for the third author.

References

  1. 1. Bagchi A. Differential games in economic models. In: Lecture Notes in Control and Information Sciences. Vol. 64. Springer Verlag; 1984
  2. 2. Eisele T. Nonexistence and nonuniqueness of open-loop equilibria in linear quadratic differential games. Journal of Optimization Theory and Applications. 1982;37:443-468
  3. 3. Lukes DL, Russel DL. A global theory for linear quadratic differential games. Journal of Mathematical Analysis and Applications. 1971;33:96-123
  4. 4. Mehlmann A. Applied Differential Games. New York: Springer Verlag; 1988
  5. 5. Basar T, Olsder G. Dynamic noncooperative game theory. 2nd ed. London: SIAM; 1999
  6. 6. Abou-Kandil H, Bertrand P. Analytical solution for an open-loop Stackelberg game. IEEE Transactions on Automatic Control. 1985;AC-30:1222-1224
  7. 7. Medanic J, Radojevic D. Multilevel Stackelberg strategies in linear quadratic systems. Journal of Optimization Theory and Applications. 1987;24:485-479
  8. 8. Pan L, Yong J. A differential game with multi-level of hierarchy. Journal of Mathematical Analysis and Applications. 1991;161:522-544
  9. 9. Tolwinski B. A Stackelberg solution of dynamic games. IEEE Transactions on Automatic Control. 1973;AC-28:85-93
  10. 10. Jank G, Kun G. Optimal control of disturbed linear quadratic differential games. European Journal of Control. 2002;8(2):152-162
  11. 11. Kun G. Stabilizability, controllability and optimal strategies of linear and nonlinear dynamical games [Ph.D. Thesis]. RWTH Aachen; 2000
  12. 12. Freiling G, Jank G. Existence of open-loop Stackelberg equilibria. In: Proceedings of the Mathematical Theory of Networks and Systems, MTNS 98. Symposium held at Padova, Italy; 1998
  13. 13. Freiling G, Jank G, Lee S-R. Open-loop Stackelberg equilibria in linear quadratic differential games. Journal of Optimization Theory and Applications. 2001;110(3):515-544
  14. 14. Simaan M, Cruz JB. On the Stackelberg strategy in nonzero-sum games. Journal of Optimization Theory and Applications. 1973;11(5):533-555
  15. 15. Knobloch HW, Kwakernaak H. Lineare KontrollTheorie. London: Springer Verlag; 1985
  16. 16. Abou-Kandil H, Freiling G, Ionescu V, Jank G. Matrix Riccati Equations in Control and Systems Theory. Basel: Birkhäuser Verlag; 2003

Written By

T.-P. Azevedo Perdicoúlis, G. Jank and P. Lopes dos Santos

Submitted: October 15th, 2019 Reviewed: March 20th, 2020 Published: May 11th, 2020