Cristina Benea
email: cristina.benea@univ-nantes.fr

Camil Muscalu

Mixed-norm estimates for paraproducts

come

Introduction

Our aim is to present a few recent tools from harmonic analysis that could prove useful in the study of nonlinear differential equations. These involve multilinear Littlewood-Paley theory in several variables on mixed norm L p spaces

f L p x L q t := f L q t L p x := ˆR ˆR f (x, t) q dt p/q dx 1/p .
Our main results will be formulated as Leibniz rules in mixed norm L p spaces, but other multipliers can be treated similarly. Of great importance to us are the less conventional cases involving quasi-Banach target spaces (s 1 , s 2 can be < 1 in Theorem 1) or L ∞ input spaces (we allow for p j = ∞ or q j = ∞). From the technical point of view, these are more interesting because they are not direct consequences of the linear Littlewood-Paley theory.

Theorem 1. For any α, β > 0

D α 1 D β 2 (f • g) L s 1 x L s 2 y D α 1 D β 2 f L p 1 x L p 2 y • g L q 1 x L q 2 y + f L p 3 x L p 4 y • D α 1 D β 2 g L q 3 x L q 4 y + D α 1 f L p 5 x L p 6 y • D β 2 g L q 5
x L

q 6 y + D β 2 f L p 7 x L p 8 y • D α 1 g L q 7
x L q 8 y , whenever 1 < p j , q j ≤ ∞, max 1 2 , 1 1+α , 1 1+β < s 1 , s 2 < ∞ and so that the indices satisfy the natural Hölder-type conditions.

A result of a similar type appeared in [START_REF] Kenig | Well-posedness and scattering results for the generalized Korteweg-de Vries equation via the contraction principle[END_REF], as an important tool in establishing local wellposedness for the generalized Korteweg-de Vries equation. This is a dispersive, nonlinear equation given by [START_REF] Benea | Multiple vector valued inequalities via the helicoidal method[END_REF]

∂u ∂t + ∂ 3 u ∂x 3 + u k ∂u ∂x = 0, t, x ∈ R, k ∈ Z + u(x, 0) = u 0 (x)
In order to prove existence, the authors use the contraction principle, but to be able to do so, they need to construct a suitable Banach space. The norm of the Banach space involves mixed L p norms of fractional derivatives in the first variable D α 1 , and the Leibniz rule employed in this paper is

(2) D α 1 (f • g) -f • D α 1 g -D α 1 f • g L p x L q t C D α 1 1 f L p 1 x L q 1 t D α 2 1 g L p 2 x L q 2 t . 1
Here α ∈ (0, 1), α 1 +α 2 = α and 1

p 1 + 1 p 2 = 1 p , 1 q 1 + 1 q 2 = 1 q . Also, p, p 1 , p 2 , q, q 1 , q 2 ∈ (1, ∞), but one can allow q 1 = ∞ if α 1 = 0.
The fractional derivatives appear as a consequence of the smoothness requirement on the initial data: u 0 is assumed to be in some Sobolev space H α (R), where α depends on the value of k in [START_REF] Benea | Multiple vector valued inequalities via the helicoidal method[END_REF].

The paraproduct of two functions (termed para-multiplication operator in [START_REF] Bernicot | Local estimates and global continuities in Lebesgue spaces for bilinear operators[END_REF], where they were first used in the study of non-linear differential equations) is a bilinear operator associated to the Littlewood-Paley decompositions of two functions f and g. For any k ∈ Z, the Fourier projection of

f onto the shell |ξ| ∼ 2 k is denoted Q k f (x) := f * ψ k (x), while the projection onto |ξ| ≤ 2 k is P k f (x) := f * ϕ k (x). Then it is not difficult to see that f • g = k ((f * ψ k ) • (g * ψ k )) * ϕ k + k ((f * ϕ k ) • (g * ψ k )) * ψ k + k ((f * ψ k ) • (g * ϕ k )) * ψ k .
Any of the three elements on the right hand side of the expressions above is called a classical paraproduct and is denoted Π(f, g). They also play the role of mollifiers: instead of estimating D α (f • g), we estimate D α (Π(f, g)). When a derivative hits ψ k or ϕ k , this becomes equivalent to multiplication by 2 kα ; and correspondingly, 2 kα ψ k (x) = D α ψk (x).

We will see in Section 2 how Theorem 1 can be deduced from results on bi-parameter paraproducts.

The concept of paraproduct extends readily to bilinear Fourier multipliers:

Theorem A (Coifman, Meyer [START_REF] Coifman | Wavelets, Calderón-Zygmund Operators and Multilinear Operators[END_REF]). Any bilinear multiplier operator associated to a symbol m(ξ, η) satisfying ∂ α m(ξ, η) (ξ, η) -α for sufficiently many multi-indices α, maps

L p (R) × L q (R) into L s (R) provided that 1 < p, q ≤ ∞, 1 2
< s < ∞, and

1 p + 1 q = 1 s .
However, we will not be working with classical paraproducts as above, but with disretized paraproducts, which are associated to a collection I of dyadic intervals:

(3) Π I (f, g)(x) = I∈I c I 1 |I| 1 2 f, ϕ I g, ψ I ψ I (x),
where the functions ψ I and ϕ I are so that supp ψI ⊆ 1 |I| , 2 |I| , supp φI ⊆ 0, 1 |I| , are L 2 -normalized and decay fast away from I.

The discretized paraproducts above can be used as a black box in the study of several other bilinear multipliers singular at a point, as we will see in Section 2. The information on the Fourier multiplier will be encoded in the decay of the double Fourier coefficients of its restriction to the Whitney squares associated to the point singularity.

The approach based on discretized operators, presented in various instances in [START_REF] Muscalu | Classical and Multilinear Harmonic Analysis[END_REF], developed with the study of the bilinear Hilbert transform operator, defined by ξ+η) dξdη.. Indeed, can be written as

BHT (f, g)(x) : = p.v. ˆR f (x -t)g(x + t) dt t (4) = C ˆR2 f (ξ)ĝ(η)sgn(ξ -η)e 2πix(
C 1 f (x) = -p.v. ˆR A(x + t) -A(x) t f (x + t) dt t = = -p.v. ˆR ˆ1 0 a(x + αt)dα f (x + t) dt t ,
where a(x) = A ′ (x) ∈ L ∞ . A question that remained open for nearly thirty years, long after the Cauchy integral on Lipschitz curves was comprehended, was whether BHT : L p × L ∞ → L p , for 1 < p < ∞. This question was eventually answered in the late 90's, reviving the field of time-frequency analysis (which priorly consisted of Carleson's celebrated proof of the pointwise convergence of Fourier series [START_REF] Carleson | On convergence and growth of partial sums of Fourier series[END_REF], and Fefferman's reinterpretation of the latter [START_REF] Fefferman | Pointwise convergence of Fourier series[END_REF]).

Theorem B (Lacey, Thiele [START_REF] Lacey | On Calderón's conjecture[END_REF]). BHT is a bounded bilinear operator from L p × L q into L s , for any 1 < p, q ≤ ∞, 0 < s < ∞, satisfying

1 p + 1 q = 1 s and 2 3 < s < ∞.
In some sense, proving quasi-Banach valued results for multilinear operators is not as much about understanding the behavior of T (f, g) in a space where the triangle inequality doesn't hold, as it is about understanding the admissible input spaces for the operator. This is especially relevant for the bilinear Hilbert transform operator above; it is still not clear if the operator is bounded for values of s between 1 2 and 2 3 . This would correspond to both p and q being strictly less that 2, loosing some of the orthogonality (in frequency) properties that are so significant in the proof.

Later on, the result was extended to multilinear multipliers singular along a subspace of dimension k:

Theorem C (Muscalu, Tao, Thiele [START_REF] Muscalu | Multi-linear operators given by singular multipliers[END_REF]). Let Γ ⊂ R n be a non-degenerate subspace of dimension k, with 0 ≤ k < n+1 2 , and let T m be an n-linear operator given by

T m (f 1 , . . . , f n )(x) = ˆRn m(ξ 1 , . . . , ξ n ) f1 (ξ 1 ) • . . . • fn (ξ n )e 2πix(ξ 1 +...+ξn) dξ 1 . . . dξ n .
Above, the multiplier m satisfies the estimates

|∂ α ξ m(ξ)| dist (ξ, Γ) -|α|
for all partial derivatives up to some finite order. Then T :

L p 1 × . . . × L pn → L p whenever 1 p 1 + . . . + 1 pn = 1 p , 1 < p j ≤ ∞, 1 n < p < ∞ and moreover 1 p i 1 + . . . + 1 p r < n + 1 -2k + r 2 for all 1 ≤ i 1 < . . . < i r ≤ n and 1 ≤ r ≤ n (here we set p n+1 = p).
The non-degeneracy condition requires Γ to be a graph over any k variables; otherwise, the problem reduces to a lower dimensional one, and as a consequence, the range of boundedness will be different.

The case k = 0 corresponds to the Coifman-Meyer theorem A, while k = 1, n = 2 to the Lacey-Thiele theorem B.

There exist also certain results for multipliers that depend also on the spacial variable:

Theorem D (Bernicot, [3]). Consider a smooth symbol a(x, ξ 1 , ξ 2 ) satisfying |∂ β x ∂ α ξ a(x, ξ)| (1 + dist (ξ, Γ)) -|α| ,
for sufficiently many indices α and β. Then the bilinear operator associated to this symbol satisfies the same estimates as the bilinear Hilbert transform of Theorem B.

In order to prove Theorem 1, we need to estimate bi-parameter paraproducts:

Π ⊗ Π(f, g)(x, y) = k,l [(f * ϕ k ⊗ ϕ l ) • (g * ψ k ⊗ ψ l )] * (ψ k ⊗ ψ l ) (x, y),
and the remaining similar eight terms obtained by permuting the ψ k , ϕ k , ψ l , ϕ l functions.

The first result along these lines was proved by Journé in [START_REF] Journé | Calderón-Zygmund operators on product spaces[END_REF], who in fact developed a theory for linear bi-parameter Calderón-Zygmund operators. However, Journé did prove that Π ⊗ Π :

L 2 (R 2 ) × L ∞ (R 2 ) → L 2 (R 2
). The general result was proved later in [START_REF] Muscalu | Bi-parameter paraproducts[END_REF]:

Theorem E (Muscalu, Pipher, Tao, Thiele [START_REF] Muscalu | Bi-parameter paraproducts[END_REF]). Π ⊗ Π is a bounded operator from

L p (R 2 ) × L q (R 2 ) into L s (R 2 ) provided that 1 < p, q ≤ ∞, 1 p + 1 q = 1 s
, and 0 < s < ∞.

In [START_REF] Benea | Multiple vector valued inequalities via the helicoidal method[END_REF] together with [START_REF]Quasi-banach valued inequalities via the helicoidal method[END_REF], we managed to prove the following result:

Theorem 2. Let 1 < p i , q i ≤ ∞ and 1 2 < s i < ∞, be so that

1 p i + 1 q i = 1 s i for any index i = 1, 2.
Then the bi-parameter paraproduct Π ⊗ Π satisfies the following mixed norm estimates:

(5) Π ⊗ Π : L p 1 x L p 2 y × L q 1 x L q 2 y → L s 1 x L s 2 y .
A similar result holds for multi-parameter paraproducts Π ⊗ . . . ⊗ Π, if the lebesgue exponents are strictly between 1 and ∞ (although we can allow the outer-most exponent to be between 1 2 and 1 as well). Theorem E was proved using discretized paraproducts in both variables, that is Π I ⊗ Π J . This is not the approach we take; the mixed norm L p spaces already have a vector-valued structure buit-in. Instead, we use some multiple vector-valued estimates for paraproducts (which we deduce from similar estimates for the discretized paraproducts). In Section 3 we point out to the bridge between vector-valued and multi-parameter theory.

First, in [START_REF] Benea | Multiple vector valued inequalities via the helicoidal method[END_REF], we treated the case 1 ≤ s 2 < ∞, corresponding to a Banach case, by developing a way of proving multiple vector-valued estimates for certain bilinear operators ( paraproducts and BHT ). In [START_REF]Quasi-banach valued inequalities via the helicoidal method[END_REF], we extended these methods to quasi-Banach spaces, allowing for values of s 2 strictly between 1 2 and ∞. We should mention that a similar result, within a smaller Banach range, was proved independently around the same time in [START_REF] Plinio | Banach-valued multilinear singular integrals[END_REF].

The vector-valued result, on which our proof relies, is the following theorem:

Theorem 3. Consider the tuples R 1 = r 1 1 , . . . , r n 1 , R 2 = r 1 2 , .
. . , r n 2 and R = r 1 , . . . , r n satisfying for every 1 ≤ j ≤ n : 1 < r j 1 , r j 2 ≤ ∞, 1 2 < r j < ∞, and 1

r j 1 + 1 r j 2 = 1 r j .
Then the paraproduct Π satisfies the estimates

Π : L p R; L R 1 (W, µ) × L q R; L R 2 (W, µ) → L s R; L R (W, µ) , for any 1 < p, q ≤ ∞, 1 2 < s < ∞ with 1 p + 1 q = 1 s . The L R norm on (W, Σ, µ) = n j=1 W j , n j=1 Σ j , n j=1 µ j is defined as f L R (W,µ) := ˆW1 . . . ˆWn | f (w 1 , . . . , w n )| r n dµ n (w n ) r n-1 /r n . . . dµ 1 (w 1 )
1/r 1

Reduction to discretized paraproducts

We briefly explain how to reduce the study of bilinear Fourier multipliers as in Theorem A, to that of discretized paraproducts. But first we illustrate this reduction for classical paraproducts. The trilinear form associated to the paraproducts can be written as

Λ Π (f, g, h) = k ˆR(f * ϕ k )(x)(g * ψ k )(x)(h * ψ k )(x)dx = k∈Z 2 -k n∈Z ˆ1 0 (f * ϕ k )(2 -k (n + β))(g * ψ k )( -k (n + β))(h * ψ k )( -k (n + β))dβ = k ˆ1 0 |I|=2 -k 1 |I| 1/2 f, ϕ β I g, ψ β I h, ψ β I = ˆ1 0 I 1 |I| 1/2 f, ϕ β I g, ψ β I h, ψ β I .
The functions ψ β I are given by

ψ β I (t) = 2 -k/2 ψ k (2 -k (n + β) -t)
, and similarly for ϕ β I . They are L 2 normalized and verify the properties in the definition of the discretized paraproducts. The parameter beta varies within the compact interval [0, 1], and for that reason its presence is of no consequence.

Regarding the paraproduct Π(f, g)

= k P k (Q k f • Q k g), for every k ∈ Z, P k (Q k f • Q k g) is supported in frequency inside the set |ξ| ∼ 2 k , |η| ∼ 2 k ,
which can be written as a union of a finite number of Whitney squares with respect to the origin. That is, squares in the frequency plane ξη, so that the diameter of the box is comparable to the distance to the singularity.

Conversely, let m(ξ, eta) be a symbol satisfying ∂ α m(ξ, η) (ξ, η) -α for sufficiently many multi-indices α. We can write m as

m(ξ, η) = Q m(ξ, η) • φ Q (ξ, η) = Q m Q (ξ, η),
where Q runs over Whitney squares associated to the point singularity, and φ Q represent a smooth partition of unity associated to the collection of suqares Q. Every m Q is smooth and supported mainly on Q, hence we can consider its Fourier series:

m Q (ξ, η) = n 1 ,n 2 c Q n 1 ,n 2 e 2πin 1 ξ |Q| e 2πin 2 ξ |Q| = n 1 ,n 2 c Q n 1 ,n 2 e 2πin 1 ξ |Q| e 2πin 2 ξ |Q| φ Q 1 (ξ)φ Q 2 (η),
where this time φ Q 1 (ξ) is a smooth function supported on 11 10 Q 1 , which is constantly equal to 1 on Q 1 . (Here we write

Q = Q 1 × Q 2 )
. The smoothness of the symbol m is reflected in the decay of the Fourier coefficients, which is uniform in Q:

|c Q n 1 ,n 2 | (1 + |n 1 | + |n 2 |) -M .
In fact, c Q n 1 ,n 2 only depends on the diameter of the square, hence we write c k n 1 ,n 2 for a square of diameter comparable to 2 k .

Then we have

T m (f, g)(x) = n 1 ,n 2 k c k n 1 ,n 2 ((f * ϕ k,n 1 ) • (g * ψ k,n 2 )) * ψ k (x)
+ like terms.

The functions ψ k,n 1 are the modulated functions ψ k , which correspond to a shift in the spatial variable. Then expressions of the form

k c k n 1 ,n 2 ((f * ϕ k,n 1 ) • (g * ψ k,n 2 )) * ψ k (x)
represent shifted paraproducts, which can be reduced again to discretized paraproducts. The shifts with respect to the parameters n 1 and n 2 produce a dependency of these variables, but which is acceptable in the end thanks to the fast decay of the coefficients c k n 1 ,n 2 .

The Leibniz rule from Theorem 1. Using paraproducts, D α 1 D β 2 (f, g)(x, y) can be represented as a sum of paraproducts applied to D α 1 f and D β 2 g and to similar terms (this explains the numerous terms in Theorem 1).

When the derivatives are applied to the term k,l

P k P l (Q k Q l f • Q k Q l g), we obtain D α 1 D β 2 (Π(f, g))(x, y) = k,l [(f * ψ k ⊗ ψ l ) • (g * ψ k ⊗ ψ l )] * (2 kα φk ⊗ 2 lβ φl )(x, y).
The functions φk and φl have a slower decay than ϕ k , ϕ l :

φk (ξ) = |ξ| α 2 kα φk , φl (η) = |η| β 2 β φl .
The simple lack of smoothness at the origin causes φ to decay as (1 + |x|) -1-α (here we have φ so that φk (x) = 2 k φ(2 k x)).

The φk and φl will be again decomposed in Fourier series in frequency as before, and we are reduce to the study of the operator ( 6)

n 1 ,n 2 k c k,l n 1 ,n 2 ((f * ψ k,n 1 ⊗ ψ l,n 2 ) • (g * ψ k,n 1 ⊗ ψ l,n 2 )) * ϕ k ⊗ ϕ l (x, y),
where this time the coefficients satisfy uniformly in k and l the estimate

(7) |c k,l n 1 ,n 2 | 1 (1 + |n 1 |) (1+α) • 1 (1 + |n 2 |) (1+β) .
The expression in ( 6) is essentially

n 1 ,n 2 c n 1 ,n 2 Π ⊗ Π(f, g)(x, y),
and we will need to estimate this in L s 1 x L s 2 y . Using the subadditivity of

• s 0 L s 1 x L s 2 y
, where

s 0 = min(1, s 1 , s 2 )
, and assuming the estimate in Theorem 2, Theorem 1 is reduced to the summability of

n 1 ,n 2 1 (1 + |n 1 |) s 0 (1+α) • 1 (1 + |n 2 |) s 0 (1+β) .
The latter is true provided s 0 (1 + α) > 1 and

s 0 (1 + β) > 1, i.e. if min(1, s 1 , s 2 ) > max 1 1 + α , 1 1 + β .

From multiple vector-valued operators to multi-parameter operators

The study of multi-parameter operators in harmonic analysis is not an easy task. The reason for that, at least partly, is the more complicated characterization of the BM O space in higher dimensions, which plays a very important role in the study of bilinear operators as well. This can avoided however, by regarding multi-parameter operators as (some multiple) vector-valued operators, an approach we are going to take.

Correspondingly, vector-valued extensions of an operator T can be regarded as mixednorm estimates for the bi-parameter operator T ⊗ Id (in the second component, nothing happens). This is a useful point of view because it also suggests that bi-parameter operators can be understood in a way similar to the treatment of vector-valued extensions.

Sometimes in time-frequency analysis, multi-parameter operators behave unexpectedly. In [START_REF] Muscalu | Bi-parameter paraproducts[END_REF], it was noticed that even though Π ⊗ Π is bounded on all admissible L p spaces, BHT ⊗ BHT = ∞ a.e. The range of boundedness for Π ⊗ BHT was only recently understood in [START_REF] Silva | Vector valued inequalities for families of bilinear Hilbert transforms and applications to biparameter problems[END_REF] and [START_REF] Benea | Multiple vector valued inequalities via the helicoidal method[END_REF].

The paraproducts on the other hand have a special "splitting" property. Recall that Q k is the Littlewood-Paley projection onto {|ξ| ∼ 2 k }(which is really the convolution with ψ k (•)), and P k is the projection onto {|ξ| ≤ 2 k }, corresponding to the convolution with ϕ k . Then we can regard paraproducts as being expressions of the form

(8) k Q k (P k f • Q k g)(x, y) , k Q k (Q k f • P k g)(x, y) or k P k (Q k f • Q k g)(x, y).
It is important for us that the outer-most function φk (ξ 1 +ξ 2 ) and ψk (ξ 1 +ξ 2 ) are identically equal to 1 on the supports of ψk (ξ 1 )• ψk (ξ 2 ) and ψk (ξ 1 )• φk (ξ 2 ) respectively. This can always be achieved with the price of an extra decomposition.

Proposition 1. Let T m : L p (R n ) × L q (R n ) → L r (R n
) be a bilinear operator with smooth symbol m, and Π : L p (R) × L q (R) → L r (R) a paraproduct as described above.

(1

) If Π is given by k Q k (P k f • Q k g)(x, y), then (T m ⊗ Π)(f, g)(x, y) = k Q 2 k T m (P y k f, Q y k g) (x) = k T m (P y k f, Q y k g)(x).
(

) If Π is given by k P k (Q k f • Q k g)(x, y), then (T m ⊗ Π)(f, g)(x, y) = k P 2 k T m (Q y k f, Q y k g) (x) = k T m (Q y k f, Q y k g)(x). 2
Here we need to explain the notation: Q 2 k denotes the projection onto |ξ 2 | ∼ 2 k in the second variable, and P y k f is a function of x only, with the variable y fixed. The exact formulas are

P y k f (x) = ˆR ϕ k (s)f (x, y -s)ds, P 2 k f (x, y) = ˆR ϕ k (s)f (x, y -s)ds, Q y k f (x) = ˆR ψ k (s)f (x, y -s)ds, Q 2 k f (x, y) = ˆR ψ k (s)f (x, y -s)ds.
With this observation at hand, we can present our approach to multiparameter paraproducts.

Sketch of proof for Theorem 2. Now we show how to deduce the results of Theorem 2, for any 1 2 < s 1 , s 2 < ∞. If Π y , the paraproduct acting on the variable y is of the form

Π y (•, •) = k Q k (P k (•) , Q k (•)) , then we can write Π ⊗ Π as Π ⊗ Π(f, g)(x, y) = k Q 2 k Π P y k , Q y k (x)
. A less known result, which plays an important role in our approach, is the following lemma, which appears in [START_REF] Ruan | Multi-parameter Hardy spaces via discrete Littlewood-Paley theory[END_REF]: Lemma 1. Let f ∈ S(R n ), and 1 ≤ l ≤ n, and {i 1 , . . . i l } ⊂ {1, . . . , n}. Then

f L p   k 1 ,...,k l |Q i 1 k 1 . . . Q i l k l f | 2   1/2 L p for any 0 < p < ∞.
This is saying that the L p norm of f is bounded by the L p norm of the square function, for any 0 < p < ∞. The reverse statement is used more often, but it only holds for 1 < p < ∞. Also, a Banach-valued result holds, and it will be needed for the special case 1 2 < s 1 < 1, and p 2 = ∞ or q 2 = ∞, when the Banach space concerned is L 1 .

We have

k Q 2 k Π P y k , Q y k (x) L s 2 y L s 1 x k Π P y k , Q y k (x) 2 1/2 L s 2 y L s 1 x (9)
sup k P y k f (x) L p 2 y L p 1 x • k Q y k g(x) 2 1/2 L q 2 y L q 1 x .
In the above inequality we used the multiple vector-valued estimate

Π x : L p 1 x L p 2 y (ℓ ∞ ) × L q 1 x L q 2 y ℓ 2 → L s 1
x L s 2 y ℓ 2 , which is a consequence of Theorem 3.

On the last line of (9), we recognize a maximal operator in big

sup k P y k f (x) L p 2 y L p 1 x and a square function in k Q y k g(x) 2 1/2 L q 2 y L q 1 x
. The latter is not bounded on L ∞ , leaving out the case q 2 = ∞.

If 1 ≤ s 1 , s 2 < ∞, the case when p 2 = ∞ or q 2 = ∞ can be obtained by duality: the dual of L p x L q y is L p ′ x L q ′ y . More more difficult however is the case when 1 2 < s 1 < 1 and p 2 = ∞ or q 2 = ∞, and needs to be dealt with differently. Indeed, we treat it similarly to vector-valued extensions for operators: we prove sharp estimates for the localized version

Π F,G,H ′ I 0 ⊗ Π : L ∞ x L ∞ y × L q x L q y → L q
x L q y , with sharp operatorial bounds that depend on the dyadic interval I 0 , and the fixed sets F, G, H ′ . Then the mixed norm L p estimates are deduced through careful stopping times.

On the other hand, if Π y is of the form

Π y (•, •) = k P k (Q k (•) , Q k (•)) , we can write Π ⊗ Π as Π ⊗ Π(f, g)(x, y) = k P 2 k Π Q y k , Q y k (x). Then the boundedness of Π ⊗ Π in L s 1
x L s 2 y follows from the vector-valued inequality Π

x : L p 1 x L p 2 y ℓ 2 × L q 1 x L q 2 y ℓ 2 → L s 1 x L s 2 y ℓ 2 .
Remark:. Through the above method, we can recover the results of Theorem E, and their multi-parameter equivalents from [START_REF]Multi-parameter paraproducts[END_REF].

A few comments on quasi-Banach spaces

Even though for 0 < p < 1, the triangle inequality is missing in L p spaces, the boundedness of a (multi-) linear operator on such spaces can still be proved thanks to Marcinkiewicz interpolation theorem, which is true also for multi-sublinear operators. In this situation, the dual of L p is {0} for non-atomic spaces(such as L p (R n )), or a complicated space containing ℓ ∞ in the case of an atomic space such as ℓ p . We will not attempt to dualize the L p quasinorm, but instead the L p,inf ty quasinorm, which could seem surprising.

Using generalized restricted type dualization, we have

(10) f p,∞ ∼ sup E,0< E <∞ inf E ′ ⊆E major subset f, 1 E ′ E 1-1 p , where we say E ′ is a major subset of E if E ′ ⊆ E and E ′ ≥ E /2.
More generally, we have

(11) f p,∞ ∼ sup 0< E <∞ inf Ẽ⊆E major subset f • 1 Ẽ r E 1 r -1 p .
This means that, given a set E of finite measure, we can in fact remove an exceptional subset whose measure is relatively small (which can represent the set where the maximal function of f is too large, for example), and estimate f on the complement of the exceptional set. Such a technique is extremely useful, but there might be certain technicalities involved and one needs to exercise care. If we want to evaluate T f p 0 ,∞ and T f p 1 ,∞ , and from this deduce estimates for T L p →L p via a Marcinkiewicz interpolation theorem, the exceptional set should be independent of the function f . The type of interpolation most suitable to this techniques is the generalized restrictedtype interpolation (which is an adaptation of Marcinkiewicz's ideas). The principle behind it is that whatever is true for characteristic functions should also hold for function in L p spaces. We present a bilinear theorem which is often used in time-frequency analysis: Proposition 2. Let (p, q, s) be a tuple so that 1 2 < s < ∞, 1 < p, q < ∞ and

1 s = 1 p + 1 q ,
and T a bilinear operator satisfying the restricted type estimate: for any sets of finite measure E 1 and E 2 , and any functions f, g so that |f (x)| ≤ 1 E 1 (x) and |g(x)| ≤ 1 E 2 (x) respectively, the estimate

(12) T (f, g) s,∞ ≤ K s 1 ,s 2 ,s E 1 1/s 1 E 2 1/s 2
holds for all tuples (s 1 , s 2 , s) satisfying 1 s 1 + 1 s 2 = 1 s in a neighborhood of (p, q, s), with the constant K s 1 ,s 2 ,s depending continuously on s 1 , s 2 , s.

Then T is of strong type (p, q, s), in the sense that (13) T (f, g) s ≤ K p,q,s f p g q for any sequences of functions for which the RHS is finite.

The interpolation theorem above extends easily to the framework of multiple Banach or quasi-Banach spaces; the conditions |f (x)| ≤ 1 E 1 , |g(x)| ≤ 1 E 2 (x) are replaced by f (x) L R 1 (W,µ) ≤ 1 E 1 (x) and g(x) L R 2 (W,µ) ≤ 1 E 2 (x) respectively. Moreover, the measure spaces can be arbitrary, for example if we want to prove: T ( f , g) L R (W,µ) L s (ν) ≤ K p,q,s f L R 1 L p (ν 1 ) g L R 2 L q (ν 2 ) .

Remark:. In [START_REF]Quasi-banach valued inequalities via the helicoidal method[END_REF], identity (11) plays an essential role. In proving Theorem 3, it was important for us to linearize the operator k |T (f k , g k )| r 1/r for values of r < 1. This could not be achieved pointwise (the dual of ℓ r in this case is unknown), but using [START_REF] Muscalu | Bi-parameter paraproducts[END_REF] we were able to linearize the L p,∞ norm of k |T (f k , g k )| r 1/r .

  This operator was introduced by Alberto Calderón, in relation to the analysis of the Cauchy integral on Lipschitz curves and to what are now called Calderón's commutators.


David Cohen
email: david.cohen@umu.se

Guillaume Dujardin
email: guillaume.dujardin@inria.fr

EXPONENTIAL INTEGRATORS FOR NONLINEAR SCHRÖDINGER EQUATIONS WITH WHITE NOISE DISPERSION

Keywords: Stochastic partial differential equations, Nonlinear Schrödinger equation, White noise dispersion, Numerical methods, Geometric Numerical Integration, Exponential integrators, Mean-square convergence AMS subject classifications. 65C30, 65C50, 65J08, 60H15, 60-08

This article deals with the numerical integration in time of the nonlinear Schrödinger equation with power law nonlinearity and random dispersion. We introduce a new explicit exponential integrator for this purpose that integrates the noisy part of the equation exactly. We prove that this scheme is of mean-square order 1 and we draw consequences of this fact. We compare our exponential integrator with several other numerical methods from the literature. We finally propose a second exponential integrator, which is implicit and symmetric and, in contrast to the first one, preserves the L 2 -norm of the solution.

1. Introduction. We consider the time discretisation of the following nonlinear Schrödinger equation with white noise dispersion idu

+ c∆u • dβ + |u| 2σ u dt = 0 u(0) = u 0 , ( 1.1)
where the unknown u = u(x,t), with t ≥ 0 and x ∈ R d , is a complex valued random process,

∆u = d ∑ j=1 ∂ 2 u ∂ x 2 j
denotes the Laplacian in R d , c is a real number, σ is a positive integer, and β = β (t) is a real valued standard Brownian motion. This stochastic partial differential equation is understood in the Stratonovich sense, using the • symbol for the Stratonovich product.

The existence of a unique global square integrable solution to (1.1) was shown in [START_REF] De | The nonlinear Schrödinger equation with white noise dispersion[END_REF] for σ < 2/d and in [START_REF] Debussche | 1D quintic nonlinear Schrödinger equation with white noise dispersion[END_REF] for d = 1 and σ = 2, see also [START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF]. The existence and uniqueness of solutions to the one-dimensional cubic case of the above problem was also studied in [START_REF] Marty | On a splitting scheme for the nonlinear Schrödinger equation in a random medium[END_REF]. Furthermore, as for the deterministic Schrödinger equation, the L 2 -norm, or mass, of the solution to (1.1) is a conserved quantity. This is not the case for the total energy of the problem.

We now review the literature on the numerical analysis of the nonlinear Schrödinger equation with white noise dispersion (1.1). The early work [START_REF] Garnier | Stabilization of dispersion-managed solitons in random optical fibers by strong dispersion management[END_REF] studies the stability with respect to random dispersive fluctuations of the cubic Schrödinger equation. Furthermore, numerical experiments using a split step Fourier method are presented. The paper [START_REF] Marty | On a splitting scheme for the nonlinear Schrödinger equation in a random medium[END_REF] presents a Lie-Trotter splitting integrator for the above problem (1.1). The mean-square order of convergence of this explicit numerical method is proven to be at least 1/2 for a truncated Lipschitz nonlinearity [START_REF] Marty | On a splitting scheme for the nonlinear Schrödinger equation in a random medium[END_REF]Sect. 5 and 6]. Furthermore, [START_REF] Marty | On a splitting scheme for the nonlinear Schrödinger equation in a random medium[END_REF] conjectures that this splitting scheme should have order one, and supports this conjecture numerically. An analysis of asymptotic preserving properties of the Lie-Trotter splitting is carried out in [START_REF] Duboscq | Analyse et simulations numériques d'équations de Schrödinger déterministes et stochastiques[END_REF] for a more general nonlinear dispersive equation. Very recently, the authors of [START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF] studied an implicit Crank-Nicolson scheme for the time integration of (1.1). They show that this scheme preserves the L 2 -norm and has mean-square order one of convergence in probability.

In the present publication, we will consider exponential integrators for an efficient time discretisation of the nonlinear stochastic Schrödinger equation (1.1). Exponential integrators for the time integration of deterministic semi-linear problems of the form ẏ = Ly + N(y), are nowadays widely used and studied, as witnessed by the recent review [START_REF] Hochbruck | Exponential integrators[END_REF]. Applications of such numerical schemes to the deterministic (nonlinear) Schrödinger equation can be found in, for example, [START_REF] Hochbruck | Exponential integrators for quantum-classical molecular dynamics[END_REF][START_REF] Berland | Solving the nonlinear Schrödinger equation using exponential integrators[END_REF][START_REF] Berland | Conservation of phase space properties using exponential integrators on the cubic Schrödinger equation[END_REF][START_REF] Celledoni | Symmetric exponential integrators with an application to the cubic Schrödinger equation[END_REF][START_REF] Dujardin | Exponential Runge-Kutta methods for the Schrödinger equation[END_REF][START_REF] Gauckler | Exponential integrators for nonlinear Schrödinger equations over long times[END_REF][START_REF] Cano | Exponential time integration of solitary waves of cubic Schrödinger equation[END_REF][START_REF]Projected explicit Lawson methods for the integration of Schrödinger equation[END_REF][START_REF] Besse | High order exponential integrators for nonlinear Schrödinger equations with application to rotating Bose-Einstein condensates[END_REF] and references therein. Furthermore, these numerical methods were investigated for stochastic parabolic partial differential equations in, for example, [START_REF] Lord | A numerical scheme for stochastic PDEs with Gevrey regularity[END_REF][START_REF] Kloeden | The numerical approximation of stochastic partial differential equations[END_REF][START_REF] Lord | Stochastic exponential integrators for the finite element discretization of SPDEs for multiplicative and additive noise[END_REF], more recently for the stochastic wave equations in [START_REF] Cohen | A trigonometric method for the linear stochastic wave equation[END_REF][START_REF] Wang | An exponential integrator scheme for time discretization of nonlinear stochastic wave equation[END_REF][START_REF] Quer-Sardanyons | A fully discrete approximation of the onedimensional stochastic wave equation[END_REF][START_REF] Anton | Full discretisation of semi-linear stochastic wave equations driven by multiplicative noise[END_REF], where they are termed stochastic trigonometric methods, and lately to stochastic Schrödinger equations driven by Ito noise in [START_REF] Dujardin | Exponential integrators for stochastic Schrödinger equations driven by ito noise[END_REF].

The main result of this paper is a mean-square convergence result for an explicit and easy to implement exponential integrator for the time discretisation of (1.1). Indeed, we will show in Section 3 convergence of mean-square order one for this scheme as well as convergence in probability. Note that the proofs of the results presented here use similar techniques as the one used in [START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF].

In order to show the above convergence result, we begin the exposition by introducing some notations and recalling useful results in Section 2. After that, we present our explicit exponential integrator for the numerical approximation of the above stochastic Schrödinger equation and analyse its convergence in Section 3. Various numerical experiments illustrating the main properties of our numerical scheme will be presented in Section 4. In the last section, we discuss the preservation of the mass, or L 2 -norm, by symmetric exponential integrators.

2. Notation and useful results. We denote the classical Lebesgue space of complex functions by L 2 := L 2 (R d , C), endowed with its real vector space structure, and with the scalar product

(u, v) := Re ∫ R d u v dx.
For s ∈ N, we further denote by H s := H s (R d , C) the Sobolev space of functions in L 2 such that their s first derivatives are in L 2 . The Fourier transform of a tempered distribution v is denoted by F (v) or v. With this, H s is the Sobolev space of tempered distributions v such that

(1 + |ζ | 2 ) s/2 v ∈ L 2 .
Next, we consider a filtered probability space (Ω, F , P, {F t } t≥0 ) generated by a onedimensional standard Brownian motion β = β (t).

With the above definitions in hand, we can write the mild formulation of the stochastic nonlinear Schrödinger equation (1.1) (with the constant c = 1 for ease of presentation) [START_REF] Marty | On a splitting scheme for the nonlinear Schrödinger equation in a random medium[END_REF][START_REF] De | The nonlinear Schrödinger equation with white noise dispersion[END_REF][START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF]

u(t) = S(t, 0)u 0 + i ∫ t 0 S(t, r)(|u(r)| 2σ u(r)) dr, ( 2.1)
with the random propagator S(t, r) expressed in the Fourier variables as

F (S(t, r)v(r))(ζ ) = exp ( -i |ζ | 2 (β (t) -β (r)) ) v(r)(ζ ) for t ≥ r ≥ 0, ζ ∈ R d and v a tempered distribution.
We finally collect some results that we will use in the error analysis presented in Section 3:

• The random propagator S(t, r) is an isometry in H s for any s, see for example [START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF].

• There is a constant C such that, for t ≥ 0, h ∈ (0, 1) and r ∈ (t,t + h) and for any F tmeasurable function v ∈ L 2 (Ω, H s+4 ), one has the bounds (see [3, Lemma 2.10 and equation

(2.46)]) E[∥S(r,t)v -v∥ 2 H s ] ≤ ChE[∥v∥ 2 H s+2 ] (2.2) ∥E[(S(r,t) -I)v]∥ 2 H s ≤ Ch 2 E[∥v∥ 2 H s+4 ]. (2.3)
• Without much loss of generality, we will truncate the nonlinearity in (1.1) in Section 3. Therefore, we recall the following estimates. Let f be a function from H s to H s , which sends H s+2 to itself and H s+4 to itself, with f (0) = 0, twice continuously differentiable on those spaces, with bounded derivatives of order 1 and 2. Consider u a solution on [0, T ] of

u(r) -u(t) = S(r,t)u(t) -u(t) + i ∫ r t S(r, σ ) f (u(σ )) dσ .
Then, there exists a constant C, which depends on f , such that (see [START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF]Equations (2.30) and (2.44)])

E[∥u(r) -u(t)∥ 2 H s ] ≤ Ch sup σ ∈[0,T ] E[∥u(σ )∥ 2 H s+2 ] (2.4) E[∥u(r) -u(t)∥ 4 H s ] ≤ Ch 2 sup σ ∈[0,T ] E[∥u(σ )∥ 4 H s+2 ], (2.5)
with h, r,t as in the above point (provided that the right-hand side is finite).

3. Exponential integrator and mean-square error analysis. This section presents an explicit time integrator for (1.1), and further states and proves a mean-square convergence result for this numerical method. As a by-product result, we also obtain convergence in probability of the exponential integrator.

3.1. Presentation of the exponential integrator. Let T > 0 be a fixed time horizon and an integer N ≥ 1. We define the step size of the numerical method by h = T /N and denote the discrete times by t n = nh, for n = 0, . . . , N. Looking at the mild solution (2.1) of the problem (1.1) on the interval [t n ,t n+1 ], and discretising the integral (by freezing the integrand at the left-end point of this interval), one can iteratively define the following explicit exponential integrator

u 0 = u(0) u n+1 = S(t n+1 ,t n )u n + ihS(t n+1 ,t n )(|u n | 2σ u n ). (3.1)
We thus obtain a finite sequence of numerical approximations u n ≈ u(t n ) of the exact solution to the problem (1.1) at the discrete times t n = nh.

Truncated Schrödinger equation.

As in [START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF], we introduce a cut-off function in order to cope with the nonlinear part of the stochastic partial differential equation (1.1)

: Let θ ∈ C ∞ (R + ) with θ ≥ 0, supp(θ ) ⊂ [0, 2] and θ ≡ 1 on [0, 1]. For k ∈ N * and x ≥ 0, we set θ k (x) = θ ( x k ). Finally, one defines f k (u) = θ k (∥u∥ 2 H s+4 ) |u| 2σ u.
Observe that, for s > d/2 and σ ∈ N ⋆ , for a fixed k ∈ N * , f k is a bounded Lipschitz function from H s to H s which sends H s+2 to H s+2 and H s+4 to H s+4 . It is twice differentiable on these spaces, with bounded and continuous derivatives of order 1 and 2. Thus one has a unique global adapted solution u k to the truncated problem in L ∞ (Ω, C ([0, T ], H s )) if the initial value u 0 ∈ H s , see [START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF]. Note that, with the assumptions above, u k ∈ L ∞ (Ω, C ([0, T ], H s )) as soon as u 0 ∈ H s+2 , and

u k ∈ L ∞ (Ω, C ([0, T ], H s+4 )) as soon as u 0 ∈ H s+4 . The global solution u k ∈ L ∞ (Ω, C ([0, T ], H s )) to the truncated problem solves u k (t) = S(t, 0)u 0 + i ∫ t 0 S(t, r) f k (u k (r)) dr, (3.2)
and the exponential integrator takes the form

u k 0 = u(0) u k n+1 = S(t n+1 ,t n )u k n + ihS(t n+1 ,t n ) f k (u k n ). (3.3)
Note that this method looks like the composition of two methods : The first is the explicit Euler equation applied to the differential equation u ′ = f k (u), the second is the exact solution of the linear stochastic Schrödinger equation.

Main result and convergence analysis.

This subsection states and proves the main result of this paper on the mean-square convergence of the exponential integrator applied to the nonlinear Schrödinger equation with white noise dispersion (1.1). THEOREM 3.1. Let us fix s > d/2, the initial value u 0 ∈ H s+4 (R d ) and an integer k ≥ 1. Consider the unique adapted truncated solution of the random nonlinear Schrödinger equation u k (t) given by (3.2) with path a.s. in C ([0, T ], H s+4 (R d )). Further, consider the numerical solutions {u k n }, n = 0, 1, . . . , N, given by the explicit exponential integrator (3.3) with step size h. One then has the following error estimate

∀ h ∈ (0, 1), sup n | nh≤T E[∥u k n -u k (t n )∥ 2 H s ] ≤ Ch 2
for the discrete times t n = nh. Here, the constant C does not depend on n, h with nh ≤ T but may depend on k, T,

sup t∈[0,T ] E[∥u k (t)∥ 4 s+2 ], sup t∈[0,T ] E[∥u k (t)∥ 2 s+4 ]. Proof.
For ease of presentation, we will ignore the index k refereeing to the cut-off in the notations of the numerical and exact solutions as well as in the nonlinear function f k . But we keep in mind that the constants below may depend on this index. We denote by C such a constant, providing it does not depend on n ∈ N nor on h ∈ (0, 1) such that nh ≤ T .

In order to later apply a discrete Gronwall-type argument, we first look at the error between the exact and numerical solutions

e n+1 := u(t n+1 ) -u n+1 = S(t n+1 ,t n )e n + ihS(t n+1 ,t n ) ( f (u(t n )) -f (u n ) ) -i ∫ t n+1 t n ( S(t n+1 ,t n ) f (u(t n )) -S(t n+1 , r) f (u(r) ) dr = S(t n+1 ,t n )e n + ihS(t n+1 ,t n ) ( f (u(t n )) -f (u n ) ) -i ∫ t n+1 t n ( S(t n+1 ,t n ) -S(t n+1 , r) ) f (u(t n )) dr -i ∫ t n+1 t n S(t n+1 , r) ( f (u(t n ) -f (u(r) ) dr =: I 1 + I 2 + I 3 + I 4 .
The so-called mean-square error thus reads

E[∥e n+1 ∥ 2 s ] = 4 ∑ j=1 E[∥I j ∥ 2 s ] + 2 4 ∑ j=1 4 ∑ k= j+1 E[Re(I j , I k ) s ], (3.4)
with the

H s norm ∥•∥ 2 s = Re(•, •) s = ∥•∥ 2 H s .
We now proceed with the estimations of the above quantities. Before estimating the mixed terms in (3.4), we start with the first four terms. By isometry of the random propagator S(t, r), one gets

E[∥I 1 ∥ 2 s ] = E[∥S(t n+1 ,t n )e n ∥ 2 s ] = E[∥e n ∥ 2 s ].
For the second term, we again use the isometry property of the free random propagator and further the fact that the function f is Lipschitz. This gives us

E[∥I 2 ∥ 2 s ] = E[∥hS(t n+1 ,t n ) ( f (u(t n )) -f (u n ) ) ∥ 2 s ] = h 2 E[∥ f (u(t n )) -f (u n )∥ 2 s ] ≤ Ch 2 E[∥e n ∥ 2 s ].
Using the isometry property of S(t, r), Cauchy-Schwarz's inequality, the estimate (2.2) from Section 2, and the fact that the exact solution is bounded, we can bound the third term by

E[∥I 3 ∥ 2 s ] = E[∥ ∫ t n+1 t n S(t n+1 ,t n )(I -S(t n , r)) f (u(t n )) dr∥ 2 s ] ≤ E[ ( ∫ t n+1 t n 1 • ∥S(t n+1 ,t n )(I -S(t n , r)) f (u(t n ))∥ s dr ) 2 ] ≤ h ∫ t n+1 t n E[∥(I -S(t n , r)) f (u(t n ))∥ 2 s ] dr = h ∫ t n+1 t n E[∥S(t n , r)(S(r,t n ) -I) f (u(t n ))∥ 2 s ] dr ≤ Ch 2 ∫ t n+1 t n E[∥ f (u(t n ))∥ 2 s+2 ] dr ≤ Ch 3 sup t∈[0,T ] E[∥u(t)∥ 2 s+2 ] ≤ Ch 3 .
In order to estimate the fourth term, we use the isometry property of the free random propagator, Cauchy-Schwarz's inequality, the fact that f is Lipschitz, the estimate (2.4) on the time-variations of the exact solution, and the fact that the exact solution is bounded which is recalled in Section 2. We then obtain

E[∥I 4 ∥ 2 s ] = E[∥ ∫ t n+1 t n S(t n+1 , r) ( f (u(t n )) -f (u(r)) ) dr∥ 2 s ] ≤ Ch ∫ t n+1 t n E[∥ f (u(t n )) -f (u(r))∥ 2 s ] dr ≤ Ch ∫ t n+1 t n E[∥u(t n ) -u(r)∥ 2 s ] dr ≤ Ch 3 sup t∈[0,T ] E[∥u(t)∥ 2 s+2 ] ≤ Ch 3 .
Next, we go on with deriving bounds for the mixed terms present in (3.4). Using Cauchy-Schwarz's inequality, the above bounds for the moments of I 2 and I 3 , and the fact that for all real numbers a, b, we have ab ≤ 1 2 (a 2 + b 2 ), we obtain the bound

|E[(I 2 , I 3 ) s ]| ≤ ( E[∥I 2 ∥ 2 s ] ) 1/2 ( E[∥I 3 ∥ 2 s ] ) 1/2 ≤ Ch ( E[∥e n ∥ 2 s ] ) 1/2 h 3/2 ≤ C(hE[∥e n ∥ 2 s ] + h 4 ).
Similarly, one has

|E[(I 2 , I 4 ) s ]| ≤ C(hE[∥e n ∥ 2 s ] + h 4 )
and

|E[(I 3 , I 4 ) s ]| ≤ Ch 3 .
The term containing I 1 and I 2 can be estimated using Cauchy-Schwarz's inequality and the fact that the function f is Lipschitz:

|E[(I 1 , I 2 ) s ]| = E[(S(t n+1 ,t n )e n , ihS(t n+1 ,t n ) ( f (u(t n )) -f (u n ) ) ) s ] ≤ ( E[∥e n ∥ 2 s ] ) 1/2 h ( E[∥ f (u(t n )) -f (u n )∥ 2 s ] ) 1/2 ≤ ChE[∥e n ∥ 2 s ].
E[(I 1 , I 3 ) s ] = E[(S(t n+1 ,t n )e n , ∫ t n+1 t n S(t n+1 ,t n )(I -S(t n , r)) f (u(t n )) dr) s = E[(e n , ∫ t n+1 t n (I -S(t n , r)) f (u(t n )) dr) s ≤ h 1/2 ( ∫ t n+1 t n |E[(e n , (I -S(t n , r)) f (u(t n ))) s ]| 2 dr ) 1/2 .
We next apply the law of total expectation and again Cauchy-Schwarz's inequality in order to get

E[(I 1 , I 3 ) s ] ≤ h 1/2 ( ∫ t n+1 t n |E[(e n , E{(I -S(t n , r)) f (u(t n ))|F t n }) s ]| 2 dr ) 1/2 ≤ h 1/2 ( ∫ t n+1 t n E[∥e n ∥ 2 s ] • E[∥E{(I -S(t n , r)) f (u(t n ))|F t n }∥ 2 s ] dr ) 1/2 .
Finally, using (2.3) and the fact that the exact solution is bounded, one obtains the bound

E[(I 1 , I 3 ) s ] ≤ Ch 1/2 ( E[∥e n ∥ 2 s ] ) 1/2 h ( ∫ t n+1 t n E[∥ f (u(t n ))∥ 2 s+4 ] dr ) 1/2 ≤ Ch 2 ( E[∥e n ∥ 2 s ] ) 1/2 ( sup t∈[0,T ] E[∥ f (u(t))∥ 2 s+4 ] ) 1/2 ≤ Ch 2 ( E[∥e n ∥ 2 s ] ) 1/2 ≤ C(h 3 + hE[∥e n ∥ 2 s ]).
In order to estimate the last term |E[(I 1 , I 4 ) s ]|, we use the mild formulation

u(r) -u(t n ) = S(t n , r)u(t n ) -u(t n ) + i ∫ r t n S(t n , θ ) f (u(θ )) dθ = (S(t n , r) -I)u(t n ) + i ∫ r t n S(t n , θ ) f (u(θ )) dθ ,
and then Cauchy-Schwarz's inequality and a Taylor expansions of

f ∈ C 2 b (H s , H s ) to arrive at |E[(I 1 , I 4 ) s ]| = E[(S(t n+1 ,t n )e n , ∫ t n+1 t n S(t n+1 , r)( f (u(t n )) -f (u(r))) dr) s ] = ∫ t n+1 t n 1 • E[(e n , S(t n , r)( f (u(t n )) -f (u(r)))) s ] dr ≤ Ch 1/2 ( ∫ t n+1 t n |E[(e n , S(t n , r)( f (u(t n )) -f (u(r)))) s ]| 2 dr ) 1/2 ≤ Ch 1/2 ( ∫ t n+1 t n E[(e n , S(t n , r) { D f (u(t n ))(u(r) -u(t n )) } ) s ] 2 dr ) 1/2 +Ch 1/2 ( ∫ t n+1 t n |E[(e n , S(t n , r) { ∫ 1 0 D 2 f (θ u(r) + (1 -θ )u(t n )) dθ × (u(r) -u(t n ), u(r) -u(t n )) } ) s ]| 2 dr ) 1/2 ≤ Ch 1/2 ( ∫ t n+1 t n |E[J 1 ]| 2 dr ) 1/2 +Ch 1/2 ( ∫ t n+1 t n |E[J 2 ]| 2 dr ) 1/2 .
It thus remains to bound the above two terms. In order to start to estimate the first term, we insert the mild solution and obtain

h 1/2 ( ∫ t n+1 t n |E[J 1 ]| 2 dr ) 1/2 ≤ h 1/2 ( ∫ t n+1 t n |E[(e n , S(t n , r)D f (u(t n )) { (S(t n , r) -I)u(t n ) + i ∫ r t n S(t n , θ ) f (u(θ )) dθ } ) s ]| 2 dr ) 1/2 ≤ h 1/2 ( ∫ t n+1 t n E[(e n , S(t n , r)D f (u(t n )) { (S(t n , r) -I)u(t n ) } ) s ] 2 dr ) 1/2 + h 1/2 ( ∫ t n+1 t n E[(e n , S(t n , r)D f (u(t n )) { ∫ r t n S(t n , θ ) f (u(θ )) dθ } ) s ] 2 dr ) 1/2 .
We can now apply Cauchy-Schwarz's inequality, the fact that S, f , D f are bounded and the regularity estimate (2.3) from Section 2 to arrive at

h 1/2 ( ∫ t n+1 t n |E[J 1 ]| 2 dr ) 1/2 ≤ Ch 1/2 ( ∫ t n+1 t n E[∥e n ∥ 2 s ]E[∥(S(t n , r) -I)u(t n )∥ 2 s ] dr ) 1/2 +Ch 1/2 ( ∫ t n+1 t n E[∥e n ∥ 2 s ]E[∥ ∫ r t n S(t n , θ ) f (u(θ )) dθ ∥ 2 s ] dr ) 1/2 ≤ Ch 1/2 (E[∥e n ∥ 2 s ]) 1/2 h 1/2 h sup t∈[0,T ] (E[∥u(t)∥ 2 s+4 ]) 1/2 +Ch 1/2 (E[∥e n ∥ 2 s ]) 1/2 ( ∫ t n+1 t n (r -t n ) 2 dr ) 1/2 ≤ Ch 2 (E[∥e n ∥ 2 s ]) 1/2 ( 1 + sup t∈[0,T ] (E[∥u(t)∥ 2 s+4 ]) 1/2 ) ≤ C(h 3 + hE[∥e n ∥ 2 s ]) ( 1 + sup t∈[0,T ] (E[∥u(t)∥ 2 s+4 ]) 1/2
) .

For the second term, we again use Cauchy-Schwarz's inequality with the fact that S, D f and D 2 f are bounded and the bound (2.5):

h 1/2 ( ∫ t n+1 t n |E[J 2 ]| 2 dr ) 1/2 ≤ Ch 1/2 ( ∫ t n+1 t n E[∥e n ∥ 2 s ]E[∥u(r) -u(t n )∥ 4 s ] dr ) 1/2 ≤ Ch 1/2 (E[∥e n ∥ 2 s ]) 1/2 h 1/2 h sup t∈[0,T ] (E[∥u(t)∥ 4 s+2 ]) 1/2 ≤ Ch 2 (E[∥e n ∥ 2 s ]) 1/2 sup t∈[0,T ] (E[∥u(t)∥ 4 s+2 ]) 1/2 ≤ C(h 3 + hE[∥e n ∥ 2 s ]) sup t∈[0,T ] (E[∥u(t)∥ 4 s+2 ]) 1/2 .
Altogether, we arrive at

E[(I 1 , I 4 ) s ] ≤ C(h 3 + hE[∥e n ∥ 2 s ]) ( 1 + sup t∈[0,T ] (E[∥u(t)∥ 4 s+2 ]) 1/2 + sup t∈[0,T ] (E[∥u(t)∥ 2 s+4 ]) 1/2
) .

Collecting all the above bounds, the mean-square error (3.4) can thus be estimated by

E[∥e n+1 ∥ 2 s ] ≤ (1 + K 1 h + K 2 h 2 )E[∥e n ∥ 2 s ] + K 3 h 3 + K 4 h 4
and an application of a discrete Gronwall lemma gives the final bound

E[∥e n ∥ 2 s ] = E[∥u k n -u k (t n )∥ 2 s ] ≤ Ch 2
which concludes the proof of the theorem. Using the above mean-square convergence result and similar arguments as in [START_REF] Marty | On a splitting scheme for the nonlinear Schrödinger equation in a random medium[END_REF][START_REF] Gazeau | Probability and pathwise order of convergence of a semidiscrete scheme for the stochastic Manakov equation[END_REF] or [START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF], one can also show that the exponential method (3.1) has order of convergence one in probability.

PROPOSITION 3.2. Let T > 0 and assume that u 0 ∈ H s+4 (R d ) with s > d/2 is such that the nonlinear Schrödinger equation with white noise dispersion (1.1) possesses a unique adapted solution u with paths a.s. in C ([0, T ], H s+4 (R d )). Let us apply the stochastic exponential integrator (3.1) to compute u n with step size h = T /N. Then, one has

lim C→+∞ P ( max n=0,...,N ∥u(t n ) -u n ∥ s ≥ Ch ) = 0
uniformly in h, where we recall that t n = nh.

4. Numerical experiments. This section presents various numerical experiments for the nonlinear Schrödinger equation with white noise dispersion (1.1). We will use the following numerical schemes:

1. The explicit exponential integrator (3.1); 2. The Lie-Trotter splitting

u * = S(t n+1 ,t n )u n u n+1 = Y (h)u * (4.1)
from [START_REF] Marty | On a splitting scheme for the nonlinear Schrödinger equation in a random medium[END_REF]. Here, Y (h)u * denotes the value at time h of flow associated to the problem i ∂ u ∂t + |u| 2σ u = 0 with initial datum u * ; 3. The Strang splitting

u * = S(t n + h/2,t n )u n u = Y (h)u * u n+1 = S(t n+1 ,t n + h/2) u, ( 4.2)
where again Y (h) is defined as above; 4. The implicit Crank-Nicolson scheme

i u n+1 -u n h + χ n √ h ∆u n+1/2 + g(u n , u n+1 ) = 0 (4.3)
from [START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF]. Here, we have set

u n+1/2 = 1 2 (u n + u n+1 ), χ n = β (t n+1 )-β (t n ) √ h and g(u, v) = 1 σ +1 ( |u| 2σ +2 -|v| 2σ +2 |u| 2 -|v| 2 )( u+v 2
) .

We will consider the stochastic partial differential equation (1.1) on the one and two dimensional torus with periodic boundary conditions. The spatial discretisation is done by a pseudospectral method with M Fourier modes in 1d, and M 2 Fourier modes in 2d.

Numerical experiments in 1d

. This subsection presents convergence plots for the above mentioned numerical methods applied to the nonlinear Schrödinger equation with white noise dispersion (1.1); space-time evolution plots; experiments illustrating the influence of the power nonlinearity σ supporting a conjecture proposed in [START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF]; and finally illustrations of the preservation of the L 2 -norm along numerical solutions.

c = σ = 1. The initial datum is u 0 (x) = e -(x-π) 2 for x ∈ [0, 2π]. Furthermore, M = 2 8
Fourier modes are used for the spatial discretisation. The mean-square errors E[∥u(x, T end )u N (x)∥ 2

L 2 ] at time T end = 0.5 are displayed in Figure 4.1 for various values of the time step h = 2 -ℓ for ℓ = 6, . . . , 17. Here, we simulate the exact solution u(x,t) with the exponential method, with a small time step h exact = 2 -17 . The expected values are approximated by computing averages over M s = 5000 samples. We computed the estimate for the largest standard errors to be 5.78 • 10 -4 for the Crank-Nicolson scheme and around 10 -6 for the other numerical schemes. These estimates are far from optimal but we observed that using a larger number of samples (M s = 10000) does not improve significantly the behaviour of the convergence plots. This is also the case for the other convergence plots presented below. In Figure 4.1, we observe convergence of order 1 for the exponential integrator. This is in agreement with Theorem 3.1. The orders of convergence for the splitting schemes and for the Crank-Nicolson scheme are also seen to be 1.

Note that the explicit exponential method (3.3), as well as the Lie and Strang splitting methods (4.1)-(4.2) take full advantage of the exact integration of the stochastic linear part of the Schrödinger equation when one uses periodic boundary conditions and hence the spectral properties of the Laplace operator are exactly known. In contrast, the Crank-Nicolson scheme (4.3) does not integrate the stochastic part of the equation exactly. One can even argue that the error in the identity

1 + iX 1 -iX = e 2iX + O(X 3 ),
which is the cornerstone of the error analysis of the linear part of the Crank-Nicolson scheme applied to a Schrödinger equation, is fully under control in the deterministic case (when X = -h 2 ξ 2 , and ξ is the Fourier variable), while it can be much higher in the stochastic case (when X = -c ∆W n 2 ξ 2 ) even for small time steps. Once again, such an error corresponding directly to the stochastic part of the PDE is not present in the three other schemes (3.1), (4.1) and (4.2). This explains, in 1d as well as in higher dimension (see next section for numerical 8 . This illustrates, in the case σ = 1, the interplay and the balance between the random dispersion and the nonlinearity. In contrast, the qualitative behaviour is different for higher values of σ .

The article [START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF] conjectures that the power nonlinearity σ = 4 is the critical case for (1.1) in dimension one. We now present numerical experiments supporting this conjecture. Problem (1.1) with the initial value u 0 (x) = 2.3 • e -14(x-π) 2 is integrated over the time interval [0, 0.05] with discretisation parameters h = 2 -12 and M = 2 14 . Figure 4.4 shows the spacetime evolution for the power nonlinearity σ = 3.9 and σ = 4. Blow-up of the solution can be observed in the critical case σ = 4 thus numerically confirming the conjecture from [START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF]. Of course, this is only a rough result and one can think of more sophisticated techniques such as adaptive mesh refinement techniques to have a better understanding of the behaviour of the solution close to the blow-up.

4.1.3. Preservation of the L 2 -norm. It is known that the L 2 -norm of the solution to the SPDE (1.1) remains constant for all times [START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF]. Figure 4.5 illustrates the corresponding preservation properties of the above numerical integrators along one sample path. For this numerical experiment, we consider the parameters c = 1, σ = 1, h = 2 -5 , M = 2 8 and the initial value u 0 (x) = e -10(x-π) 2 for x ∈ [0, 2π]. Exact preservation of the L 2 -norm for the splitting schemes and for the Crank-Nicolson scheme is observed, whereas a small drift is observed for the exponential integrator (3.1). In Section 5, we will propose a symmetric exponential integrator that preserves exactly the L 2 -norm.

4.2.

Numerical experiments in 2d. This subsection presents convergence plots for (1.1) in two dimensions as well as experiments illustrating the influence of the power nonlinearity σ supporting a conjecture proposed in [START_REF] Belaouar | Numerical analysis of the nonlinear Schrödinger equation with white noise dispersion[END_REF].

Convergence plots.

We illustrate the mean-square convergence of the exponential integrator (3.1) in 2d. To do so, we consider the problem (1.1) on [0, 2π] × [0, 2π] with parameters σ = 1 and c = 1 or c = 0.1. The initial value is set to be u 0 (x, y) = e -((x-π/2) 2 +(y-π/2) 2 ) e i10x + e -0.5((x-3π/2) 2 +(y-3π/2) 2 ) e -i10y for (x, y) ∈ [0, 2π] × [0, 2π]. Furthermore, M = 2 6 Fourier modes are used in each directions for the spatial discretisation. The temporal errors at time T end = 0.5 are displayed in Figure 4.6 for various values of the time step h = 2 -ℓ for ℓ = 15, . . . , 23. Here, we simulate the exact solution u(x, y,t) with a small time step h exact = 2 -23 . The expected values are approximated by computing averages over M s = 25 samples (for these computationally expensive simulations). In this figure, we observe convergence of order 1 for the exponential integrator. This is in agreement with Theorem 3.1. 5. L 2 -preserving exponential integrators. As seen above, the proposed explicit exponential integrator unfortunately does not preserve the L 2 -norm. This can be fixed by considering symmetric exponential integrators using ideas from [START_REF] Celledoni | Symmetric exponential integrators with an application to the cubic Schrödinger equation[END_REF]. We thus propose the following symmetric exponential method for the numerical discretisation of nonlinear Schrödinger equation with white noise dispersion (1.1)

u 0 = u(0) N * = N(S(t n + h 2 ,t n )u n + h 2 N * ) u n+1 = S(t n+1 ,t n )u n + hS(t n + h,t n + h 2 )N * , ( 5.1)
where N(u) = i|u| 2σ u is the nonlinearity. This numerical method preserves the L 2 -norm as seen in the following proposition. PROPOSITION 5.1. The exponential integrator (5.1) preserves the L 2 -norm, as does the exact solution of the nonlinear Schrödinger equation with white noise dispersion (1.1).

Proof. This proof is an adaptation of the proof stating conditions for a Runge-Kutta methods to preserve quadratic invariants, see [19, Section IV.2.1] and further [START_REF] Celledoni | Symmetric exponential integrators with an application to the cubic Schrödinger equation[END_REF]. Let us compute the L 2 -norm of u 1 :

∥u 1 ∥ 2 = ∥S(t 1 ,t 0 )u 0 + hS(t 0 + h,t 0 + h 2 )N * ∥ 2 = ∥u 0 ∥ 2 + h 2 ∥N * ∥ 2 + h ( S(t 1 ,t 0 )u 0 , S(t 0 + h,t 0 + h 2 )N * ) + h ( S(t 0 + h,t 0 + h 2
)N * , S(t 1 ,t 0 )u 0 ) using the isometry of the random propagator S(t, r). We next define Y := S(t 0 + h 2 ,t 0 )u 0 + h 2 N * so that u 0 = S(t 0 ,t 0 + h 2 )(Y -h 2 N * ). Inserting this quantity in the above equation and using the definition of S(t, r) yields

∥u 1 ∥ 2 = ∥u 0 ∥ 2 + h 2 ∥N * ∥ 2 - h 2 2 ∥N * ∥ 2 - h 2 2 ∥N * ∥ 2 + h ( (Y, N * ) + (N * ,Y ) ) = ∥u 0 ∥ 2
since the last term in brackets is zero (this follows from the fact that N * = N(Y ) and the fact that the L 2 -norm is a first integral). dispersion (1.1). We showed that this integrator has mean-square order one (Theorem 3.1). We compared it with other methods from the literature. In contrast to methods such as the Lie-Trotter splitting or the Crank-Nicolson method, it does not preserve the L 2 -norm exactly (Figure 4.5). However, it shares the same order and our numerical experiments show that it outperforms methods that do not integrate exactly the linear part of the equation, such as the Crank-Nicolson method, in terms of size of constant errors, for reasonably large noise intensity (Figure 4.1). Furthermore, we used this new scheme in Section 4.2 to support a conjecture on the critical power to get blow-up in finite time in the nonlinear Schrödinger equation (1.1). Finally, we proposed another exponential integrator (5.1) which is symmetric and has the same numerical order as the one proposed initially. It however is implicit and hence has higher numerical cost.

Figure 4 . 1 :

 41 Figure 4.1: Mean-square errors for c = 1: Exponential integrator (□), Lie-Trotter (♢), Crank-Nicolson ( * ), Strang (•). The dotted lines have slopes 1 and 2.

Figure 4 . 2 :

 42 Figure 4.2: Mean-square errors for c = 0.25: Exponential integrator (□), Lie-Trotter (♢), Crank-Nicolson ( * ), Strang The dotted lines have slopes 1 and 2.

Figure 4 .

 4 3 shows the evolution of |u n | 2 along one sample of the numerical solution obtained by the exponential integrator (3.1) for the above problem with the discretisation parameters h = 2 -14 and M = 2

Figure 4 . 3 :

 43 Figure 4.3: Space-time evolution (up) and contour plot (bottom) for the exponential integrator (3.3).

Figure 4 . 4 :

 44 Figure 4.4: Space-time evolution for the exponential integrator: σ = 3.9 (up) and σ = 4 (bottom).

4. 2 . 2 .

 22 Evolution plots. Let us now consider the following parameters c = 1, h = 2 -11 , M = 2 7 and the initial value 5 • e -14((x-π/2) 2 +(y-π/2) 2 ) • e i10x for (x, y) ∈ [0, 2π] × [0, 2π].

  Figure 4.7 displays snapshots of the numerical solutions for the Schrödinger equation with power nonlinearity σ = 1.9 and σ = 2. Blow-up of the solution can be observed numerically in the conjectured critical case σ = 4/d = 2 from [3].

Figure 4 . 5 :

 45 Figure 4.5: Preservation of the L 2 -norm: Exponential integrator (□), Lie-Trotter (♢), Crank-Nicolson ( * ), Strang (•).

Figure 4 . 6 :

 46 Figure 4.6: Mean-square errors in 2d for c = 1 (left) and c = 0.1 (right): Exponential integrator (□), Lie-Trotter (♢), Crank-Nicolson ( * ), Strang (•). The dotted lines have slopes 1 and 2.

Figure 4 . 7 :

 47 Figure 4.7: Snapshots of the evolution of the exponential integrator in 2d: σ = 1.9 (up) and σ = 2 (bottom). Discretisation parameters: h = 2 -11 and M = 2 7 . Note the scale on the z-axis on Figure 4.7f.

5. 1 .

 1 Numerical experiments for the symmetric exponential integrator.

Figure 5 Figure 5 . 1 :

 551 Figure 5.1: Preservation of the L 2 -norm (top) and mean-square errors (bottom) for the symmetric exponential integrator (5.1) (+) and for the exponential integrator (3.1) (□). The dotted lines have slopes 1 and 2.

  The last two terms |E[(I 1 , I 3 ) s ]| and |E[(I 1 , I 4 ) s ]| demand more work. For the first one, we use the isometry of the random propagator S(t, r) and Cauchy-Schwarz's inequality to get:


Konstantin Avrachenkov
email: k.avrachenkov@inria.fr

Vikas Vikram Singh

Stochastic Coalitional Better-response Dynamics and Stable Equilibrium *

Keywords: Strong Nash equilibrium, Coalitional better-response, Stochastic stability, Network formation games, Strongly stable networks

We consider coalition formation among players in an n-player finite strategic game over infinite horizon. At each time a randomly formed coalition makes a joint deviation from a current action profile such that at new action profile all the players from the coalition are strictly benefited. Such deviations define a coalitional better-response (CBR) dynamics that is in general stochastic. The CBR dynamics either converges to a K-stable equilibrium or becomes stuck in a closed cycle. We also assume that at each time a selected coalition makes mistake in deviation with small probability that add mutations (perturbations) into CBR dynamics. We prove that all K-stable equilibria and all action profiles from closed cycles, that have minimum stochastic potential, are stochastically stable. Similar statement holds for strict K-stable equilibrium. We apply the CBR dynamics to study the dynamic formation of the networks in the presence of mutations. Under the CBR dynamics all strongly stable networks and closed cycles of networks are stochastically stable.

Introduction

Nash equilibrium is most desirable solution concept in non-cooperative game theory. When a strategic game is played repeatedly over infinite horizon then the Nash equilibrium that is played in the long run depends on an initial action profile as well as the way all the players choose their actions at each time. Several discrete time dynamics have been studied in the literature to study the Nash equilibrium selection in the long run. Young [START_REF] Young | The evolution of conventions[END_REF] considered an n players strategic game where at each time all the players make a simultaneous move and each player chooses an action that is the best response to k previous games among the m, k ≤ m, most recent games in the past. In general this dynamics need not converge to a Nash equilibrium, it may stuck into a closed cycle. Young [START_REF] Young | The evolution of conventions[END_REF] also considered the case where at each time with small probability each player makes mistake and chooses some non-optimal action. These mistakes add mutations into the dynamics. In general the mutations can be sufficiently small. This leads to the definition of stability of Nash equilibrium as mutations vanish. This type of stability is called stochastic stability. Young proposed an algorithm to compute the stochastically stable Nash equilibria. For 2×2 coordination games he showed that the risk dominant Nash equilibrium is stochastically stable. Kandori et al. [START_REF] Kandori | Learning, mutation, and long run equilibria in games[END_REF] considered a different dynamic model where at each time each player plays with every other player in pairwise contest. The pairwise contest is given by 2 × 2 symmetric matrix game and each player chooses an action which has higher expected average payoff. The mutations are present into dynamics due to wrong actions taken by the players. For 2 × 2 coordination games they showed that a risk dominant Nash equilibrium is stochastically stable. That is, for 2 × 2 coordination games the dynamics given by [START_REF] Young | The evolution of conventions[END_REF] and [START_REF] Kandori | Learning, mutation, and long run equilibria in games[END_REF] selects the same Nash equilibrium. Fudenberg et al. [START_REF] Fudenberg | Evolutionary game dynamics in finite populations with strong selection and weak mutation[END_REF] proposed a dynamics where at each time only one player is selected to choose actions. The mutations with small probability also occur at each time. The risk dominant Nash equilibrium in 2 × 2 coordination games need not be stochastically stable under this dynamics.

The Nash equilibrium concept is inadequate for the situations where players can a priori communicate, being in a position to form a coalition and jointly deviate in a coordinated way. To capture such situations (strict) K-stable equilibrium [START_REF] Sawa | Coalitional stochastic stability in games, networks and markets[END_REF] is an adequate solution concept, where K is a set of all feasible coalitions. When there is no restriction on coalition formation, (strict) K-stable equilibrium corresponds to (strict) strong Nash equilibrium [START_REF] Aumann | Acceptable points in general cooperative n-person games[END_REF]. As motivated from the application of K-stable equilibria in network formation games considered in [START_REF] Dutta | Stable networks[END_REF][START_REF] Jackson | Strongly stable networks[END_REF][START_REF] Jackson | Social and Economic Networks[END_REF] we restrict ourselves to only pure actions. A K-stable equilibrium need not always exist and in such case there exist some set of action profiles forming a closed cycle such that it is possible to reach from one action profile to another via sequence of improving deviations by the coalitions; and it is not possible to reach an action profile outside of the closed cycle from an action profile belonging to closed cycle via improving deviations by the coalitions.

Recently, some stochastic dynamics involving the coalition formation among players have been proposed [START_REF] Avrachenkov | Network formation games with teams[END_REF][START_REF] Newton | Coalitional stochastic stability[END_REF][START_REF] Sawa | Coalitional stochastic stability in games, networks and markets[END_REF]. Sawa [START_REF] Sawa | Coalitional stochastic stability in games, networks and markets[END_REF] studied the stochastic stability in general finite games where the mutations are present through a logit choice rule. Newton [START_REF] Newton | Coalitional stochastic stability[END_REF] considers the situation where profitable coalitional deviations are given greater importance than unprofitable single player deviations. Avrachenkov et al. [START_REF] Avrachenkov | Network formation games with teams[END_REF] considered a variant of network formation game and discuss the stochastic stability of the networks when the networks are formed dynamically, in the presence of mutations, over infinite horizon. In general, the stochastic stability results depend on the way actions being chosen during the infinite play. Some other famous works on stochastic stability in different settings include [START_REF] Foster | Stochastic evolutionary game dynamics[END_REF][START_REF] Fudenberg | Imitation processes with small mutations[END_REF][START_REF] Fudenberg | Evolutionary game dynamics in finite populations with strong selection and weak mutation[END_REF][START_REF] Newton | Recontracting and stochastic stability in cooperative games[END_REF][START_REF] Newton | Coalitions, tipping points and the speed of evolution[END_REF][START_REF] Gale | College admissions and the stability of marriage[END_REF][START_REF] Roth | Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis[END_REF][START_REF] Klaus | Stochastic stability for roommate markets[END_REF][START_REF] Newton | A one-shot deviation principle for stability in matching problems[END_REF].

In this paper we propose a new stochastic dynamics due to the coalition formation in a strategic game over infinite horizon. We call our dynamics a coalitional better-response (CBR) dynamics where at each time players are allowed to form a coalition and make a joint deviation from the current action profile if it is strictly beneficial for all the members of the coalition. We assume that the coalition formation is random and at each time only one coalition can be formed among all feasible coalitions. We also consider the situation where at each time a selected coalition makes wrong decision with small probability, i.e., it moves to an action profile where all the players from the coalition are not strictly benefited. These mistakes work as mutations and add perturbations into CBR dynamics. We prove that the perturbed CBR dynamics selects K-stable equilibria or closed cycles, that has minimum stochastic potential among all action profiles, in the long run as mutations vanish. If there is no restriction on coalition formation, CBR dynamics selects all the strong Nash equilibria and closed cycles, i.e., all the strong Nash equilibria and closed cycles are stochastically stable. The similar CBR dynamics can be given for the case where each time a coalition deviate from a current action profile such that all the players from the coalition are at least as well off at new action profile and at least one player is strictly better off. In this case the similar results hold for strict K-stable equilibrium and strict strong Nash equilibrium (SSNE). Our CBR dynamics can be applied to network formation games which shows that all the strongly stable networks and closed cycles of networks are stochastically stable. Our CBR dynamics generalizes the stochastic dynamics considered in [START_REF] Avrachenkov | Network formation games with teams[END_REF] by considering the general finite games. The stochastic dynamics for pairwise stable networks considered in [START_REF] Jackson | The evolution of social and economic networks[END_REF] can also be viewed as a special case of our CBR dynamics.

The paper is organized as follows. Section 2 contains the model and few definitions. We describe the CBR dynamics in Section 3. We conclude our paper in Section 4.

The Model

We consider an n-player strategic game. Let N = {1, 2, • • • , n} be a finite set of players, and A i be a finite set of actions of player i whose element is denoted by a i . We denote A = n i=1 A i as a set of all action profiles and a = (a 1 , a 2 , • • • , a n ) denotes an element of A. The payoff function of player i is defined as u i : A → R. We consider settings where players may form a coalition and jointly revise their strategies. In many situations it may not be feasible to form all types of coalitions. Let K ⊆ P(N ) \ φ be the set of all feasible coalitions, where P(N ) denotes the power set of N and φ an empty set. For a coalition S ∈ K, define A S = i∈S A i whose element is denoted by a S and a -S denotes an action profile of players outside S. A coalition of players jointly deviate from a current action profile if at new action profile each player from the coalition is strictly benefited. Such a deviation leads to the definition of K-stable equilibrium. In some cases, a coalition of players jointly deviate from a current action profile if new action profile makes each player at least as well off and one player strictly better off. Such a deviation leads to the definition of strict K-stable equilibrium. Definition 2.1. An action profile a * is said to be a K-stable equilibrium if there is no S ∈ K and a ∈ A such that

1. a i = a * i , ∀ i / ∈ S.
2. u i (a) > u i (a * ), ∀ i ∈ S.

If K = P(N ) \ φ, a K-stable equilibrium is a strong Nash equilibrium (SNE) [START_REF] Aumann | Acceptable points in general cooperative n-person games[END_REF]. Let A(S, a) be the set of all action profiles reachable from a via deviation of coalition S. It is defined as, A(S, a) = {a |a i = a i , ∀ i / ∈ S and a i ∈ A i , ∀ i ∈ S}.

A coalition always has option to do nothing, so a ∈ A(S, a). Let I 1 (S, a) be a set of improved action profiles reachable from an action profile a via deviation of coalition S, i.e.,

I 1 (S, a) = {a |a i = a i , ∀ i / ∈ S and u i (a ) > u i (a), ∀ i ∈ S}. (1)
For an improved action profile a ∈ I 1 (S, a), an action profile a S of all the players from S is called a better-response of coalition S against a fixed action profile a -S of the players outside S. Define, I 1 (S, a) = A(S, a) \ I 1 (S, a) as a set of all action profiles due to the erroneous decisions of coalition S. It is clear that a ∈ I 1 (S, a), i.e., I 1 (S, a) is always nonempty for all S and a. A K-stable equilibrium need not always exist. In such a case there exist a set of action profiles lying on a closed cycle and all such action profiles can be reached from each other via an improving path. The definitions of closed cycle and improving path are as follows:

Definition 2.2 (Improving Path). An improving path from a to a is a sequence of action profiles and coalitions

a 1 , S 1 , a 2 , • • • , a m-1 , S m-1 , a m such that a 1 = a, a m = a and a k+1 ∈ I 1 (S k , a k ) for all k = 1, 2, • • • , m -1.

Definition 2.3 (Cycles).

A set of action profiles C form a cycle if for any a ∈ C and a ∈ C there exists an improving path connecting a and a . A cycle is said to be a closed cycle if no action profile in C lies on an improving path leading to an action profile that is not in C.

Theorem 2.4. There always exists a K-stable equilibrium or a closed cycle of action profiles, or both K-stable equilibrium and closed cycle.

Proof. An action profile is a K-stable equilibrium if and only if it is not possible for any feasible coalition from set K to make an improving deviation from it to another action profile. So, start at an action profile. Either it is K-stable equilibrium or there exists a coalition that can make an improving deviation to another action profile. In the first case result is established. For the second case the same thing holds, i.e., either this new action profile is a K-stable equilibrium or there exists a coalition that can make an improving deviation to another action profile. Given the finite number of action profiles, the above process either finds an action profile which is a K-stable equilibrium or it reaches to one of previous profiles, i.e., there exists a cycle. Thus, we have proved that there always exists either a K-stable equilibrium or a cycle. Suppose there are no K-stable equilibria. Given the finite number of action profiles and non-existence of K-stable equilibria there must exists a maximal set C of action profiles such that for any a ∈ C and a ∈ C there exists an improving path connecting a and a , and no action profile in C lies on an improving path leading to an action profile that is not in C. Such a set C is a closed cycle.

An strict K-stable equilibrium can be defined similarly. An action profile a * in Definition 2.1 is said to be strict K-stable equilibrium if the condition 1 is same and the condition 2 is u i (a) ≥ u i (a * ) for all i ∈ S with at least one strict inequality. Further if K = P(N ) \ φ, a * is a strict strong Nash equilibrium (SSNE). In this case, for a given action profile a and a coalition S ∈ K the set of improved action profiles I 2 (S, a) is defined as,

I 2 (S, a) = {a |a i = a i , ∀ i / ∈ S, and u i (a ) ≥ u i (a), ∀ i ∈ S, u j (a ) > u j (a)
, for some j ∈ S}.

(2) and I 2 (S, a) = A(S, a) \ I 2 (S, a). The definitions of improving path and cycles can be defined analogously to previous case. A result similar to Theorem 2.4 holds, i.e., there always exists at least a strict K-stable equilibrium or a closed cycle of action profiles or both. A strict K-stable equilibrium is always a K-stable equilibrium, i.e., the set of strict K-stable equilibrium is a subset of the set of K-stable equilibrium. Now, we give few examples of two player game illustrating the presence of K-stable equilibrium and closed cycle. In particular, we allow only the coalitions of size 1, and hence a K-stable equilibrium is a Nash equilibrium.

Example 2.5. Consider a two player game

b 1 b 2 a 1 a 2 (4, 3) (2, 5) (6, 1) (3, 2) .
Here (a 2 , b 2 ) is the only Nash equilibrium that can be reached from all other action profiles via improving deviations. The situation is described in Figure 1. 1 represents a deviation by player 1. The other directed edges are similarly defined. The self loop at (a 2 , b 2 ) shows that a unilateral deviation from (a 2 , b 2 ) is not possible.

A directed edge (a 1 , b 1 ) {1} --→ (a 2 , b 1 ) of Figure
Example 2.6. Consider a two player game

b 1 b 2 b 3 a 1 a 2 a 3    (4, 4) (0, 0) (0, 0) (0, 0) (4, 5) (1, 6) (0, 0) (2, 5) (6, 1)    . (a1, b1) (a2, b1) (a2, b2) (a1, b2) {2} {1} {2} {1}

Dynamic play

We consider the situation where n players play the strategic game, defined in Section 2. We assume that the players can a priori communicate with each other and hence they can form a coalition. Then, they jointly deviate from the current action profile to a new action profile if new action profile is strictly beneficial for all the members of the coalition. We consider the coalition formation over infinite horizon. At each time a coalition is randomly formed and it makes an improving deviation from current action profile to a new action profile according to the improved action profile sets defined by [START_REF] Aumann | Acceptable points in general cooperative n-person games[END_REF]. That is, at new action profile the actions of the players outside the coalition remain same as before and each player of the coalition is strictly benefited. If there is no such improved action profile for a coalition then it does not deviate. The same thing repeats at next stage and it continues for infinite horizon. Such deviations define a coalitional better-response (CBR) dynamics. We assume that the coalition formation is random and at each time only one coalition can be formed. If there are more than one improved action profiles for a coalition then each improved action profile can be chosen with positive probability. That is, the CBR dynamics is stochastic. The CBR dynamics defines a Markov chain over a finite set of action profiles A. We also assume that at each time a selected coalition makes mistake and make a joint deviation to an action profile where all the members of selected coalition are not strictly benefited. This happens with very small probability. Such mistakes add mutations into CBR dynamics. These mutations add another level of stochasticity in the CBR dynamics and as a result we have perturbed Markov chain, see e.g., [START_REF] Avrachenkov | Singular perturbations of markov chains and decision processes[END_REF][START_REF] Avrachenkov | Analytic perturbation theory and its applications[END_REF]. We are interested in the action profile which is going to be selected by the CBR dynamics as mutations vanish. We next describe the stochastic CBR dynamics as discussed above.

A stochastic CBR dynamics without mistakes

At each time t = 0, 1, 2, • • • a coalition S t is selected randomly with probability p St > 0. We assume that at each time selected coalition makes an improving deviation from current action profile a t , i.e., at time t + 1, the new action profile is a t+1 ∈ I 1 (S t , a t ) with probability p I 1 (a t+1 |S t , a t ) where p I 1 (•|S t , a t ) is a probability distribution over finite set I 1 (S t , a t ). If there is no improving deviation for coalition S t , a t+1 = a t . Let X 0 t denotes the action profile at time t, then {X 0 t } ∞ t=0 is a finite Markov chain on set A. The transition law P 0 of the Markov chain is defined as follows:

P 0 (X 0 t+1 = a |X 0 t = a) = S∈K;I 1 (S,a) =φ p S p I 1 (a |S, a)1 I 1 (S,a) (a ) + S∈K;I 1 (S,a)=φ p S 1 {a =a} (a ), (3)
where 1 B is an indicator function for a given set B. It is clear that the K-stable equilibria and closed cycles are the recurrent classes of P 0 . A K-stable equilibrium corresponds to an absorbing state of P 0 and a closed cycle corresponds to a recurrent class of P 0 having more than one action profiles.

From Example 2.6 it is clear that in general the closed cycles together with K-stable equilibria can be present in a game. In that case the CBR dynamics need not converge. In Example 2.6 the CBR dynamics need not converge to Nash equilibrium (a 1 , b 1 ) because once CBR dynamics enter into closed cycle given in Figure 2 We call a game acyclic if it has no closed cycles. The acyclic games include coordination games. There exists at least one K-stable equilibrium for acyclic games from Theorem 2.4. For acyclic games the Markov chain defined by (3) is absorbing. Hence, from the theory of Markov chain the CBR dynamics given in Section 3.1 will be at K-stable equilibrium in the long run no matter from where it starts (see [START_REF] Kemeny | Finite Markov Chains[END_REF]).

A stochastic CBR dynamics with mistakes

Now, we assume that at each time t a selected coalition S t makes error in making a deviation from a t and as a result it moves to an action profile where some players in the coalition S t are not strictly better off. We assume that at action profile a t , coalition S t makes error with probability εf (S t , a t ) ∈ (0, 1), where f (S t , a t ) takes into account the fact that some coalitions can be more prone to make errors than others and that some action profiles may lead to wrong choices more often than others. The parameter ε allows us to tune the frequency of errors. Therefore, at time t + 1 the coalition S t selects an improving deviation with probability (1 -εf (S t , a t )). In particular it selects a t+1 ∈ I 1 (S t , a t ) according to distribution p I 1 (•) defined above. By combining the probabilities we obtain that the coalition selects a t+1 ∈ I 1 (S t , a t ) with probability (1 -εf (S t , a t ))p I 1 (a t+1 |S t , a t ) . The coalition selects a non-improving deviation with probability εf (S t , a t ). Let p I 1 (•|S t , a t ) be a probability distribution over finite set I 1 (S t , a t ), the coalition chooses a t+1 ∈ I 1 (S t , a t ) with probability εf (S t , a t )p I 1 (•|S t , a t ). If there is no improving deviation, then with probability 1 -εf (S t , a t ) the coalition does not modify the action profile, i.e., a t+1 = a t , and with the complementary probability selects an action profile in I 1 (S t , a t ) according to the distribution p I 1 (•|S t , a t ). The transition law P ε of perturbed Markov chain {X ε t } ∞ t=0 is defined as below:

P ε (X ε t+1 = a |X ε t+1 = a) = S∈K;I 1 (S,
for all a, a ∈ A.

The perturbed Markov chain {X ε t } ∞ t=0 is irreducible because given nonzero errors it is possible to reach all the action profiles starting from any action profile in a finite number of steps. It is also aperiodic because with positive probability the state does not change. Hence, there exists a unique stationary distribution µ ε for perturbed Markov chain. However, when ε = 0, there can be several stationary distributions corresponding to different K-stable equilibria or closed cycles. Such Markov chains are called singularly perturbed Markov chains, [START_REF] Avrachenkov | Singular perturbations of markov chains and decision processes[END_REF][START_REF] Avrachenkov | Analytic perturbation theory and its applications[END_REF]. We are interested in the action profiles to which stationary distribution µ ε assigns positive probability as ε → 0. This leads to the definition of a stochastically stable action profile. Definition 3.1. An action profile a is stochastically stable relative to process P ε if lim ε→0 µ ε a > 0.

We recall few definitions from Young [START_REF] Young | The evolution of conventions[END_REF]. If P ε (a |a) > 0, a, a ∈ A, the one step resistance from an action profile a to an action profile a = a is defined as the minimum number of mistakes (mutations) that are required for the transition from a to a = a and it is denoted by r(a, a ). From (4) it is clear that the transition from a to a has the probability of order ε if a / ∈ I 1 (S, a) for all S and thus has resistance 1 and is of order 1 otherwise, so has resistance 0. So, in our setting r(a, a ) ∈ {0, 1} for all a, a ∈ A. A zero resistance between two action profiles corresponds to a transition with positive probability under P 0 . One can view the action profiles as the nodes of a directed graph that has no self loops and the weight of a directed edge between two different nodes is represented by one step resistance between them. Since P ε is an irreducible Markov chain then there must exist at least one directed path between any two recurrent classes H i and H j of P 0 which starts from H i and ends at H j . The resistance of any path is defined as the sum of the weights of the corresponding edges. The resistance of a path which is minimum among all paths from H i to H j is called as resistance from H i to H j and it is denoted by r ij . The resistance from any action profile a i ∈ H i to any action profile a j ∈ H j is r ij because inside H i and H j action profiles are connected with a path of zero resistance. Now we recall the definition of stochastic potential of a recurrent class H i of P 0 from [START_REF] Young | The evolution of conventions[END_REF]. It can be computed by restricting to a reduced graph. Construct a graph G where total number of nodes are the number of recurrent classes of P 0 (one action profile from each recurrent class) and a directed edge from a i to a j is weighted by r ij . Take a node a i ∈ G and consider all the spanning trees such that from every node a j ∈ G, a j = a i , there is a unique path directed from a j to a i . Such spanning trees are called a i -trees. The resistance of an a i -tree is the sum of the resistances of its edges. The stochastic potential of a i is the resistance of an a i -tree having minimum resistance among all a i -trees. The stochastic potential of each node in H i is same and it is a stochastic potential of H i [START_REF] Young | The evolution of conventions[END_REF].

Theorem 3.2. For the stochastic CBR dynamics defined in Section 3.2, all K-stable equilibria and all the action profiles from closed cycles, that have minimum stochastic potential, are stochastically stable. Furthermore, if one action profile in a closed cycle is stochastically stable then all the action profiles in the closed cycle are stochastically stable.

Proof. We know that the Markov chain P ε is aperiodic and irreducible. From ( 3) and ( 4) it is easy to see that lim

ε→0 P ε (a |a) = P 0 (a |a), ∀ a, a ∈ A.
From (4) it is clear that, if P ε (a |a) > 0 for some ε ∈ (0, ε 0 ], then we have

0 < ε -r(a,a ) P ε (a |a) < ∞.
Markov chain P ε satisfies all three required conditions of Theorem 4 in [START_REF] Young | The evolution of conventions[END_REF] from which it follows that as ε → 0, µ ε converges to a stationary distribution µ 0 of P 0 and an action profile a is stochastically stable, i.e., µ 0 a > 0, if and only if a is contained in a recurrent class of P 0 having minimum stochastic potential. We know that the recurrent classes of Markov chain P 0 are K-stable equilibria or closed cycles. Therefore, all the K-stable equilibria and the action profiles from closed cycles having minimum stochastic potential are stochastically stable. The proof of last part follows from the fact that the stochastic potential of each action profile in a closed cycle is the same.

Remark 3.3. The stochastic stability results do not depend on the function f (•) or the distributions of p I 1 (•), p I 1 (•) and p = (p S ) S∈K . Corollary 3.4. If K = P(N ) \ φ, all strong Nash equilibria and all action profiles from closed cycles are stochastically stable for the stochastic CBR dynamics defined in Section 3.2.

Proof. If K = P(N ) \ φ, all the strong Nash equilibria and closed cycles are the recurrent classes of P 0 . Now, it is always possible to reach one action profile from another action profile by at most one error due to the formation of grand coalition. Then, the resistance r ij between any two distinct recurrent classes H i and H j is always 1. Hence, the stochastic potential of each recurrent class of P 0 is J -1, where J is the number of recurrent classes of P 0 . In fact, a spanning tree in graph G includes only J -1 links and each of them has resistance 1. The proof then follows from Theorem 3.2.

We can have a similar CBR dynamics without mistakes and with mistakes as given in Sections 3.1 and 3.2 respectively, if for all S ∈ K and a ∈ A the set of improved action profiles is I 2 (S, a) defined by [START_REF] Avrachenkov | Singular perturbations of markov chains and decision processes[END_REF]. We have the following results. Theorem 3.5. For a stochastic CBR dynamics corresponding to improved action profile sets defined by (2), all strict K-stable equilibria and all the action profiles from closed cycles, that have minimum stochastic potential, are stochastically stable. Furthermore, if one action profile in a closed cycle is stochastically stable then all the action profiles in the closed cycle are stochastically stable.

Proof. The proof follows from the similar arguments given in Theorem 3.2.

Corollary 3.6. If K = P(N ) \ φ, all strict strong Nash equilibria and all action profiles from closed cycles are stochastically stable for the stochastic CBR dynamics corresponding to improved action profile sets defined by [START_REF] Avrachenkov | Singular perturbations of markov chains and decision processes[END_REF].

Proof. The proof follows from the similar arguments given in Corollary 3.4.

Equilibrium selection in coordination games

First we consider a 2 × 2 coordination game and discuss which Nash equilibrium is selected, by CBR dynamics defined in Section 3.2, in the long run when probability of making mistakes vanish. Our equilibrium selection results in 2×2 coordination games are different from the results given in [START_REF] Kandori | Learning, mutation, and long run equilibria in games[END_REF], [START_REF] Young | The evolution of conventions[END_REF]. We first consider the case where only the coalitions of size 1 are formed. In this case, a K-stable equilibrium is a Nash equilibrium. Consider a 2 × 2 coordination game, If R 1 > R 2 , then (s 1 , s 1 ) is risk dominant Nash equilibrium and if R 2 > R 1 , then (s 2 , s 2 ) is risk dominant Nash equilibrium. The state space of Markov chain is {(s 1 , s 1 ), (s 1 , s 2 ), (s 2 , s 1 ), (s 2 , s 2 )}, where (s 1 , s 1 ) and (s 2 , s 2 ) are the absorbing states of Markov chain P 0 . From Remark 3.3, the stochastic stability results do not depend on the distributions of p I 1 (•), p I 1 (•) and p = (p S ) S∈K and function f (•). Therefore, we assume that all the distributions are uniform and function f (•) has constant value 1. Under this assumption, the transition probability matrix of perturbed Markov chain is

s 1 s 2 s 1
P ε =      1 -ε 2 ε 4 ε 4 0 1-ε 2 ε 0 1-ε 2 1-ε 2 0 ε 1-ε 2 0 ε 4 ε 4 1 -ε 2      . The unique stationary distribution of P ε is µ ε = 1-ε 2-ε , ε 2(2-ε) , ε 2(2-ε) , 1-ε 2-ε . As ε → 0, µ ε → ( 1 2 , 0, 0, 1 2
). That is, both the Nash equilibria are stochastically stable. This happens because we require only 1 mutation to reach from one Nash equilibrium to another Nash equilibrium. Therefore, the resistance from one Nash equilibrium to another Nash equilibrium is 1. Then, the stochastic potential of both the Nash equilibria will be 1. For the case when all types of coalitions can be formed the CBR dynamics always selects a payoff dominant Nash equilibrium whenever it exists because it is an SNE. When payoff dominant Nash equilibrium does not exist then both the Nash equilibria are strong Nash equilibria and in that case CBR dynamics selects both the Nash equilibria. The stochastic dynamics by Young [START_REF] Young | The evolution of conventions[END_REF] and Kandori et al. [START_REF] Kandori | Learning, mutation, and long run equilibria in games[END_REF] always select a risk dominant Nash equilibrium. Among symmetric coordination games if we go beyond 2 × 2 matrix games the result by Young [START_REF] Young | The evolution of conventions[END_REF] cannot be generalized, i.e., it need not select a risk dominant Nash equilibrium. Consider an example of 3 × 3 matrix game from [START_REF] Young | The evolution of conventions[END_REF],

s 1 s 2 s 3 s 1 s 2 s 3      (6, 6) (0, 5) (0, 0) (5, 0) (7, 7) (5, 5) (0, 0) (5, 5) (8, 8)      .
Here (s 1 , s 1 ), (s 2 , s 2 ) and (s 3 , s 3 ) are three Nash equilibria. The stochastic dynamics by Young [START_REF] Young | The evolution of conventions[END_REF] selects (s 2 , s 2 ) that is not a risk dominant Nash equilibrium. A Nash equilibrium of an m×m symmetric coordination game is risk dominant if it is risk dominant in all pairwise contest (see [START_REF] Harsanyi | A general theory of equilibrium selection in games[END_REF]). We now discuss the equilibrium selection by CBR dynamics in above 3 × 3 coordination game. We first consider the case where only the coalitions of size 1 are formed. The state space of Markov chain is {(s 1 , s 1 ), (s 1 , s 2 ), (s 1 , s 3 ), (s 2 , s 1 ), (s 2 , s 2 ), (s 2 , s 3 ), (s 3 , s 1 ), (s 3 , s 2 ), (s 3 , s 3 )}, where (s 1 , s 1 ), (s 2 , s 2 ), and (s 3 , s 3 ) are absorbing states of Markov chain P 0 . We label the states (s 1 , s 1 ) as 1, (s 2 , s 2 ) as 2 and (s 3 , s 3 ) as 3. Then, the resistance from (s 1 , s 1 ) to (s 2 , s 2 ) is denoted by r 12 , where r 12 = 1. Similarly, r 13 = 2, r 31 = 2, r 21 = 1, r 23 = 1, r 32 = 1. There are three 1-trees as given below. The minimum resistance of a 1-tree among all 1-trees is 2. Hence, the stochastic potential of (s 1 , s 1 ) is 2. Similarly, by constructing 2-trees and 3-trees we can calculate the stochastic potential of (s 2 , s 2 ) and (s 3 , s 3 ). The stochastic potential of (s 2 , s 2 ) and (s 3 , s 3 ) is also 2. Hence, all the Nash equilibria are stochastically stable from Theorem 3.2. For the case where there is no restriction in coalition formation, CBR dynamics selects (s 3 , s 3 ) because it is a strong Nash equilibrium.

Application to network formation games

Network formation games are nowadays a consolidated branch of game theory [START_REF] Demange | Group Formation in Economics: Networks, Clubs, and Coalitions[END_REF][START_REF] Dutta | Networks and Groups: Models of Strategic Formation[END_REF][START_REF] Jackson | Social and Economic Networks[END_REF]. A network formation game can be viewed as the link formation game given in [START_REF] Dutta | Stable networks[END_REF]. A pairwise stable network [START_REF] Jackson | A strategic model of social and economic networks[END_REF] is induced by a strategy profile which is a K-stable equilibrium, where K is a set of all single player coalitions and all the coalitions of size 2, in the link formation game. In general, the networks which are stable against the deviations of all the coalitions are called strongly stable networks. In the literature, there are two definitions of strongly stable networks. The first definition is due to Dutta and Mutuswami [START_REF] Dutta | Stable networks[END_REF] in which a strongly stable network is induced by a strategy profile that is an SNE in the link formation game. The second definition is due to Jackson and van den Nouweland [START_REF] Jackson | Strongly stable networks[END_REF] in which a strongly stable network is induced by a strategy profile that is an SSNE in the link formation game. Under the stochastic dynamics given by Jackson and Watts [START_REF] Jackson | On the formation of interaction networks in social coordination games[END_REF] a pairwise stable or a network belonging to a closed cycle is a stochastically stable network if its stochastic potential is minimum among all the networks. This result follows from Theorem 3.5 if K is a set of all single player coalitions and all the coalitions of size 2. It follows from Corollary 3.4 and Corollary 3.6 that under stochastic CBR dynamics all strongly stable networks and closed cycles of networks are stochastically stable.

Conclusions

We introduce coalition formation among players in an n-player strategic game over infinite horizon and propose a CBR dynamics. The mutations are present in the dynamics due to erroneous decisions taken by the coalitions. We show that all K-stable equilibria and all action profiles from closed cycles, that have minimum stochastic potential, are stochastically stable. Similar development holds for strict K-stable equilibrium. When there is no restriction on coalition formation, all SNE and closed cycles are stochastically stable. Similar development holds for SSNE.

Figure 1 :Figure 2 :

 12 Figure 1: Nash equilibrium and Improving deviations

  then it will never come out of it. The closed cycle C = {(a 2 , b 2 ), (a 2 , b 3 ), (a 3 , b 3 ), (a 3 , b 2 )} is a recurrent class and (a 1 , b 1 ) is an absorbing state of Markov chain P 0 corresponding to the game given in Example 2.6.

  a) =φ p S (1 -εf (S, a))p I 1 (a |S, a)1 I 1 (S,a) (a ) + εf (S, a)p I 1 (a |S, a)1 I 1 (S,a) (a ) + S∈K;I 1 (S,a)=φ p S (1 -εf (S, a))1 {a =a} (a ) + εf (S, a)p I 1 (a |S, a)1 I 1 (S,a) (a ) ,

  , b 11 ) (a 12 , b 12 ) (a 21 , b 21 ) (a 22 , b 22 )   , where a jk , b jk ∈ R, j, k ∈ {1, 2} and a 11 > a 21 , b 11 > b 12 , a 22 > a 12 , b 22 > b 21 . A i = {s 1 , s 2 }, i = 1, 2. Here (s 1 , s 1 ) and (s 2 , s 2 ) are two Nash equilibria. In this game there are two types of Nash equilibria one is payoff dominant and other one is risk dominant. If a 11 > a 22 , b 11 > b 22 , then (s 1 , s 1 ) is payoff dominant and if a 11 < a 22 , b 11 < b 22 , then (s 2 , s 2 ) is payoff dominant. In other cases payoff dominant Nash equilibrium does not exist. From [27], define, R 1 = min a 11 -a 21 a 11 -a 12 -a 21 + a 22 , b 11 -b 12 b 11 -b 12 -b 21 + b 22 , R 2 = min a 22 -a 12 a 11 -a 12 -a 21 + a 22 , b 22 -b 21 b 11 -b 12 -b 21 + b 22 .

Figure 3 :

 3 Figure 3: 1-trees

Acknowledgements

This research was sponsored by the European Commission within the framework of the CONGAS project FP7-ICT-2011-8-317672.