Mirko Fiacchini
email: mirko.fiacchini@gipsa-lab.fr

Marc Jungers
email: marc.jungers@univ-lorraine.fr

Necessary and sufficient condition for stabilizability of discrete-time linear switched systems: a set-theory approach ⋆

Keywords: Switched linear systems, set-theory, stabilizability, invariance

In this paper, the stabilizability of discrete-time linear switched systems is considered. Several sufficient conditions for stabilizability are proposed in the literature, but no necessary and sufficient. The main contributions are the necessary and sufficient conditions for stabilizability based on set-theory and the characterization of a universal class of Lyapunov functions. An algorithm for computing the Lyapunov functions and a procedure to design the stabilizing switching control law are provided, based on such conditions. Moreover a sufficient condition for non-stabilizability for switched system is presented. Several academic examples are given to illustrate the efficiency of the proposed results. In particular, a Lyapunov function is obtained for a system for which the Lyapunov-Metzler condition for stabilizability does not hold.

Introduction

Switched systems are systems for which the current timevarying dynamics, specified by the so-called switching law, belongs to a finite set of modes (see [START_REF] Liberzon | Switching in Systems and Control[END_REF]). In the last decades, a large literature has been devoted to study switched systems for practical reasons, as they model complex systems like embedded ones, and for theoretical ones, since their behavior and stability properties are not intuitive nor trivial, [START_REF] Liberzon | Basic problems in stability and design of switched systems[END_REF]. Depending on the assumptions on the switching law, different frameworks have risen. The switching law is often considered as a perturbation or as a part of the control inputs.

When the switching law is a perturbation, that is an arbitrary function, sufficient and conservative conditions to ensure the stability have been provided (see for overviews [START_REF] Lin | Stability and stabilizability of switched linear systems: a survey of recent results[END_REF][START_REF]Handbook of Hybrid Systems Control: Theory, Tools, Applications[END_REF][START_REF] Sun | Stability Theory of Switched Dynamical Systems[END_REF]). Several refinements have been proposed to obtain necessary and sufficient conditions for stability of switched systems. Among these conditions, one can cite the joint spectral radius approach [START_REF] Bauer | A necessary and sufficient condition for robust asymptotic stability of time-variant discrete systems[END_REF][START_REF] Lin | Persistent disturbance attenuation properties for networked control systems[END_REF][START_REF] Jungers | The Joint Spectral Radius: Theory and Applications[END_REF]; the polyhedral Lyapunov functions [START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encounterd in control theory[END_REF] and the path-dependent switched Lyapunov ones [START_REF] Lee | Uniformly stabilizing sets of switching sequences for switched linear systems[END_REF]. Specific necessary and sufficient conditions exist ⋆ Corresponding author M. Fiacchini. for two-dimensional systems [START_REF] Boscain | Stability of planar switched systems: the linear single input case[END_REF] or positive ones [START_REF] Gurvits | On the stability of switched positive linear systems[END_REF].

In case the switching law is a part of the control inputs, sufficient conditions for stabilizability have been provided, mainly by using a min-switching policy [START_REF] Liberzon | Switching in Systems and Control[END_REF]Chapter 3] introduced in [START_REF] Wicks | Construction of piecewise Lyapunov functions for stabilizing switched systems[END_REF], developed in [START_REF] Kruszewski | Converging algorithm for a class of BMI applied on statedependent stabilization of switched systems[END_REF] via BMI and leading to Lyapunov-Metzler inequalities [START_REF] Geromel | Stability and stabilization of discrete-time switched systems[END_REF]. Based on the setinduced Lyapunov functions introduced in [START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF], sufficient conditions for uniform ultimate boundedness have been proposed for uncertain switched linear systems in [START_REF] Lin | Synthesis of uniformly ultimate boundedness switching laws for discrete-time uncertain switched linear systems[END_REF]. Nevertheless to the best knowledge of the authors, necessary and sufficient conditions for the stabilizability and for the nonstabilizability of discrete-time switched linear systems do not exist in the literature.

The proposed approach is based on set-theory and invariance for control and analysis. A seminal work dealing with the characterization of invariance is [START_REF] Bertsekas | Infinite-time reachability of statespace regions by using feedback control[END_REF]. More recently, the works [START_REF] Gilbert | Linear systems with state and control constraints: The theory and application of maximal output admissible sets[END_REF][START_REF] Kolmanovsky | Theory and computation of disturbance invariant sets for discrete-time linear systems[END_REF][START_REF] Blanchini | Set invariance in control[END_REF] lay the basis of set-theoretic methods and invariance in control. The relation between contractivity and polyhedral Lyapunov functions is presented in [START_REF] Blanchini | Ultimate boundedness control for discrete-time uncertain systems via set-induced Lyapunov functions[END_REF]. In [START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encounterd in control theory[END_REF][START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF], it is proved that the existence of a contractive polytope is a necessary and sufficient condition for exponential stability and that polyhedral functions form a universal class of Lyapunov functions for linear parametric uncertain systems.

Preprint submitted to Automatica 20 September 2013

See [START_REF] Blanchini | Set-Theoretic Methods in Control[END_REF] for a detailed review on the topic.

This paper provides new necessary and sufficient conditions for stabilizability and sufficient ones for non-stabilizability of discrete-time linear switched systems. A family of nonconvex, homogeneous functions is proved to be a universal class of Lyapunov functions for switched linear systems. The key idea is to use the set-theory offering numerically sound algorithms to check the stabilizability (and providing the stabilizing switching law) or the non-stabilizability. The paper extends the results presented in the preliminary work [START_REF] Fiacchini | Necessary and sufficient condition for stabilizability of discrete-time linear switched systems: a set-theory approach[END_REF].

The outline of the paper is as follows. In Section 2, preliminaries and set-theory tools are presented. Section 3 is devoted to the new necessary and sufficient conditions for stabilizability. Section 4 provides the stabilizing switching control law. Section 5 presents sufficient conditions for nonstabilizability. Links with the Lyapunov-Metzler approach are discussed in Section 6. The results are illustrated by examples in Section 7, before concluding remarks in Section 8.

Notation:

Define N n = {x ∈ N : 1 ≤ x ≤ n} with n ∈ N. Given D, E ⊆ R n , α ∈ R and M ∈ R m×n , define D + E = {z = x + y ∈ R n : x ∈ D, y ∈ E}, the scalar multiple αD = {αx ∈ R n : x ∈ D} and MD = {Mx ∈ R m : x ∈ D}. Given a set D ⊆ R n , int(D)
is its interior and ∂ D its boundary. The set B n is the unit euclidean ball in R n . The i-th element of a finite set of matrices is denoted as A i , of a set of sets as Ω i .

Preliminaries

Consider the discrete-time switched system

x k+1 = A σ (k) x k , (1)
where x k ∈ R n is the state at time k ∈ N and σ : N → N q is the switching law that, at any instant, selects the transition matrix among the finite set {A i } i∈N q , with A i ∈ R n×n for all i ∈ N q . Given the initial state x 0 and a switching law σ (•), we denote with x σ N (x 0 ) the state of the system (1) at time N starting from x 0 by applying the switching law σ (•). In some cases σ can be a function of the state, for instance in the case of switching control law, as shown later.

Remark 1 Two main cases have to be discriminated depending on the assumptions on the switching law. If σ (•) is supposed to be an arbitrary function of time, that is acting as a perturbation, then the problem of asymptotic stability of the system under every possible switching law is usually considered. For this case necessary and sufficient conditions for stability exist. When σ (•) is considered as a manipulable signal, then the problem of asymptotic stabilizability (simply denoted as stabilizability in what follows) is addressed, that consists in the existence and the characterization of the switching laws that yield asymptotic stability if applied. This is the problem considered in the paper.

A concept widely employed in the context of set-theory and invariance is the C-set, see [START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF][START_REF] Blanchini | Set-Theoretic Methods in Control[END_REF]. A C-set is a compact, convex set with 0 ∈ int(Ω). We define an analogous concept useful for our purpose. For this, we first recall that a set Ω is a star-convex set if there exists x 0 ∈ Ω such that every convex combination of x and x 0 belongs to Ω for every x ∈ Ω.

Definition 1 A set Ω ⊆ R n is a C * -set if it
is compact, starconvex with respect to the origin and 0 ∈ int(Ω).

We define the analogous of the gauge function of a C * -set as

Ψ Ω (x) = min α≥0 {α ∈ R : x ∈ αΩ}, (2)
for the C * -set Ω ⊆ R n .
In what follows, we will refer to Ψ Ω (x) as the Minkowski function of Ω at x, with a slight abuse since it is usually defined for C-sets (or symmetric C-sets), [START_REF] Rockafellar | Convex Analysis[END_REF][START_REF] Schneider | Convex bodies: The Brunn-Minkowski theory[END_REF][START_REF] Blanchini | Set-Theoretic Methods in Control[END_REF]. Some basic properties of the C * -sets and their Minkowski functions are listed below. The proof is avoided, since they follow directly from the definition.

Property 1 Any C-set is a C * -set. Given a C * -set Ω ⊆ R n ,
we have that αΩ ⊆ Ω for all α ∈ [0, 1], and the Minkowski function Ψ Ω (•) is: homogeneous of degree one, i.e.

Ψ Ω (αx) = αΨ Ω (x) for all α ≥ 0 and x ∈ R n ; positive definite; defined on R n and radially unbounded.

The Minkowski functions induced by C-sets have been used in literature as Lyapunov functions candidates, see [START_REF] Blanchini | Ultimate boundedness control for discrete-time uncertain systems via set-induced Lyapunov functions[END_REF]. In particular, it has been proved that they provide a universal class of Lyapunov functions for linear parametric uncertain systems, [START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encounterd in control theory[END_REF][START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF], and switched systems with arbitrary switching, [START_REF] Lin | Stability and stabilizability of switched linear systems: a survey of recent results[END_REF]. In this paper we prove that the Minkowski functions induced by C * -sets form a universal class of Lyapunov function for switched systems with switching control law.

For this, we provide a definition of Lyapunov function for the particular context, in analogy with the definition given in [START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF] for linear parametric uncertain systems.

Definition 2 A positive definite continuous function V : R n → R is a global Lyapunov function for the system (1) if there exist a positive N ∈ N and a switching law σ (•), defined on R n , such that V is non-increasing along the trajectories x σ k (x) and decreasing after N steps, i.e.

V (x σ 1 (x)) ≤ V (x) and V (x σ N (x)) < V (x), for all x ∈ R n .
The Definition 2 is a standard definition of global Lyapunov function (or, better, global control Lyapunov function) except for the N-steps decreasing requirement. On the other hand, such a function implies the convergence of every subsequence in j ∈ N of the trajectory, i.e. x σ i+ jN (x) for all i < N, then also the convergence of the trajectory itself. This, with the stability assured by V (x σ 1 (x)) ≤ V (x), ensures global asymptotic stabilizability of the switched system.

2

It is proved in [START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encounterd in control theory[END_REF] that for an autonomous linear switched system, the origin is asymptotically stable if and only if there exists a polyhedral Lyapunov function, see also [START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF][START_REF] Lin | Stability and stabilizability of switched linear systems: a survey of recent results[END_REF]. Our main objective is to prove that analogous results can be stated in the case that the switching sequence is a properly chosen selection, that is considering it as a control law.

The system (1) is asymptotically stabilizable if there exists a switching law and a Lyapunov function for the resulting time-varying system. The switching law will belong to the class of state-dependent one, that is σ (k) = g(x k ), where g : R n → N q . We define, with a slight abuse of notation, the state-dependent switching law as σ (k) = σ (x k ).

Assumption 1

The matrices A i , with i ∈ N q , are nonsingular.

Remark 2 Assumption 1 is not restrictive. In fact, the stable eigenvalues of the matrices A i are beneficial from the stability point of view of the switched systems and poles in zero are related to the most contractive dynamics. Moreover, the results presented in the following can be extended to the general case with appropriate considerations. Finally, recall that sampled linear systems do not present poles in the origin and then real systems satisfy Assumption 1.

Consider the following algorithm:

Algorithm 1 Computation of a contractive C * -set for the system (1) satisfying Assumption 1.

• Initialization: given the C * -set Ω ⊆ R n , define Ω 0 = Ω and k = 0; • Iteration for k ≥ 0:

Ω i k+1 = A -1 i Ω k , ∀i ∈ N q , Ω k+1 = i∈N q Ω i k+1 ;
(3)

• Stop if Ω ⊆ int j∈N k+1 Ω j ; denote Ň = k + 1 and Ω = j∈N ŇΩ j . (4)
From the geometrical point of view, Ω i k+1 is the set of x mapped in Ω k through A i . Then Ω k+1 are the x ∈ R n for which there exists a selection i(x) ∈ N q such that A i(x) x ∈ Ω k . Thus, Ω k is the set of x that can be driven in Ω in at most k steps and hence Ω the set of those which can reach Ω in Ň or less steps, by an adequate switching law.

Proposition 1

The sets Ω i k and Ω k with i ∈ N q and for all k ≥ 0 are C * -sets.

Proof: Clearly Ω 0 is a C * -set. It is sufficient to prove that A -1 D and D ∪ E are C * -sets, for all nonsingular A ∈ R n×n and every C * -sets D and E to prove the results by induction. By definition αx ∈ D for all x ∈ D and α ∈ [0, 1]. Then given α ∈ (0, 1] we have Algorithm 1 provides a C * -set Ω contractive in Ň steps, for every initial C * -set Ω ∈ R n , if and only if the switched system (1) is stabilizable. Such a necessary and sufficient condition, which is the main contribution of the paper, is stated in the theorem below.

αA -1 D = {αx ∈ R n : Ax ∈ D} = {y ∈ R n : Ay ∈ αD} ⊆ {x ∈ R n : Ax ∈ D} = A -1 D, since D is a C * -set. For α = 0, αA -1 D = {0} ⊆ A -1 D, triv- ially. Then A -1 D is a star-convex

Theorem 1 There exists a Lyapunov function for the switched system (1) if and only if Algorithm 1 ends with finite Ň.

Proof: Sufficiency follows from the fact that, if the algorithm ends in finite time, then Ω induces a Lyapunov function. Indeed, Ω being a C * -set from Proposition 1, its Minkowski function is defined. Moreover, considering

λ = λ (Ω) = min λ {λ ≥ 0 : Ω ⊆ λ Ω}, (5)
we have that λ < 1, since Ω ⊆ int( Ω) and Ω is a C * -set. Since Ω is the set of x such that x σ k (x) are in Ω for k = k(x) ≤ Ň, and for an appropriate switching sequence, then

x σ k(x) (x) ∈ Ω ⊆ λ Ω, (6)
for all x ∈ Ω and in particular for x ∈ ∂ Ω. This means that there exists a switching σ (x) and k(x) ≤ Ň such that

Ψ Ω(x σ k(x) (x)) ≤ λ Ψ Ω(x), (7)
for all x ∈ ∂ Ω. Then the Minkowski function decreases after k(x) step, for all x on the boundary. Moreover, it does not increase, for all j ≤ k(x). In fact, given x ∈ ∂ Ω, the elements x σ j (x) can be stirred in Ω in k(x)j steps for all j ≤ k(x), being elements of the same sequence whose last element is in Ω. This means that x σ j (x) ∈ Ω and then

Ψ Ω(x σ j (x)) ≤ Ψ Ω(x), ∀ j ∈ N k(x) , (8)
for all x ∈ ∂ Ω. Then for every x ∈ ∂ Ω there exists a switching sequence of length k(x) such that the Ψ Ω is not increasing for the first k(x) -1 steps and it decreases of at least a proportional value λ at the instant k(x), from ( 7) and [START_REF] Boscain | Stability of planar switched systems: the linear single input case[END_REF]. Since every x is on the boundary of a level set of Ψ Ω(x), in particular x ∈ ∂ Ψ Ω(x) Ω , and from the homogeneity of the Minkowski function and the linearity of the switched system, we have that ( 7) and ( 8) hold for every x ∈ R n . Thus from ( 7) and ( 8) valid on the whole R n , we have

Ψ Ω(x σ Ň (x)) ≤ λ Ψ Ω(x), (9)
for all x ∈ R n which proves that Ψ Ω is a Lyapunov function.

Then, if Algorithm 1 ends with finite Ň, a Lyapunov function exists, in particular Ψ Ω(x).

To prove necessity, suppose that there exists a Lyapunov function for the switched system [START_REF] Bauer | A necessary and sufficient condition for robust asymptotic stability of time-variant discrete systems[END_REF]. We demonstrate that this implies finite termination of Algorithm 1. From Definition 2, there is a switching law σ (•), a positive value N ∈ N and a continuous positive definite function V : R n → R such that for every x we have V (x σ N (x)) < V (x). Consider the set

Ω V = {x ∈ R n : V (x) ≤ 1}, (10)
which is closed from continuity of V and bounded from its radially unboundedness. Hence Ω V is compact and 0 ∈ int(Ω V ), since V is continuous and positive definite. Thus for every C * -set Γ, there exists ε > 0 such that the C * -set εΓ

satisfies εΓ ∈ int(Ω V ). Posing Ω = εΓ in Algorithm 1, we have Ω ⊆ int(Ω V ).
From the globally asymptotic stability of the system (1), there exists a switching law σ (x) defined on R n and a finite N V ∈ N such that for all x ∈ Ω V there exists k(x) ≤ N V for which x σ k(x) (x) ∈ Ω. Consider Ω N V obtained by applying Algorithm 1 with Ω defined above, supposing that the stop condition has not been satisfied, otherwise the result would be directly proved. Since the set Ω j is the set of states that can be stirred in Ω in at most j steps, then Ω V ⊆ j∈N N V Ω j and then we have

Ω ⊆ int(Ω V ) ⊆ int j∈N N V Ω j ,
that contradicts the fact that the stop condition has not be satisfied. Then Algorithm 1 terminates with Ň ≤ N V .

Then finite termination of Algorithm 1 is a necessary and sufficient condition for the global asymptotic stabilizability of the switched system (1). An alternative formulation of such a necessary and sufficient condition is presented below.

Theorem 2 There exists a Lyapunov function for the switched system (1) if and only if there exists a C * -set whose Minkowski function is a Lyapunov function for the system.

Proof: The result follows directly from the proof of Theorem 1, where the Minkowski function of Ω is proved to be a Lyapunov function for the switched systems.

Theorem 2 states the main theoretical contribution of the paper, namely that the existence of a Lyapunov function induced by a C * -set is a necessary and sufficient condition for stabilizability of switched systems. Hence, such functions, nonconvex and homogeneous of degree one, form a class of universal Lyapunov functions for the switched systems. Such result is in line with the fact that the existence of convex Lyapunov functions is sufficient but not necessary for the stabilizability of a switched system, as proved in [START_REF] Blanchini | Stabilizability of switched linear systems does not imply the existence of convex Lyapunov functions[END_REF].

Remark 3

The Algorithm 1 terminates after a finite number of iterations only if the switched system is stabilizable, then there is no guarantee of finite termination in general (which means it is a semi-algorithm, to be exact, as noticed by a reviewer). In Section 5 below, a sufficient condition for non-stabilizability is provided that could be used to exclude the existence of a Lyapunov function and then to terminate the (semi-)algorithm. Nevertheless, there are cases in which stabilizability cannot be assessed nor excluded by means of a proper algorithm, i.e. after a finite number of iterations. This is not surprising as in the nonlinear context the problem of the existence a Lyapunov function is often undecidable. In our case, we proved that a Lyapunov function exists and is computable if the switched system is stabilizable.

Duality robustness-control of switched systems

In this section, we recall some results from the literature on the stability of a switched linear system with arbitrary switching law σ (•). Our purpose is to highlight the evident analogies with the approach proposed in this paper concerning stabilizability of switched linear systems.

Consider the linear switched system (1) and assume that the switching law is arbitrary. This would mean that the switching law might be regarded as a parametric uncertainty and the results in [START_REF] Molchanov | Criteria of asymptotic stability of differential and difference inclusions encounterd in control theory[END_REF][START_REF] Blanchini | Ultimate boundedness control for discrete-time uncertain systems via set-induced Lyapunov functions[END_REF][START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF] on robust stability apply with minor adaptations, see also [START_REF] Lin | Stability and stabilizability of switched linear systems: a survey of recent results[END_REF]. The following algorithm provides a polytopic contractive set, and then an induced polyhedral Lyapunov function, for this class of systems, see [START_REF] Blanchini | Set-Theoretic Methods in Control[END_REF].

Algorithm 2 Computation of a λ -contractive C-set for the system [START_REF] Bauer | A necessary and sufficient condition for robust asymptotic stability of time-variant discrete systems[END_REF] with arbitrary switching law.

• Initialization: given the C-set Γ ⊆ R n and λ ∈ [0, 1), define Γ 0 = Γ and k = 0; • Iteration for k ≥ 0:

Γ i k+1 = λ A -1 i Γ k , ∀i ∈ N q , Γ k+1 = Γ ∩ i∈N q Γ i k+1 ; (11)
• Stop if Γ k ⊆ Γ k+1 ; denote N = k and Γ = Γ k .
The set Γ is the maximal λ -contractive set in Γ for the switched system with arbitrary switching law. Provided the Algorithm 2 terminates with finite N, it can be proved that the system is globally exponentially stable, see [START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF]. We finally recall that, for linear parametric uncertain systems, the existence of a polyhedral Lyapunov function is a necessary and sufficient condition for asymptotic stability.

Theorem 3 ([24, 4]) There exists a Lyapunov function for a linear parametric uncertain system if and only if there exists a polyhedral Lyapunov function for the system.

The result in Theorem 3 holds for general parametric uncertainty and applies also for switched systems with arbitrary switching law, as remarked in [START_REF] Lin | Stability and stabilizability of switched linear systems: a survey of recent results[END_REF]. [START_REF] Blanchini | Ultimate boundedness control for discrete-time uncertain systems via set-induced Lyapunov functions[END_REF][START_REF] Blanchini | Nonquadratic Lyapunov functions for robust control[END_REF].

Remark 5 As for the duality of the Algorithms 1 and 2 highlighted in Remark 4, evident conceptual analogies hold between Theorem 2 and Theorem 3. Then the class of Minkowski functions induced by C * -sets is universal for linear switched systems with switching control law, in analogy with the class of polyhedral functions (i.e. induced by C-sets) for the case of arbitrary switching law,

Switching control law

Besides a Lyapunov function, Algorithm 1 provides a stabilizing switching control law or, better, a family of stabilizing control laws for system (1), if it terminates in finite time.

Proposition 2 If Algorithm 1 ends with finite Ň then Ψ Ω :

R n → R is a Lyapunov function for the switched system [START_REF] Bauer | A necessary and sufficient condition for robust asymptotic stability of time-variant discrete systems[END_REF] and given the set valued map [START_REF] Gilbert | Linear systems with state and control constraints: The theory and application of maximal output admissible sets[END_REF] any switching law defined as

Σ(x) = arg min (i,k) {Ψ Ω i k (x) : i ∈ N q , k ∈ N Ň } ⊆ N q × N Ň ,
( σ (x), ǩ(x)) ∈ Σ(x), ( 13
)
is a stabilizing switching law and such that

Ψ Ω(x σ ǩ(x) (x)) ≤ λ Ψ Ω(x), Ψ Ω(x σ j (x)) ≤ Ψ Ω(x), ∀ j ∈ N ǩ(x) ,
with λ as in [START_REF] Blanchini | Set invariance in control[END_REF].

Proof: The fact that Ψ Ω(•) is a Lyapunov function has been proved in the proof of Theorem 1. Denote α = Ψ Ω(x), to simplify the notation. Then x ∈ ∂ (α Ω) by defini- tion. Moreover, from definition of Ω, there are some values (i, k) ∈ N q × N Ň such that x ∈ ∂ (αΩ i k ), since Ω is the union of Ω i k for all i ∈ N q and k ∈ N Ň . Concerning the (i, k) for which x ∈ ∂ (αΩ i k ) is not satisfied, we have that x / ∈ (αΩ i k ) and then Ψ Ω i k (x) > α. This is due to the fact that x is either on the boundary or in the complement of every αΩ i k , for all i ∈ N q and k ∈ N Ň , otherwise α would not be the minimal value such that x ∈ α Ω. Then for every i ∈ N q and k ∈ N Ň we have two possibilities: either

Ψ Ω i k (x) = α, if x ∈ ∂ (αΩ i k ), or Ψ Ω i k (x) > α, if x / ∈ (αΩ i k ).
By construction, Ω i k is the set that can be stirred in Ω, and then also in the contracted set λ Ω, in k steps by means of a sequence of modes whose first element is i. Moreover, the Minkowski function does not increase along the first k -1 elements of the generated trajectory, see the proof of Theorem 1. Then from homogeneity of the Minkowski functions, the set Σ(x) is composed by the (i, k) where i is the first element of a control sequence σ (x) that leads to have x σ k (x) ∈ λ α Ω and x σ j (x) ∈ α Ω for all j ∈ N k . As ( σ (x), ǩ(x)) is a selection of the set Σ(x), the result follows.

It could be reasonable, to speed up the convergence of the trajectory of the system to origin, to select among the elements of Σ(x), those whose k is minimal.

Corollary 1

If Algorithm 1 ends with finite Ň then the switching law defined by ( 12) and ( 13) is such that

Ψ Ω(x σ p Ň (x)) ≤ λ p Ψ Ω(x), ( 14
)
for every p ∈ N and all x ∈ R n .

Proof: From Proposition 2 we have that, if Algorithm 1 ends with finite Ň, then there exists a switching law σ (x) and the related ǩ(x) ≤ Ň such that the Minkowski function of Ω does not increase for k ≤ ǩ(x) and it decreases of a proportional value of λ after ǩ(x) steps, for all x ∈ R n . Since ǩ(x) ≤ Ň, then the value of Ψ Ω(x) decreases at least once within the next Ň steps, that means that

Ψ Ω(x σ Ň (x)) ≤ λ Ψ Ω(x),
that implies [START_REF] Jungers | The Joint Spectral Radius: Theory and Applications[END_REF] as the property applies on the whole R n .

Remark 6 If the system is asymptotically stabilizable, then the algorithm ends with finite Ň for all initial C * -set Ω. Clearly, the value of Ň and the complexity of the set Ω depend on the choice of Ω. In particular, if Ω is the euclidean norm ball (or the union of ellipsoids), the sets Ω i k and Ω k , with i ∈ N q and k ∈ N Ň , are unions of ellipsoids, and so is Ω. Then, the switching law computation reduces to check the minimal value among x T P j x with j ∈ M, where {P j } j∈ M are the M positive definite matrices that define Ω, with M = 5 CONFIDENTIAL. Limited circulation. For review only Preprint submitted to Automatica Received September 20, 2013 01:46:40 PST q + • • • + q Ň = (q Ň+1q)/(q -1), for q > 1 and M = Ň for q = 1. Moreover, if Ω is a polytope (or a union of polytopes), also Ω i k , Ω k , with i ∈ N q and k ∈ N Ň , and Ω are so. In this case, the switching law is obtained by evaluating the linear inequalities defining those polytopes.

Non-stabilizable switched system

In this section, conditions ensuring that there is not a switching law such that the system (1) converges to the origin are given. We will refer to this case as non-stabilizability of the switched system. First, a sufficient condition is provided.

Proposition 3 Given the switched system [START_REF] Bauer | A necessary and sufficient condition for robust asymptotic stability of time-variant discrete systems[END_REF] and the C * -set Ω ⊆ R n and denoting

Ω = i∈N q A -1 i Ω, ( 15
)
if Ω ⊆ Ω then Ψ Ω(A i x) ≥ Ψ Ω(x), ∀i ∈ N q , ( 16
)
for all x ∈ R n . Proof: The set Ω is a C * -set from the proof of Propo- sition 1. Consider first x ∈ ∂ Ω, which implies Ψ Ω(x) = 1.
From the definition of Ω, in [START_REF] Kolmanovsky | Theory and computation of disturbance invariant sets for discrete-time linear systems[END_REF], for every i

∈ N q either x ∈ ∂ (A -1 i Ω) or x / ∈ A -1 i Ω.
In fact, otherwise, there would be i

(x) ∈ N q such that x ∈ int(A -1 i(x) Ω) ⊆ int( Ω), which con- tradicts x ∈ ∂ Ω. For every i ∈ N q such that x ∈ ∂ (A -1 i Ω) one have that A i x ∈ ∂ Ω, while if i ∈ N q is such that x / ∈ A -1 i Ω then A i x /
∈ Ω. Thus it follows that A i x / ∈ int(Ω) for all i ∈ N q , and then, from Ω ⊆ Ω, also A i x / ∈ int( Ω), for all i ∈ N q . Since Ψ Ω(y) ≥ 1 if and only if y / int( Ω), then condition (16) holds at x ∈ ∂ Ω. Finally, since every x ∈ R n is on the bound- ary of a scalar multiple of Ω and from the homogeneity of the Minkowski function of a C * -set, condition ( 16) is satisfied for every x ∈ R n . Proposition 3 states that the existence of a C * -set Ω such that Ω, defined in [START_REF] Kolmanovsky | Theory and computation of disturbance invariant sets for discrete-time linear systems[END_REF], is contained in Ω suffices to prove non-stabilizability. Notice that Ω is the union of the preimages of Ω through A i for all i ∈ N q . In case the C * -set is such that Ω ⊆ int(Ω), the Minkowski function increases at any point of the state space, for every mode.

Corollary 2 Given the switched system [START_REF] Bauer | A necessary and sufficient condition for robust asymptotic stability of time-variant discrete systems[END_REF] and the C * -sets Ω ⊆ R n and Ω ⊆ R n as in [START_REF] Kolmanovsky | Theory and computation of disturbance invariant sets for discrete-time linear systems[END_REF], if Ω ⊆ int(Ω) then

Ψ Ω(A i x) > Ψ Ω(x), ∀i ∈ N q , ( 17
)
for all x ∈ R n .
Hence, the existence of a C * -set Ω ⊆ R n such that Ω as in [START_REF] Kolmanovsky | Theory and computation of disturbance invariant sets for discrete-time linear systems[END_REF] satisfies Ω ⊆ Ω implies that there is not a stabilizing switching sequence. We introduce an algorithm whose finite termination is related to the existence of such a set and then to the non-stabilizability of the switched linear system (1).

Algorithm 3 Test of non-stabilizability for the system [START_REF] Bauer | A necessary and sufficient condition for robust asymptotic stability of time-variant discrete systems[END_REF] such that Assumption 1 holds.

• Initialization:

given the C * -set Ω ⊆ R n , define Ω 0 = Ω0 = Ω and k = 0; • Iteration for k ≥ 0 compute Ω i k+1
and Ω k+1 as in ( 3) and define Ωk+1 =

j∈N k+1 Ω j ∪ Ω. (18)
• Stop if Ω k+1 ⊆ Ωk ; denote N = k and Ω = Ω N : the system ( 1) is non-stabilizable.

The finite termination of Algorithm 3 is a sufficient condition for non-stabilizability of the system (1), as proved below.

Theorem 4 If Algorithm 3 ends with finite N then there is no switching law stabilizing the switched system [START_REF] Bauer | A necessary and sufficient condition for robust asymptotic stability of time-variant discrete systems[END_REF].

Proof: For every k ∈ N, the set in ( 18) is a C * -set from Proposition 1 and the fact that the union of C * -sets is a C *set. Suppose that Algorithm 3 ends with finite N and define Ω = i∈N q A -1 i Ω. For all nonsingular matrix A ∈ R n×n and every C * -sets D, E ⊆ R n we have that also the set

A -1 (D ∪ E) = (A -1 D) ∪ (A -1 E) is a C * -set. It follows that Ω = i∈N q A -1 i j∈N NΩ j ∪ Ω = = Ω N+1 ∪ j∈N NΩ j ⊆ j∈N NΩ j ∪ Ω = Ω.
Then from Proposition 3, the Minkowski function of Ω is non-decreasing for every mode and at every point of the state space and the system is non-stabilizable.

Remark 7

Notice that the termination condition of Algorithm 3 is equivalent to Ωk+1 ⊆ Ωk . In fact, we have that

Ωk+1 = Ω k+1 ∪ j∈N k Ω j ∪ Ω = Ω k+1 ∪ Ωk ⊆ Ωk ,
which holds if and only if Ω k+1 ⊆ Ωk and Ωk ⊆ Ωk , trivially satisfied the latter.

A class of switched systems such that finite termination is assured is characterized in the following theorem.

Theorem 5 If there is a continuous positive definite and radially unbounded function V : R n → R such that

V (A i x) > V (x), ∀i ∈ N q , (19)
for all x ∈ R n , then Algorithm 3 ends with finite N and the switched system ( 1) is non-stabilizable.

6

CONFIDENTIAL. Limited circulation. For review only Preprint submitted to Automatica Received September 20, 2013 01:46:40 PST Proof: From [START_REF] Liberzon | Basic problems in stability and design of switched systems[END_REF] and Assumption 1, it follows that

V (A -1 i x) < V (x), ∀i ∈ N q , (20)
for all x ∈ R n . Consider the set defined

Ω V = {x ∈ R n : V (x) ≤ 1}, (21)
which is compact and such that 0 ∈ int( Ω V ), being V continuous, positive definite and radially unbounded, as the set Ω V in [START_REF] Geromel | Stability and stabilization of continuous-time switched linear systems[END_REF]. Then the C * -set Ω initializing Algorithm 3 can be chosen such that Ω ⊆ Ω V , after an adequate scaling. From (20), we have that there is a finite N ∈ N such that

∏ k∈N N A -1 i(k) x ∈ Ω, ∀x ∈ Ω V ,
and every sequence of modes i(k

) ∈ N q with k ∈ N N , which implies Ω N ⊆ Ω, being Ω ⊆ Ω V .
Then, since Ω ⊆ ΩN , see [START_REF] Liberzon | Switching in Systems and Control[END_REF], Algorithm 3 stops after N iterations at most.

In the case that the function V (•) is such that V (A i x) ≥ V (x), for all i ∈ N q , the finite termination of Algorithm 3 is not ensured (nor excluded) by Theorem 5. In particular, if stability is ensured by a function V (•) such that V (A i x) = V (x), for all i ∈ N q and every x ∈ R n , that does not guarantee convergence, the algorithm could terminate in finite time or not, as shown in the following illustrative example.

Example 1 Consider the linear system given by ( 1) with q = 1 and A 1 = R(β π), where R(θ ) is the rotation matrix of angle θ and with β ∈ R \ Q such that β ∈ (0, 0.5). The system is stable but not convergent to the origin, then a Lyapunov function does not exist and Algorithm has not a finite termination. Suppose that Algorithm 3 is applied with initial set Ω = {x ∈ R 2 : x ∞ ≤ 1}, which is a square centered in the origin. The sequence of sets Ω k with k ∈ N are the square Ω rotated of the angle kβ π with k ∈ N. We prove that for every m, k ∈ N with k > m, the sets Ω k = Ω m . In fact otherwise we would have that the rotation is the same, except for a multiple of π/2, since the square does not change only if it is rotated of dπ/2 with d ∈ N. But this implies that, for an adequate d ∈ N, we have kβ π = mβ π + dπ/2 and then β = d/2(km), which contradicts the fact that β is an irrational number. Hence Algorithm 3 does not end in finite time, since Ωk is the union of Ω j with j < k. Conversely, choosing the euclidean norm ball as initial condition, i.e. Ω = B 2 , the algorithm stops at the first step. In fact, we have Ω 1 = Ω0 = Ω. Notice that the euclidean ball is the only C * -set whose Minkowski function does not increase (nor decrease) along the trajectories. Furthermore, the sequence Ωk generated by Algorithm 3 initialized with the square converges to the euclidean ball of radius √ 2 for k → ∞.

The finite termination of Algorithm 3 is only a sufficient condition for non-stabilizability of the system (1), see Theorem 4. The finite termination is attained if and only if there is a positive definite radially unbounded function increasing along the trajectories, for every possible switching sequence, see Theorem 5. There are cases in which the system (1) is non-stabilizable but Algorithm 3 does not ends in finite time (and Algorithm 1 neither, clearly).

Lyapunov-Metzler approach

Conditions for the stabilizability of switching system are available in literature. Those based on the Lyapunov-Metzler inequalities are among the less conservative. Such conditions are given by nonlinear matrix inequalities whose solution is often numerically intractable, see [START_REF] Geromel | Stability and stabilization of discrete-time switched systems[END_REF][START_REF] Geromel | Stability and stabilization of continuous-time switched linear systems[END_REF]. In the continuous-time context, it has been proved that the existence of a stable convex combination of the matrices A i , with i ∈ N q , is a sufficient condition (and also necessary for q = 2) for the Lyapunov-Metzler inequalities to hold. Such a condition on the convex combinations of the modes is at the core of the stabilizing techniques in the literature, see [START_REF] Liberzon | Switching in Systems and Control[END_REF]. For discrete-time systems, such a relation is less evident and other available sufficient conditions are more conservative, see [START_REF] Geromel | Stability and stabilization of discrete-time switched systems[END_REF]. It is worth then to directly consider the Lyapunov-Metzler condition to obtain an appropriate comparison, although its evaluation would require a computationally demanding approach. It has to be recalled, nevertheless, that Lyapunov-Metzler conditions deal with nonconvex Lyapunov functions, namely homogeneous ones whose level sets are union of ellipsoids.

Numerical examples

Example 2 Consider the system (1) with q = 4, n = 2 and

A 1 = 1.5 0 0 -0.8 , A 2 = 1.1 R( 2π 5 ) A 3 = 1.05 R( 2π 5 -1), A 4 = -1.2 0 1 1.3 .
The matrices A i , with i ∈ N 4 , are not Schur, which implies that the system (1) is not stabilizable by any constant switching law. We apply Algorithm 1 with Ω = B 2 . The sets Ω k , k ∈ N are thus unions of ellipsoids. The result at the first step is depicted in Figure 1, left. Ω 1 is the union the four ellipsoids A - to Ω 1 . The next step of the algorithm leads to a set k∈N 2 Ω k given by the union of the 4 + 4 2 = 20 ellipsoids at most, i.e. A -1 j B 2 with j ∈ N 4 and A -1 j A -1 i B 2 , for all (i, j) ∈ N 4 × N 4 . Since B 2 does not belong to k∈N 2 Ω k , see Figure 1 right, the termination condition is not satisfied. The algorithm stops at the fifth iteration. Figure 2 emphasizes that B 2 is included in k∈N 5 Ω k . A stabilizing switching law, satisfying ( 13) is given in Figure 3 for the initial condition x 0 = (-3, 3) T . The Lyapunov function converges to zero, see Figure 3. Example 3 As a second example, consider for q = n = 2:

A 1 = 0 -1.01 1 -1 , A 2 = 0 -1.01 1 -0.5 .
The Lyapunov-Metzler approach results in a set of linear matrix inequalities once two parameters are fixed, both contained in [0, 1], see [START_REF] Geromel | Stability and stabilization of discrete-time switched systems[END_REF]. The LMI conditions have been checked on a grid of these parameters, with step of 0.01. No admissible solution was found, whereas our algorithm stops at the third step. Figure 4 shows that B 2 ⊆ int( k∈N 3 Ω k ).

The Lyapunov function and the switching law are given in Figure 5. Notice that the Lyapunov function is not a decreasing function, but only a non-increasing one which is strictly decreasing at least once every three (the number of steps of the algorithm) instants, as proved in the main result. Example 4 As mentioned above, there are undecidable cases for which neither Algorithm 1 nor Algorithm 3 are finite. Consider

A 1 = 1.3 0 0 0.9 R(θ ), A 2 = 1.4 0 0 0.8 , (22)
with θ = 0 for the moment. Matrices A 1 and A 2 are not Schur. Four steps are applied for each algorithm. The results are drawn in Figure 6. Notice that x = (1, 0) T is related to an unstable eigenvalue for both modes, then Algorithm 1 cannot be finite. Moreover in direction x = (0, 1) T , ∪ k∈N i Ω k is increasing with i, then Algorithm 3 cannot be finite. Example 5 Consider the system given by ( 22) with θ = π 5 , which means that the first mode performs now a rotation of π 5 . Algorithm 1 stops after seven steps implying the stabilizability of the system. The result is given in Figure 7. The issue of the stabilizability of discrete-time linear switched systems has been studied in this paper. Via a set-theory approach, necessary and sufficient conditions for the stabilizability and sufficient ones for non-stabilizability have been provided. The family of nonconvex, homogeneous functions induced by a C * -set is proved to be a class of universal Lyapunov functions for switched systems. In addition, the stabilizing switching laws are characterized. Our method allows moreover to stabilize counter-examples for the Lyapunov-Metzler approach. Several academic illustrations are proposed to strengthen the discussions and to emphasize the efficiency of our approach.

1 i

 1 set and it is also compact from Assumption 1. It contains the origin in its interior since A -are continuous operators under Assumption 1. Then A -1 D is a C * -set. The property on the union follows from the definition of C * -set.

Remark 4

 4 Notice the analogies between the Algorithms 1 and 2: they share the same iterative structure and they both 4 CONFIDENTIAL. Limited circulation. For review only Preprint submitted to Automatica Received September 20, 2013 01:46:40 PST generate contractive sets which induce Lyapunov functions provided they terminate in a finite number of steps. The main substantial difference consists in the use of intersection/union operators and in the family of sets generated, C * -sets by Algorithm 1 and C-sets by Algorithm 2. Interestingly, the C-sets are closed under the intersection operation whereas C * -sets are closed under the union. The C * -sets have for switched systems with switching control law the role that C-sets have for the case of arbitrary switching law.

2 Fig. 1 .

 21 Fig. 1. Ball B 2 in dashed and Ω 1 and k∈N 2 Ω k solid line.

2 Fig. 2 .

 22 Fig. 2. Ball B 2 in dashed and k∈N 5 Ω k in solid line. Trajectory starting from x 0 = (-3, 3) T in dotted line.

Fig. 3 .

 3 Fig. 3. Lyapunov function and switching control law in time.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Ball B 2 in dashed and k∈N 3 Ω k in solid line. Trajectory starting from x 0 = (-3, 3) T in dotted line.

8 CONFIDENTIAL.

 8 Limited circulation. For review only Preprint submitted to Automatica Received September 20, 2013 01:46:40 PST

2 Fig. 6 .

 26 Fig. 6. Ball B 2 in dashed and ∪ k∈N i Ω k , for i ∈ N 4 in solid line.

2 Fig. 7 .Example 6 1 5 .Example 7 2 Fig. 8 .

 27615728 Fig. 7. Ball B 2 in dashed and ∪ k∈N i Ω k , for i ∈ N 7 in solid line.

Fig. 9 .

 9 Fig. 9. Ball B 3 in dark and ∪ k∈N j Ω k , for j ∈ N 3 , in light gray.


Ghislain Dutheil De La Rochère

Jean-Michel Josselin
email: jean-michel.josselin@univ-rennes1.fr

Yvon Rocaboy

SDI, NATO, and the social composition function FINAL REVISION

Keywords: JEL classification: D74, H56, H87 International public goods, social composition function, international organizations, alliances, best-shot, NATO

The Strategic Defense Initiative (SDI) intends to renew the leadership of the USA on the western alliance. The initiative takes place in a period when a summation technology prevails for the aggregation of contributions of NATO allies. We investigate whether SDI induces a shift in Hirshleifer's social composition function.

Panel data tests over the period 1970-1990 do not confirm any break towards a bestshot aggregator. SDI does not alter the core of deterrence. It is indeed a public good at the US level but not at the NATO level, where it is one of the joint products of the alliance. We also investigate the lessons to be drawn for the current debates on ballistic defense.

SDI, NATO, and the social composition function

Introduction

According to [START_REF] Hirshleifer | From weakest-link to best-shot: The voluntary provision of public goods[END_REF], the social composition function of an alliance can be summation [START_REF] Samuelson | The pure theory of public expenditure[END_REF]) but also best-shot or weakest link [START_REF] Cornes | Dyke maintenance and other stories: Some neglected types of public goods[END_REF][START_REF] Cornes | Weak links, good shots and other public goods games: building on BBV[END_REF]. Collective action significantly depends on the prevailing technology of aggregation of allies' contributions [START_REF] Sandler | Hirshleifer's social composition function in defense economics[END_REF]. The shared defense of NATO is a fine example of the evolution of the social composition function of an alliance. The nuclear policy and technology of the USA in the 1950s prompt a bestshot that prevails until 1970, when the alliance moves to a summation technology from 1971 to 1990, then to another summation period, characterized by increased strategic behaviors [START_REF] Sandler | Burden sharing, strategy, and the design of NATO[END_REF][START_REF] Gadea | A long-run analysis of defence spending in the NATO countries (1960-99)[END_REF][START_REF] O'neal | NATO burden sharing and the forces of change[END_REF][START_REF] Khanna | NATO burden sharing: 1960-1992[END_REF][START_REF] De La Rochère | The role of aggregation technologies in the provision of supranational public goods: A reconsideration of NATO's strategies[END_REF]. At the midst of the first summation period, President Reagan initiates the Strategic Defense Initiative (SDI).

The so-called Star War project will never be really completed but from its inception it contributes to a dramatic increase in military space expenditures [START_REF] Zervos | The impact of the US Strategic Defense Initiative on the space race[END_REF]).

Admittedly, President Reagan does not properly reach the aim of an effective SDI, in budgetary and military terms [START_REF] Freedman | The evolution of nuclear strategy[END_REF]. SDI nevertheless remains a prominent feature of Mr. Reagan's first mandate. The aim is to develop a National Missile Defense (NMD) system, an innovative laser-based concept designed to protect the United States from long range nuclear missile attacks. Political will is definitely at the origin of SDI. It is a means to a renewed leadership of the USA. However, being a national rather than a theater missile defense system, this system is controversial [START_REF] O'hanlon | Star War strikes back[END_REF].

The controversy is ongoing. The new strategic concept of NATO emanating from the Lisbon Summit in November 2010 cites as a new threat the proliferation of ballistic missiles and nuclear weapons. In order to face it, NATO leaders have decided to develop missile defense capacities. The first step has been to provide protection to NATO deployed forces, with theatre missile defense. The next step consists in protecting the civil populations of all NATO allies, with territorial missile defense. In June 2011, NATO Defense Ministers approved the NATO Ballistic Missile Defense Action Plan. This important strategic move will concern all the allies but the first contributor for the technologies involved remains the USA. Even if the time horizon for the plan is a decade, it can have an impact on the present behavior of the allies and it could drive the alliance towards a period of best-shot technology for the aggregation of individual contributions to NATO. In this renewed context, understanding what happened during the Star War period can illuminate the ongoing strategic shifts towards territorial missile defense. In particular, it can provide lessons about the likely evolution of aggregation technologies in the alliance.

To our knowledge, the few existing economic studies of SDI mainly focus either on the USA-USSR arms race [START_REF] Zervos | The impact of the US Strategic Defense Initiative on the space race[END_REF] or on the deterrence-defense tradeoff in a game-theoretic framework [START_REF] Brams | Deterrence versus defense: A game-theoretic model of Star Wars[END_REF]. Insightful though these are, those studies do not take into account two dimensions of the NMD system designed by the Reagan administration, which we would like to study here. First, we investigate the social composition function of the alliance. NMD is evidently a national program, but the national policy of the former best-shot of the western alliance might be expected to extend its impact beyond strictly national interests. Now, SDI is conceived during a period when NATO works under a summation aggregation technology, which leads us to our second point. In budgetary and strategic terms, SDI is an endeavor of tremendous policy consequences: deterrence has indeed been the key to the initial strategy of NATO. Can it be replaced with defense provided by the US NMD? Can we find empirical evidence that SDI provided a best-shot during the nineteen-eighties? Instead of adopting a long term perspective for the identification of social composition functions [START_REF] Gadea | A long-run analysis of defence spending in the NATO countries (1960-99)[END_REF][START_REF] De La Rochère | The role of aggregation technologies in the provision of supranational public goods: A reconsideration of NATO's strategies[END_REF], we focus our statistical analysis on the period 1970-1990 in order to try to capture and identify a possible breakpoint in aggregation technologies for the NATO alliance during the SDI period. We thus follow the track of [START_REF] Conybeare | Alternative collective-goods models of military alliances: Theory and empirics[END_REF] who investigate and propose ways of distinguishing best-shot, weakest-link and summation aggregation technologies in military alliances, with an empirical focus on World War One and Cold War alliances. We will show that our results corroborate their own analysis of NATO over the period 1961-1987, though they are obtained through a different empirical strategy.

The article is organized as follows. Section 2 describes the way in which SDI is both a technological innovation and a political will that can alter the social composition function of the alliance. Section 3 presents the econometric results testing the possibility for the USA to become a best-shot in NATO during the nineteen-eighties. Section 4 provides a discussion of those empirical results.

"The Cold War is over": the political economy of Star War

The above quotation is from President Reagan leaving office in January 1989 after two mandates. In the early 1980s, US-Soviet relations enter a phase of intense friction, potentially as dangerous as the 1962 Cuban missile crisis. The magnitude of the perceived threat is probably amplified by the US presidential campaign of 1980.

Nevertheless, when the then elected President Reagan launches the Strategic Defense Initiative with his speech of March 23, 1983, it spurs or revives the space arms race between the two superpowers of the time. Econometric evidence [START_REF] Zervos | The impact of the US Strategic Defense Initiative on the space race[END_REF] reinforces the argument that SDI contributes to the bankruptcy of the Soviet Union. At the time of its launching however, heated arguments fuel a debate full of technical and strategic controversies. [START_REF] Greenberg | The Empire strikes out. Why Star Wars did not end the Cold War[END_REF] mentions how SDI can be conceived as a bargaining chip for arms control negotiations. It can also be interpreted as a way to undermine the 1972 Anti-Ballistic Missile Treaty, providing a way to modify it rather than withdrawing from it (O'Hanlon 1999), thereby minimizing the diplomatic consequences of a rather bold initiative. It is true that SDI is never properly realized as such, if only because the timescale for implementation would be decades rather than years. In the meantime, arms control progressively appears to be a more plausible means of escaping from mutual assured destruction (as evidenced for instance by the December 1987 treaty aiming at eliminating intermediate nuclear forces). Nevertheless, as a political initiative, the simple announcement of SDI breeds such hostility on the Soviet side that it reinforces its credibility, probably more than is deserved [START_REF] Freedman | The evolution of nuclear strategy[END_REF]. Furthermore, budgets point at a "best-shot" effort by the USA. Since the announcement of SDI in 1983, the USA has spent $3.5 billion a year on missile defense programs (O'Hanlon 1999). The rise in space military expenditures matches that of the early 1960s during the space race between "Apollo and Sputnik". Furthermore, [START_REF] Zervos | The impact of the US Strategic Defense Initiative on the space race[END_REF] identifies 1986 as the date when the US space military expenditures surpass the Soviet ones for the first time in history, as a consequence of a trend rooted back in the mid-1970s. The ensuing candidacy for best-shot is exemplified by [START_REF] Sandler | Hirshleifer's social composition function in defense economics[END_REF]: the "Star War" best-shooter has the capability to destroy enough missiles from the first strike of the enemy to SDI and NATO final revision-1 deter it from attacking. At the scale of the alliance, only one such system is required. The defense missile system can at first glance be viewed as a best-shot public good.

There remains to check whether it is the case or not.

Econometric analysis

The theoretical setting behind our empirical investigations is that of a joint product model of alliance. A pure public good best-shot model would imply zero contributions by non best-shot allies and obviously would not be realistic in our case.

The joint product model is thus a rather more adequate framework. In a joint product setting, Nash equilibrium conditions have been provided by [START_REF] Sandler | Impurity of defense: An application to the economics of alliances[END_REF] in the summation case and by [START_REF] Conybeare | Alternative collective-goods models of military alliances: Theory and empirics[END_REF] in the best-shot case. We use here a simple model to describe both cases. The alliance consists of countries = 1, ⋯ , . . Under a best-shot technology, 3-= max 12 )*+ 1 with 3-4567%6897 = 0.

In the first stage we use OLS with the Panel Corrected Standard Errors (PCSE) method [START_REF] Beck | What to do (and not to do) with time series cross-section data[END_REF] with fixed effects and lagged variables. Two models are tested, each of them characterized by an aggregation technology assumed to be constant over the whole period 1970-1990:

(3 )*+ ,7 = < , + = ), ,7 + > -./ ,7% + ? ,7

(4 )*+ ,7 = < A, + = A ), ,7 + > A 3-,7% + ? ,7

Equation 3 is the reaction function of ally within a summation technology (equation 1) while equation 4 corresponds to the best-shot case (equation 2). Table 1 provides the estimations of the two equations. Coefficients for ), are significant at the 1% level. However, none of the two aggregation technologies have significant coefficients. We thus hypothesize that a break may occur during the period, with a shift from one social composition function to another or a change in the behavior of the allies within a given technology of aggregation.

(Table 1 about here)

The empirical strategy is then to introduce unknown breakpoints B C within the period. We define them in the following way:

(5

E*FG1 ,7% = B C × E*FG ,7%
The aggregation technology is represented by variable E*FG, which is such that 1914), Warsaw Pact (1963-1987), and NATO (1961-1987). For the latter, the authors conclude on the prevalence of summation-type ally behavior over best-shot or weakest-link behavior (p.541). Here we use panel data and we allow a break in the considered period. Although the empirical strategies are different, both lines of research suggest that NATO abides by a summation aggregation technology as soon as conventional forces get more and more weight in the alliance. This is also the case with the Warsaw Pact [START_REF] Conybeare | Alternative collective-goods models of military alliances: Theory and empirics[END_REF]. Best-shot attributes (nuclear deterrence by the alliance leaders) could provide incentives to free-ride on the best-shooter.

E*FG =
However, potential risks of weakest-link would lead western allies voluntarily to engage into matching behaviors of sustained contributions to their alliance (matching would be centrally planned within the Warsaw Pact). Nonetheless, what we would like to discuss now is why a political initiative as striking and prominent as SDI did not trigger a shift in the social composition function of NATO.

Discussion

The expected shift of technology from summation to best-shot following SDI does not seem to take place. If ever there is a change in the behavior of the allies, it happens earlier in 1980 or 1981 and it remains within a summation framework with only a slight change in the contributing behavior of allies from the first to the second period. To try to understand why SDI does not shift the social composition function towards a best-shot aggregator, it may prove insightful to go back to the earlier years of NATO when the USA did play best-shot.

As [START_REF] Pedlow | NATO strategy documents 1949-1969[END_REF] of the alliance at its inception is straightforwardly announced: "Insure the ability to deliver the atomic bomb promptly. This is primarily a US responsibility assisted as practicable by other nations" (MC3 7a). Under the item "cooperative measures", the directive claims that "The essence of our overall concept is to develop a maximum of strength through collective defense planning" (MC3 8). Though the expression "atomic bomb" is soon replaced in the later documents by "strategic bombing", it nevertheless remains that NATO basically aims at providing deterrence as a pure public good inside the alliance.

Deterrence is indeed plainly and forcefully described as such in directive MC48 of November 22, 1954. "In face of the threat of such a war, the primary aim of NATO, must more than ever before, be to prevent war. This aim can only be achieved if the Allied nations are so powerful in the vital elements of modern warfare that the enemy will conclude that he has little hope of winning a war involving NATO. This means that NATO must be able to withstand the initial Soviet onslaught, to deliver decisive atomic counter-attacks against the war-making capacity of the enemy, and to prevent the rapid overrunning of Europe" (MC48 33). In economic terms, deterrence is a pure public good. It is non rival: unlike situations involving conventional forces, retaliation can take place whatever the magnitude or geographical aim of the threat. It is also non-excludable: all allies are protected and none can be excluded. Finally, the use of the public good is mandatory once the allies have signed the Treaty. Deterrence is a credible commitment: the automatic pledge of retaliation is sustained by the fact that NATO would have a first-strike advantage and a second-strike capability thanks to its sufficient stockpile of nuclear weapons.

First-strike deterrence thus works as a collective good provided to the members of the alliance. The aggregation technology during 1949-1970 is not summation, but best-shot. This does not mean that non best-shot contributions are redundant or useless. The latter statement is largely denied by the very writing of such a fundamental document as directive MC48. Complementarity remains crucial in the alliance, thereby justifying the joint product approach.

SDI and NATO final revision-1

In a context of summation, SDI can appear as an attempt at reinstalling the best-shot status of the USA while securing the ballistic protection of the US territory.

However, to become a successful best-shot implies that you have the capacity to provide the core of the public good that unites the allies. Now, SDI is a NMD policy with strategic aims that are radically different from standard Theater Missile Defense (TMD), like for instance Patriot missiles. Our point is that this national defense initiative amounts to fueling the alliance with a private good. SDI is indeed a public good at the US level but at the NATO level, it is a private good that becomes one of the joint products of the alliance as they have been analyzed by [START_REF] Sandler | Economics of alliances: The lessons for collective action[END_REF]: strategic, tactical and conventional weapons are complementary in the overall strategy, and SDI is one of them. President Reagan's first mandate displays a political will to bend down the USSR, pushing forward a US national defense system in an alliance characterized from its inception by global nuclear deterrence.

Another aspect of our discussion is that the doctrine of flexible response initiated in the late 1960s shows a significant inflexion from 1981 until the shift to the crisis management doctrine in 1990 (Sandler and Murdoch 2000, Table 1, p.305).

Besides the US efforts, France and UK proceed to build-up and modernize their strategic arsenals thereby increasing deterrence and the share of jointly produced nonexcludable public outputs. At the same time, NATO adopts the forward-defense (deep strike) strategy in 1984. Precision-guided munitions target the Warsaw Pact rearechelon forces. The new strategy reduces the importance of the thinning conventional forces. [START_REF] Sandler | On sharing defence burdens in the 1990s and beyond[END_REF] consider that this inflexion in the implementation of the flexible response doctrine augments the share of non-excludable benefits derived from defense. In the context of our discussion, if these events do increase the publicness of defense activity, this is not solely due to one ally but to the joined efforts of a handful of them, which decreases the likelihood of a single best-shot.

There are certainly lessons to be drawn from that "Star War" episode. It may illuminate the current debates on missile defense. Considering the current variety and dispersion of threats that NATO faces, the weakest-link technology may want renewed consideration, not only for moral hazard considerations but also for the possible technological weakness of the defense system of one of the allies. The achievement of the Territorial Missile Defense strategy might be a way to prevent it.

The guess is that missile defense strategy, even within the framework of a summation social composition function, "would be able to knock down enough of an enemy's missiles so that if he ever pushed a button to attack, he would be doing so in the knowledge that his attack was unable to prevent a devastating retaliatory strike (Reagan's memoirs, quoted by Greenberg 2000, p.140). And the ballistic initiative of the USA would prove useful to NATO, if not best-shot.

  Interpreted in the social composition function framework of Hirshleifer, SDI is a defense innovation supported by the political power in an attempt to strengthen the US position against the Soviet threat. A likely consequence is that the USA may again become a best-shot within NATO. Now, if we adopt a long run perspective, the inception of SDI approximately takes place in the middle of a period of summation technology for the NATO alliance. 1970-1990 is indeed characterized by the flexible escalation doctrine by which primary fronts involve non-nuclear engagements only, nuclear weapons being kept within second stage interdiction strikes. The technology of aggregation of technologies in the western alliance has thus moved from a bestshot played by the USA from 1955 to 1970, to a summation composition function that gives a renewed weight to conventional forces. Behind this change in aggregation technology lays a new strategic doctrine put forward by NATO directive MC14/3 of January 16, 1968 whereby "The conventional forces of the Alliance, land, sea and air, many of which are organically supported by tactical nuclear weapons, are a further essential component of the deterrent" (MC14/3, 25c; see also MC14/3, A8). This new strategic concept is to be implemented through measures described in NATO directive MC48/3 of December 8, 1969. The USA does follow the strategic line proponing "The requirement for adequate conventional forces and for improving capabilities for non-nuclear operations while maintaining NATO's nuclear capability. This should include achieving optimum dual capability, especially in air forces, and the flexibility to employ these forces in non-nuclear operations" (MC 48/3, 5b). Concurrently, the American political scene progressively develops a rhetoric pushing forward the imminent Soviet domination, culminating with Ronald Reagan's election. SDI can be seen as an attempt to go beyond the current state of strategic military doctrine of the time. That political will would involve a change in the aggregation technology of the western alliance.

Following

  Allies have initial endowments (e.g. annual GDP) with numéraire expressing private consumption as well as the provision of non-military national public goods.Defense activity with unit price involves a contribution to the alliance-wide deterrence and an ally-specific local public good. The utility function is = ( , , ( , … , , … ,The Nash program of a given ally is[START_REF] Cornes | Dyke maintenance and other stories: Some neglected types of public goods[END_REF] Sandler 1984) Dutheil et al. (2011), in the case of a summation aggregation technology, the reaction function of ally is(1 = $ ( % , ,With % the sum of the defense expenditures of allies other than ally . In the bestshot case, the reaction function of non best-shot country is (2 = $ ( '( , , With '( the defense expenditure of the best-shot ally; the latter has the reaction function '( = $ '( ( '( , . Equipped with those testable forms, we now move on to the empirical analysis per se. The panel goes over the period 1970-1990 for 14 NATO allies (Belgium, Canada, Denmark, France, Germany, Greece, Italy, Luxemburg, the Netherlands, Norway, Portugal, Turkey, the UK, and the USA). Data is obtained from NATO 2009 sources for national defense expenditures (denoted by )*+ for ally ) and IMF 2008 for GDP (denoted by ), ). Units are million USD and the logarithm of variables is used in the regressions on this balanced panel data set. Under a summation technology, considering a given ally , the other allies' cumulated defense efforts are denoted by -./ = ∑ )*+ 1 12

  -./ "I 3-. The social composition function can be either summation or best-shot. Dummy variable B C takes value 1 from 1970 until year J and value 0 afterwards. Until date J, E*FG1 = -./1 "I 3-1: during the first period, summation or best-shot can prevail. Afterwards, E*FG2 = -./2 "I 3-2: there may or may not be a shift in the aggregation technology.Still using the PCSE method, we test all possible combinations of breakpoints B C from 1970 to 1990 and of aggregation technologies (for instance 3-1 then -./2 or -./1 then -./2): (6)*+ ,7 = < + = ), ,7 + L E*FG1 ,7% + L A E*FG2 ,7% + ? ,7If the SDI hypothesis is verified, then we could expect a technology shift from summation to best-shot around 1983. However, in statistical terms, this is one possibility amongst many others. With a time horizon of 21 years and 4 possible combinations of aggregation technologies, 84 models are in competition and must be investigated as such. Detailed estimations are provided in appendix 1. Only five models emerge with significant coefficients.

  Table 2 sums up the results. Model A evidences best-shot until 1972 and then summation. Model B does the same with a break in 1975. Model E begins with best-shot with a break in 1981 followed by another best-shot. Models C and D show two summation periods with respective

	breaks in 1980 and 1981.
	(Table 2 about here)
	We then run J tests in order to cross-evaluate the five models remaining in
	competition (detailed results are provided in appendix 2). Models A, B and E can be
	rejected at the 1% threshold. Models C and D are quite similar, with close break dates
	and the same aggregation pattern. None of them is rejected at the 1% threshold.

Model D cannot be rejected at the 5% threshold (except when compared to model C).

At the 10% threshold, no specification dominates. All in all, model D and to a slightly lesser extent model C seem to provide the best specifications. A constant social composition function seems to prevail, namely summation, over the whole period comprehending the Strategic Defense Initiative. The econometric analysis does not confirm any technology shift towards best-shot.

Our result corroborates that of

[START_REF] Conybeare | Alternative collective-goods models of military alliances: Theory and empirics[END_REF]

while using a different empirical strategy.

[START_REF] Conybeare | Alternative collective-goods models of military alliances: Theory and empirics[END_REF]

distinguish best shot, weakest link, and summation aggregation technologies, and applied cross-sectional data analysis to four alliances on the entire period: Triple Alliance (1880-1914), Triple Entente (1880-

Table 1 :

 1 Estimation results for the significant technology combinations without

	breakpoints
		Model of	Model of
	Variables	constant	constant
		summation	best-shot
	),	0.677*** (0.081)	0.683*** (0.074)
	-./	-0.025 (0.119)
	3-		-0.036 (0.090)
	M A	0.993	0.994
	(***) significant at the 1% level

Table 2 :

 2 Estimation results for the significant technology combinations with If the coefficient is statistically significant, the competing model specification is the best

	breakpoints
		Model A	Model B	Model C	Model D	Model E
	Variables
		J = 1972	J = 1975	J = 1980	J = 1981	J = 1981
	),	0.720*** (8.913)	0.714*** (8.786)	0.704*** (9.859)	0.713*** (9.958)	0.675*** (9.900)
	-./1			-0.217** (-2.027)	-0.243** (-2.132)
	-./2	-0.010** (-2.225)	-0.009* (-1.927)	-0.212** (-1.996)	-0.238** (-2.106)
	3-1	-0.009* (-1.882)	-0.008* (-1.763)			-0.155* (-1.802)
	3-2					-0.151* (-1.771)
	M A	0.994	0.994	0.995	0.995	0.995
	(*), (**), (***): respectively significant at 10%, 5% and 1% level

(*), (**), (***): respectively significant at 10%, 5% and 1% level