Bertrand Chopard
email: bertrand.chopard@u-paris10.fr.

Thomas Cortade Z
email: thomas.cortade@univ-lorraine.fr.

Eric Langlais
email: eric.langlais@u-paris10.fr.

Béatrice Dumont

Damage rules and the patent hold-up problem : An analysis of Article L. 615-7

Keywords: lost pro…t rule, unjust enrichment rule, intellectual property rights, patent litigations, pretrial negotiations JEL classi…cation: 03, L1, L4, D8, K2, K4

This paper provides an analysis of two damage rules (Lost Pro…t versus Unjust Enrichment) introduced in the French Code de la Propriété Intellectuelle in 2007 (Loi du 27 Octobre 2007, Art. L. 615-7). We use a simple sequential game where both the decisions to infringe and to enforce the patent, as well as the decisions to accomodate, settle or litigate the case, and the outputs decisions (Cournot competition) are endogenous. We characterize the equilibria associated with each rule, and compare their properties. We show that: 1/ the Unjust Enrichment rule provides Patentees with higher damages compensation than the Lost Pro…t one; however, 2/ Lost Pro…t induces more deterrence of infringement, and is associated with less trials than Unjust Enrichment; 3/ Unjust Enrichment may deter the Patentee to enforce his right; 4/ when there is a positive probability that the case settles, Patentee's expected utility is higher under Lost Pro…t than under Unjust Enrichment.

Introduction

The reform of the French Code de la Propriété Intellectuelle passed in 2007 has provided Courts with a set of rules that may be used for assessing the value of damages awarded to plainti¤s, retaining a large de…nition for the loss of business: "Pour …xer les dommages et intérêts, la juridiction prend en considération les conséquences économiques négatives, dont le manque à gagner, subies par la partie lésée, les béné…ces réalisés par le contrefacteur et le préjudice moral causé au titulaire des droits du fait de l'atteinte [...]."

(Loi du 29 octobre 2007; for both industrial property (Art. L. 615-7, L.622-7, L.623-28 and L.716-4) and copyright (Art. L.331-1-3))"

French Jurisdictions have now the opportunity to consider the loss of business and pro…ts borne by the patentee (Lost Pro…ts rule), as well as the illegal bene…ts obtained by the infringer (Unjust Enrichment rule). The main motivation for such a reform was that the ancient code (Loi No 68-1 du 2 janv. 1968, art. 57) only considered that the damages paid by the infringer to the patentee must be set according to the value of forfeiting goods (i.e. the illegal pro…ts obtained by the infringer if they have been successfully sold). The practical consequences were that the compensations obtained by plainti¤s were generally set at a very low level in France [START_REF] Baudry | Typlogie des contentieux français en matière de contrefaçon. Analyse statistique pour la période 1990-2004[END_REF], and it may be suspected that this has prevented many patentee(s) to sue their infringer(s), given the high costs and delays associated with legal disputes in IPR infringement cases.

In this paper, we analyze some of the e¤ects of Art. L. 615-7, in link with the use of both the Lost Pro…t and Unjust Enrichment rules1 . In our model, we focus on the case of a Intellectual Property Rights that normally would be licensed. We will assume that IPR are probabilistic, i.e. there is a risk that the litigated IPR be found invalid; this is now the standard assumption adopted in the literature (see Anton andYao, 2003, 2006;[START_REF] Choi | Alternative damage rules and probabilistic intellectual property rights: unjust enrichment, lots pro…ts, and reasonable remedies[END_REF][START_REF] Crampes | Litigation and settlement in patent infringement cases[END_REF][START_REF] Farrell | How strong are weak patents?[END_REF][START_REF] Meurer | The settlement of patent litigation[END_REF][START_REF] Schankerman | Damages and injunctions in protecting intellectual property[END_REF][START_REF] Shapiro | Injunctions, hold-up, and patent royalties[END_REF]. It has strong empirical supports, since many studies have reported the dramatic increase in the number of patent litigation cases over the two last decades [START_REF] Lanjouw | The enforcement of intellectual property rights: a survey of the empirical literature[END_REF][START_REF] Bessen | The patent litigation explosion[END_REF][START_REF] Baudry | Typlogie des contentieux français en matière de contrefaçon. Analyse statistique pour la période 1990-2004[END_REF], and [START_REF] Allison | Empirical analysis of the validity of litigated patents[END_REF] found a …gure close to 50% for the plainti¤s'rate of success considering all litigated patents. On the other hand, our model departs in several respects with those existing in the literature: 1/ we consider for both players a richer set of strategies than usually considered: both the decision to enforce the patent, and the decision to infringe it, are endogenous here; 2/ we assume that pretrial negotiations operate under asymmetric information between litigants, the legal costs of the Infringer being private information. Such an assumption may be seen as an analytical short-cut (see also Chopard and ali, 2010) capturing that parties opposed in a litigation may initially be unequally endowed in terms of skill or ability to predict the verdict at trial.2 This is consistent with the assumption that the occurrence of a trial is not certain, nor is certain the verdict in case of trial.

Section 2 introduces the basic framework. Section 3 discusses the properties of the equilibria when Lost Pro…t is awarded by Courts, and section 4 considers the same issues when Unjust Enrichment are applied. Section 5 compares the di¤erent e¤ects of these damage rules at equilibrium: on 1/ the value of damages awarded to plainti¤s in case they prevail at trial, 2/ the level of deterrence of IPR infringement, 3/ the level of deterrence of IPR enforcement, 4/ the frequency of trials, and 5/ the level of plainti¤s'total expected pro…ts associated with IPR litigations. Section 6 concludes.

Model and assumptions

We consider here that the Patentee holds an IPR on a drastic innovation. The game between the Infringer and the Patentee has four main stages. At stage 1, Nature chooses the legal cost (i.e. type) of the Infringer c e which is a private information. The Patentee only knows that the value of the Infringer's cost is a random variable c e 2 [c ¯e; c e ] distributed according to a cumulative function G(c e ) and a density g(c e ). In contrast, the Patentee's litigation costs, denoted c h , are common knowledge. At stage 2, the Infringer has to decide whether he enters and imitates the patent without a license (chooses Infringe), and competes à la Cournot with the Patentee (the potential market is a duopoly); or he does not enter and earns 0 (chooses Non Infringe) such that the Patentee earns M (the potential market is a monopoly). In case of infringement, the game reaches the next to last stage. At stage 3, the Patentee chooses either Accommodate to adapt the entry of the Infringer (thus, they earn their duopoly pro…ts, respectively A e for the Infringer and A h for the Patentee), or Litigate such that the Patentee earns at least the market pro…t L h , while the Infringer earns at best L e , knowing that the case may be defended at trial or be settled. When the case is litigated, the game reaches the last stage. At stage 4, the pretrial bargaining process takes place: the Patentee makes a (take-it-or-leave-it) licensing price O¤ er `to the Infringer, corresponding to a price for the patent agreement (or fees for the normal use of the patent). On the one hand, if the Infringer chooses Accept, they settle amicably their dispute -and they earn their duopoly pro…ts, up to the cost and price of licensing, respectively u e (`) = L The market demand is linear with a demand price given by: P = a b(y h + y e ), where a; b > 0 and y h ; y e denoting the quantity produced by the Patentee and the Infringer, respectively. The technology of production entails constant marginal costs of production, respectively: k < a (after innovation occurs, for both …rms). Note that when the patent is not infringed, the Patentee produces y M = a k 2b and earns his monopoly pro…t M = b a k 2b 2 , while the Infringer produces nothing and earns 0. We will also make the following assumptions, in order to let aside technical di¢ culties (existence, uniqueness of equilibrium) which are not at the heart of our point here: The next assumption means that Plainti¤'s claim is credible at trial:

Assumption 2: D c h > 0.
Before proceeding to the analysis, let us discuss two assumptions of our model, that may be seen as restrictive. First, we consider a screening game. The reason is that when legal costs are private information, their signalling role typically does not exist under the fee shifting rule introduced here (see Chopard and ali, 2010); however, our objective was to analyse the pure e¤ects of damages rules, and thus a complete analysis of fee shifting, or the study of policies substituting damages with legal costs, are beyond the scope of this paper. Second, we introduce a one-shot pretrial negotiations game; but this is wlog, since the generality of this set up for pretrial negotiations is well known in the L&E literature (see [START_REF] Daughety | Settlement[END_REF][START_REF] Spier | Litigation[END_REF].

Equilibria under the Lost Pro…t rule

The two following propositions give the results for the Lost Pro…t rule, under which D LP = M L h . By L i LP for i = h; e we will denote the value of …rm i's pro…t at equilibrium under the Lost Pro…t rule. Proof. The proof consists in three main stages.

Proposition 1 If ( L e ) LP c e M ( L h ) LP ,
-At stage 4, assume the Patentee believes that all types of Infringer have chosen Infringe (we will verify this is consistent). Hence, assume he o¤ers a licensing price `> 0, associated with a cut-o¤ value c `2]c ¯e; c e [ satisfying u e (`) = u e (c `) with D LP = M L h ; thus any Infringer c e < c rejects `(a trial occurs with probability G(c `)), while any Infringer c e c `accepts `(the case is settled with probability 1 G(c `)). The maximization of: = c e +c h ).

U h (`; c `) = (1 G(c `)) u h (`) + G(c `)u h (c h ) s:t: u e (`) = u e (c
-At stage 3, if the Patentee chooses Litigate and the Infringer chooses Infringe whatever his type, Cournot competition between both …rms yields the output levels

y L h LP = a k b(3 ) ; y L e LP = (1 )(a k) b(3 )
which solve the system 3 :

(

1 ) @ L h @y h = 0 (1)
@ L e @y e + @ L h @y e = 0

(2) 3 The best response functions are de…ned as: On the other hand, if the Patentee chooses Accommodate and the Infringer chooses Infringe, the symmetric Cournot-Nash equilibrium at the market stage corresponds to the output level

y L h = arg max
y A = a k 3b = y A h = y A e
which is the solution to the (usual) system 4 :

@ L h @y h = 0 @ L e @y e = 0
Thus, the Patentee chooses Litigate rather than

Accommodate if U h (` ; c e ) L h LP + M L h LP G(c e )c h + (1 G(c e )) c e A h
; this inequality holds under assumption 2, given that the Lost Pro…t rule implies M > L h LP > A h . -At stage 2, the Infringer knows that at the pretrial negotiation stage he will obtain at least

u e (` ) = L e LP ` (if Infringe is chosen) whatever his type, rather than 0 (if Non Infringe is chosen). Thus, Infringe is the best decision if L e LP ` 0 , ( L e ) LP c e M ( L h ) LP
. If this condition holds, then all Infringers'types choose Infringe, and thus Patentee's belief is also consistent.

Proposition 1 illustrates 5 a situation with a strong strategic interaction between the litigants: when the patent is weak -in the sense that Remark that the threat of a trial introduces a distortion in the sharing of the market output between …rms: the Patentee produces more than the Infringer y L h LP > y L e LP under the Lost Pro…t rule, despite identical marginal costs. The …rst order conditions (1)-( 2) illustrate the general property that along the equilibrium path where the Patentee chooses Litigate (hence, either the case is settled, or there is a trial), his best response function is not a¤ected under Lost Pro…t by the occurrence of a trial as compared to the standard Cournot-Nash equilibrium (same FOC). In 4 The best response functions are de…ned as: contrast, the Infringer's best response function displays lower incentives to produce ( @ L e @ye + @ L h @ye < @ L e @ye ). In word, the threat of a trial produces a negative externality at the market stage, and the Lost Pro…t rule posits this externality on the Infringer.

y A h = arg max y h n A h = (P k)y h s.t. P = a b(y h + ye)
The following proposition considers cases associated with a strong patent:

Proposition 2 If > ( L e ) LP c e M ( L h ) LP ,
U h ( ~; c`) = (1 G(c e )) L h LP + ~ + G(c e ) L h LP + M L h LP c h It is easy to see that U h ( ~; c`) = L h LP + M L h LP G(c e )c h + (1 G(c e ))c e > A h (given assumption 2) since : M > L h LP > A h
. But this cannot be an equilibrium; to see why, let us investigate the second case. Case 2: assume that the Patentee makes a licensing o¤er `> ãt the pretrial stage. Then, the Infringer chooses (Infringe) if his type is c e ce ; otherwise, he chooses Non Infringe. Then, conditionally on the Infringer's type, the Patentee chooses Litigate (conditional on Infringe) and produces y L h LP , or he produces his output y M (conditional on Non Infringe). This yields him:

U h (`; ce ) = (1 G(c e )) M + G(c e ) L h LP + M L h LP c h
Once more it is easy to see that ), infringement may be deterred at least when the Infringer has a high legal cost. Moreover, proposition 2

U h (`; ce ) = (1 G(c e )) M +G(c e ) L h LP +G(c e ) M L h LP c h > A h ,
shows interestingly that the distortion in pro…ts, that follows from the distortion in outputs levels due to the threat of a trial, is not monotonic in : it increases for 2]0; 1=3] (i.e. for small enough), and decreases for 2]1=3; 1] (i.e. for large enough). However, under Cournot competition where …rms produce close substitutes, infringement always entails a dilution of monopoly pro…t, since at equilibrium we have: M L h + L e LP (with a strict equality only for = 1, for which L h LP = M and L e LP = 0).

Equilibria under the Unjust Enrichment rule

The three next propositions focus on the Unjust Enrichment rule, for which D U E = L e . By L i U E for i = h; e we will denote the value of …rm i's pro…t at equilibrium under the Unjust Enrichment rule.

Proposition 3 If

A h ( L h ) U E +G(c e )(c h +c e ) ( L e ) U E c e ( L e ) U E 1 c e ( L e ) U E
, the next pro…le of strategies is an equilibrium:

-the Patentee chooses Litigate, produces y L h U E = y L e LP , and makes a licensing o¤ er whose value is ` = Proof. We only give a sketch of the proof, since it is very close to the one of proposition 1.

-At stage 4, assume the Patentee expects that all types of Infringer have chosen Infringe. The maximization of: which solve the system 6 :

U h (`; c `) = (1 G(c `)) u h (`) + G(c `)u h (c h ) s:t: u e (`) = u e (c
@ L h @y h + @ L e @y h = 0 (3)
(1 ) @ L e @y e = 0 (4)

But the Patentee chooses Litigate rather than Accommodate only if U h (` ; c e )

L h U E + L e U E G(c e )c h + (1 G(c e )) c e A h , A h ( L h ) U E +G(c e )(c h +c e ) ( L e ) U E c e ( L e ) U E
, which may not hold given assumption 2, since under the Unjust Enrichment rule we have now M > A h > L h U E . -At stage 2, the Infringer knows that if the Patentee enforces his right, then at the pretrial negotiation stage he will obtain at least u e (` ) = L e U E ` (if Infringe is chosen) whatever his type, rather than 0 (if Non Infringe is chosen). Thus, Infringe is the dynamic consistent decision

if L e U E ` 0 , 1 c e ( L e ) U E
. If this condition holds, Patentee's belief is also consistent.

Remark that according to the …rst order conditions (3)-(4), the negative externality of a trial is now shifted to the Patentee at the market stage, under the Unjust Enrichment rule: the threat of a trial introduces a distortion in the sharing of the output between …rms, explaining that the Patentee now produces less than the Infringer: y L h U E < y L e U E . Remark also that proposition 3 means that under the Unjust Enrichment rule, if the patent is weak enough but in a sense not too weak, it is always enforced since it is always infringed: the Patentee has always the opportunity to extract the licensing fees ` = L e U E + c e > 0. Once more, all Infringer's types have thus an incentive to choose Infringe rather than Non Infringe.

The next proposition discusses the case with a strong patent.

Proposition 4 If > max 1 c e ( L e ) U E ; A (1 G(ĉe)) M G(ĉe)(( L h ) U E c h ) G(ĉe)( L e ) U E
, where ĉe 2 [c ¯e; c e [ satis…es ĉe = ( 1) L e U E , the next pro…le of strategies is an equilibrium: -the Patentee produces y M = a k 2b conditional on c e > ĉe ; he chooses Litigate and produces y L h U E = y L e LP conditional on c e ĉe , and makes a licensing o¤ er `> ^= L e U E .

6 The best response functions are now:

y L h = arg max
`if U h `; ĉe = (1 G(ĉ e )) M + G(ĉ e ) L h U E + L e U E c h A , A (1 G(ĉe)) M G(ĉe)(( L h ) U E c h ) G(ĉe)( L e ) U E
. Under assumption 2 this condition may not hold since under the Unjust Enrichment rule we have now M > A h > L h U E . Hence the result.

The consequence of proposition 4 is that, when the patent is (too) strong, infringement may be deterred, under the Unjust Enrichment rule, at least in case where the Infringer pertains to the highest types. As shown in the next proposition, the counterpart of the two previous results is that the Patentee may prefer to accommodate the infringement of his right under the Unjust Enrichment rule. The proof is straightforward since at stage 3, the Patentee chooses Accommodate

rather than Litigate if U h (` ; c e ) L h U E + L e U E G(c e )c h + (1 G(c e )) c e < A h , < A h ( L h ) U E +G(c e )(c h +c e ) ( L e ) U E c e ( L e ) U E
. Hence, the result:

Proposition 5 If < A h ( L h ) U E +G(c e )(c h +c e ) ( L e ) U E c e ( L e ) U E
, the next pro…le of strategies is an equilibrium: the Patentee chooses Accommodate, the Infringer chooses Infringe whatever his type, and both …rms produce y A = a k 3b .

Proposition 5 means that when the patent is too weak, enforcing his right may be a strategy too costly for the Patentee under the Unjust Enrichment rule, albeit it is always infringed; thus, it may be worth to accommodate the infringement. Note that this equilibrium occurs under the Unjust Enrichment rule (while it does not under the Lost Pro…t rule) despite the Patentee's claim is credible at trial.

Discussion

In the next graph, we report for each rule the outcome associated with the equilibrium strategies of the Infringer and of the Patentee 7 , for di¤erent intervals of (patent strength):

Graph 1

By conditional infringement, we mean that some Infringer's types do infringe (those having the smallest c e ) while others do not. By conditional trial, we mean that a trial occurs conditional on Infringer's types who infringe. Except for the highest values of where the outcome is the same under both rules, we observe that the features of equilibria associated with the di¤erent intervals is generally very di¤erent 8 . More generally, we obtain …ve main conclusions which allow to shed some lights on the consequences of the 2007 reform.

The …rst conclusion is that the Unjust Enrichment rule does not yield more deterrence than the Lost Pro…t -yet, we obtain the opposite result: the threshold of infringement under Lost Pro…t is smaller than under Unjust Enrichment, implying that the …rst rule is more e¤ective in deterring infringement than the second.

The second conclusion is that the Unjust Enrichment rule has another unfortunate deterrent e¤ect the Lost pro…t has not: the Patentee may be deterred from enforcing his right under the

) 2 + 9 + (1 G(c e ))c e G(c e )c h A h 1 (3 ) 2 0 has been performed for (1 G(c e ))c e G(c e )c h A h = 0.
As a matter of comparison, [START_REF] Lanjouw | The enforcement of intellectual property rights: a survey of the empirical literature[END_REF] found that the ratio of legal costs over R&D expenditures is close to 20%. 8 It can be shown that this structure is also obtained for di¤erent values of the parameters.

Unjust Enrichment rule soon as the patent is weak enough. The driving force is that, despite the claim of the Patentee is credible at trial, his total expected pro…t (utility) associated with the enforcement strategy is smaller than his market pro…t when infringement is accommodated.

The third conclusion is that the frequency of trial is higher under the Unjust Enrichment rule;

we give a general proof of this result in the next proposition.

Proposition 6 The Unjust Enrichment rule yields a frequency of trials which is as least as large as the Lost Pro…t rule.

Proof. Let us …rst compare the equilibria of propositions 1 and 3 (i.e. assume a solution where the case may be settled out of Court under both rules). In this case, a trial occurs with the same frequency under both rules: G(c e ).

Now, let us compare the equilibria of propositions 2 and 4 (i.e. assume a solution where the Infringer may choose Non Infringe with some positive probability under both rules). By construction, we have:

ce ĉe = L e LP M L h LP (1 ) L e U E
and it can easily be veri…ed that the sign of ce ĉe is the same as the sign of h( ) = 2 + 10 9 .

As g(0) = 0, h(1) = 0 and h( ) This result also implies that the Unjust Enrichment rule is associated with a larger (private) legal cost for IPR litigation cases, than the Lost Pro…t rule.

is
The fourth conclusion is focused on the size of the damages awarded to the plainti¤/Patentee when he prevails at trial: the Unjust Enrichment rule warrants higher damages than the Lost Pro…t9 :

Proposition 7 When a trial occurs at equilibrium, then D LP < D U E for realistic values of

(1 G(c e ))c e G(c e )c h A h . Proof. Given that L e U E = L h LP , we have D LP D U E = M 2 L h LP .
Thus it is easy to verify that the sign of M 2 L h LP is the same as the sign of g( ) = 1 6 + 2 , with g(0) = 1 and g(1) = 4. Moreover g 0 ( ) = 6 + 2 < 0, for any 2 [0; 1]. Hence, it comes that for any < 3 2 p 2(' 0:17157), then g( ) > 0 =) D LP > D U E , while for any > 3 2 p 2, then g(

) < 0 =) D LP < D U E .
On the other hand, the numerical resolution of the inequality U h (` ; c e ) ( Note that [START_REF] Bessen | The patent litigation explosion[END_REF] …nd that in around 1=4 of IPR litigation cases both the infringer and the patentee are innovators (and thus

c e A h is close to c h A h
), and that in a majority of cases, the plainti¤ is a large …rm (thus that are realistic (< 0), the probability threshold for which the Patentee litigates the case rather than accommodates it, is larger than 0:17157. Hence the result.

The …fth conclusion is connected to Patentee's total expected gain in case of litigation (expected utility), and appears as less clear-cut.

Proposition 8 i) When the case settles with a positive probability at equilibrium, Patentee's expected utility is larger under the Lost Pro…t rule than under the Unjust Enrichment rule. ii) When at least some Infringers'types do not infringe the patent at equilibrium, Patentee's expected utility under the Lost Pro…t rule may be larger or smaller than under the Unjust Enrichment rule.

Proof. i) We have:

U h (` ; c e ) U h (` ; c e ) = L h LP L h U E + M L h LP L e U E (5)
The …rst bracketed term is positive, whereas the second (proposition 6) may be either positive or negative. However, it can be veri…ed that:

U h (` ; c e ) U h (` ; c e ) = (c e ĉe ) since L h LP = L e U E > L e LP = L h U E .
Hence the result ii) We have:

U h (`; ce ) U h `; ĉe = (G(ĉ e ) G(c e )) M + c h +G(c e ) L h LP G(ĉ e ) L h U E + G(c e ) M L h LP G(ĉ e ) L e U E (6)
still remembering that L h LP = L e U E > L e LP = L h U E . Thus, the term on the …rst line is always positive, while the term of the second line is positive only when G(ĉe) G(ce) (> 1) is not too large. Finally, the term on the third line is negative given proposition 7 and G(ĉe) G(ce) > 1.

Note that the comparison performed here requires that we focus on values of for which the same equilibrium outcome occurs whatever the rule; but this may have no sense for some values Infringer. In a sense, the advantage of the Lost pro…t rule is explained by the market discipline it imposes to the Infringer, which prevents him from producing a large quantity despite he holds the same production costs as the Patentee. But note that case i) requires that there is a positive probability that the case settles amicably (and thus, infringement is never deterred).

In contrast, part ii) of proposition 8 means that the superiority of the Lost Pro…t rule may not hold soon as the probability that infringement is deterred is positive. Under conditional infringement, the choice/comparison between both rules re ‡ects the existence of a trade-o¤ 11 : 1 0 In contrast, case i) only occurs for small values of c e M (for example at 1%). The result is available on request. 1 1 This is a rough interpretation of the di¤erence between the terms on the second and third lines in condition (6), which may be written as: G(ce)

L h LP + M L h LP G(ĉe) L h U E + L e U E .
roughly speaking, the Lost Pro…t rule is associated with a larger probability that the Patentee earns his monopoly pro…t, whereas the Unjust Enrichment rule yields a higher probability that higher damages are awarded in case of trial.

Conclusion

For practical purposes, French Jurisdictions may be prone to choose between one rule or the other just because of the available and quality of information regarding Infringers'pro…ts or Patentees' pro…ts. Indeed, as the reform of the French IPR law passed in 2007, a major argument that some legal commentators put in favor of the Unjust Enrichment rule was that it is consistent with the idea that "infringement must not pay". Moreover, the introduction of the Unjust Enrichment rule was seen as a substitute for punitive damages (despite the European Commission forbid their use) since it allows the disgorgement of the illegal bene…ts obtained by the infringer, thus creating the conditions to improve the deterrence of infringers 12 . However, our analysis shows that these ideas are not correct. The Unjust Enrichment rule entails less deterrence and at the same time, is associated with more trials, than the Lost Pro…t rule. Moreover, a main ‡aw of the Unjust

Enrichment rule is that it may also deter the Patentee from enforcing his right (which we …nd not possible to occur under Lost Pro…t). Finally, regarding the preservation of Patentees total (expected) pro…t, the comparison is less obvious, no rule being better than the other.

Our paper has also shown the central role of the patent quality/strength, which was supposed to be exogenous here; but for a given level of , the features of the equilibrium are di¤erent between both rules most of the time, which makes harder their comparison. To overcome these problems, we will consider the issue of an endogenous patent strength in future research.

  u h (`) = L h + `for the Patentee. On the other hand, if the Infringer chooses Reject, then a trial occurs. The Court sets for the Patentee/plainti¤ with probability 2]0; 1[, i.e. claims that the patent is valid. The verdict consists in a damage that the Infringer must pay to the Patentee, denoted as D 2 D LP = M L h ; D U E = L e depending on whether the Lost Pro…t rule or the Unjust Enrichment rule is applied; thus, the expected pro…t for each party is respectively u e (c e ) = L e D c e for the Infringer, and u h (c h ) = L h + D c h for the Patentee (i.e. duopoly pro…ts minus legal cost incurred at trial, up to the expected award D).

Assumption 1 :

 1 the ratio 1 G g is decreasing on [c ¯e; c e ], and satis…es: 1 G g jc ¯e > c h + c e and 1 G g j ce < c h +c ¯e.

  where c e satis…es 1 G g jc e = c e + c h , the next pro…le of strategies is an equilibrium: -the Patentee produces y L h LP = a k b(3 ) , chooses Litigate, and makes the licensing o¤ er ` = M L h LP + c e > 0. -the Infringer chooses Infringe, produces y L e LP = (1 )(a k) b(3 ) , and chooses Reject if c e 2 [c ¯e; c e [, or Accept if c e 2 [c e ; c e ].

  solution (` ; c e ) corresponding to the best licensing price ` = M L h LP + c e > 0 (given by u e (c e ) = u e (` )) associated with the cut-o¤ value c e (which satis…es 1 G g jc e

  y h fU h (` ; c e ) s.t. P = a b(y h + ye)g y L e = arg max ye fue(ce) s.t. P = a b(y h + ye)g

D

  ( L e ) LP c e M ( L h ) LP -the Patentee always enforces his property right since it is always infringed. As the Patentee litigates and settles, he has the opportunity to extract a licensing price ` and obtains a payo¤ larger than at trial, L h LP +` . The counterpart is that all Infringer's types have an incentive to chose Infringe rather than Non Infringe, and the highest types c e 2]c e ; c e ] obtain an informational rent in settling the case ( LP c e for all c e 2]c e ; c e ] ).

  P k)ye s.t. P = a b(y h + ye) o 5 In a sense, holding a strong patent is neither necessary nor su¢ cient for enforcing the patent.

  and if it exists ce 2 [c ¯e; c e [ which satis…es ce = , the next pro…le of strategies is an equilibrium: -the Patentee produces y M = a k 2b conditional on c e > ce ; he chooses Litigate and produces y L h LP = a k b(3 ) conditional on c e ce , and makes a licensing o¤ er `> ~= M L h LP +c e . -the Infringer chooses (Infringe, Reject) and produces y L e LP if c e 2 [c ¯e; ce [; while he chooses Non Infringe if c e 2 [c e ; c e ]. Proof. We only provide here a brief sketch of the proof. If > ( L e ) LP c e M ( L h ) LP , then at stage 2 all Infringer's types cannot choose Infringe since u e (` ) < 0, and thus the equilibrium of proposition 1 breaks. Then, consider the threshold value ce for which u e (c e ) = 0 , L e LP M L h LP = ce (assuming that ce 2]c ¯e; c e [) and let us compare two alternative situations. Case 1: at stage 4, assume that the Patentee o¤ers ~(< ` ) de…ned as ~= L e LP = M L h LP + ce ; then the Infringer chooses either (Infringe, Accept) if his type satis…es c e ce , or (Infringe, Reject) if his type satis…es c e < ce . When the Patentee chooses Litigate at stage 3, this yields him:

  given assumption 2 and given that (1 G(c e )) M + G(c e ) L h LP > A h . Then we have:U h ( ~; ce ) U h (`; ce ) = (1 G(c e )) L h + L e LP M .It is easy to verify that the sign of M L h + L e LP is the same as the sign of f ( ) = 1+2 3 2 , with f (0) = 1 and f (1) = 0; moreover, f ( ) increases for 2 [0; 1=3[ and decreases for 2]1=3; 1]. This implies M L h + L e LP > 0 for all 2 [0; 1[, and M L h + L e LP = 0 for = 1. Hence, the result.Proposition 2 illustrates that when the patent is strong enough (i.e. > ( L e ) LP c e M ( L h ) LP

  + c e > 0. -the Infringer chooses Infringe, produces y L e U E = y L h LP , and chooses Reject if c e 2 [c ¯e; c e [, or Accept if c e 2 [c e ; c e ].

  solution (` ; c e ) corresponding to the best licensing price ` = L e U E + c e > 0 (which solves u e (c e ) = u e (` )) still associated with the cut-o¤ value c e (which satis…es 1 G g jc e = c e + c h ). -At stage 3, if the Patentee chooses Litigate and the Infringer chooses Infringe, Cournot competition between both …rms yields the output levels y L h U E = (1 )(a k) b(3 ) ; y L e U E = a k b(3 )

,M

  y h fU h (` ; c e ) s.t. P = a b(y h + ye)g y L e = arg max ye fue(ce) s.t. P = a b(y h + ye)g -the Infringer chooses Infringe, produces y L e U E = y L h LP , and then he chooses Reject if his type is c e 2 [c ¯e; ĉe [; while he chooses Non Infringe if his type is c e 2 [ĉ e ; c e ].Proof. Let us simply highlight that at stage 2, it comes now that if L Non Infringe is the dynamic consistent decision at least for the highest Infringer's types, conditional on the fact that the Patentee chooses Litigate. The end of the proof is very similar to the one of proposition 2, excepted that ĉe = (1) L e U E is the new cut-o¤ value which allows to separate Infringer's types between the decisions Infringe (and Reject) and Non Infringe.Whether the Patentee proposes ^= L e U E or `> ^depends on the sign of U h ( ^; ĉe ) U h `; ĉe = (1 G(ĉ e )) < 0. Thus, the equilibrium is such that the Patentee o¤ers

7

  We have numerically solved the inequalities (see proposition 1) ; the numerical resolution of the inequality (see proposition 3) U h (` ; c e ) A h , 9(1

  convex on ]0; 1[, we obtain that ce < ĉe ) G(c e ) G(ĉ e ) (c e < ĉe ) G(c e ) < G(ĉ e ) for any 2 [0; 1[, and ce = ĉe at = 1).

  has been performed under di¤erent assumptions about the value of (1 G(c e ))c e G(c e )c h A h , making a distinction between cases with negative values as provided in the next table:

( 1 G

 1 (c e ))c e G(c e )c h A h < 0). Thus, our simulations suggest that for values of (1 G(c e ))c e G(c e )c h A h

  ) case ii) must only be considered for a consistent comparison -which means that only a large value for ( 0:74597) is relevant (see graph 1) 10 . Part i) of proposition 8 shows interestingly that focusing on the size of the damages awarded to the Patentee but ignoring the feedback e¤ects at the market stage, is misleading when we turn to the comparison of Patentee's total expected utility (pro…ts). The di¤erence U h (` ; c e ) U h (` ; c e ) is driven by two terms which have opposite signs (see (5)): on the one hand, we have L h LP L h U E > 0; on the other hand, we found that = (D LP D U E ) < 0. Thus, we have shown that despite D LP < D U E , the Lost Pro…t rule has a large and positive feedback e¤ect at the market stage, which is bene…cial to the Patentee, and detrimental to the

  1 G(c e ))c e G(c e )c h

	A	=	20%	10%	3%	2%	1%
	h
		:60943 :52203 :43221 :41523 :39638
	and positive ones, as in the next table:
	(1 G(c e ))c e G(c e )c h A	= 0%	1%	2%	3%	5%	9%
	h
		:375 :37268 :37033 :36794 :36303 :35264

The

reform also introduces a third possible rule, Ideal Royalties: "Toutefois, la juridiction peut, à titre d'alternative et sur demande de la partie lésée, allouer à titre de dommages et intérêts une somme forfaitaire qui ne peut être inférieure au montant des redevances ou droits qui auraient été dus si le contrefacteur avait demandé l'autorisation d'utiliser le droit auquel il a porté atteinte." (Loi du 29 octobre 2007; for both industrial property : Art. L.. We let it aside for further research.

There is some empirical support for this assumption[START_REF] Osborne | Who should be worried about asymmetric information in litigation?[END_REF].

Note that this implies that ` < ` .


Noha Ibrahim
email: noha.ibrahim@imag.fr

Frédéric Le Mouël
email: frederic.le-mouel@insa-lyon.fr

A Survey on Service Composition Middleware in Pervasive Environments

Keywords: middleware, service oriented architecture, service composition, pervasive environment, classification

The development of pervasive computing has put the light on a challenging problem: how to dynamically compose services in heterogeneous and highly changing environments? We propose a survey that defines the service composition as a sequence of four steps: the translation, the generation, the evaluation, and finally the execution. With this powerful and simple model we describe the major service composition middleware. Then, a classification of these service composition middleware according to pervasive requirements -interoperability, discoverability, adaptability, context awareness, QoS management, security, spontaneous management, and autonomous management -is given. The classification highlights what has been done and what remains to do to develop the service composition in pervasive environments.

Introduction

Middleware are enabling technologies for the development, execution and interaction of applications. These software layers are standing between the operating systems and applications. They have evolved from simple beginnings -hiding network details from applications -into sophisticated systems that handle many important functionalities for distributed applications -providing support for distribution, heterogeneity and mobility. SOA middleware [START_REF] Erl | Service-Oriented Architecture (SOA): Concepts, Technology, and Design[END_REF] is a programming paradigm that uses ``services'' as the unit of computer work. Service-oriented computing enables the development of loosely coupled systems that are able to communicate, compose and evolve in an open, dynamic and heterogeneous environment. A serviceoriented system comprises software systems that interact with each other through well-defined interfaces.

If middleware were designed to help manage the complexity and heterogeneity inherent in distributed systems, one can imagine the new role middleware has to play in order to respect the evolution from distributed and mobile computing to pervasive one. Hardly a day passes without some new evidence of the proliferation of portable computers in the marketplace, or of the growing demand for wireless communication. Support for mobility has been the focus of number of experimental systems, researches and commercial products, and that since several decades. The mission of mobile computing is to allow users to access any information using any device over any network at any time. When this access becomes to every information using every device and over every network at every time, one can say that mobile computing has evolved to what we now call pervasive computing [START_REF] Satyanarayanan | Pervasive Computing: Vision and Challenges[END_REF].

In pervasive environments where SOA has been adopted, functionalities are more and more modeled as services, and published as interfaces. The proliferation of new services encourages the applications to use these latter, all combined together. In this case, we speak of a composite service. The process of developing a composite service is called service composition [START_REF] Dustdar | A survey on web services composition[END_REF]. Composing services together is the new challenge awaiting the SOA middleware [START_REF] Erl | Service-Oriented Architecture (SOA): Concepts, Technology, and Design[END_REF] meeting the pervasive environments [START_REF] Satyanarayanan | Pervasive Computing: Vision and Challenges[END_REF]. Indeed, the variety of service providers in a pervasive environment, and the heterogeneity of the services they provide require applications and users of these kind of environments to develop models, techniques and algorithms in order to compose services and execute them. The service composition needs to follow some

IJCSI IJCSI

2 requirements [START_REF] Niemela | Survey of requirements and solutions for ubiquitous software[END_REF][33] [START_REF] Salminen | Lightweight middleware architecture for mobile phones[END_REF] in order to resolve the challenges brought by pervasivity.

Several surveys [START_REF] Alamri | Classification of the state-of-the-art dynamic web services composition techniques[END_REF][7] [START_REF] Rao | A Survey of Automated Web Service Composition Methods[END_REF][31] [START_REF] Mascolo | Survey of Middleware for Networked Embedded Systems[END_REF] dealt with service composition. Many of them [START_REF] Dustdar | A survey on web services composition[END_REF][31] classified the middleware under exclusive criteria such as manual versus automated, static versus dynamic, and so on.

Others [START_REF] Alamri | Classification of the state-of-the-art dynamic web services composition techniques[END_REF][22] [START_REF] Mascolo | Survey of Middleware for Networked Embedded Systems[END_REF] classified the service composition middleware under different domains such as artificial intelligence, formal methods, and so on. But none of these surveys proposed a generic reference model to describe the service composition middleware in pervasive environments.

In this article, we propose:

• a generic service composition middleware model, the SCM model, a novel way to describe the service composition problem in pervasive environments, • a description of six middleware architectures using the SCM model as a backbone and highlighting the strength and weakness of each middleware, • and finally, a classification of these latter under pervasive requirements identified by the literature to be essential for service composition in pervasive environments.

The outlines are as follows. In section 2, we define the service composition middleware (SCM) model and explain its modules. In section 3, we describe six service composition middleware by mapping their architecture to the SCM model. In section 4, we classify these middleware according to the pervasive requirements we identify. Finally, section 5 concludes our work and gives research directions to the service composition problem.

SCM: Service Composition Middleware Model

Based on several studies [START_REF] Rao | A Survey of Automated Web Service Composition Methods[END_REF][24] that resolve the service composition process problem into several fundamental problems, we define a service composition middleware as a framework providing tools and techniques for composing services. We define a service composition middleware model, SCM model, as an abstract layer, general enough to describe all existing service composition middleware. The SCM model is at a highlevel of abstraction, without considering a particular service technology, language, platform or algorithm used in the composition process. The aim of this definition is to give the basis to discuss similarities and differences, advantages and disadvantages of all available service composition middleware and to highlight the nowadays existing lacks concerning the service composition problem in pervasive environments.

As depicted Figure 1, the SCM interacts with the application layer by receiving functionality requests from users or applications [5][7]. SCM needs to respond to the functionality requests by providing services that fulfill the demand. These services can be atomic or composite.

The Service Repository represents all the distributed service repository where services are registered. The SCM interacts with the Service Repository to choose services to compose.

The SCM is split into four components: the Translator, the Generator, the Evaluator, and the Builder. The process of service composition includes the following phases:

1. Applications specify their needed functionalities by sending requests to the middleware. These requests can be described with diverse languages or techniques. The request descriptions are translated to a system comprehensible language in order to be used by the middleware. Most systems distinguish between external specification languages and internal ones. The external ones are used to enhance the accessibility with the outside world, commonly the users. Users can hence express what they need or want in a relatively easy way, usually using semantics and ontologies. Internal specification corresponds more to a formal way of expressing things and Figure 1 SCM model uses specific languages, models, and logics, usually for SOA a generic service model. Some research [START_REF] Mokhtar | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF] provide a translation mechanism of the available service technologies and service descriptions into one model. Others, such as SELF-SERV [START_REF] Constantinescu | Large Scale, Type-Compatible Service Composition[END_REF], propose a wrapper to provide a uniform access interface to services [START_REF] Fujii | Semantics-based dynamic service composition[END_REF]. These middleware usually realize transformation from one model to another or from one technology to another. The technologies are predefined in advance and usually consist of the legacy ones.

If new technology models appear in the environment, the Translator will need to be expanded to take these technologies into consideration.

Another family of research [START_REF] Chakraborty | Service Composition for Mobile Environments[END_REF] [START_REF] Sirin | Semiautomatic Composition of Web Services using Semantic Descriptions[END_REF] do not provide the Translator module as they use common model to describe all the services of the environment. They use common description languages such as DAML-S -recently called OWL-S [START_REF]OWL-S: Semantic Markup for Web Servicesr[END_REF], -for describing atomic services, composed services and user queries. 2. Once translated, the request specification is sent to the Generator. The Generator will try to provide the needed functionalities by composing the available service technologies, and hence composing their functionalities. It tries to generate one or several composition plans with the same or different technology services available in the environment. It is quite common to have several ways to do a same requirement, as the number of available functionalities in pervasive environments is in expansion. Composing service is technically performed by chaining interfaces using a syntactically or semantically method matching. The interface chaining is usually represented as a graph or described with a specific language. Graph based approaches [START_REF] Fujii | Semantics-based dynamic service composition[END_REF][10], represent the semantic matching between the inputs and outputs of service operations. It is a powerful technique as many algorithms can be applied upon graphs and hence optimize the service composition. Number of languages have been proposed in the literature to describe data structure in general and functionalities offered by devices in particular. If some languages are widely used, such as XML, and generic for multiple uses others are more specific to certain tasks as service composition, orchestration or choreography such as Business Process Execution Language (BPEL4WS or BPEL [START_REF] Juric | Business Process Execution Language for Web Services[END_REF]) and OWL-S [START_REF]OWL-S: Semantic Markup for Web Servicesr[END_REF]. 3. The Evaluator chooses the most suitable composition plan for a given context. This selection is done from all the plans provided by the Generator. In pervasive environments, this evaluation depends strongly on many criteria like the application context, the service technology model, the quality of the network, the non functional service QoS properties, and so on. The evaluation needs to be dynamic and adaptable as changes may occur unpredictably and at any time. Two main approaches are commonly used: the rule-based planning [START_REF] Casati | Adaptive and Dynamic Service Composition in eFlow[END_REF][28] [START_REF] Shankar | SWORD: A developer toolkit for web service composition[END_REF] and the formal methods approach [START_REF] Chakraborty | Service Composition for Mobile Environments[END_REF][10][12] [START_REF] Mokhtar | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF]. The rules evaluate whether a given composition plan is appropriate or not in the actual context. If rules were commonly used as an evaluation approach, their use lacks of dynamism proper to pervasive environments. A major problem of the evaluation approach is namely the lack of dynamic tools to verify the correctnessfunctional and non functional aspects -of the service composition plan. This aspect is at the main advantage of what most formal methods offer. The nowadays most popular and advanced technique to evaluate a given composition plan is the evaluation by formal methods (like Petri nets and process algebras like the Pi-calculus). Petri nets are a framework to model concurrent systems. Their main attraction is the natural way of identifying basic aspects of concurrent systems, both mathematically and conceptually. Petri nets are very commonly merged with composition languages such as BPEL [START_REF] Juric | Business Process Execution Language for Web Services[END_REF] and OWL-S [START_REF]OWL-S: Semantic Markup for Web Servicesr[END_REF]. On the other hand, Automata or labeled transition systems are a well-known model underlying formal system specifications and are more and more used in the service composition process [START_REF] Mokhtar | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF]. 4. The Builder executes the selected composition plan and produces an implementation corresponding to the required composite service. It can apply a range of techniques to realize the effective service composition. These techniques depend strongly on the service technology model we are composing and on the context we are evolving in. Once the composite service available, it can be executed by the application that required its functionality. In the literature, we distinguish different kinds of builders provided by the service composition middleware. Some builders are very basic and use only simple invocation in sequence to a list of services [START_REF] Ibrahim | MySIM: a Spontaneous Service Integration Middleware for Pervasive Environments[END_REF]. These services need to be IJCSI IJCSI 4 available otherwise the composition result is not certain. Others [START_REF]Understanding UPnP: A White Paper[END_REF] provide complex discovery protocols adapted to the heterogeneous nature of the pervasive environments. The discovery takes in charge to find and choose the services taking part into the composition process and to choose contextually the most suitable ones if many are available. Finally some systems propose solutions not only located in the middleware layer but also in the networking one.

We argue that the SCM model is generic enough to describe the service composition process in pervasive environments. In the next section, we use the SCM model as a backbone for describing various middleware that do the service composition.

Service Composition Middleware in Pervasive Environments

In this section, we describe six middleware for service composition adapted for pervasive environments by mapping them to our SCM model. The chosen middleware are architectures, platforms or algorithms that propose solutions to the service composition problem: MySIM [START_REF] Ibrahim | MySIM: a Spontaneous Service Integration Middleware for Pervasive Environments[END_REF], PERSE [START_REF] Mokhtar | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF], SeSCo [START_REF] Kalasapur | Dynamic Service Composition in Pervasive Computing[END_REF], Broker [START_REF] Chakraborty | Service Composition for Mobile Environments[END_REF], SeGSeC [START_REF] Fujii | Semantics-based dynamic service composition[END_REF] and WebDG [START_REF] Medjahed | Composing Web services on the Semantic Web[END_REF]. For each middleware, we describe the service composition runtime process, the prototypes developed and identify the four modules of our SCM model in their provided architectures.

MySIM: Spontaneous Service Integration for Pervasive Environment

MySIM [START_REF] Ibrahim | MySIM: a Spontaneous Service Integration Middleware for Pervasive Environments[END_REF] is a spontaneous middleware that integrate services in a transparent way without disturbing users and applications of the environment. Service integration is defined as being a service transformation from one service technology to another (Translator), a service composition and a service adaptation. MySIM selects services that are composable, generates composition plans (Generator), evaluate their QoS degrees (Evaluator) and implements new composite services in the environment (Builder). These new services publish well known interfaces but new implementations and better QoS. MySIM also proposes to adapt the application execution to the services available by redirecting the application call to services with better QoS.

MySIM architecture is depicted under the SCM model in Figure 2. The Translator service transforms services into a generic Service model. The Generator service is responsible of the syntactic and semantic matching of the service operations for composition and adaptation issues. The QoS service evaluates the composition or substitution matching via non functional properties and the Decision service decides which services to compose or to substitute. Finally the Builder service implements the composite service, and the Registry service publishes its interfaces.

MySIM is implemented under the OSGi/Felix platform. It uses the reflexive techniques to do the syntactic interface matching and ontology online reasoner for the semantic matching. The service composition is technically done by generating new bundles (unit of deployment) that composes the services together. The results show the heavy cost of the semantic matching. The solution is interesting but solutions need to be found to make the spontaneous service integration scalable to large environments.

3.2 PERSE: Pervasive Semantic-aware Middleware PERSE [START_REF] Mokhtar | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF] proposes a semantic middleware, that deals with well known functionalities such as service discovery, registration and composition. This middleware provides a service model to support interoperability between heterogeneous both semantic and syntactic service description languages (Translator). The model further supports the formal specification of service conversations as finite state automata, which enables the automated reasoning about service behavior independently from the underlying conversation specification language. Hence, pervasive service conversations described with different service conversation languages (Generator) can be integrated (Builder) toward the realization of a user task. The model also supports the specification of service nonfunctional properties based on existing QoS models to meet the specific requirements of each pervasive application through the QoS aware Composition service (Evaluator). 3. The Evaluator module is the most developed as it verifies the correctness of the composition plan and analyzes the service QoS before composing services. A Translator is also available to translate the legacy services into a common model semantically and syntactically described. The Generator semantically matches services. The Builder discovers the services in the environment and simply invoke them in sequence. [START_REF] Mokhtar | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF] have implemented a prototype of PERSE using Java 1.5. Selected legacy plugins have been developed for SLP using jSLP, UPnP [START_REF]Understanding UPnP: A White Paper[END_REF] using Cyberlink, and UDDI using jUDDI. The efficiency of PERSE has been tested and proved in the cost evaluation of semantic service matching, the time to organize the semantic service registry, the time to publish and locate a semantic service description as well as the comparison of the scalability of the registry compared with a WSDL service registry, and finally the processing time for service composition with and without the support of QoS.

SeSCo: Seamless Service Composition

SeSCo [START_REF] Kalasapur | Dynamic Service Composition in Pervasive Computing[END_REF] presents a service composition mechanism for pervasive computing. It employs the service-oriented middleware platform called Pervasive Information Communities Organization (PICO) to model and represent resources as services. The proposed service composition mechanism models services as directed attributed graphs, maintains a repository of service graphs, and dynamically combines multiple basic services into complex services (Builder). The proposed service composition mechanism constructs possible service compositions based on their semantic and syntactic descriptions (Generator). SeSCo [START_REF] Kalasapur | Dynamic Service Composition in Pervasive Computing[END_REF] proposes a hierarchical service overlay mechanism based on a LATCH protocol (Evaluator). The hierarchical scheme of aggregation exploits the presence of heterogeneity through service cooperation. Devices with higher resources assist those with restricted resources in accomplishing service-related tasks such as discovery, composition, and execution.

SeSCo architecture is depicted under SCM model in Figure 4. No Translator module is provided and SeSCo uses the same language to present the user task and the composite service. The service matching is done on a semantic interface matching and the evaluation is upon the input/output matching correctness.

SeSCo [START_REF] Kalasapur | Dynamic Service Composition in Pervasive Computing[END_REF] evaluated its approach by calculating the composition success ratio for different lengths of composition which is essentially the number of services that can be used to compose a single service. This evaluation shows the effect of limiting the length of the composition to a predefined number. If the service density is higher, even with a lower value of composition length, a successful composition can be achieved. However, at lower service densities, it might be necessary to allow higher composition lengths for better composition.

Broker Approach for Service Composition

Broker [START_REF] Chakraborty | Service Composition for Mobile Environments[END_REF] presents a distributed architecture and associated protocols for service composition in mobile environments that take into consideration mobility, dynamic changing service topology, and device resources. The composition protocols are based on distributed brokerage mechanisms (Evaluator) and utilize a distributed service discovery process over adhoc network connectivity. The proposed architecture is based on a composition manager, a device that manages the discovery, integration (Generator), and execution of a composite request (Builder). Two broker selectionbased protocols -dynamic one and distributed one -are proposed in order to distribute the composition requests Broker architecture is depicted under the SCM model in Figure 5. The Broker arbitration is the Evaluator module as it evaluates the available devices and decides to distribute the composition request, described in a special language (DSF), taking into account the device context. The evaluation is done here before the composition process. The Service Integration describes the composition sequence using a specific language (ESF) and pass it to the Service Execution (the Builder) to execute it.

Broker [START_REF] Chakraborty | Service Composition for Mobile Environments[END_REF] implemented a protocol part of a distributed event-based mobile network simulator, to test the two proposed broker arbitration protocols and the composition efficiency. Simulation results show that their protocols -especially the distributed approachexceed the usual centralized broker composition in terms of composition efficiency and broker arbitration efficiency.

SeGSeC: Semantic Graph-Based Service Composition

SeGSeC [START_REF] Fujii | Semantics-based dynamic service composition[END_REF] proposes an architecture that obtains the semantics of the requested service in an intuitive form (e.g. using a natural language) (Tranlator), and dynamically composes the requested service based on its semantics (Generator). To compose a service based on its semantics, the proposed architecture supports semantic representation of services -through a component model named Component Service Model with Semantics (CoSMoS) -discovers services required for composition -through a middleware named Component Runtime Environment (CoRE) -and composes the requested service based on its semantics and the semantics of the discovered services -through a service composition mechanism named Semantic Graph-Based Service Composition (SeGSeC).

Figure 6 SeGSeC mapped to SCM SeGSeC architecture is depicted under SCM model in Figure 6. The Request Analyser translates the user request into an internal system language using graphbased approach. The Semantic Analyser and Service composer produce the composition workflow ready to be executed by the Service performer. The workflow respects the semantic matching composition rules and the correctness is guaranteed via the Evaluator module.

SeGSeC [START_REF] Fujii | Semantics-based dynamic service composition[END_REF] was evaluated according to the number of services deployed and the time needed to discover, match and compose services. Another set of evaluations took not only the number of deployed services but especially the number of operations these services implement. Their results show that SeGSeC performs efficiently when only a small number of services are deployed and that it scales to the number of services deployed if the discovery phase is done efficiently.

WebDG: Semantic Web Services Composition

WebDG [START_REF] Medjahed | Composing Web services on the Semantic Web[END_REF] proposes an ontology-based framework for the automatic composition of web services. [START_REF] Medjahed | Composing Web services on the Semantic Web[END_REF] presents an algorithm to generate composite services from high level declarative descriptions. The algorithm uses composability rules, in order to compare the syntactic and semantic features of web services to determine whether two services are composable.

WebDG architecture is depicted under SCM model in Figure 7. The service composition approach is depicted under four phases of request specification (Translator), service description matchmaking (Generator), composition plan selection (Evaluator) and composite service generation (Builder). A prototype implementation WebDG is provided and tested on a E-government Web service applications. The WebDG evaluation aims to test the possibility of generating plans for a large number of service interfaces, the effectiveness and speed of the matchmaking algorithm, and the role of the selection phase (QoC parameters) in reducing the number of generated plans. The result show that most of the time is spent on checking message composability. On the other hand, a relatively low value of composition completeness generates more plans, each plan containing a small number of composable operations. In contrast, a high value of this ratio generates a smaller number of plans, each plan having more composable operations.

Classification of the Pervasive Service Composition Middleware

As shown above, the SCM model is generic enough to provide generic functional modules that describe the existing service composition middleware. We choose to classify the middleware -MySIM [START_REF] Ibrahim | MySIM: a Spontaneous Service Integration Middleware for Pervasive Environments[END_REF], PERSE [START_REF] Mokhtar | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF], SeSCo [START_REF] Kalasapur | Dynamic Service Composition in Pervasive Computing[END_REF], Broker [START_REF] Chakraborty | Service Composition for Mobile Environments[END_REF], SeGSeC [START_REF] Fujii | Semantics-based dynamic service composition[END_REF] and WebDG [START_REF] Medjahed | Composing Web services on the Semantic Web[END_REF] according to pervasive environment requirements. We first list and explain these pervasive requirements for service composition middleware, then a classification of these middleware is given.

Pervasive Requirements

Pervasive computing brought new challenges to distributed and mobile computing. We identify the following eight fundamental requirements for service composition in pervasive environments: interoperability, discoverability, adaptability, context awareness, QoS management, security, spontaneous management and autonomous management.

Interoperability is the ability of two or more systems or components to exchange information and to use the information that has been exchanged. Ubiquitous computing environments, quoting Mark Weiser's definition, consist of various kinds of computational devices, networks and collaborating software and hardware entities. Due to the large number of heterogeneous and cooperating parties, interoperability is required at all levels of ubiquitous computing. Service composition middleware need to take advantage of all the functionalities available in the surroundings, and for that they need to be interoperable.

Discoverability is a major issue for ubiquity and composition as devices and services need to be located and accessed before being composed. One of the fundamental challenges of distributed and highly dynamic environments is how the applications can discover the surrounding entities and, conversely, how the applications can be discovered by the other entities in the system. In a pervasive system, the execution environment of applications can be logically considered as a single container including all applications, other components, and resources. Moreover, the idea in distributed environments is that the resources can be accessed without any knowledge of where the resources or the users are physically located.

Adaptability is the ability of a software entity to adapt to the changing environment. Changes in applications' and users' requirements or changes within the network, may require the presence of adaptation mechanisms within the middleware. Moreover, adaptation is necessary when a significant mismatch occurs between the supply and demand of a resource. As the application's execution environment changes due to the user's mobility, the vital resources need to be substituted by corresponding resources in the new environment in order to ensure continuous operation. The requirement for adaptation is present on many different layers of a computing system.

Context awareness is the ability of pervasive middleware to be aware in terms of devices coming and leaving, functionalities offered and retrieved, quality of service changing, etc. They need to be aware of all these changes, in order to offer the best functionalities to applications regardless the context around. When considering context-aware systems in general, some common functionalities that are present in almost every system, can be identified: context sensing and processing, context information representation, and the applications that utilize the context information. In

IJCSI IJCSI

8 general, the context information can be divided into lowand high-level context information. Low-level context information can be collected using sensors in the system. Low-level context information sources can be combined or processed further to higher level context information.

QoS management is essential in dynamic environments, where connectivity is very variable. A pervasive middleware for service composition need to take the non functional parameters of applications and devices into consideration in order to provide viable and flexible composition plans and composite services. QoS parameters concern not only the services but also the devices where the execution is taking place. The composition execution need to rely on this parameter in order to take place in the best conditions. Not only the QoS of different services need to be compatible, but also the devices performing the composition need to respect certain characteristics and constraints.

Security mechanisms, such as authentication, authorization, and accounting (AAA) functions may be an important part of the middleware in order to intelligently control access to computer and network resources, enforcing policies, auditing network/user usage, etc. Another important aspect concerns privacy and trust in pervasive environments. In presence of unknown devices, middleware need to respect privacy of users, and provide trust mechanisms adapted to the ever changing nature of the environment.

Spontaneous management concerns the ability of a pervasive middleware to compose services independently of user and application requests. The middleware spontaneously composes services that are compatible together and produces a new composite service into the environment. The new service is registered and can publish its interfaces in order to be discovered and executed by applications. Spontaneous service composition is an interesting feature in pervasive environments, as services meet when the user encounter, and interesting composite service can be generated from these meetings, even though not required at that moment by users.

Autonomous Management concerns the ability for a pervasive middleware to control and manage its resources, functions, security and performance, in face of failures and changes, with little or no human intervention. The complexity of future ubiquitous computing environments will be such that it will be impossible for human administrators to perform their traditional functions of configuration management, performability management, and security management. Instead, one must resort to automate most of these management functions, allowing humans to concentrate on the definition and supervision of high-level management policies, while the middleware itself takes care of the translation of these high-level policies into automated control structures. The challenge is therefore to move from classical middleware support for configuration, performability and security management to support for self-configuration, self-tuning, self-healing and self-protecting capabilities.

We classify the service composition middleware -MySIM [START_REF] Ibrahim | MySIM: a Spontaneous Service Integration Middleware for Pervasive Environments[END_REF], PERSE [START_REF] Mokhtar | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF], SeSCo [START_REF] Kalasapur | Dynamic Service Composition in Pervasive Computing[END_REF], Broker [START_REF] Chakraborty | Service Composition for Mobile Environments[END_REF], SeGSeC [START_REF] Fujii | Semantics-based dynamic service composition[END_REF], and WebDG [START_REF] Medjahed | Composing Web services on the Semantic Web[END_REF] -under the above requirements. For each middleware, we analyze its four modules -Translator, Generator, Evaluator, and Builder -and detail if they respect the pervasive requirements. The first section depicts the requirements that are fulfilled, at a certain extend, by the service composition middleware. The second section explains the requirements that are until now left behind. Our classification is given in Figure 8.

Service Composition Middleware Meeting Pervasive Requirements

In this section, we are interested in the pervasive requirements that are fulfilled by service composition middleware: discoverability, adaptability, context awareness, and QoS management.

If some pervasive requirements are relatively well fulfilled by the current composition middleware, others are still at a preliminary stage.

All middleware provide the discoverability and context awareness requirements. These requirements are intrinsic to every composition middleware wanting to evolve in dynamic and ever changing environment such as the pervasive environments. These requirements are essential when constructing and evaluating composition plans, but also when discovering and invoking services. Indeed, generating and evaluating composition plans must be contextual, as services can come and go at any time, and a given composition plan constructed at a certain time, need to be evaluated before execution, in case some changes have affected it. Hence, the context awareness is not only provided by the Builder but also by the Generator and Evaluator modules.

The adaptability requirement is fulfilled by four of the six classified middleware (MySIM [START_REF] Ibrahim | MySIM: a Spontaneous Service Integration Middleware for Pervasive Environments[END_REF], PERSE [START_REF] Mokhtar | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF], SeSCo [START_REF] Kalasapur | Dynamic Service Composition in Pervasive Computing[END_REF], and Broker [START_REF] Chakraborty | Service Composition for Mobile Environments[END_REF]) for different SCM modules. The environmental changes, that affect a pervasive environment, such as devices coming and leaving, services being unavailable, require from the middleware special mechanisms in order to re-evaluate and adapt their service composition to these changes. As we can see, some middleware propose adaptation mechanisms, but this requirement is far from being fulfilled by all service composition middleware in the environment. In nowadays researches, adaptation is more considered as a field of research [START_REF]Understanding UPnP: A White Paper[END_REF] than a requirement to fulfill. Adapting services can be seen as a way of integrating services into their new environments.

The QoS management requirement is fulfilled by five of the six classified middleware (MySIM [START_REF] Ibrahim | MySIM: a Spontaneous Service Integration Middleware for Pervasive Environments[END_REF], PERSE [START_REF] Mokhtar | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF], SeSCo [START_REF] Kalasapur | Dynamic Service Composition in Pervasive Computing[END_REF], Broker [START_REF] Chakraborty | Service Composition for Mobile Environments[END_REF] and WebDG [START_REF] Medjahed | Context-based matching for web service composition[END_REF]). The modules that usually respect the QoS properties the Generator, Evaluator and the Builder. The Evaluator relies on the service QoS parameters in order to choose the most suitable plan from all possible composition plans. QoS is especially relevant for stateful services. A plan composition of stateful services need to take QoS into account, as the resulting composition may not execute in case of severe incompatibilities in QoS between combined services. The Builder can analysis the QoS parameter in order to choose the devices and platforms where to execute the service composition, depending on power or memory properties, but also to choose services to compose depending on the devices they execute on. This requirement is especially considered in the development of multimedia applications in variable environments such as pervasive environments [START_REF] Girma | Planning-Based Multimedia Adaptation Services Composition for Pervasive Computing[END_REF]. Indeed, composing services within multimedia applications imposes a rigorous respect of the QoS properties otherwise the whole application may not execute.

Service Composition Middleware Missing Pervasive Requirements

Nowadays service composition middleware present real lack in providing interoperability, spontaneous management, security mechanisms and autonomous management to service composition in pervasive environments.

The interoperablity requirement is more than left behind in nowadays service composition middleware. Figure 8 shows that only three middleware (MySIM [START_REF] Ibrahim | MySIM: a Spontaneous Service Integration Middleware for Pervasive Environments[END_REF], PERSE [START_REF] Mokhtar | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF] and SeGSeC [START_REF] Fujii | Semantics-based dynamic service composition[END_REF]) fulfill this requirement, and only for the Translator module. Interoperability is currently resolved by explicit technical translations from one service model to another. By this way, interoperability is only resolved at a technology level. On a more theoretical and formal level, the use of semantic and ontology based languages [START_REF] Bittner | Ontology and semantic interoperability[END_REF] is not sufficient to make service composition fully interoperable. Very often, service providers use different ontology domain and ontology transformations from one domain to another are more than needed.

Spontaneous management is only considered by MySIM [START_REF] Ibrahim | MySIM: a Spontaneous Service Integration Middleware for Pervasive Environments[END_REF] middleware. Indeed all of the other five middleware are goal-oriented and respond mainly to predefined functionality requests coming from the application layer. None of these middleware propose a spontaneous service composition that deliver new services and functionalities into the environment, without the intervention of users or applications. MySIM [START_REF] Ibrahim | MySIM: a Spontaneous Service Integration Middleware for Pervasive Environments[END_REF] proposes a service integration middleware that generates new services in the environment spontaneously and automatically. Compatible services are composed on the fly, without any intervention and upon the middleware own decision based on semantic and syntactic service matching.

IJCSI IJCSI 10

The middleware listed above, do not propose solutions to address the problem of security or trust. They rely on the existing mechanisms proposed by the middleware and network layers, if any. Several other studies [START_REF] Barthe | Compositional Verification of Secure Applet Interactions[END_REF] [START_REF] Dragoni | A Security-by-contracts Architecture for Pervasive Services[END_REF] address security features for service composition using contracts [START_REF] Dragoni | A Security-by-contracts Architecture for Pervasive Services[END_REF], verification formal methods [START_REF] Barthe | Compositional Verification of Secure Applet Interactions[END_REF], or a security model for enforcing access control in extensible component platforms [START_REF] Parrend | Component-Based Access Control: Secure Software Composition through Static Analysis[END_REF].

No real autonomous composition management is provided. The middleware do not propose mechanism to manage their resources, functions, security, and performance, in face of failures and changes, with little or no human intervention. Pervasive environments that are capable of composing functionalities autonomously are still at preliminary state of consumption. A major domain that dealt with autonomous management of the composition is the multi-agent systems. Combining multi-agent systems and service-oriented architecture is a well known research field to add autonomy features to services [9][18][21] [START_REF] Vo | Conversation-Based Specification and Composition of Agent Services[END_REF].

Conclusions

The development of pervasive computing has put the accent on a well identified problem, the service composition problem. Composing services together on various platforms, extending environments with new functionalities, are the new trends pervasive computing aims to achieve. Many composition middleware have reached a certain maturity, and propose complete architectures and protocols to discover and compose services in pervasive environments. Many surveys [5][7][22][31] [START_REF] Mascolo | Survey of Middleware for Networked Embedded Systems[END_REF] list service composition middleware according to predefined criteria or properties. They very often consider middleware for the composition of a particular technology such as Web services composition middleware. The application of service composition middleware to pervasive environment is rather new, and a real lack in analyzing and classifying service composition middleware under a reference model is noticed.

In this article, we surveyed six complete service composition architectures for pervasive environments, located in the middleware layer, MySIM [START_REF] Ibrahim | MySIM: a Spontaneous Service Integration Middleware for Pervasive Environments[END_REF], PERSE [START_REF] Mokhtar | Semantic Middleware for Service-Oriented Pervasive Computing[END_REF], SeSCo [START_REF] Kalasapur | Dynamic Service Composition in Pervasive Computing[END_REF], Broker [START_REF] Chakraborty | Service Composition for Mobile Environments[END_REF], SeGSeC [START_REF] Fujii | Semantics-based dynamic service composition[END_REF] and WebDG [START_REF] Medjahed | Composing Web services on the Semantic Web[END_REF]. We do not claim the exhaustiveness of our classification, but we think that the major middleware for service composition in pervasive environments are depicted. We introduced a novel approach to study the service composition problem. We studied these systems by reducing the composition problem to four main problems: the service translations, the composition plan generations, the plan contextual evaluations, and finally the real composition implementation. In each of these domains, several trends appeared to be commonly used: simple translation between diverse service technologies for the Translator, graph based approach or language composition one for the Generator, formal methods approach for the Evaluator, and discovery and invocation mechanisms for the Builder. Finally, we classified these middleware under several requirements related to the ubiquity of the environments. If some requirements such as discoverability and context awareness are well verified, others are still being explored such as interoperability, adaptability and QoS management. Security, spontaneous and autonomous management open the way to many promising research trends, at the intersection of several major domains such as artificial intelligence and autonomic computing, for service composition middleware in pervasive environments.

Figure 2

 2 Figure 2 MySIM mapped to SCM

Figure 3 Figure 4

 34 Figure 3 PERSE mapped to SCM

Figure 5

 5 Figure 5 Broker mapped to SCM

Figure 7

 7 Figure 7 WebDG mapped to SCM

Figure 8

 8 Figure 8 Service composition Middleware Classification

IJCSI IJCSI 12

Frédéric Le Mouël holds an engineering diploma in Languages and Operating Systems, and a Phd degree from the University of Rennes 1, France. His dissertation focused on an adaptive environment for distributed execution of applications in a mobile computing context. Frédéric Le Mouël is currently associate professor in the National Institute for Applied Sciences of Lyon(INSA Lyon, France), Telecommunications Department, Center for Innovation in Telecommunication and Integration of Services (CITI Lab.). His main interests are service-oriented middleware and more specifically on the fields of dynamic adaptation, composition, coordination and trust of services.