Dan Goreac

Alexandra Claudia Grosu

Eduard-Paul Rotenstein

Approximate and Approximate Null-Controllability of a Class of Piecewise Linear Markov Switch Systems

 allowing to reduce the dual stochastic backward system to a family of ordinary di¤erential equations. Second, we prove by examples that the notion of approximate controllability is strictly stronger than approximate null-controllability. A su¢ cient criterion for this stronger notion is also provided. The results are illustrated on a model derived from repressed bacterium operon (given in [19] and reduced in [5]).

Introduction

This short paper aims at giving an answer to an approximate (null-)controllability problem left open in [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF]. We deal with Markovian systems of switch type consisting of a couple mode/ trajectory denoted by ( ; X) : The mode component evolves as a pure jump Markov process and cannot be controlled. It corresponds to spikes inducing regime switching. The second component X obeys a controlled linear stochastic di¤erential equation (SDE) with respect to the compensated random measure associated to . The linear coe¢ cients governing the dynamics depend on the current mode.

The controllability problem deals with criteria allowing one to drive the X T component arbitrarily close to acceptable targets. An extensive literature on controllability is available in di¤erent frameworks: …nite-dimensional deterministic setting (Kalman's condition, Hautus test [START_REF] Hautus | Controllability and observability conditions of linear autonomous systems[END_REF]), in…nite dimensional settings (via invariance criteria in [START_REF] Schmidt | Invariance theory for in…nite dimensional linear control systems[END_REF], [START_REF] Curtain | Invariance concepts in in…nite dimensions[END_REF], [START_REF] Russell | A general necessary condition for exact observability[END_REF], [START_REF] Jacob | Exact observability of diagonal systems with a …nite-dimensional output operator[END_REF], [START_REF] Jacob | On controllability of diagonal systems with one-dimensional input space[END_REF], etc.), Brownian-driven control systems (exact terminal-controllability in [START_REF] Peng | Backward stochastic di¤erential equation and exact controllability of stochastic control systems[END_REF], approximate controllability in [START_REF] Buckdahn | A characterization of approximately controllable linear stochastic di¤erential equations[END_REF], [START_REF] Goreac | A Kalman-type condition for stochastic approximate controllability[END_REF], mean-…eld Brownian-driven systems in [START_REF] Goreac | Controllability properties of linear mean-…eld stochastic systems[END_REF], in…nite-dimensional setting in [START_REF] Fernández-Cara | On the approximate controllability of a stochastic parabolic equation with a multiplicative noise[END_REF], [START_REF] Sirbu | Null controllability of an in…nite dimensional SDE with state-and controldependent noise[END_REF], [START_REF] Barbu | Carleman estimates and controllability of linear stochastic heat equations[END_REF], [START_REF] Goreac | Approximate controllability for linear stochastic di¤erential equations in in…nite dimensions[END_REF], etc.), jump systems ( [START_REF] Goreac | A note on the controllability of jump di¤usions with linear coe¢ cients[END_REF], [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF], etc.). We refer to [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF] for more details on the literature as well as applications one can address using switch models.

The paper [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF] provides some necessary and some su¢ cient conditions under which approximate controllability towards null target can be achieved. In all generality, the conditions are either too strong (su¢ cient) or too weak (only necessary). Equivalence is obtained in [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF] for particular cases : (i) Poisson-driven systems with mode-independent coe¢ cients and (ii) continuous switching. In the present paper, we extend the work of [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF] and give explicit equivalence criterion for the general switching case. The approach relies, in a …rst step, as it has already been the case in [13, Theorem 1], on duality techniques (brie ‡y presented in Subsection 2.1). However, the intuition on this new criterion and its proof are extensively based on the recent ideas in [START_REF] Confortola | Backward stochastic di¤erential equations driven by a marked point process: an elementary approach, with an application to optimal control[END_REF]. The dual backward stochastic system associated to controllability is interpreted as a system of (backward) ordinary di¤erential equations in Proposition 12. Reasoning on this new system provides the necessary and su¢ cient criterion for approximate null-controllability for general switching systems with mode-dependent multiplicative noise (Theorem 6 whose proof relies on Propositions 13 and 14). As a by-product, we considerably simplify the proofs of [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF]Criteria 3 and 4] (in Subsection 2.3). Second, we give some elements on the stronger notion of [START_REF] Goreac | A Kalman-type condition for stochastic approximate controllability[END_REF] showing that this is no longer the case for general switching systems. Furthermore, we show that the condition exhibited in [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF]Proposition 3] in connection to approximate null-controllability is actually su¢ cient for general approximate controllability (see Condition 10). The proof follows, once again, from the deterministic reduction inspired by [START_REF] Confortola | Backward stochastic di¤erential equations driven by a marked point process: an elementary approach, with an application to optimal control[END_REF]. The theoretical results are illustrated on a model derived from repressed bacterium operon (given in [START_REF] Krishna | Stochastic simulations of the origins and implications of long-tailed distributions in gene expression[END_REF] and reduced in [START_REF] Crudu | Hybrid stochastic simpli…cations for multiscale gene networks[END_REF]). We begin with presenting the problem, the standing assumptions and the main results: the duality abstract characterization in Theorem 2, the explicit criterion in Theorem 6. We give a considerably simpli…ed proof of the results in [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF] in Subsection 2.3. We discuss the di¤erence between null and full approximate controllability in Subsection 2.4, Example 9 and give a su¢ cient criterion for the stronger notion of approximate controllability (Criterion 10). Section 3 focuses on an example derived from [START_REF] Krishna | Stochastic simulations of the origins and implications of long-tailed distributions in gene expression[END_REF] (see also [START_REF] Crudu | Hybrid stochastic simpli…cations for multiscale gene networks[END_REF]). The proofs of the results and the technical constructions allowing to prove Theorem 6 are gathered in Section 4.

The Control System and Main Results

We brie ‡y recall the construction of a particular class of pure jump, non explosive processes on a space and taking their values in a metric space (E; B (E)) : Here, B (E) denotes the Borel -…eld of E: The elements of the space E are referred to as modes. These elements can be found in [START_REF] Davis | Markov models and optimization[END_REF] in the particular case of piecewise deterministic Markov processes (see also [START_REF] Brémaud | Point processes and queues : martingale dynamics[END_REF]). To simplify the arguments, we assume that E is …nite and we let p 1 be its cardinal. The process is completely described by a couple ( ; Q) ; where : E ! R + and the measure Q : E ! P (E), where P (E) stands for the set of probability measures on (E; B (E)) such that Q ( ; f g) = 0: Given an initial mode 0 2 E; the …rst jump time satis…es P 0; 0 (T 1 t) = exp ( t ( 0 )) : The process t := 0 ; on t < T 1 : The post-jump location 1 has Q ( 0 ; ) as conditional distribution. Next, we select the inter-jump time T 2 T 1 such that P 0; 0 T 2 T 1 t = T 1 ; 1 = exp t 1 and set t := 1 ; if t 2 [T 1 ; T 2 ) : The postjump location 2 satis…es P 0; 0 2 2 A = T 2 ; T 1 ; 1 = Q 1 ; A ; for all Borel set A E: And so on. To simplify arguments on the equivalent ordinary di¤erential system, following [4, Assumption (2.17)], we will assume that the system stops after a non-random, …xed number M > 0 of jumps i.e. P 0; 0 (T M +1 = 1) = 1. The reader is invited to note (see Remark 5) that, for large M; the criteria given in the main result (Theorem 6) no longer depend on M (due to the …nite dimension of the mode and state spaces).

We look at the process under P 0; 0 and denote by F 0 the …ltration F [0;t] := f r : r 2 [0; t]g t 0 : The predictable -algebra will be denoted by P 0 and the progressive -algebra by P rog 0 : As usual, we introduce the random measure q on (0; 1) E by setting q (!; A) = P k 1 1 (Tk(!); T k (!) (!))2A ; for all ! 2 ; A 2 B (0; 1) B (E) : The compensated martingale measure is denoted by e q. (For our readers familiar with [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF], we emphasize that the notation is slightly di¤erent, the counting measure q corresponds to p in the cited paper and the martingale measure e q replaces q in the same reference. Further details on the compensator are given in Subsection 4.1.)

We consider a switch system given by a process (X(t); (t)) on the state space R N E; for some N 1 and the family of modes E. The control state space is assumed to be some Euclidian space R d ; d

1. The component X(t) follows a controlled di¤erential system depending on the hidden variable . We will deal with the following model (A is implicitly assumed to be 0 after the last jump).

(1)

dX x;u s = [A ( s ) X x;u s + Bu s ] ds + Z E C ( s ; ) X x;u s e q (ds; d ) ; s 0; X x;u 0 = x:
The operators A ( ) 2 R N N , B 2 R N d and C ( ; ) 2 R N N , for all ; 2 E. For linear operators, we denote by ker their kernel and by Im the image (or range) spaces. Moreover, the control process u : R + ! R d is an R d -valued, F 0 progressively measurable, locally square integrable process. The space of all such processes will be denoted by U ad and referred to as the family of admissible control processes. The explicit structure of such processes can be found in [18, Proposition 4.2.1], for instance. Since the control process does not (directly) intervene in the noise term, the solution of the above system can be explicitly computed with U ad processes instead of the (more usual) predictable processes.

The Duality Abstract Characterization of Approximate Null-Controllability

We begin with recalling the following approximate controllability concepts. De…nition 1 The system (1) is said to be approximately controllable in time T > 0 starting from the initial mode 0 2 E; if, for every F [0;T ] -measurable, square integrable 2 L 2 ; F [0;T ] ; P 0; 0 ; R N , every initial condition x 2 R N and every " > 0, there exists some admissible control process u 2 U ad such that E 0; 0 h jX x;u T j 2 i ": The system (1) is said to be approximately null-controllable in time T > 0 if the previous condition holds for = 0 (P 0; 0 -a.s.).

At this point, let us consider the backward (linear) stochastic di¤erential equation ( 2)

( dY T; t = h A ( t ) Y T; t R E (C ( t ; ) + I) Z T; t ( ) ( t ) Q ( t ; d ) i dt + R E Z T; t ( ) q (dt; d ) ; Y T; T = 2 L 2 ; F [0;T ] ; P 0; 0 ; R N :
Classical arguments on the controllability operators and the duality between the concepts of controllability and observability lead to the following characterization (cf. [13, Theorem 1]).

Theorem 2 ([13, Theorem 1]) The necessary and su¢ cient condition for approximate null-controllability (resp. approximate controllability) of ( 1) with initial mode 0 2 E is that any solution Y T; Remark 3 Concerning the operator A; it is assumed to be a switched matrix but it could also depend on (t; t ) or on all the times and marks prior to t: This is why, we implicitly assumed that A = 0 after the last jump (M th ) occurs. Similar assertions are true for C (otherwise, the backward equation ( 2) should be written with the compensator b q replacing ( t ) Q ( t ; d ).) The reader may also look at the end of Subsection 4.1.

Main Result : An Iterative Invariance Criterion

Before stating the main result of our paper, we need the following invariance concepts (cf. [START_REF] Curtain | Invariance concepts in in…nite dimensions[END_REF], [START_REF] Schmidt | Invariance theory for in…nite dimensional linear control systems[END_REF]).

De…nition 4 We consider a linear operator A 2R N N and a family

C = (C i ) 1 i k R N N . (i) A set V R N is said to be A-invariant if AV V: (ii) A set V R N is said to be (A; C)-invariant if AV V + k P i=1 Im C i :
We construct a mode-indexed family of linear subspaces of R N denoted by V M;n 0 n M; 2E by setting

(3) A ( ) := A ( ) Z E (C ( ; ) + I) ( )Q( ; d ) and V M;M = ker B ;
for all 2 E; and computing, for every 0 n M 1;

(4) V M;n the largest A ( ) ;

h (C ( ; ) + I) V M;n+1 : 2 E; Q ( ; ) > 0 i invariant subspace of ker B :
Here, V denotes the orthogonal projection operator onto the linear space V R N . Whenever there is no confusion at risk, having …xed the maximal number of jumps M 1; we drop the dependency on M (i.e. we write V n instead of V M;n for all 0 n M ).

Remark 5 (i) A simple recurrence argument shows that V M;n V M;m , for every 0 n m M . Furthermore, V M;M n = V M 0 ;M 0 n ; for all 0 n M M 0 : Moreover, since the dimension of ker B cannot exceed

N; V M;0 = V min(M;N p );0 :
(ii) This spaces do not depend on the choice of the controllability horizon T > 0: Therefore, if the approximate (null-)controllability is described by these sets, it is independent of the time horizon.

The main result of the paper is the following.

Theorem 6 The switch system (1) is approximately null-controllable (in time T > 0) with 0 as initial mode, if and only if the generated set V 0 0 reduces to f0g : The proof is postponed to Section 4. This proof uses the reduction of backward equations with respect to Marked point processes to a system of ordinary di¤erential equations given in [START_REF] Confortola | Backward stochastic di¤erential equations driven by a marked point process: an elementary approach, with an application to optimal control[END_REF]. In order to formulate this system (see Proposition 12), we need to explain some concepts and notations in Subsection 4.1. To prove necessity of the condition, one uses convenient feedback controls and the equivalence between invariance and the concept of feedback invariance (see Proposition 13). Su¢ ciency (given by Proposition 14) follows from (time-) invariance of convenient linear subspaces with respect to ordinary di¤erential dynamics.

Comparison With [13]

We begin with giving a di¤erent (and simpler) proof of (some of) the results in [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF]. Besides the general (abstract) characterization of approximate and approximate null-controllability, explicit invariance criteria were given in two speci…c settings.

(i) In the case without multiplicative noise C = 0; one notes that the subspaces V n (for 0 n < M ) do not depend on n: They reduce, in fact, to the largest A ( )-invariant subspace of ker B : Moreover, in this framework, A ( )-invariance and A ( )-invariance coincide and Theorem 6 yields the following.

Criterion 7 ([13, Criterion 4]) The system ( 1) is approximately null-controllable (with initial mode 0 2 E) if and only if the largest subspace of ker B which is A ( 0 ) -invariant is reduced to the trivial subspace f0g for all 0 2 E:

(ii) In the case of Poisson-driven systems with mode-independent coe¢ cients A and C; one works with the mode-independent operator

A := A R E (C ( ) + I) Q(d ).
The reader familiar with [13, Criterion 3] will note that the necessary and su¢ cient criterion concerns a notion of strict invariance. We get the same condition provided the system has the possibility to stabilize (the maximal number of jumps M N + 1 is allowed to exceed the dimension of the state space). Moreover, without loss of generality, one assumes that E is the support of Q:

Criterion 8 ([13, Criterion 3]) Let us assume that A 2 R N N ; B 2 R N d are …xed and C ( ) 2 R N N ;
for all 2 E and that ( ) Q ( ; d ) is independent of 2 E: Moreover, we assume that M N + 1. Then the associated system is approximately null-controllable if and only if the largest subspace V 0 ker B which is

(A ; [C ( ) V0 : 2 E])-invariant is reduced to f0g.
Proof. The reader will note that the V n spaces in (4) no longer depend on 2 E: They are obviously nondecreasing in n (see Remark 5). Since ker B R N ; it follows that, provided that M N + 1; one has

V 0 = V 1 (indeed, V 0 V 1 ::: V M = ker B and, whenever V k = V k+1
; for some 0 k M 1, it follows (by de…nition), that V j = V k ; for all j k: On the other hand, the inclusions cannot always be strict if M N + 1 by recalling that the dimension of ker B cannot exceed N ). Moreover, this space V 0 is the largest subspace V 0 ker B which is (A ; [(C ( ) + I) V0 : 2 E])-invariant which is the same as (A ; [C ( ) V0 : 2 E])invariant. The proof is complete by invoking Theorem 6.

Approximate or Approximate Null-Controllability

Using Riccati techniques, one proves (see [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF]Criterion 3]) that, for Poisson-driven systems with mode-independent coe¢ cients, approximate controllability and approximate null-controllability properties coincide. However, in the case of actual switching systems, the two notions have no reason to and do not coincide. This is illustrated by the following example.

Example 9

We consider the space dimension N = 4; the control dimension d = 2; E = f0; 1g, a switching rate = 1 and a transition probability Q ( ; 1 ) = 1; for 2 E: Moreover, we consider, for 2 f0; 1g ;

B = 0 B B @ 1 0 0 1 0 0 0 0 1 C C A ; A ( ) = 0 B B @ 0 0 0 0 0 0 0 0 1 + 0 0 0 0 2 0 0 1 C C A ; C ( ; 1 ) = 0 B B @ 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 C C A :
The reader is invited to note that ker B = span e 3 ; e 4 (standard vectors of the basis of R 4 ): Thus, simple

computations yield V 1 0 span e 4 ; V 1
1 span e 3 : Hence, V 0 0 = V 0 1 = f0g and the system is approximately null-controllable starting from every initial mode (if M 2). However, if one considers 0 = 0; assumes the mode can jump twice M = 2 and sets := 1 T1 T <T2 e 3 1 T2 T e 3 ; then one easily notes that (Y t ; Z t ) := 1 T1 t T;t<T2 e 3 1 T2 t T e 3 ; (1 t T ^T1 2 1 T1<t T ) e 3 obey the equation (2). To this purpose, it su¢ ces to note that A ( t )Y t + (C ( t ; 1 t ) + I) Z t = 0 on [0; T ^T2 ] : For every u 2 U ad ; Itô's formula (e.g. [15, Chapter II, Section 5, Theorem 5.1]) applied to the inner product

D X 0;u ; Y E on [0; T ] yields E 0;0 hD X 0;u T ; Ei = E 0; 0 h R T 0 hu t ; B Y t i dt i = 0: In particular, this implies that E 0;0 X 0;u T 2 E 0;0 h j j 2 i
> 0 and, thus, the system (1) is not approximately controllable (towards ).

In fact, the reader may note that the null-controllability property strongly depends on the initial mode (through the computation of V 0 0 as last step). A su¢ cient criterion (already available in [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF]) is that the largest subspace of ker B which is (A ( 0 ) ; [(C ( 0 ; ) + I) ker B : 2 E; Q ( 0 ; ) > 0]) invariant should be reduced to f0g : It turns out that asking this condition to hold true for all 0 2 E actually implies approximate controllability. (The proof is postponed to Section 4.) Condition 10 Let us assume that the largest (A ( ) ; [(C ( ; ) + I) ker B : Q ( ; ) > 0])-invariant subspace of ker B is reduced to f0g, for every 2 E: Then, for every T > 0 and every 0 2 E, the system (1) is approximately controllable in time T > 0:

Remark 11 The reader is invited to note that the notion of (A ( ) ; [(C ( ; ) + I) ker B : Q ( ; ) > 0])invariance and that of (A ( ) ; [(C ( ; ) + I) ker B : Q ( ; ) > 0]) -invariance coincide for subspaces of ker B . Second, according to [13, Criterion 3], the notions of approximate and approximate null-controllability coincide in the context of Poisson-driven systems with mode-independent coe¢ cients. Then, a careful look at [13, Example 4] provides an example of system which is approximately controllable without satisfying the su¢ cient condition given before.

3 Towards Applications A model. We will explain how the previous method can be applied in the study of stochastic gene networks. To this purpose, we consider the following reaction system describing a repressed bacterium operon model introduced in [ It is known ([5, Page 21]) that "RBS presents infrequent bursts of activity leading to rapid production of ElRib" and "RBS rapidly switches to 0 by the reaction RBS ! ?". To take into account these elements and keep the conservation law, we proceed as follows :

(1) as RBS switches to 0; D will be reset to 1 (hence, D + T rRN AP + RBS = 1);

(2) bursts (given by the reaction having k 7 as speed) will be considered as part of the stochastic updating of the continuous species and will have null-mean (i.e. they will multiply the martingale measure generated by the mode switching mechanism). In our toy-model, as RBS switches to 1, stochastic bursts on ElRib will a¤ect (in multiplicative way) the synthesis of P rotein (i.e. the reaction ElRib k8 ! P rotein): A toy mathematical system. The …rst condition leads to a mode space E = e 1 ; e 2 ; e 3 consisting of the standard vector basis of R 3 ; with a jump intensity and a transition measure Q e i ; e j = Q i;j 1 i;j 3 given by ( 6)

( ) = * 0 @ k 3 k 3 + k 4 k 5 1 A ; + > 0; for all 2 E; Q = 0 B @ 0 1 0 k 3 k 3 +k 4 0 k 4 k 3 +k 4 1 0 0 1 C A :
We are going to assume that the positive reaction speeds k 7 ; k 8 ; k 9 and k 11 depend on the mode (note that RBS is part of and intervenes to get ElRib) and, maybe, of external one-dimensional control parameters (temperature or catalysts). Since all the reactions concerning continuous components have one reactant, the resulting ODE will be linear (see [5, Eq. ( 28)]). A …rst order model for the control will give dx t = [A ( t ) x t + Bu t ] dt; where A is given by [START_REF] Davis | Markov models and optimization[END_REF]. Furthermore, in our toy model, let us assume that the external control focuses on regulation of ElRib (i.e. B = 1 0 0 t = e 1 ). We add to that the bursts (see item (2) above) to …nally get a (toy-)model of type [START_REF] Barbu | Carleman estimates and controllability of linear stochastic heat equations[END_REF] for which, for every ; 2 E;

(7) B = e 1 ; A ( ) = 0 @ k 8 ( ) 0 0 k 8 ( t ) k 9 ( ) 0 0 k 9 ( t ) k 11 ( ) 1 A ; C ( ; ) = 0 @ 0 0 0 k 7 ( ) 0 0 0 0 0 1 A ; k 7 ( ) = 1 e 3 ( ) :
Approximate null-controllability. The largest subspace of ker B which is A e 2 e 2 I; ker Binvariant reduces to span e 3 and the largest subspace of ker B which is A e 1 e 1 I; span(e 3 ) invariant is f0g (recall that k 8 and k 9 are reaction speeds and, thus, are strictly positive and so is ): Due to the structure of the transition measure Q, as soon as M 2, the system is approximately null-controllable starting from e 1 : Nevertheless, the space ker B being A e 3 k 8 e 3 k 5 C e 3 ; e 1 + I -invariant, constructions similar to Example 9 show that, provided e 3 is reachable in M jumps, the system is not approximately controllable.

Proof of the Results

Technical Preliminaries

Before giving the reduction of our backward stochastic equation to a system of ODE, we need to introduce some notations making clear the stochastic structure of several concepts : …nal data, predictable and càdlàg adapted processes and compensator of the initial random measure. The notations in this subsection follow the ordinary di¤erential approach from [START_REF] Confortola | Backward stochastic di¤erential equations driven by a marked point process: an elementary approach, with an application to optimal control[END_REF]. Since we are only interested in what happens on [0; T ] ; we introduce a cemetery state (1; ) which will incorporate all the information after T ^TM : It is clear that the conditional law of T n+1 given (T n ; Tn ) is now composed by an exponential part on [T n ^T; T ] and an atom at 1: Similarly, the conditional law of Tn+1 given (T n+1 ; T n ; Tn ) is the Dirac mass at if T n+1 = 1 and given by Q otherwise. Finally, under the assumption P 0; 0 (T M +1 = 1) = 1, after T M ; the marked point process is concentrated at the cemetery state.

We set E T : = ([0; T ] E) [ f(1; )g. For every n 1; we let E T;n E T n+1 be the set of all marks of type e = ((t 0 ; 0 ) ; :::; (t n ; n )) ; where (8) t 0 = 0; (t i ) 0 i n are non-decreasing;

t i < t i+1 ; if t i T ; (t i ; i ) = (1; ) , if t i > T; 80 i n 1;
and endow it with the family of all Borel sets B n . For these sequences, the maximal time is denoted by jej := t n . Moreover, by abuse of notation, we set jej := n : Whenever T t > jej ; we set we get an E T;n valued random variable, corresponding to our mode trajectories.

The …nal data is F [0;T ] measurable and, thus, for every n 0; there exists a B n =B R N measurable function E T;n 3 e 7 ! n (e) 2 R N such that: [START_REF] Goreac | A note on the controllability of jump di¤usions with linear coe¢ cients[END_REF] If jej = 1; then n (e) = 0: Otherwise, on T n (!) T < T n+1 (!) ; (!) = n (e n (!)) :

A càdlàg process Y continuous except, maybe, at switching times T n is given by the existence of a family of B n B ([0; T ]) =B R N -measurable functions y n such that, for all e 2 E T;n ; y n (e; ) is continuous on [0; T ] and constant on [0; T ^jej] and :

Let us now concentrate on the speci…c form of the jump contribution Z (to the BSDE (2)). We consider a càdlàg process Y continuous except, maybe, at switching times T n . Then, as explained before, this can be identi…ed with a family (y n ) : We construct, for every n 0; and Y Tn+1 can be obtained by simple integration of the previous quantity with respect to the conditional law of T n+1 ; Tn+1 knowing F Tn : Then, Z is given by z n (e; t; ) := b y n+1 (e; t; ) y n (e; t) : The coe¢ cient function A ( t ) is adapted and can be seen as follows: if jej = 1; then A = 0; otherwise, one works with A jej : Similar constructions hold true for C: In fact, the results of the present paper can be generalized to more general path-dependence of the coe¢ cients.

Reduction to a System of Linear ODEs

We consider the family of (ordinary) di¤erential equations ( 16)

8 > > > > < > > > > : y M (e M (!) ; ) = M (e M (!)) . For n M 1; y n (e n (!) ; T ) = n (e n (!)) ; dy n (e n (!) ; t) = A jen(!)j y n (e n (!) ; t) dt R E C
jen(!)j ; + I b y n+1 (e n (!) ; t; ) y n (e n (!) ; t) b q n en(!) (dt; d ) (= A jen(!)j y n (e n (!) ; t) dt P 2E ( jen(!)j )Q( jen(!)j ; ) C jen(!)j ; + I y n+1 (e n (!) (t; ) ; t) dt);

where we have used the notation (3). The following result adapts [4, Lemma 7] to our case.

Proposition 12 A càdlàg adapted process Y given by a family of functions (y n ) as in ( 12) is solution to (2) if and only if, for P-almost all ! and all 0 n M; it satis…es the system [START_REF] Jacob | On controllability of diagonal systems with one-dimensional input space[END_REF].

The proof is quasi-identical to the one of [4, Lemma 7]. The only di¤erence in our case is the presence of the term A jen(!)j y n (e n (!) ; t) dt which is, of course, classical. The results of [4, Lemma 7] apply directly if one assumes that ( ) > 0 for all 2 E (that is if there exists no absorbing state). Otherwise, we actually get an ODE of type dy n (e n (!) ; t) = A jen(!)j y n (e n (!) ; t) dt:

An Iterative Invariance-Based Criterion (Proof of Theorem 6)

As already hinted in [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF], the (approximate) controllability properties can be expressed with respect to invariance conditions. The equivalence between the dual (backward) stochastic equation ( 2) and the (backward) ordinary di¤erential system (16) yields the following approximate controllability criterion.

Proposition 13 If the system ( 1) is approximately null-controllable with 0 as initial mode, then the generated set V 0 0 reduces to f0g : Proof. Using classical results on the di¤erent notions of invariance (e.g. [START_REF] Schmidt | Invariance theory for in…nite dimensional linear control systems[END_REF]Theorem 3.2], see also [START_REF] Curtain | Invariance concepts in in…nite dimensions[END_REF]Lemma 4.6]), invariance is equivalent to feedback invariance. Thus, one gets the existence of a family of operators

F n ; 2 L V n ; V n+1 such that A ( ) + P 2E; Q( ; )>0 (C ( ; ) + I) F n ; V n
V n ; for all n 0: We begin with picking (an arbitrary) v 0 2 V 0 0 and de…ne 0 (t 0 ; 0 ) = v 0 : We proceed by setting, for every n 1 and e n 2 E T;n , n;en to be the unique solution of the ordinary di¤erential system 8 > > > > > < > > > > > : 16) with the particular choice of the …nal data such that n (e n ) = n;en (T ) : Since we have assumed the system (1) to be approximately null-controllable, Theorem 2 and Proposition 12 yield v 0 = 0: The proof is complete by recalling that v 0 2 V 0 0 is arbitrary.

d n;en (t) = A jenj + P 2E, Q( n ; )>0
At this point, the reader may want to note that these considerations involve one equation at the time. The invariant space obtained is then employed for the next equation and gives a coherent character to the system. The basic idea is to provide some kind of local in time invariance of the sets concerned. In [START_REF] Goreac | Algebraic invariance conditions in the study of approximate (null-) controllability of Markov switch processes[END_REF], this is done using Riccati techniques. But, except for special cases, the solvability of these stochastic schemes is far from obvious. Due to the ordinary di¤erential structure of the equivalent system [START_REF] Jacob | On controllability of diagonal systems with one-dimensional input space[END_REF], we are able to elude these techniques and work directly on the deterministic systems.

Proposition 14 Conversely, if the generated set V 0 0 reduces to f0g ; then the system ( 1) is approximately nullcontrollable with 0 as initial mode.

Proof. We begin with a solution of (2) for which Y belongs to ker B : We prove by descending recurrence that y n (e; t) 2 V n jej ; for all t 2 [0; T ] and all e 2 E T;n (starting from 0 ), where we use the structure ( 12): The assertion is obvious for n = M since, by notation, V M = ker B : We assume it to hold true for n + 1 M and prove it for n 0: By equation ( 16 (recall that y n is continuous). One recalls that V n is A ( ) ;

h (C ( ; ) + I) V n+1 : Q ( ; ) > 0 i -invariant,
for every 2 E. Hence, a fortiori, V n jej is A jej ; C ( jej ; ) + I ker B : Q jej ; > 0 -invariant. Our assumption implies that V n jej = f0g and approximate controllability follows.

  the dual system (2) for which Y T; t 2 ker B ; P 0; 0 Leb almost everywhere on [0; T ] should equally satisfy Y T; 0 = 0; P 0; 0 almost surely (resp. Y T; t = 0; P 0; 0 Leb a:s:).

5 ! ?; RBS k 7 !

 57 Partitioning and simplifying. The authors of[START_REF] Crudu | Hybrid stochastic simpli…cations for multiscale gene networks[END_REF] propose a partition of "species" according to which only ElRib; P rotein and F oldedP rotein are continuous. The averaging procedures in[5, Figure 4] simplify the model to ElRib + RBS ; ElRib k8 ! P rotein; P rotein k9 ! F oldedP rotein; P rotein k10 ! ?; F oldedP rotein k11 ! ?: Due to the conservation law of [D; R; DR; RN AP; DRN AP; T rRN AP ] one should have something like D + T rRN AP ' 1:

( 9 )

 9 e (t; ) := ((t 0 ; 0 ) ; :::; (t n ; n ) ; (t; )) 2 E T;n+1 : By de…ning[START_REF] Goreac | Approximate controllability for linear stochastic di¤erential equations in in…nite dimensions[END_REF] e n := ((0; 0 ) ; (T 1 ; T1 ) ; :::; (T n ; Tn )) ;

( 12 )(

 12 If jej = 1; then y n (e; ) = 0: Otherwise, on T n (!) t < T n+1 (!) ; Y t (!) = y n (e n (!) ; t) ; t T . Similar, an R N valued F-predictable process Z de…ned on [0; T ] E is given by the existence of a family of B n B ([0; T ]) B (E) =B R N measurable functions z n satisfying (13) If jej = 1; then z n (e; ; ) = 0: On T n (!) < t T n+1 (!) ; Z t (!; ) = z n (e n (!) ; t; ) ; for t T , 2 E. To deduce the form of the compensator, one simply writes b q (!; dt; d ) := X If n M; then b q n e (dt; d ) = (d ) 1 (dt) . If n M 1; b q n e (dt; d ) := ( jej )Q( jej ; d )1 jej<1;t2[jej;T ] Leb (dt) + (d ) 1 (dt) 1 (jej<1;t>T )[jej=1 ;

  e; t; ) := y n+1 (e (t; ) ; t) 1 jej<t

for every m 0 :

 0 Then, W := \ 0 m N W m is an A jej ; h C jej ; + I V n+1 : Q jej ; > 0 i invariantsubspace of the (at most N -dimensional) space ker B : Therefore, we have proven that y n (e; t) 2 V n jej : To complete our argument, one only needs to recall that, by assumption, V 0 0 = f0g and use Theorem 2 and Proposition 12.

4. 4

 4 Proof of Su¢ ciency Condition 10 for Approximate ControllabilityProof of Condition 10. In light of the Theorem [13, Theorem 1] and Proposition 12, one only needs to show that the only solution of (16) remaining in ker B is constant 0: One proceeds as in the Proof of Proposition 14 starting with a solution of[START_REF] Brémaud | Point processes and queues : martingale dynamics[END_REF] for which Y belongs to ker B and showing that y n (e; t) 2 V n jej ker B ; for all t 2 [0; T ]

  While the notions of approximate and approximate null-controllability are known to coincide for Poisson-driven systems with mode-independent coe¢ cients, we give an example (Example

AMS MSC: 93B05, 93B25, 60J75, Keywords: Approximate (null-)controllability Controlled Markov switch process Invariance Stochastic gene networks y Acknowledgement. The work of the …rst author has been partially supported by he French National Research Agency project PIECE, number ANR-12-JS01-0006. The work of the third author has been partially supported by the Grant PN-II-ID-PCE-2011-3-0843, no. 241/05.10.2011, Deterministic and stochastic systems with state constraints.

z Université Paris-Est, LAMA (UMR 8050), UPEMLV, UPEC, CNRS, F-77454, Marne-la-Vallée, France, Dan.Goreac@u-pem.fr x Faculty of Mathematics, "Alexandru Ioan Cuza" University, Bd. Carol I, no. 9-11, Iasi, Romania { Faculty of Mathematics, "Alexandru Ioan Cuza" University, Bd. Carol I, no. 9-11, Iasi, Romania (general) approximate controllability.

  One also sets n;en (t) = n;en (je n j _ t) to extend the solution for t 2 [0; T ]. Then, one easily notes that n;en (t) 2 ker B ; for all 1 n M , all e n 2 E T;n and all t 2 [0; T ] : Moreover, a simple glance at the construction shows that by setting y n (e n ; t) := n;en (t), for 1 n M , all e n 2 E T;n and all t 2 [0; T ] ; one gets the solution of (

C ( jenj ; ) + I F n jenj ; n;en (t) dt; je n j t T n;en (je n j) = n (e n ) ; if je n j < 1, 0; otherwise. and n+1 (e n (t; )) = 1 ( jen j )Q( jen j ; ) F n jen j ; n (e n ; t) 1 T t>jenj ; if ( jenj )Q( jenj ; ) > 0; 0; otherwise

  ), one has dy n (e; t) = A

	W m+1 :=	: 8 <	v 2 W

jej y n (e; t) X 2E ( jej )Q( jej ; ) C jej ; + I y n+1 (e (t; ) ; t) ! dt: We have assumed that y n (e; t) 2 ker B and, thus, [I ker B ] y n (e; t) = 0: We infer that A jej y n (e; t) + X 2E ( jej )Q( jej ; ) C jej ; + I y n+1 (e (t; ) ; t) 2 ker B : Hence, using the recurrence assumption, y n (e; t) is (for almost all t 2 [0; T ]); an element of the linear space W 0 := 8 < : v 2 ker B : 9w 2 V n+1 ; for all 2 E s.t. Q jej ; > 0 satisfying A jej v + P 2E; Q( jej ; )>0 C jej ; + I w 2 ker B 9 = ; : By repeating our argument, we prove that y n (e; t) is (for almost all t 2 [0; T ]); an element of the linear space m : 9w 2 V n+1 ; for all 2 E s.t. Q jej ; > 0 satisfying A jej v + P 2E; Q( jej ; )>0 C jej ; + I w 2 W m


Albert Y S Lam
email: ayslam@eecs.berkeley.edu

Longbo Huang
email: huang@eecs.berkeley.edu

Alonso Silva
email: asilva@eecs.berkeley.edu

Walid Saad

A Multi-Layer Market for Vehicle-to-Grid Energy Trading in the Smart Grid

In this work, we propose a multi-layer market for vehicleto-grid energy trading. In the macro layer, we consider a double auction mechanism, under which the utility company act as an auctioneer and energy buyers and sellers interact. This double auction mechanism is strategy-proof and converges asymptotically. In the micro layer, the aggregators, which are the sellers in the macro layer, are paid with commissions to sell the energy of plug-in hybrid electric vehicles (PHEVs) and to maximize their utilities. We analyze the interaction between the macro and micro layers and study some simplified cases. Depending on the elasticity of supply and demand, the utility is analyzed under different scenarios. Simulation results show that our approach can significantly increase the utility of PHEVs.

Introduction

The rising oil prices combined with the ongoing trend for developing environmental-friendly technological solutions, implies that electrically-operated vehicles will lie at the heart of future transportation systems. In particular, it is envisioned that plug-in hybrid electric vehicles (PHEVs), which are essentially electric vehicles equipped with storage devices, will constitute one key component towards realizing the vision of green, environment-friendly transportation networks. For instance, it is forecast that up to 2.7 million electric vehicles will be put on the road in the United States, by 2020 [START_REF] Becker | Electric vehicles in the united states: A new model with forecasts to 2030[END_REF].

The presence of energy storage devices implies that PHEVs can not only serve as a green means of transportation, but also, if properly configured, they can function as a "moving" energy reservoir that can store and, possibly, supply power back to the power grid. While current PHEV deployment are mostly concerned with grid-to-vehicle interactions, enabling two-way vehicle-to-grid (V2G) interactions between the grid and PHEVs, has recently started to receive considerable attention both in research and standardization agen-cies [START_REF] Brooks | PG&E and Tesla motors: Vehicle to grid demonstration and evaluation program[END_REF][START_REF]PAP11electric vehicle roaming scenarios[END_REF][START_REF]SGIP CoS: SAE J2836 use cases for communication between plug-in vehicles and the utility grid[END_REF][START_REF] Guille | A conceptual framework for the vehicle-to-grid (V2G) implementation[END_REF][START_REF] Sovacool | Beyond batteries: An examination of the benefits and barriers to plug-in hybrid electric vehicles (PHEVs) and a vehicle-to-grid (V2G) transition[END_REF] and is expected to lie at the heart of the emerging smart grid system.

Enabling V2G interactions has several advantages such as serving as backup power sources during outages or supplying ancillary services back to the grid for regulation services. However, in order to fully reap the benefits of V2G systems, several key challenges must be addressed at different level such as control, communications, charging behavior, implementation, and market mechanisms. In [START_REF] Pillai | Vehicle-to-grid for islanded power system operation in bornholm[END_REF], the authors propose a scheme that uses PHEV batteries to absorb the randomness in intermittent wind power generation. The authors in [START_REF] Wu | Vehicle-toaggregator interaction game[END_REF] study the use of game theory for providing frequency regulation through V2G operation. Using the PHEVs as storage units is studied and analyzed in [START_REF] Erol-Kantarci | Management of phev batteries in the smart grid: Towards a cyberphysical power infrastructure[END_REF] while communication architectures suitable for V2G systems are discussed in [START_REF] Matta | A cooperative aggregation-based architecture for vehicle-to-grid communications[END_REF]. Further, the authors in [START_REF] Sortomme | Optimal scheduling of vehicle-to-grid energy and ancillary services[END_REF] considers the problem of optimally providing energy and ancillary services using electric vehicles.

Clearly, most existing work are focused on implementation, communication, and energy transfer in V2G systems. However, the need for energy transfer and exchange from PHEVs to the grid has also an economical aspect that must be addressed. In this respect, the work in [START_REF] Saad | A noncooperative game for double auction-based energy trading between phevs and distribution grids[END_REF] sheds a light on this aspect by investigating the price and quantities exchanged if the PHEVs and the grid elements form an energy trade market. Beyond [START_REF] Saad | A noncooperative game for double auction-based energy trading between phevs and distribution grids[END_REF], little work seems to have been focused on the economics of V2G exchanges which are essential for a better understanding on the potential of using V2G in future power grid systems.

The main contribution of this paper is to propose a general framework and algorithm for studying the economics of the market emerging between PHEVs, aggregators, and the smart grid elements. To address this problem, we propose a multi-layered market mechanisms in which the agreggators, the PHEVs, and the grid elements can decide on the quantity and prices at which they wish to trade energy while optimizing the tradeoff between the benefits (e.g., revenues) and costs from this energy exchange. In this proposed market, first, the aggregators and the smart grid elements (e.g., substations) submit their reservation prices and bids so as to agree on a price and energy trading mechanism. These interactions are modeled using a double auction whose result is then fed back into the second layer, which deals with the management of PHEV resources at each aggregator. In this layer, within each PHEV group, the aggregator negotiates with the PHEVs to settle for an agreement on the resource usage. In particular, the aggregator will announce its energy buying price to the PHEVs, and each PHEV determines how much energy it is willing to supply to the aggregator. The outcome of this layer is directly linked to the previous market due to the fact that the aggregator has to carefully balance its earnings from the energy market and its payments to the PHEVs within its group. Hence, unlike existing work such as in [START_REF] Saad | A noncooperative game for double auction-based energy trading between phevs and distribution grids[END_REF], the proposed scheme depends, not only on pricing issues, but also on modeling the PHEVs-to-aggregator interactions (from an economical perspective) as well as on providing incentives for the PHEVs to participate in the foreseen market and, hence, it can leverage V2G, for improving the overall smart grid performance. We characterize the equilibria resulting from the proposed multi-layered market and we show their existence. Further, using linear approximation techniques we provide a large-system analysis on the economics of V2G energy trading. Using simulations, we assess the properties and performance of the energy trading mechanisms resulting from proposed scheme and we show that our approach can significantly increase the utility of PHEVs. The paper is organized as follows: In Section 2, we present the proposed system model. In Section 3, we analyze the system for different PHEV energy supply costs. Simulation results are discussed and analyzed in Section 4 while conclusions are drawn in Section 5.

Buyer k Auctioneer Aggregator n PHEV i (X k , B k ) (A n , S n ) p n a i

The Model and the Market Mechanism

Consider a smart grid system consisting of K grid elements (e.g., substations) with K = {1, . . . , K} denoting the set of all such elements. In this grid, N electric vehicles aggregators are deployed. We let N = {1, . . . , N } denote the set of all aggregators. Each aggregator n ∈ N manages a group of PHEVs denoted by I n = {1, . . . , I n }. In this model, we are particularly interested in smart grid elements that are unable to meet their demand and, hence, need to buy energy from alternative sources such as the PHEV aggregators. Hence, hereinafter, all grid elements are referred to as buyers while the aggregators are referred to as sellers.

The energy exchange process between the aggregators and the grid elements is modeled using a two-layered market model as shown in Fig. 1 with the utility company's control center acting as a middleman that handles the prospective energy trading mechanisms. On the one hand, at the first layer, referred to as the macro layer, the aggregators and the grid elements interact so as to trade energy. At this layer, the buyers wish to optimize their performance and meet their demand by buying energy from the PHEVs through the aggregators while the aggregators wish to strategically choose their price and quantity to trade so as to optimize their revenues. On the other hand, at the second layer, referred to as the micro layer, the aggregators must interact with the PHEVs so as to optimize the energy resources and provide incentives for the PHEVs to actually participate in the trade. Clearly, the outcomes of these two layers are coupled and, thus, any market solution must take into account this interlayer dependence. Below, we discuss and analyze, in details, the market operation at each layer.

Macro Layer

An auction is a mechanism for buying or selling goods or services by taking bids and then selling them to the highest bidders. The main approach to study this mechanism is game theory by considering the bidders as the players of this game, and their bids as their strategies. For more details on auction theory see [START_REF] Krishna | Auction Theory[END_REF]. For the completeness of this work, here we give an overview of the double auction mechanism [START_REF] Huang | A strategyproof multiunit double auction mechanism[END_REF][START_REF] Huang | Design of a multi-unit double auction e-market[END_REF][START_REF] Saad | A noncooperative game for double auction-based energy trading between phevs and distribution grids[END_REF]. In this layer, each potential seller or aggregator n ∈ N sends the quantity of energy A n that it intends to supply and its reservation price S n to the auctioneer. The reservation price sent by the potential sellers corresponds to the minimum price at which the seller is willing to sell its offered amount of energy. Each buyer k ∈ K proposes a bid B k and the quantity it requests, denoted by X k , to the auctioneer. Here, we are mainly focused on the interactions between buyers and sellers in a certain window of time during which the bids and reservation prices do not vary. This can correspond to an energy trading market in which decisions are based on medium or long-term energy needs such as in a day-ahead market. In each round, each aggregator n decides its own A n with the fixed S n . After receiving all A n 's, the auctioneer determines the price P (A) of the energy, where A = (A n , 1 ≤ n ≤ N ), and Q n (A), which corresponds to the total quantity sold by aggregator n, ∀n ∈ N , by a double auction.

In this work, we adopt a double auction mechanism based on [START_REF] Huang | A strategyproof multiunit double auction mechanism[END_REF][START_REF] Saad | A noncooperative game for double auction-based energy trading between phevs and distribution grids[END_REF][START_REF] Friedman | The Double Auction Market: Institutions, Theories, and Evidence[END_REF][START_REF] Huang | Design of a multi-unit double auction e-market[END_REF]. In this auction:

• we order the sellers in an increasing order of their reser-vation price. W.l.o.g. we consider

S 1 < S 2 < . . . < S N .
(1)

• we order the buyers in a decreasing order of their reservation bids. W.l.o.g. we consider

B 1 > B 2 > . . . > B K . (2)
• if two sellers (respectively, buyers) have equal reservation prices (bids), they are aggregated into one single "virtual" seller (or buyer).

• we generate the supply curve (selling reservation price S n versus the amount of energy put out for sale A n )

• we generate the demand curve (offered bids B k versus quantity needed X k ).

• we find an intersection point.

This intersection is at the level of a certain seller L and buyer M , such that B M ≥ S L and B M +1 < S L+1 . We find seller L and buyer M and the double auction dictates that the first L -1 and M -1 buyers will participate in the energy trading. We don't consider seller L and buyer M in this trade since it's a necessary condition for matching the total supply and demand while maintaining a strategy-proof mechanism [START_REF] Huang | Design of a multi-unit double auction e-market[END_REF].

Thus all sellers with index n < L and all buyers with index k < M become the participants in the double auction so as to clear the market. In consequence, the trading prices for the sellers and the buyers can be chosen within any point in the range [S L , B M ] [START_REF] Friedman | The Double Auction Market: Institutions, Theories, and Evidence[END_REF]. In this work, for any strategy choice A (or A n , ∀n ∈ N ) by the sellers (i.e. aggregators), given seller L and buyer M at the intersection, we consider all sellers i < L and buyers k < M trade at a price P (A), given by

P (A) = S L (A) + B M (A) 2 , (3)
where the dependence on A is due to the fact that each A can give different interaction points with the demand and supply curves, and thus we can have different L and M . At the end of the auction, numerous criteria can be used for determining the amount of traded energy between each one of the L -1 sellers and M -1 buyers. We adopt the approach of [START_REF] Huang | Design of a multi-unit double auction e-market[END_REF] in which the volume is divided in such a way as to ensure a strategy-proof auction. Using the method in [START_REF] Huang | Design of a multi-unit double auction e-market[END_REF] the total quantity Q n (A) sold by any PHEV group n, for a given choice A is:

Q n (A) =    A n if M -1 k=1 X k ≥ n j=1 A j , (A n -Ψ) + if n = L -1, 0 if n > L -1, (4)
where (x) + = max{0, x} and Ψ is the oversupply, i.e., Ψ =

L-1 j=1 A j - M -1 k=1 X k .

Micro Layer

In this layer, each aggregator announces a price p n to its PHEVs by

p n = γ n P (A), ∀n ∈ N , (5)
where 0 < γ n < 1 is the commission rate. The price difference, P (A)-p n , is the commission (i.e., cost of management) earned by aggregator n from its managed PHEVs. Each aggregator can make a profit in this way and thus it has an incentive to help its PHEVS participate in the market. This provides an incentive for an aggregator to maximize its PHEVs' profits. By utility maximization, each PHEV i ∈ I n determines its available supply a i ∈ [0, a max i ] according to its utility where a max i characterizes the amount of energy the owner of PHEV i can afford to sell, i.e., after reserving enough for its own use. For the same type of vehicle, a PHEV which needs more reservation for its proper operation has a lower a max i . We have

A n = In i=1 a i , ∀n ∈ N . ( 6
)
Let a n = (a i , 1 ≤ i ≤ I n ) be the strategy of the PHEVs in group i. Aggregator n determines the actual quantity q i (a n , Q n (A)) allocated to PHEV i in group n proportional to a i by

q i (a n , Q n (A)) = a i i∈In a i × Q n (A), (7)
and thus

Q n (A) = In i=1 q i (a n , Q n (A)), ∀n ∈ N . (8)
Consider that each PHEV i ∈ I n imposes a cost of discharging its battery to supply energy to its aggregator. We denote this cost by c i (a), where a is the amount of energy sold by PHEV i. We assume that during each transaction, each PHEV will try to maximize its profit by choosing the amount of energy a i to be

a i = arg max ai {p n (a n ) -c i (a i )}.

Market Mechanism

The interaction between the macro and micro layers can be seen as a market mechanism or an algorithm, shown in Algorithm 1, which is used to find the market equilibrium P * , A * n . It terminates when a pre-determined number of iterations t max has been reached or the percentage change of the market price is less than a certain threshold ξ.

As we can see in simulation later, Algorithm 1 performs very efficiently and converges within a few steps.

Algorithm 1 Market Mechanism

1: For all k, buyer k submits its bid B k and its requested amount X k to the auctioneer 2: t ← 1 3: repeat

4:

For all n, aggregator n submits its reservation price S n and its proposed supply A n to the auctioneer

5:

The auctioneer implements a double auction and determines the market price P (t) and the allocated quantity Q n for aggregator n for all n 6:

For each aggregator n, the selling price p n is announced to its PHEVs

7:

For each PHEV i, it determines its proposed selling amount a i by maximizing its utility according to p n and returns a i back to its aggregator 8:

Each aggregator n sums up all a i 's from its PHEVs 9:

t ← t + 1 10: until t > t max or | P (t) -P (t-1)

P (t) | < ξ

Linear Approximation for Large systems

In a practical smart grid, both the number of PHEVs and smart grid element are expected to be large. In this respect, it is of interest to analyze the impact of the presence of large numbers of buyers and aggregators on the overall proposed market mechanism. Therefore, here, we consider the situations when N and M are sufficiently large such that the corresponding supply and demand curves can be approximated by a linear function, depending on the distribution of aggregators' reservation price (buyers' bids). We assume that the reservation prices S n from each one can be ordered nicely into a line with each point being one unit apart. Fig. 2 shows one example of the supply and demand curves, each of which is approximated by one single linear function. In the following, since the focus of this paper is on the supply side, we study different types of supply curves while always keeping the demand curve of the same type.

Linear Cost Function with Homogeneous PHEVs

In this subsection, we consider that the cost function of PHEV i is a linear function with respect to the amount of energy it provides, i.e., c i (a) = η i a, within a certain interval [0, a max i ]. If the amount of energy to be sold exceeds a max i , the cost will become infinite. Note that this case also takes into account the inconvenience cost (e.g., when the PHEV does not have enough energy to operate normally). Then its utility function is given by u i (a) = (γ n P -η i )a. The problem PHEV i needs to address is the following: We note that, a PHEV can always decide not to participate in the market in which case it maximum utility will be u * i = 0. As a result, the maximum utility in ( 9) is always nonnegative. In this case, the solution a * i of ( 9) is

u * i = maximize ai∈[0,a max i ] u i (a i ). (9)
a * i = a max i if η i ≥ p n , 0 else. ( 10
)
We can then subdivide the set of PHEVs I n in two disjoint sets I

n ∪ I (2) n = I n , where a * i = 0, ∀i ∈ I (1)
n , and

a * i = a max i , ∀i ∈ I (2)
n . Thus, we obtain

A n = i∈In a i = i∈I (1) n a i + i∈I (2) n a i . (11)
Since for all i ∈ I

n , a * i = 0, then i∈I (1) n a i = 0, and in consequence

A n = i∈I (2) n a i = i∈I (2) n a max i . ( 12
)

Linear Approximation

Consider the linear case as in Fig. 2(b). The PHEVs are price takers and the supply and demand curves are given by

Supply(P, Q) = αP, (13)
Demand(P, Q) = Q 0 -βP. ( 14
)
Here Q 0 is the total demand from all the buyers and P is the price determined from the double auction in the macro layer. Also, α will depend on I

(2) n for all aggregator n. In that case, the equilibrium price P * and the quantity sold Q * can be determined when the supply meets the demand, i.e.,

Supply(P * , Q * ) = Demand(P * , Q * ) ⇒ αP * = Q 0 -βP * ,
or equivalently, when

P * = Q 0 α + β . ( 15
)
The utility for each PHEV i in group n will be thus given by

1. If η i ≥ γnQ0 (α+β) then a * i = 0 and u * i = 0. 2. If η i < γnQ0 (α+β) then a * i = a max i and u * i = (γ n P * -η i ) a * i = γ n Q 0 (α + β) -η i a max i . (16)
The total utility U n of aggregator n is given by

U n = i∈I (2) n γ n Q 0 (α + β) -η i a max i . ( 17
)
From this simple example, we can deduce the following properties:

1. If the supply slope of a market 1 is higher than that of a market 2, i.e., α 1 > α 2 , then the utility gained in market 1 is smaller than that in market 2.

2. If the demand slope of a market 1 is higher than that of a market 2, i.e., β 1 > β 2 , then the utility gained in market 1 is smaller than that in market 2.

3. If the total possible demand of a market 1 is higher than that of a market 2, i.e., Q 1 0 > Q 2 0 , then the utility gained in market 1 is greater than that in market 2.

Quadratic Cost Function

We first recall that under the quadratic cost model, each PHEV i will supply the following amount of energy:

a * i = p n (a n ) -η i 2υ i a max i 0 . (18)
In order to make the analysis easier, below we assume that a * i ≤ a max i for all i. Then, we have:

a * i = p n (a n ) -η i 2υ i , and
A * n = C n p n (a n ) -d n , (19)
where

C n = i 1 2υ i and d n = i η i 2υ i . (20)
In this case, A * n is the supply from one aggregator and A * n is the slope of the supply curve, i.e., α = A * n . Thus, we have by ( 15) that:

P * = Q 0 A * n + β . (21)
Hence, we see that there is an iteration process of the market price, which approximates the actual price iteration:

• In iteration t, with A n (t) computed, we obtain the optimal price P * (t) = Q0 An(t)+β .

• In iteration t + 1, we compute the new supply quantity by (19), i.e., A n (t + 1) = C n γ n P * (t)d n .

Based on the above observation, we have the following simple lemma characterizing the necessary conditions under which there exists market equilibriums, i.e., ( 19) and (21) both hold.

Lemma 1. The following conditions are necessary for the above iteration process converges to an market equilibrium (P * , A * n ):

(β + d n ) 2 -4(d n β -C n Q 0 ) ≥ 0, ∀n ∈ N (22) (β -d n ) 2 + 4C n Q 0 ≥ 0, ∀n ∈ N . (23)
Proof. In equilibrium, this price must result in a supply that is exactly equal to the resulting A n , i.e.,

A n = C n Q 0 γ n A n + β -d n . (24)
This gives rise to the following condition on A n :

A 2 n + (β + d n )A n + βd n -C n γ n Q 0 = 0. ( 25
)
Note that the above argument also shows an interesting fact that there is an implicit iteration for the market price P as follows:

P * = Q 0 C n γ n P * -d n + β . (26)
This similarly implies that the fixed point should be:

C n γ n P * 2 + (β -d n )P * -Q 0 = 0. (27)
Since both (25) and ( 27) are quadratic functions, we see that the only way there exists a market equilibrium is when ( 22) and (23) hold.

In the next section, we will show how the algorithm evolves through simulation and demonstrate the intuition behind the iteration process.

Simulation Results

For simulations, we consider a smart grid network in which a number of aggregators sell their energy surplus to smart grid elements (buyers) through a utility company. The simulation setting is as follows. Each aggregator manages a certain number of PHEVs, randomly generated in the range of [500,1000]. Each PHEV has a maximum battery capacity of 250 miles with power consumption 22kWh per 100 miles [START_REF] Silva | Evaluation of energy consumption, emissions and cost of plug-in hybrid vehicles[END_REF][START_REF] Motors | Roadster innovations: Motor[END_REF] out of which an arbitrary amount of energy, between 30 and 100 miles, is reserved for the PHEV's private use. The reservation prices of the aggregators are uniformly selected in [START_REF] Matta | A cooperative aggregation-based architecture for vehicle-to-grid communications[END_REF]50] dollars/MWh while the buyers' bids are randomly chosen from [START_REF] Huang | Design of a multi-unit double auction e-market[END_REF]60]

Small Numbers of Buyers and Aggregators

We simulate the cases with small numbers of buyers and aggregators. We consider 5 buyers (K = 5) in each case and we compare our two-layer approach with a greedy approach, in which each PHEV always proposes to sell a max i . Fig. 3 shows the average results of 1000 independent simulation runs for each case. Figs. 3(a) and 3(b) present the average utility per aggregator corresponding to the linear and quadratic cost functions, respectively. We can see that our approach always gives higher average utility than the greedy one, as shown in Figs. 3(a) and 3(b). In the cases of linear cost, we can see that the average utility start by increasing with N but then, it starts to decrease when the number of aggregators reaches that of buyers (N = 6). This result is due to the fact that, for small N , an increase in the number of participating aggregators leads to a larger amount of energy sold which, subsequently, improves the average utility. However, when N ≥ 6, an increase in the number of aggregators N will yield a decrease in the settled price which leads to a decrease in the utility. In the cases with quadratic cost, the average utility increases with N on the grounds that more aggregators participate in the market resulting in a larger amount of total energy sold. Hence, in general, the equilibrium trading price decreases with N as more aggregators lead to an increased competition, which subsequently imposes a lower market price.

Fig. 3(c) shows the average number of iterations required to reach an equilibrium. Clearly, as more aggregators participate in the market, the number of iterations till convergence increases. Moreover, Fig. 3(c) shows that the convergence time is faster in the case with quadratic cost. With a linear cost function, each PHEV i takes either 0 or a max i in each iteration, and thus, the algorithm is more like to oscillate more around the equilibrium point before convergence. With a quadratic cost function, due to the concavity of the utility, the algorithm moves toward the equilibrium in a smoother manner which is further corroborated in the subsequent simulations.

Large Numbers of Buyers and Aggregators

Here, we simulate cases in which a large number of buyers (K = 1000) and aggregators (N = 1000) are deployed so as to verify the analytical results induced from the linear approximation studied in Section 3.1. As previously mentioned, when N (K) increases, the supply (demand) curve approaches a linear function as all random numbers are generated uniformly. We first study the results with a fixed demand curve (i.e. with β and Q 0 fixed) and they correspond to the situations when the value evolves in a particular simulation. Fig. 4 1 shows the results for linear PHEV cost functions when the algorithm iterates. Fig. 4(a) gives the total utility computed from double auction for each iteration while we have the corresponding supply and demand curves in Fig. 4(b) ( the part shows intersection points only). We can see that the total utility decreases with the supply slope (α). For example, we consider iterations 1 and 2. α 1 is larger than α 2 and we have the utility gained in iteration 1 is smaller than that in iteration 2. We also study the quadratic PHEV cost functions and the similar results are shown in Fig. 5. 1 However, with the quadratic cost function, the algorithm converges faster and smoother. Next we study the results for six different demand curves with a fixed supply curve (i.e. α fixed). Fig. 6 1 shows the six cases with a fixed Q 0 . The simulation also aligns the results deduced in Section 3.1: the larger β, the smaller the utility.

Conclusion

We have studied the V2G energy trading market, in which PHEVs sell their excessive energy to some loads in the distribution network. We have proposed a multi-layer system to coordinate the trading where those PHEVs in a close geographical area are represented by an aggregator. In the macro layer, the energy buyers and the aggregators engage in a double auction to determine the trading price and the actual energy quantity sold for each aggregator. In the micro layer, each aggregator helps its managed PHEVs maximize their utilities. A mechanism is proposed to coordinate the interaction between the macro and micro layers. We have analyzed the system performance when the numbers of buyers and aggregators are large. Simulation results show that our mechanism is always better than the greedy approach and verify some of our analytical results.

Figure 1 :

 1 Figure 1: The two-layer market model. The numbers in the figure correspond to the step numbers in Algorithm 1.

Figure 2 :

 2 Figure 2: Supply and demand curves

  dollars/MWh. Each buyer requests energy demand with the amount chosen in [20, 60] MWh. The commission rate is set to γ n = 0.91, ∀n ∈ N . Each PHEV i has random cost function parameters η i ∈ [10, 50] and υ i ∈ [1000, 2000] for quadratic cost function and β i = 0 for the linear cost function. The algorithm always starts by setting a i = a max i , ∀i ∈ I n , ∀n ∈ N .

Figure 3 :

 3 Figure 3: Basic simulations for small numbers of buyers and aggregators.

Figure 4 :

 4 Figure 4: Linear cost function with 1000 buyers (K) and 1000 aggregators (N)

Figure 5 :

 5 Figure 5: Quadratic cost function with 1000 buyers (K) and 1000 aggregators (N)

Figure 6 :

 6 Figure 6: Fixed Q 0 with 1000 buyers (K) and 1000 aggregators (N)

The numbers in Subfigure (b) correspond to iteration/case numbers in Subfigure (a). For clearer demonstration, In Subfigure (b), only the curves corresponding to the first few iterations/cases are given.