All-Against-One Linear-Quadratic Differential Games
Shahriar Talebi Marwan A. Simaan Zhihua Qu







All-Against-One Linear-Quadratic
 Differential Games
    
	The authors are with the Department of Electrical and Computer Engineering, University of Central Florida, Orlando, FL. Emails: shahriar@ece.ucf.edu, simaan@ucf.edu, qu@ucf.edu.
	This work was supported in part by the US National Science Foundation under grants ECCS-1308928.
Shahriar Talebi, Student Member, IEEE, Marwan A. Simaan, Life Fellow, IEEE,  Zhihua Qu, Fellow, IEEE,


    
=================================================================================================================================================================================================================================================================================================================================================================================================




All-Against-One (AAO) games are a special class of multi-player games where all players except one are in direct conflict with the remaining player.  In the case of Linear Quadratic Differential (LQD) games, the AAO structure can be used to describe a situation where all players except one are trying to regulate the state of the system (drive it towards the origin) while the opposing player is trying to de-regulate the state (drive it away from the origin). Similar to the standard LQD games, the closed-loop Nash strategies in the AAO LQD games are expressed in terms of the solutions of a set of coupled matrix Riccati differential equations. However, conditions for existence of a solution to these equations are different and more challenging in the AAO case. In this paper, we derive conditions for existence, definiteness, and uniqueness of a solution to these equations as well as conditions for boundedness of the resulting state trajectory to ensure that the opposing player fails in accomplishing its objective. Finally, we consider two options for designing Nash strategies for the players and we illustrate the results with an example of 3-against-1 pursuit-evasion differential game.




§ INTRODUCTION

Many large enterprises consist of a large number of interacting subsystems.  These systems often operate optimally when all subsystems have a harmonious non-conflicting relationship among themselves.  When one subsystem decides to operate in a manner that is not consistent with the others, the operation of the entire enterprise suffers resulting in an adversarial environment that affects not only the behavior of the dissenting subsystem but also possibly the other conforming subsystems as well.  The disruption caused by one dissenting subsystem may cause the remaining subsystems to act as a unified team or it may result in the entire enterprise disintegrating and behaving in a non-cooperative manner within itself.  These types of systems are best analyzed under the general framework of game theory and more specifically using a new structure, which we refer to as All-Against-One (AAO) games.

An example of AAO games, which has recently been considered in the literature, is the multi-pursuer one-evader pursuit evasion game <cit.>.  In this game, a group of pursuers are trying to catch one evader who is trying to escape.  The solution of these types of games involves the development of movement strategies for the pursuers and evader that will conclude with either the evader escaping or being captured.      Except for this multi-pursuers one-evader problem, game theory has mainly been concerned with independent non-cooperative players with typically different objectives <cit.>. The Nash equilibrium has been a very useful concept in defining strategies for such games <cit.>.  The AAO structure, however, provides a unique configuration that allows for a more specific analysis of problems where a group of players, all having different but similar objectives, act against one opposing player. 

In this paper, we focus on All-Against-One (AAO) Linear Quadratic Differential (LQD) game.  Non-zero sum LQD games have been studied for decades, beginning with the seminal paper by Starr and Ho <cit.>.  An M-player LQD game is described by the system dynamics:

    ẋ = A x + ∑_j=1^MB_j u_j,    x(t_0) =x_0;

and cost functions

    J_i = 1/2 x^⊺(t_f) S_if x(t_f) + 1/2∫_t_0^t_f[x^⊺ Q_i x
    + u_i^⊺ R_i u_i ]dt

for i=1,2,...,M, where x is the state vector and u_1 through u_M are the players' control vectors. Matrices A, B_i, Q_i and R_i are all bounded and of proper dimensions and S_if≥ 0 and Q_i ≥ 0 are symmetric positive semi-definite matrices and R_i > 0 is symmetric positive definite for i = 1, 2, ..., M.  For simplicity of notation and derivations, we have not included the input cross-coupling terms in the cost functions.

The AAO LQD game is described by the same dynamics as in (<ref>) and cost functions as in (<ref>) except that now S_1f < 0 and Q_1 < 0 are symmetric negative definite matrices while S_if≥ 0 and Q_i ≥ 0 for i = 2, 3, ..., M remain as before.  This formulation puts players 2,…,M directly in conflict with player 1.  That is, while players 2 through M are trying to regulate the state of the system by minimizing its deviation from the origin as in the standard LQD game, player 1 is now trying to de-regulate (or de-stabilize) the system by maximizing the deviation of the state from the origin.   Because of this, existence results of the closed-loop Nash strategies for players in the standard LQD game <cit.> do not apply to the AAO games. 

In this paper, we derive conditions for existence, definiteness, and uniqueness of the closed-loop Nash strategies in AAO LQD games as well as boundedness of the resulting state trajectory. The paper is organized as follows: In section <ref>, we define the problem and derive new conditions for existence and definiteness of the closed-loop Nash strategies as well as sufficient conditions for the exponential boundedness of the resulting state trajectory. One advantage of the AAO structure is that it provides for an additional option for the group of players to consider forming a cooperative team against the opposing player in an attempt to improve their collective performance.  In section <ref>, we discuss the Team-Nash strategy for the group of players in designing their strategies against the opposing player as an alternative option to the Nash strategy among all players. In section <ref>, we present an illustrative example of three-pursuers one-evader, as a three-against-one game that considers different pursuit-evasion scenarios and shows simulation results for both pursuers' strategies when the evader is using a strategy that yields a Nash equilibrium in each case. Concluding remarks are presented in section <ref>.



 §.§ Notation

The real maximum (minimum) eigenvalue of a symmetric n × n matrix Q(t) at each instant of time t is denoted by λ_Q^max(t) (λ_Q^min(t)). 
The maximal (minimal) eigenvalue of the same matrix Q(t) over the interval [t_0,t_f] is a real constant defined as λ̅_Q≜max_t ∈ [t_0,t_f]λ_Q^max(t) (λ_Q≜min_t ∈ [t_0,t_f]λ_Q^min(t)). 
The Euclidean norm of a vector v is denoted by v. The Frobenius norm of a matrix S is defined as S_F =tr{SS^⊺} where tr{.} is the trace of a matrix. Function blkdiag{Q_1,…,Q_m} constructs a larger matrix with diagonal blocks consist of matrices Q_i. Matrix I_n is the identity matrix of dimension n, vector 1_n denotes a vector of dimension n with all entries equal to 1, vector 𝐞_i is the standard basis for ℝ^n in the i^th direction and ⊗ indicates the Kronecker product. The set of positive (negative) semi-definite ℝ^n × n matrices is denote by ℝ_+^n × n (ℝ_-^n × n) and ∏ indicates the Cartesian product of sets.

We use the notation ℐ_t_f^δ to denote a subset of [t_0,t_f] defined as ℐ_t_f^δ = [t_f-δ,t_f] ⊆ [t_0,t_f] where δ is arbitrary and 0 < δ≤ t_f-t_0.




§ CHARACTERIZATION OF CLOSED-LOOP NASH STRATEGIES IN AAO LQD GAMES 

It is well known <cit.> that the closed-loop Nash strategies for the game described by (<ref>) and (<ref>) are of the form 

    u_i^* = -R_i^-1 B_i^⊺ S_i x

for i = 1, 2, ..., M, where S_i's satisfy the following M-coupled differential Riccati equations:

    Ṡ_̇i̇ + S_i A + A^⊺ S_i + Q_i + S_i H_i S_i 
    
    - ∑_j=1^M (S_i H_j S_j + S_j H_j S_i ) = 0,

with boundary conditions S_i(t_f) = S_if, and H_i = B_i R_i^-1 B_i^⊺. The resulting system trajectory will satisfy

    ẋ = Ax

where

    A≜ A -  ∑_j=1^M H_j S_j.

The above characterization (and all the subsequent analysis) related to the AAO games can be easily extended if the input cross-coupling terms were presented in the cost functions (<ref>).



 §.§ Definiteness of AAO Solutions

For the standard LQD game where S_if≥ 0 and Q_i ≥ 0 for i = 1, 2, ..., M, it is well known <cit.> that all matrices satisfying (<ref>) will be positive semidefinite.  That is, S_i(t) ≥ 0 for t ∈ [t_0,t_f] and for i = 1, 2, ..., M. Because S_1f<0 and Q_1<0 in the AAO games this result is no longer valid for these games.  The following theorem provides the equivalent result for the AAO LQD formulation.

 
For the AAO game, let {S_i(t), i=1,⋯, M} satisfy (<ref>) over any interval ℐ_t_f^δ⊆ [t_0,t_f], then for all t ∈ℐ_t_f^δ we have S_1(t) < 0 and S_i(t) ≥ 0 for i = 2, 3, ..., M.


Let λ_S_1^max(t) and v(t) be the maximum eigenvalue and corresponding unit eigenvector of S_1(t). The matrix S_1(t) is piecewise continuously differentiable and symmetric for t ∈ℐ_t_f^δ but not necessarily analytic. 
Thus, its eigenvectors (or eigenspaces) are not necessarily continuous (therefore not differentiable) [An example of such a matrix is presented in [Kato , p. 111]]. Continuity (differentiability) of the eigenvectors of S_1(t) requires S_1(t) to be holomorphic (analytic) (see <cit.>, Theorem 1.10). However, in our case we only have continuity of S_1(t) and thus we cannot differentiate v(t).
Instead, we can show [see <cit.>, Theorem 3.6.1] that λ_S_1^max(t) is not only continuous but also differentiable almost everywhere, and at any point that it is differentiable its derivative satisfies

    d/dtλ_S_1^max(t) =    v^⊺(t) Ṡ_̇1̇ v(t) 
    
    =    -v^⊺(t) ( S_1 A + A^⊺ S_1 + S_1 H_1 S_1 ) v(t) 
        + ∑_j=1^M ( v^⊺(t) S_1 H_j S_j v(t) + v^⊺(t) S_j H_j S_1 v(t) ) 
        - v^⊺(t) Q_1 v(t)

which can be simplified as

    d/dtλ_S_1^max(t) = λ_S_1^max(t) v^⊺(t) [ - A - A^⊺ - λ_S_1^max(t) H_1 
    
    + ∑_j=1^M ( H_j S_j + S_j H_j ) ] v(t) - v^⊺(t) Q_1 v(t).

Now for sufficiently small λ_S_1^max(t) we have

    d/dtλ_S_1^max(t) ≈  - v^⊺(t) Q_1 v(t) > 0

since Q_1 < 0. Given that  S_1(t_f)=S_1f < 0, we know λ_S_1^max(t_f) < 0 and hence by (<ref>) and the continuity of λ_S_1^max(t), the maximal eigenvalue λ_S_1^max(t) < 0 for all t ∈ℐ_t_f^δ. 
This proves that λ_S_1^max(t) starts from a negative value at t=t_f and stays negative as it evolves backward in time. Noting that λ_S_1^max(t) is the maximum eigenvalue of S_1(t), this proves that S_1(t) < 0 for all t ∈ℐ_t_f^δ. 
Now, for i = 2, 3..., M, let A be as defined in (<ref>) then (<ref>) can be written as

    Ṡ_̇i̇ + S_i A + A^⊺ S_i + Q_i + S_i H_i S_i = 0

with S_i(t_f) = S_if. Let Ψ(t,τ) be the state transition matrix of -A^⊺(t). It is known that for t, τ∈ℐ_t_f^δ,

    ∂Ψ(t,τ)/∂ t = -A^⊺(t) Ψ(t,τ),   Ψ(τ,τ) = I_n;

Then S_i(t) will satisfy

    S_i(t) = Ψ(t,t_f) S_i(t_f) Ψ^⊺(t,t_f) 
    
    + ∫_t^t_fΨ(t,τ) [ Q_i + S_i H_i S_i ] Ψ^⊺(t,τ) dτ.

Now, since S_i(t_f) ≥ 0,   Q_i ≥ 0 and R_i >0 for i = 2, 3..., M, it follows from (<ref>) that for all t ∈ℐ_t_f^δ we have S_i(t) ≥ 0 for i = 2, 3, ..., M. This completes the proof.




 §.§ Existence of AAO Solutions

Sufficient conditions for existence of S_i(t) matrices satisfying (<ref>) have been derived in <cit.> and <cit.> only for an LQD game consisting of two players and with all positive definite weight matrices (i.e. S_1f>0, S_2f>0, Q_1>0 and Q_2>0).  Clearly, in the AAO formulation these conditions do not apply since there is one player with negative definite weight matrices (S_1f<0 and Q_1<0). The next theorem provides sufficient conditions for existence of set of S_i(t) matrices satisfying (<ref>) for an M-player AAO game. We first state the following two Lemmas that are needed in the proof of theorem <ref>.


	Let Y(t) be a matrix that satisfies
	
    Ẏ(t) ≤ - Y(t) A - A^⊺ Y(t),    Y(t_f) = 0

	over the interval ℐ_t_f^δ⊆ [t_0,t_f]. Then it follows that Y(t) ≥ 0, for all t ∈ℐ_t_f^δ.



   Define Z(t,τ) = Φ^⊺ (t,τ) Y(t) Φ(t,τ) while Φ(t,τ) for all t, τ∈ℐ_t_f^δ is defined as follows
	
    ∂Φ(t,τ)/∂ t = A Φ(t,τ),   Φ(τ,τ) = I_n.

	Since Y(t_f) = 0 and Φ(t,τ) is bounded due to A being bounded, then Z(t_f,τ) = 0 for all τ∈ℐ_t_f^δ. Also,
	
    ∂ Z(t,τ)/∂ t = Φ^⊺ (t,τ) [ A^⊺ Y + Ẏ + Y A] Φ(t,τ) ≤ 0

	where Y is a solution of (<ref>). Now if we define g(t,τ,v) = v^⊺ Z(t,τ) v for all t, τ∈ℐ_t_f^δ and v ∈ℝ^n then ∂/∂ t g(t,τ,v) ≤ 0 for all t ∈ℐ_t_f^δ. Therefore the mean value theorem yields
	
    0 ≤ g(t_1,τ,v) - g(t_2,τ,v) = v^⊺ [ Z(t_1,τ) - Z(t_2,τ) ] v

	for all t_1, t_2 ∈ℐ_t_f^δ where t_1 ≤ t_2, and as a result  Z(t_1,τ) ≥ Z(t_2,τ). We conclude that Z(t,τ) ≥ Z(t_f,τ) = 0 for all t, τ∈ℐ_t_f^δ. Finally choosing τ = t yields Y(t) ≥ 0 for all t ∈ℐ_t_f^δ. 


Now, for a bounded symmetric matrix Q, define the following map from ∏_1^M ℝ^n × n to ℝ^n × n as follows

    ℛ_Q(W_1, ... , W_M) ≜ Q + W_1 H_1 W_1 - ∑_i=2^M W_i H_i W_i 
    
    + ( -W_1 + ∑_i=2^M W_i )  ∑_j=1^M H_j W_j + ∑_j=1^M W_j H_j ( -W_1 + ∑_i=2^M W_i )

and let L_Q(t) be the unique solution of following terminal value linear differential equation

    L̇_Q(t) =  - L_Q(t) A - A^⊺ L_Q(t) - (Q - Q_1 + ∑_i=2^M Q_i )

with boundary condition L_Q(t_f) = -S_1f + ∑_i=2^M S_if. The following lemma provides the condition under which solutions S_i(t) of (<ref>) stay in the following bounded set:

    ℰ≜{ S ∈ℝ^n × n | S=S^⊺,  S_F ≤l_q}
 
where l_q = sup_t ∈ [t_0,t_f]L_Q(t)_F. We also define the space χ≜ C(ℐ_t_f^δ, ∏_1^M ℰ). Space χ is complete under the norm[Since it is a closed subset of C( ℐ_t_f^δ, ∏_1^M ℝ^n × n) which is a Banach space under the same norm.]

    (S_1,…,S_M)_χ≜sup_t ∈0.9ℐ_t_f^δ∑_j=1^M S_j_F.


This lemma enables us to establish Theorem <ref> on the existence of a set of solutions S_i(t) of (<ref>).


For the AAO game,

every solution set {S_i(t), i=1,2,...,M} satisfying (<ref>) over any interval ℐ_t_f^δ⊆ [t_0,t_f] stays within ℰ for all t ∈ℐ_t_f^δ⊆ [t_0,t_f] provided that ℛ_Q maps ℝ_-^n × n× (∏_2^M ℝ_+^n × n) into ℝ_+^n × n.



Since L_Q(t) satisfies the linear differential equation (<ref>) and matrices A, Q and Q_i are bounded, then (by Gronwall's Lemma <cit.> and Theorem 1.1.5 in <cit.>) L_Q(t) exists for all t ∈ [t_0, t_f]. Therefore, l_q exists and the set ℰ in (<ref>) is well-defined and bounded.
Next, we prove that 

    0 < -S_1(t) + ∑_i=2^M S_i(t) ≤ L_Q(t)

The left inequality of (<ref>) follows from Theorem <ref>. Now for the right inequality, define

    Y(t) ≜ L_Q(t) + S_1(t) - ∑_i=2^M S_i(t)

then after considerable algebraic manipulations (<ref>), (<ref>) and (<ref>) yield

    Ẏ= - Y A - A^⊺ Y - ℛ_Q(S_1, ... , S_M)

with boundary condition Y(t_f) = 0. Thus 

    Ẏ≤-YA-A^⊺Y
 
over ℐ_t_f^δ⊆ [t_0,t_f] provided that ℛ_Q(S_1, ... , S_M) ≥ 0 which follows by the assumption and Theorem <ref>.
Therefore, according to Lemma <ref> we conclude Y(t) ≥ 0 for all t ∈ℐ_t_f^δ. Therefore, inequality (<ref>) is proved for all t ∈ℐ_t_f^δ. Since according to Theorem <ref>, -S_1(t) > 0 and S_i(t) ≥ 0 for i=2,3,…,M, it follows that for i=1,2,…,M and for all t ∈ℐ_t_f^δ

    S_i(t)_F =    tr{S_i(t) S_i^⊺(t)}
    ≤    tr{L_Q(t) L_Q^⊺(t)}
    ≤   l_q

This completes the proof.



For the AAO game, there exists a unique solution set {S_i(t), i=1,2,...,M} satisfying (<ref>) for all t ∈ [t_0,t_f]
provided that ℛ_Q maps ℝ_-^n × n× (∏_2^M ℝ_+^n × n) into ℝ_+^n × n.



The Riccati differential equations in (<ref>) are equivalent to the following integral equations for i=1,2,…,M,

    S_i(t) = S_if + ∫_t^t_f f_i(τ,S_1,…,S_M) dτ

where

    f_i≜ S_i A + A^⊺ S_i + Q_i - S_i H_i S_i - ∑_j=1, j ≠ i^M (S_i H_j S_j + S_j H_j S_i ).

Functions f_i are locally Lipschitz for i=1,2,…,M because

    Δ f_i_F =   f_i(t,S_1,…,S_M) - f_i(t,S_1^*,…,S_M^*)_F 
    
    		=   ‖(S_i - S_i^*) A + A^⊺ (S_i - S_i^*) 
        - S_i H_i (S_i - S_i^*)-  (S_i - S_i^*) H_i S_i^* 
       - ∑_j=1, j ≠ i^M ((S_i - S_i^*) H_j S_j + S_j^* H_j (S_i - S_i^*)
        + S_i^* H_j (S_j - S_j^*) + (S_j - S_j^*) H_j S_i )‖_F 
    ≤   S_i - S_i^*_F { 2 A_F  
       + h∑_j=1^M (S_j_F + S_j^*_F ) }
       + ∑_j=1, j ≠ i^M S_j - S_j^*_F {h( S_i^*_F + S_i_F ) }
    ≤    K_c ∑_j=1^M S_j - S_j^*_F

where

    K_c = 2 A_F  + h∑_j=1^M (S_j_F + S_j^*_F )

and h = max_1 ≤ i ≤ MH_i_F. 
It follows that, K_c is bounded for all S_i, S_i^* ∈ℰ as follows

    sup_t  ∈0.9ℐ_t_f^δ K_c ≤ 2 sup_ t ∈ [t_0,t_f]A_F  + 2 M h l_q≜K_c

for some δ > 0 to be determined later and denoted as δ according to the following process.

Process: Noting from (<ref>) that the boundary condition S_if∈ℰ for i=1,2…,M.
Next, operator 𝒯χ→χ is defined as follows:

    𝒯(S_1,…,S_M)_(t)≜
    {( S_1f + ∫_t^t_f f_1 dτ)   ,…,  ( S_Mf + ∫_t^t_f f_M dτ)}.

Operator 𝒯 is a contraction mapping for δ = δ = 1/2M K_c, since

    Δ𝒯_χ =   𝒯(S_1,…,S_M)_(t) - 𝒯(S_1^*,…,S_M^*)_(t)_χ
    
    		=   {∫_t^t_fΔ f_1 dτ  ,…,  ∫_t^t_fΔ f_M dτ}_χ
    
    					  =   sup_ t ∈0.9ℐ_t_f^δ∑_i=1^M ∫_t^t_fΔ f_i dτ_F 
    ≤   sup_t ∈0.9ℐ_t_f^δ∑_i=1^M ∫_t^t_fΔ f_i _F dτ
    ≤   δ M sup_t ∈0.9ℐ_t_f^δΔ f_i _F 
    ≤   δ M K_c (S_1,…,S_M) - (S_1^*,…,S_M^*)_χ
    
                          =   1/2(S_1,…,S_M) - (S_1^*,…,S_M^*)_χ

for all (S_1,…,S_M), (S_1^*,…,S_M^*) ∈χ.
By the contraction mapping theorem <cit.>, there exists a unique solution set {S_i(t), i=1,2,...,M} of (<ref>) over the interval [t_f-δ,t_f].
Furthermore, by the assumption and Theorem <ref> it follows that ℛ_Q(S_1, ... , S_M)  ≥ 0 over ℐ_t_f^δ, and by applying Lemma <ref> on S_i(t) over ℐ_t_f^δ , we conclude that S_i(t_f-δ) ∈ℰ for i=1,2,...,M. 

Now, we extend the local existence property established using the above process to the entire interval [t_0, t_f] as follows.
We repeat the same process for the Riccati equations in (<ref>) over the interval ℐ_t_f-δ^δ = [t_f - 2δ, t_f-δ] with S_i(t_f-δ) ∈ℰ as the new boundary condition. By recalling that the Lipschitz condition (<ref>) holds and defining a contraction mapping as in (<ref>) over a new space χ defined over the new interval ℐ_t_f-δ^δ =[t_f-2δ,t_f-δ], it can be similarly shown that S_i(t) exist over this interval and that based on Lemma <ref> S_i(t_f-2δ) ∈ℰ.
Finally, this process can be repeated over successive intervals ℐ_t_f-kδ^δ =[t_f-kδ,t_f-(k-1)δ] for k=1,2,…. The initial time t_0 will be reached since at every iteration δ = 1/2M K_c > 0 and K_c is a uniform bound on ℰ as shown in (<ref>). This ends the proof.


For the existence of AAO solutions note that:


  * The purpose of the symmetric matrix Q appearing in (<ref>) and Theorem <ref> is to establish the upper bound L_Q(t) described in (<ref>).


  * It can be shown that the condition 
ℛ_Q (ℝ_-^n × n× (∏_2^M ℝ_+^n × n) ) ⊂ℝ_+^n × n
is fulfilled for several sub-classes of AAO games, for which explicit conditions on existence of a solution can be determined in terms of weighting matrices Q_i and S_if. One such subclass is illustrated in Corollary <ref>.



Before providing the explicit conditions of existence, we provide the following lemma which is used in the proof of the next corollary and Theorem <ref>.


	For the AAO game, if Q_1 + ∑_i=2^M Q_i > 0 and S_1f + ∑_i=2^M S_if > 0, then for every solution set {S_i(t), i=1,2,...,M} satisfying (<ref>) over any interval ℐ_t_f^δ⊆ [t_0,t_f], it follows that P(t) >0, for all t ∈ℐ_t_f^δ.



	For every solution set {S_i(t), i=1,2,...,M} that satisfies (<ref>), let 
    P(t)= S_1(t) + ∑_i=2^M S_i(t)
 then it would satisfy the following

    Ṗ + P A + A^⊺ P +  Q_1 + ∑_i=2^M  Q_i +  S_1 H_1 S_1 + ∑_i=2^M S_i H_i S_i = 0;

with boundary condition P(t_f) =  S_1f + ∑_i=2^M S_if.
Then P(t) will satisfy

    P(t) = Ψ(t,t_f) P(t_f) Ψ^⊺(t,t_f) + ∫_t^t_fΨ(t,τ) [  Q_1 
    
    + ∑_i=2^M  Q_i +  S_1 H_1 S_1 + ∑_i=2^M S_i H_i S_i ] Ψ^⊺(t,τ) dτ.

where Ψ(t,τ) is as in (<ref>). Since matrices R_i >0 for i = 1,2,…,M, this yields H_i ≥ 0, and from the hypothesis of the lemma and (<ref>), it follows that P(t) > 0 for all t ∈ℐ_t_f^δ. This completes the proof.



Consider an AAO game with diagonal matrices A, B_i, S_if, Q_i and R_i for i=1,2,…,M. If Q_1 + ∑_i=2^M Q_i > 0, S_1f + ∑_i=2^M S_if > 0, and H_1 ≤ H_i for i=2,3,…,M, then ℛ_Q maps ℝ_-^n × n× (∏_2^M ℝ_+^n × n) into ℝ_+^n × n for any Q ≥ 0 and thus a unique solution set {S_i(t), i=1,2,...,M} of (<ref>) exists for all t ∈ [t_0,t_f].


See Appendix <ref>.




 §.§ Boundedness of the System Trajectory

The next theorem provides a sufficient condition for the system trajectory to be exponentially bounded. Specifically, if the final time is large enough, then the state vector of the system is guaranteed to end up in a small hyper-ball. Essentially, this theorem provides conditions that guarantee that opposing player cannot accomplish its goal of de-stabilizing the system. 



For an AAO game with a solution set {S_i(t), i=1,⋯, M} satisfying (<ref>), if Q_1 + ∑_i=2^M Q_i > 0 and S_1f + ∑_i=2^M S_if > 0, then the state trajectory in (<ref>) will be exponentially bounded. In particular, for any small r>0, it follows x(t_f)≤ r provided that

    t_f-t_0 ≥λ_P/λ_Q{ 2
    ln(x_0/r)
    + ln(λ_P/λ_P)
    }.




Let

    V (t)= x^⊺(t) P(t) x(t),

where the state vector x(t) is defined in (<ref>) and P(t) is as in (<ref>). Matrix P(t) is positive definite for all t based on Lemma <ref>. Then, using (<ref>) and (<ref>) it follows that

    V̇(t) 
    
    = - x^⊺( ∑_i=1^M  ( Q_i + S_i H_i S_i ) ) x

Since, Q_1 + ∑_i=2^M Q_i > 0 and H_i ≥ 0 for i=1,2,…,M it follows that V̇(t) < 0 which yields a decaying dynamics for the system. Now if we define Q = ∑_i=1^M  Q_i, then it follows that

    V̇≤ - x^⊺Q x ≤  - λ_Q/λ_P
     V

Then one can conclude that

    V(t) ≤  V(t_0) exp{-λ_Q/λ_P(t-t_0)}

which is an exponential decaying bound for the system. Also, we can conclude that

    (x(t)/x_0)^2 ≤λ_P/λ_Pexp{-λ_Q/λ_P (t-t_0)}.

Finally, by rearranging the terms, in order to achieve x(t_f)≤ r, t_f-t_0 should be greater than the expression provided in the theorem. This ends the proof.





§ TWO OPTIONS FOR THE GROUP OF PLAYERS 

The AAO game offers several possible options for the M-1 players in the group.  In this paper we consider only two as illustrated in Figure <ref>.  The first option is for the players in the group to ignore the fact that they have similar cost functions and decide to design Nash strategies among themselves as well as the opposing player <cit.>.  The second option, which intuitively appears to be the better choice, is for the players in the group to form a team and cooperate among themselves in designing a collective Nash strategy against the remaining player <cit.>.  However, being restricted to operate within the framework of the team, although beneficial to the entire group, may or may not be beneficial to each player, and as a result may be beneficial to the opposing player. We will refer to the first option as the Nash solution and to the second as the Team-Nash solution. The Nash strategies of the first option are determined as described in (<ref>) and (<ref>).  The Team-Nash strategies of the second option are determined by first forming a team cost function as a convex combination of the individual cost functions of the M-1 players in the group.  That is 

    J_T=∑_i=1^M-1α_i J_i+1

where α_i>0, ∑_i=1^M-1α_i=1 and J_i for i = 2, ..., M as they are defined in (<ref>).

The weight α_i can be viewed as the relative contribution of Player i+1 to the team.
So the cost function for the team of players becomes

    J_T = 1/2 x^⊺(t_f) S_T_f x(t_f) + 1/2∫_t_0^t_f[x^⊺ Q_T x
    + u_T^⊺ R_T u_T ]dt

where 

    S_T_f   = ∑_i=1^M-1α_i S_(i+1)f,
    
    Q_T    = ∑_i=1^M-1α_i Q_i+1, 
    
    R_T    = blkdiag {α_1 R_2,  α_2 R_3, …,  α_M-1 R_M}.

The opposing player's cost function stays the same as J_1.
Also, the control inputs of the players in the group are combined as one vector but it will be reallocated to each player later at the implementation stage.
Consequently, the system dynamics of (<ref>) can be reorganized as follows

    ẋ = A x + B_1 u_1 + B_T u_T

where u_T = [u_2^⊺, u_3^⊺, ... , u_M^⊺]^⊺  is the team control vector. 
	
The system dynamics (<ref>) and cost functions J_T and J_1 form a 2-player LQD game.
The closed-loop Nash strategies can be obtained from (<ref>) as follows

    u_1^*    = -R_1^-1 B_1^⊺ S_1 x 
    
    u_T^*    = -R_T^-1 B_T^⊺ S_T x

where the matrices S_T and S_1 are the solutions to the following coupled differential Riccati equations

    Ṡ_̇1̇ + S_1 A + A^⊺ S_1 + Q_1 - S_1 H_1 S_1 
    
     - S_1 H_T S_T - S_T H_T S_1 = 0,


    Ṡ_̇Ṫ + S_T A + A^⊺ S_T + Q_T - S_T H_T S_T  
    
    - S_T H_1 S_1 - S_1 H_1 S_T = 0,

where H_T = B_T R_T^-1 B_T^⊺ and with boundary conditions S_1(t_f) = S_1f and S_T(t_f) = S_T_f.
Note that assigning different values of α_i will yield different teams with different strengths and weaknesses, and correspondingly different Nash solutions. 
Also, note that even though this game is solved as a 2-player LQD game, upon implementation the controls are reallocated to each player and the game remains as a multi-player game.




§ ILLUSTRATIVE EXAMPLE 

To illustrate the AAO framework, we consider a simple 3-against-1 pursuit evasion game on a planar surface.  The evader, player 1, is trying to escape from three pursuers (players 2, 3 and 4) by maximizing its weighted distance from them while the pursuers are trying to capture the evader by minimizing these distances.  We consider a capture radius of 0.1, meaning that if the evader is within a distance of 0.1 from any of the pursuers it is considered as captured.  The dynamics of the system follows (<ref>). The state vector x ∈ℝ^6 is the combined three displacement vectors of dimension 2 each, which connects the evader E to pursuers P1, P2 and P3, respectively. To control the velocities of the players on the plane, the open-loop dynamic matrix is assumed to be A=0. The input matrix for the evader is B_1 = 1_3 ⊗ I_2 and for the pursuers are B_i = -  𝐞_i-1⊗ I_2 for i=2,3,4. Also, the combined input matrix of the pursuers as a team can be written as B_T = -I_3 ⊗ I_2. 
We consider a final time t_f=10 (which is relatively long for the given system dynamics). Each player tries to minimize the corresponding cost function as stated in (<ref>). We assume that the evader's parameters in its cost function are as follows

    S_1f = -18 I_3 ⊗ I_2,    
    	Q_1 = -6 I_3 ⊗ I_2,   
    	R_1 = I_2

and the pursuers' parameters in their cost functions are as follows

    S_2f = I_3 ⊗ I_2,    
    Q_2 = 0.5 I_3 ⊗ I_2,   
    R_2 = 150 I_2,


    S_3f = I_3 ⊗ I_2,    
    Q_3 = 0.5 I_3 ⊗ I_2,   
    R_3 = 150 I_2,


    S_4f = 16.25 I_3 ⊗ I_2,   
    Q_4 = 5.25 I_3 ⊗ I_2,  
    R_4 = 150 I_2.








Additionally, for the Team-Nash strategies we arbitrarily chose [α_1  α_2  α_3] = [0.3  0.3   0.3] representing equal contributions by all pursuers. The initial positions of the players are such that the initial state vector is x_0 = [   2  13   7   9 -10  14 ]^⊺.
The resulting state variables (which are the combined three displacement vectors that connect the three pursuers to the evader) for the Nash and Team-Nash strategies are plotted vs time in Figures <ref> and <ref> respectively. The x-y coordinates of the players' movement for both strategies are shown in Figures <ref> and <ref> respectively. Finally, the distances of pursuers to the evader for the Nash and Team-Nash strategies are plotted vs time in Figures <ref> and <ref> respectively.

For the Nash strategies in Figure <ref>, the conditions of Theorem <ref> are satisfied since

    Q_1 + ∑_j=2^4 Q_j =  (-6 + 0.5 + 0.5 + 5.25) I_3 ⊗ I_2  > 0


    S_1f + ∑_j=2^4 S_jf = (-18 + 1 + 1 + 16.25) I_3 ⊗ I_2 > 0


Consequently, according to Theorem <ref> the exponential boundedness of the system is guaranteed regardless of the initial position of the players. For the given t_f the pursuers are able to capture the evader before final time of the game.
For the Team-Nash strategies in Figure <ref>, the conditions of Theorem <ref> are not satisfied since

    Q_1 + Q_T =  (-6 + 2.08) I_3 ⊗ I_2  < 0


    S_1f + S_T_f = (-18 + 6.08) I_3 ⊗ I_2 < 0.

Consequently, the exponential boundedness of system is not guaranteed. In this case as can be seen in Figures <ref>, the evader was able to keep the state vector of the system away from the origin and as a result escape. 
In terms of accomplishing their objectives, the pursuers appear to have done a better job in using the Nash strategies compared to the Team-Nash strategies. As mentioned earlier this may be due to the fact that in the Nash strategies the pursuers are completely free to act independently while in the Team-Nash they are constraint to act cooperatively within the team structure. 



Table <ref> shows the distances between the pursuers and the evader for different values of t_f increasing from 2 to 14 and for the two strategy options discussed. As it is clear from the table for the Nash strategy, the evader could have been captured if the final time were t_f=8 instead of t_f=10 since its distance from all pursuers are within the capture radius 0.1 at t_f=8. On the other hand for the Team-Nash strategy, it is clear that even for a final time t_f =14 the pursuers are still further away from the evader and none of them is within the capture radius.
However, if t_f were extended to 18, then the simulation would show the distance between the pursuer (P1) and the evader at this final time is 0.08 which is within the capture radius and thus the evader will be captured.



§ CONCLUSION 

The current literature on linear quadratic non-zero-sum differential games has emphasized a structure in which all players are constrained to have non-negative definite state weight matrices in their cost functions.  This structure does not consider games where one or more players have cost functions that do not satisfy this constraint.  In this paper, we considered games where one of the players has an cost function with negative definite state weight matrices making this player in direct conflict with the remaining players.  These types of games are very useful in analyzing conflict situations in which one player wants to maximize the deviation of the state from the origin (i.e. de-stabilize the system) while the others are trying to regulate the state in the standard sense.  We referred to these types of games as All-Against-One.  In this paper, we derived new conditions that guarantee existence, definiteness and uniqueness of the closed-loop Nash strategies as well as boundedness of the resulting state trajectory. We also considered the Nash and Team-Nash strategies as possible options for the group of the players.  As an illustrative example, we simulated a three-pursuer one-evader pursuit evasion game and determined both close-loop Nash and Team-Nash strategies for the players and resulting trajectories. We also applied our results to derive conditions for which the evader will be captured under each case. In the case of the Nash strategies, we also showed that as the final time increased the distances between the pursuers and the evader became smaller, making it more difficult for the evader to escape.

IEEEtran








§ PROOF OF COROLLARY <REF> 

First, we prove that ℛ_Q maps ℝ_-^n × n× (∏_2^M ℝ_+^n × n) into ℝ_+^n × n or equivalently ℛ_Q(W_1, ... , W_M) is positive semi-definite for every collection {W_i(t), i=1,2,...,M} such that W_1 ≤ 0 and W_i ≥ 0 for i=2,…,M, and for any Q ≥ 0.
Suppose that all matrices are diagonal, thus, they commute and we can simplify and bound ℛ_Q(W_1, ... , W_M) from below as follows

    ℛ_Q =     Q+ H_1 W_1^2 - ∑_i=2^M H_i W_i^2 - 2 ∑_j=1^M H_j W_1 W_j 
        + 2 ∑_i=2^M ∑_j=1^M H_j W_i W_j 
    
       =    Q- H_1 W_1^2 - ∑_i=2^M H_i W_i^2  + 2 ∑_j=2^M (H_1 - H_j) W_1 W_j 
        + 2 ∑_i=2^M ∑_j=2^M H_j W_i W_j 
    
       =    Q- H_1 W_1^2 + ∑_i=2^M H_i W_i^2  + 2 ∑_j=2^M (H_1 - H_j) W_1 W_j 
        + 2 ∑_i,j=2
     i ≠ j^M H_j W_i W_j 
    ≥    - H_1 W_1^2 + ∑_i=2^M H_i W_i^2  + 2 ∑_i,j=2
     i ≠ j^M H_j W_i W_j
    ≥    H_1 ( - W_1^2 + ∑_i=2^M W_i^2 + ∑_i,j=2
     i ≠ j^M 2 W_i W_j) 
    
       =     H_1 ( - W_1^2 + (∑_i=2^M W_i )^2 ) 
    
       =     H_1 ( - W_1 + ∑_i=2^M W_i ) ( W_1 + ∑_i=2^M W_i )

First, Inequalities (<ref>) and (<ref>) are due to H_1 ≤ H_i. Second, all given matrices are assumed to be diagonal which result in all S_i (solutions of (<ref>)) to be diagonal and has the same definiteness as W_i by Theorem <ref>.
Third, H_1 ≥ 0, Theorem <ref> and Lemma <ref> together yield that S_1 + ∑_i=2^M S_i ≥ 0 and therefore by (<ref>) it follows that ℛ_Q(S_1,…,S_M) ≥ 0.
Finally, 

similar argument as in Theorem <ref> results in existence of S_i for all t ∈ [t_0,t_f].

[
    < g r a p h i c s >
]Shahriar Talebi
(S'17) received his B.Sc. degree in Electrical Engineering from Sharif University of Technology, Iran, in 2013, M.Sc. degree in Electrical Engineering from
University of Central Florida, Orlando, FL, in 2017, both in the area of control theory. He is currently working towards a PhD degree. His research interest includes Cooperative/Non-cooperative Game Theory, Networked Control, Optimal Control, Optimization and Inverse Problems.


[
    < g r a p h i c s >
]Marwan A. Simaan
(S'69-M'72-SM'79-F'88-LF'12) received the Ph.D. degree in electrical engineering from the University of Illinois at Urbana-Champaign in 1972. He is currently the Florida 21st Century Chair and Distinguished Professor of Electrical Engineering and Computer Science with the University of Central Florida. His research covers a broad spectrum of topics in game theory, control, optimization, and signal processing. He has authored or co-authored 5 books (one co-authored and 4 edited/co-edited), 140 archival journal papers and book chapters, 235 papers in conference proceedings, and 24 industry technical reports. He is a member of the U.S. National Academy of Engineering. He is a fellow of the American Society for Engineering Education, the American Association for the Advancement of Science, the American Institute for Medical and Biological Engineering, and the National Academy of Inventors. He has served on numerous professional committees and editorial boards, including the AACC Awards Committee, the IEEE Fellow Committee, the IEEE Education Medal Committee, the IEEE Proceedings and IEEE Access Editorial Boards, the AAAS Engineering Section Steering Group, and Others. In 1995, he was named a Distinguished Alumnus of the Department of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign. In 2008, he received the University of Illinois, College of Engineering Award for Distinguished Service in Engineering. He is a registered Professional Engineer with the Commonwealth of Pennsylvania.


[
    < g r a p h i c s >
]Zhihua Qu
(M'90-SM'93-F'09) received the Ph.D. degree in electrical engineering from the Georgia Institute of Technology, Atlanta, in June 1990. Since then, he has been with the University of Central Florida (UCF), Orlando. Currently, he is the SAIC Endowed Professor in College of Engineering and Computer Science, a Pegasus Professor and the Chair of Electrical and Computer Engineering, and the Director of FEEDER Center. His areas of expertise are nonlinear systems and control, with applications to autonomous systems and energy/power systems. His recent work focuses upon cooperative control, distributed optimization, and plug-and-play control of networked systems. 


