François James
email: francois.james@univ-orleans.fr

N Vauchelet
email: vauchelet@ann.jussieu.fr

Chemotaxis: from kinetic equations to aggregate dynamics

Keywords: duality solutions, non local conservation equations, hydrodynamic limit, measure-valued solutions, chemotaxis. 2010 AMS subject classifications: 35B40, 35D30, 35L60, 35Q92

come

Introduction

Kinetic frameworks have been investigated to describe the chemotactic movement of cells in the presence of a chemical substance since in the 80's experimental observations showed that the motion of bacteria (e.g. Escherichia Coli) is due to the alternation of 'runs and tumbles'. The so-called Othmer-Dunbar-Alt model [START_REF] Alt | Biased random walk models for chemotaxis and related diffusion approximations[END_REF][START_REF] Erban | From individual to collective behavior in bacterial chemotaxis[END_REF][START_REF] Othmer | Models of dispersal in biological systems[END_REF][START_REF] Othmer | Aggregation, blowup, and collapse: the ABCs of taxis in reinforced random walks[END_REF] describes the evolution of the distribution function of cells at time t, position x and velocity v, assumed to have a constant modulus c > 0, as well as the concentration S(t, x) of the involved chemical. A general formulation for this model can be written as

       ∂ t f ε + v • ∇ x f ε = 1 ε |v ′ |=c T [S ε ](v ′ → v)f ε (v ′ ) -T [S ε ](v → v ′ )f ε (v) dv ′ , -∆S ε + S ε = ρ ε (t, x) := |v|=c f ε (t, x, v) dv.
(1.1)

1

The second equation describes the dynamics of the chemical agent which diffuses in the domain.

It is produced by the cells themselves with a rate proportional to the density of cells ρ and disappears with a rate proportional to S. The transport operator on the left-hand side of the first equation stands for the unbiased movement of cells ('runs'), while the right-hand side governs 'tumbles', that is chemotactic orientation, or taxis, through the turning kernel T [S](v ′ → v), which is the rate of cells changing their velocity from v ′ to v.

The parameter ε corresponds to the time interval of information sampling for the bacteria, usually ε ≪ 1, and when it goes to zero, one expects to recover the collective behaviour of the population, that is a macroscopic equation for the density ρ(t, x) of cells. Such derivations have been proposed by several authors. When the taxis is small compared to the unbiased movement of cells, the scaling must be of diffusive type, so that the limit equations are of diffusion or drift-diffusion type, see for instance [START_REF] Chalub | Kinetic models for chemotaxis and their drift-diffusion limits[END_REF] for a rigorous proof. In [START_REF] Hillen | The diffusion limit of transport equations derived from velocity jump processes[END_REF][START_REF] Othmer | The diffusion limit of transport equations. II. Chemotaxis equations[END_REF], the authors show that the classical Patlak-Keller-Segel model can be obtained in a diffusive limit for a given smooth chemoattractant concentration.

We focus here on the opposite case, that is when taxis dominates the unbiased movements. This is accounted for in the model by the choice of the scaling in equation (1.1). Moreover, we consider positive chemotaxis, which means that the involved chemical is attracting cells, and therefore is called chemoattractant. The model has been proposed in [START_REF] Dolak | Kinetic models for chemotaxis: Hydrodynamic limits and spatiotemporal mechanisms[END_REF], several works have been devoted to the mathematical study of this kinetic system. Existence of solutions has been obtained for various assumptions on the turning kernel in [START_REF] Chalub | Kinetic models for chemotaxis and their drift-diffusion limits[END_REF][START_REF] Bournaveas | Global existence for a kinetic model of chemotaxis via dispersion and Strichartz estimates[END_REF][START_REF] Erban | Global existence results for complex hyperbolic models of bacterial chemotaxis[END_REF][START_REF] Hwang | Global solutions of nonlinear transport equations for chemosensitive movement[END_REF]. Numerical simulations of this system are proposed in [START_REF] Vauchelet | Numerical simulation of a kinetic model for chemotaxis[END_REF]. The limit problem is usually of hyperbolic type, see for instance [START_REF] Filbet | Derivation of hyperbolic models for chemosensitive movement[END_REF][START_REF] Perthame | PDE models for chemotactic movements: parabolic, hyperbolic and kinetic[END_REF][START_REF] Perthame | Transport Equations in Biology[END_REF] for a hyperbolic limit model which consists in a conservation equation for the cell density and a momentum balance equation.

It is not difficult to obtain the following formal hydrodynamic limit to equation (1.1), more precisely on the total density of particles ρ = lim ε ρ ε :

∂ t ρ + div x a[S]ρ = 0, -∆ xx S + S = ρ. (1.2)
Here the macroscopic velocity a[S] depends on the chemoattractant concentration S through the turning kernel. This system of equations has been obtained in [START_REF] Dolak | Kinetic models for chemotaxis: Hydrodynamic limits and spatiotemporal mechanisms[END_REF], with a rigorous proof in the two-dimensional setting for a fixed smooth S, and therefore a bounded density ρ. The aim of this paper is to obtain rigorously this limit for the whole coupled system. Severe difficulties arise then mainly due to the lack of estimates for the solutions to the kinetic model when ε goes to zero and consequently to the very weak regularity of the solutions to the limit problem. It turns out that the limit equation is in some sense a weakly nonlinear conservation equation on the density ρ. Indeed the expected velocity field depends on ρ, but through S, and therefore in a non local way. Actually it can be written as a variant of the so-called aggregation equation, for which blow-up in finite time is evidenced (see e.g. [START_REF] Bertozzi | Blow-up in multidimensional aggregation equation with mildly singular interaction kernels[END_REF]), leading to measure-valued solutions. In this respect, this equation behaves also like linear equations with discontinuous coefficients. In particular Dirac masses can arise, this is the mathematical formulation of the aggregation of bacteria. Therefore S is no longer smooth, and a major difficulty in this study will be to define properly the velocity field a = a[S] and the product aρ.

The viewpoint of the aggregation equation has been extensively studied by Carrillo et al. [START_REF] Carrillo | Global-in-time weak measure solutions and finite-time aggregation for nonlocal interaction equations[END_REF] through optimal transport techniques. Existence and uniqueness are obtained in a very weak sense, and the dynamics of aggregates is also given. We propose here another approach, based on the notion of duality solutions, as introduced in the linear case by Bouchut and James [START_REF] Bouchut | One-dimensional transport equations with discontinuous coefficients[END_REF].

The main drawback is that presently we have to restrict ourselves to the one-dimensional case, since the theory in higher dimensions is not complete yet (see [6]). The approach proposed by Poupaud and Rascle [START_REF] Poupaud | Measure solutions to the linear multidimensional transport equation with discontinuous coefficients[END_REF], which coincides with duality in the 1-d case, could also be explored. Notice however, that the properties of the expected velocity field a in the two-dimensional case are not obvious either.

More precisely, we propose to proceed in a similar way as in [5], where the nonlinear system of zero pressure gas dynamics is interpreted as a system of two linear conservation equations coupled through the definition of the product. This last point turns out to be crucial in order to obtain a proper uniqueness result for the system (1.2). In this work, the product aρ will be defined thanks to the limiting flux of the kinetic system (1.1) (see also [START_REF] James | A remark on duality solutions for some weakly nonlinear scalar conservation laws[END_REF] for another application of the same idea). As we shall see, this is closely related to the dynamics of aggregates, that is combinations of Dirac masses, which reflect some kind of collective behaviour of the population. Finally, an important application of this aggregate dynamics is the development of a numerical scheme, based on a particle method. The motion and collapsing of Dirac masses is clearly evidenced.

The paper is organized as follows. In Section 2 we precisely state the model. Section 3 is devoted to the notion of duality solutions, and contains the main results of this article. Some technical properties which will be useful for the rest of the paper are given in Section 4. Then we investigate in Section 5 the proof of the existence and uniqueness result of duality solution for system (2.8)-(2.10) stated in Theorem 3.9. In Section 6 we prove the rigorous derivation of the hydrodynamical system from the kinetic system. Finally, the dynamics of aggregates and the numerical scheme for the limit equation are described in the last section, where numerical illustrations are also provided.

Modelling

From now on we focus on the one dimensional version of the problem, so that x ∈ R. We first recall the main assumptions leading to the kinetic equation, next we proceed to the formal limit.

Kinetic model

In this work, cells are supposed to be large enough to sense the gradient of the chemoattractant instantly. Therefore the turning kernel takes the form (independent on v)

T [S](v ′ → v) = Φ(v ′ ∂ x S).
(2.1)

The function Φ is the turning rate, obviously it has to be positive. More precisely, for attractive chemotaxis, the turning rate is smaller if cells swim in a favourable direction, that is v •∇ x S ≥ 0. Thus Φ should be a non increasing function. A simplified model for this phenomenon is the following choice for Φ: we fix a positive parameter α, a mean turning rate φ 0 > 0 and take

Φ(x) = φ 0 1 + φ(x) , (2.2)
where φ is an odd function such that

φ ∈ C ∞ (R), φ ′ ≤ 0, φ(x) = +λ if x < -α, -λ if x > α, (2.3)
where 0 < λ < 1 is a given constant. Now since the transport occurs in R the set of velocities is V = {-c, c}, and the expression of the turning kernel simplifies in such a way that (1.1) rewrites

∂ t f ε + v∂ x f ε = 1 ε (Φ(-v∂ x S)f ε (-v) -Φ(v∂ x S)f ε (v)), v ∈ V.
(2.4)

-∂ xx S ε + S ε = ρ ε = f ε (c) + f ε (-c).
(2.5)

The existence of weak solutions in a L p setting for a slightly different system in a more general framework has been obtained for instance in [START_REF] Bournaveas | Global existence for a kinetic model of chemotaxis via dispersion and Strichartz estimates[END_REF][START_REF] Hwang | Global solutions of nonlinear transport equations for chemosensitive movement[END_REF]. Concerning precisely this model, we refer to [START_REF] Vauchelet | Numerical simulation of a kinetic model for chemotaxis[END_REF] for the existence theory in any space dimension. Notice that no uniform L ∞ bounds can be expected. The reader is referred to [START_REF] Vauchelet | Numerical simulation of a kinetic model for chemotaxis[END_REF] for some numerical evidences of this phenomenon, which is the mathematical translation of the concentration of bacteria. This is some kind of "blow-up in infinite time", which for ε = 0 leads to actual blow-up in finite time, and creation of Dirac masses. Moreover the balanced distribution vanishing the right hand side of (2.4) depends on S ε ; thus the techniques developed e.g. in [START_REF] Chalub | Kinetic models for chemotaxis and their drift-diffusion limits[END_REF] cannot be applied.

Formal hydrodynamic limit

We formally let ε go to 0 assuming that S ε and f ε admit a Hilbert expansion

f ε = f 0 + εf 1 + • • • , S ε = S 0 + εS 1 + • • • Multiplying (2.4
) by ε and taking ε = 0, we find

Φ(-c∂ x S 0 )f 0 (-c) = Φ(c∂ x S 0 )f 0 (c).
(2.6) Summing equations (2.4) for c and -c, we obtain

∂ t (f ε (c) + f ε (-c)) + c∂ x (f ε (c) -f ε (-c)) = 0. (2.7)
Moreover, from equation (2.6) we deduce that

f 0 (c) -f 0 (-c) = Φ(-c∂ x S 0 ) -Φ(c∂ x S 0 ) Φ(-c∂ x S 0 ) + Φ(c∂ x S 0 ) (f 0 (c) + f 0 (-c)).
The density at equilibrium is defined by ρ := f 0 (c) + f 0 (-c). Taking ε = 0 in (2.7) we finally obtain

∂ t ρ + ∂ x (a(∂ x S 0 )ρ) = 0,
where a is defined by

a(∂ x S 0 ) = c Φ(-c∂ x S 0 ) -Φ(c∂ x S 0 ) Φ(-c∂ x S 0 ) + Φ(c∂ x S 0 ) = -c φ(c∂ x S 0 ),
and we have used (2.2) for the last identity. Notice that a is actually a macroscopic quantity, since it is the simplified formulation of

a(∂ x S 0 ) = -V v Φ(v∂ x S 0 ) dv V Φ(v∂ x S 0 ) dv in the one-dimensional context.
We couple this equation with the limit of the elliptic problem (2.5) for the chemoattractant concentration, so that, in summary, and dropping the index 0, the formal hydrodynamic limit is the following system

∂ t ρ + ∂ x (a(∂ x S)ρ) = 0, (2.8) a(∂ x S) = -c φ(c∂ x S), (2.9)
-∂ xx S + S = ρ, (2.10)
complemented with the boundary conditions

ρ(t = 0, x) = ρ ini (x), lim x→±∞ ρ(t, x) = 0, lim x→±∞ S(t, x) = 0. (2.11)
We now give the precise formulation of the limit system in terms of aggregate equation. Noticing that a solution to (2.10) has the explicit expression

S(t, x) = K * ρ(t, .)(x), where K(x) = 1 2 e -|x| , (2.12)
the macroscopic conservation equation for ρ (2.8) can be rewritten

∂ t ρ + ∂ x (a(∂ x K * ρ)ρ) = 0.
When a is the identity function, this is exactly the so-called aggregation equation, and since the potential is non-smooth, blow-up in finite time is expected. We refer the reader to e.g. [START_REF] Bertozzi | Blow-up in multidimensional aggregation equation with mildly singular interaction kernels[END_REF][START_REF] Carrillo | Global-in-time weak measure solutions and finite-time aggregation for nonlocal interaction equations[END_REF], and [START_REF] James | On the hydrodynamical limit for a one dimensional kinetic model of cell aggregation by chemotaxis[END_REF] in the context of chemotaxis. Similar problems were encountered for instance in [START_REF] Nieto | High field limit for Vlasov-Poisson-Fokker-Planck equations[END_REF], where the authors investigate the high field limit of the Vlasov-Poisson-Fokker-Planck model in one space dimension. The limit system is a scalar conservation law coupled to the Poisson equation, and a proper definition of the product is needed to pass to the limit. This definition has been extended in two dimensions by Poupaud [START_REF] Poupaud | Diagonal defect measures, adhesion dynamics and Euler equation[END_REF] using defect measures but losing uniqueness.

Duality solutions

Notations

Let C 0 (Y, Z) be the set of continuous functions from Y to Z that vanish at infinity and C c (Y, Z) the set of continuous functions with compact support from Y to Z. All along the paper, we denote M loc (R) the space of local Borel measures on R. For ρ ∈ M loc we denote by |ρ|(R) its total variation. We will denote M b (R) the space of measures in M loc (R) whose total variation is finite. From now on, the space of measure-valued function M b (R) is always endowed with the weak topology σ(M b , C 0 ). We denote

S M := C([0, T ]; M b (R) -σ(M b , C 0 )).
We recall that if a sequence of measure (µ n ) n∈N in M b (R) satisfies sup n∈N |µ n |(R) < +∞, then we can extract a subsequence that converges for the weak topology σ(M b , C 0 ).

Linear conservation equations

Duality solutions are defined as weak solutions, the test functions being Lipschitz solutions to the backward linear transport equation

∂ t p + b(t, x)∂ x p = 0, p(T, .) = p T ∈ Lip(R). (3.2)
A key point to ensure existence of smooth solutions to (3.2) is that the velocity field has to be compressive, in the following sense.

Definition 3.1 We say that the function b satisfies the so-called one-sided Lipschitz condition (OSL condition) if

∂ x b(t, .) ≤ β(t) for β ∈ L 1 (0, T ) in the distributional sense. (3.3)
A formal computation shows that ∂ t (pρ) + ∂ x [b(t, x)pρ] = 0, and thus

d dt R p(t, x)ρ(t, dx) = 0, (3.4)
which defines the duality solutions for suitable p's. It is now quite classical that (3.3) ensures existence for (3.2), but not uniqueness, which is of great importance here to obtain stability results and make a convenient use of (3.4). Therefore, the corner stone in the construction of duality solutions is the introduction of the notion of reversible solutions to (3.2). A complete statement of the definitions and properties of reversible solutions would be too long in the present context, so that merely a few hints are given. Let L denote the set of Lipschitz continuous solutions to (3.2), and define the set of exceptional solutions:

E = p ∈ L such that p T ≡ 0 .
The possible loss of uniqueness corresponds to the case where E is not reduced to zero.

Definition 3.2 We say that p ∈ L is a reversible solution to (3.2) if p is locally constant on the set V e = (t, x) ∈ [0, T ] × R; ∃ p e ∈ E, p e (t, x) = 0 .
This definition leads quite directly to the uniqueness results of [START_REF] Bouchut | One-dimensional transport equations with discontinuous coefficients[END_REF]. It turns out that the class of reversible solutions is also stable by perturbations of the coefficient b.

We now restrict ourselves to those p's in (3.4). More precisely, we state the following definition.

Definition 3.3 We say that ρ ∈ S M := C([0, T ]; M b (R) -σ(M b , C 0 )
) is a duality solution to (3.1) if for any 0 < τ ≤ T , and any reversible solution p to (3.2) with compact support in

x, the function t → R p(t, x)ρ(t, dx) is constant on [0, τ ].
Remark 3.4 A similar notion of duality solution for the transport equation is available ∂ t u + b∂ x u = 0, and ρ is a duality solution of (3.1) iff u =

x ρ is a duality solution to transport equation (see [START_REF] Bouchut | One-dimensional transport equations with discontinuous coefficients[END_REF]).

We shall need the following facts concerning duality solutions.

Theorem 3.5 (Bouchut, James [START_REF] Bouchut | One-dimensional transport equations with discontinuous coefficients[END_REF])

1. Given ρ • ∈ M b (R),
(t, •)|(R) = |ρ • |(R), for a.e. t ∈]0, T [.

2.

Backward flow and push-forward: the duality solution satisfies

∀ t ∈ [0, T ], ∀ φ ∈ C 0 (R), R φ(x)ρ(t, dx) = R φ(X(t, 0, x))ρ 0 (dx), (3.5)
where the backward flow X is defined as the unique reversible solution to

∂ t X + b(t, x)∂ x X = 0 in ]0, s[×R, X(s, s, x) = x.
3. For any duality solution ρ, we define the generalized flux corresponding to ρ by b∆ρ = -∂ t u, where u = x ρ dx.

There exists a bounded Borel function b, called universal representative of b, such that b = a almost everywhere, and for any duality solution ρ,

∂ t ρ + ∂ x ( bρ) = 0 in the distributional sense. 4. Let (b n ) be a bounded sequence in L ∞ (]0, T [×R), such that b n ⇀ b in L ∞ (]0, T [×R) -w⋆. Assume ∂ x b n ≤ α n (t), where (α n ) is bounded in L 1 (]0, T [), ∂ x b ≤ α ∈ L 1 (]0, T [). Consider a sequence (ρ n ) ∈ S M of duality solutions to ∂ t ρ n + ∂ x (b n ρ n ) = 0 in ]0, T [×R, such that ρ n (0, .) is bounded in M b (R), and ρ n (0, .) ⇀ ρ • ∈ M b (R).
Then ρ n ⇀ ρ in S M , where ρ ∈ S M is the duality solution to

∂ t ρ + ∂ x (bρ) = 0 in ]0, T [×R, ρ(0, .) = ρ • . Moreover, b n ρ n ⇀ bρ weakly in M b (]0, T [×R).
The set of duality solutions is clearly a vector space, but it has to be noted that a duality solution is not a priori defined as a solution in the sense of distributions. However, assuming that the coefficient b is piecewise continuous, we have the following equivalence result: This result comes from the uniqueness of solutions to the Cauchy problem for both kinds of solutions (see Theorem 4.3.7 of [START_REF] Bouchut | One-dimensional transport equations with discontinuous coefficients[END_REF]).

Main results

We are now in position to give the definition of duality solutions for the limit system (2.8)-(2.10).

Definition 3.7 We say that (ρ, S) ∈ C([0, T ]; M b (R)) × C([0, T ]; W 1,∞ ) is a duality solution to (2.8)-(2.10) if there exists b ∈ L ∞ ((0, T ) × R) and α ∈ L 1 loc (0, T ) satisfying ∂ x b ≤ α in D ′ , such that 1. for all 0 < t 1 < t 2 < T ∂ t ρ + ∂ x (bρ) = 0 in the sense of duality on ]t 1 , t 2 [, 2.
(2.9) is satisfied in the weak sense:

∀ ψ ∈ C 1 (R), ∀ t ∈ [0, T ], R (∂ x S∂ x ψ + Sψ)(t, x) dx = ψ(x) ρ(t, dx), 3. b = a(∂ x S) a.e. Remark 3.8 For S in C([0, T ]; W 1,∞ ) and φ as in (2.3), we have a(∂ x S) ∈ C([0, T ]; L ∞ (R)).
Therefore equation (2.8) is meaningful in the duality sense. The key property is then the onesided Lipschitz condition.

Unfortunately, Definition 3.7 does not ensure uniqueness, as we shall evidence in Section 5. This is due to the fact that the product a(∂ x S)ρ is not properly defined yet. Indeed the relevant definition of this product relies on a proper definition of the flux of the system, which we introduce now. Let A be an antiderivative of a such that A(0) = 0, we set

J = -∂ x (A(∂ x S)) + a(∂ x S)S. (3.6)
This choice is justified first since this definition holds true when S is regular. Indeed we have

∂ x (A(∂ x S)) = a(∂ x S)∂ xx S, so that we can write J = a(∂ x S)(-∂ xx S + S) = a(∂ x S)ρ.
On the other hand, a more physical reason relies on the fact that the above J is the correct flux for the kinetic model, and passes to the limit when ε goes to zero, see Section 6.

We can now establish the following uniqueness theorem:

Theorem 3.9 Let us assume that ρ ini ≥ 0 is given in M b (R).
Then, for all T > 0 there exists a unique duality solution (ρ, S) with ρ ≥ 0 of (2.8)-(2.10) which satisfies in the distributional sense:

∂ t ρ + ∂ x J = 0, (3.7)
where J is defined in (3.6). It means that the universal representative in Theorem 3.5 satisfies bρ = J, in the sense of measures.

Moreover, we have ρ = X # ρ ini where X is the backward flow corresponding to a(∂ x S).

The second result concerns the rigorous proof of hydrodynamical limit for the kinetic model. Let (f ε , S ε ) be a solution of the system (2.4)-(2.5), complemented with null boundary condition at infinity and with the following initial data:

f ε (0, •, •) = f ini ε , (3.8)
such that ρ ini ε = η ε * ρ ini where η ε is a mollifier and ρ ini is given in M b (R). We recall that for fixed ε > 0, there exists (

f ε , S ε ) such that f ε belongs to C([0, T ] × R × V ) and therefore S ε ∈ C([0, T ]; C 2 (R))
, see [START_REF] Bournaveas | Global existence for a kinetic model of chemotaxis via dispersion and Strichartz estimates[END_REF], or [START_REF] Vauchelet | Numerical simulation of a kinetic model for chemotaxis[END_REF] in the present context. Theorem 3.10 Let us assume that ρ ini ≥ 0 is given in M b (R). Let (f ε , S ε ) be a solution to the kinetic-elliptic equation (2.4)-(2.5) with initial data (3.8). Then, as ε → 0, (f ε , S ε ) converges in the following sense:

ρ ε := f ε (c) + f ε (-c) ⇀ ρ in S M := C([0, T ]; M b (R) -σ(M b , C 0 )), S ε ⇀ S in C([0, T ]; W 1,∞ (R)) -weak,
where (ρ, S) is the unique duality solution of the system (2.8)-(2.10) satisfying bρ = J, in the sense of measures.

Properties of S

We gather in this section a set of properties for the solution S to (2.10) that will be used throughout the paper.

One-sided estimates

The estimates presented in this part rely only on equation (2.10). Proof. The first two items are easy consequences of the expression (2.12) for the first one, of the equation (2.10) for the second. For the third item, from convolution properties, we have for any

p ∈ [1, +∞] S(t, .) L p (R) = 1 2 e -|•| * ρ(t, .) L p (R) ≤ |ρ(t, .)|(R) 1 2 e -|•| L p (R) = 1 2 sup t∈[0,T ] |ρ(t, •)|(R),
where |ρ|(R) stands for the total mass of the nonnegative measure ρ. We proceed in the same way for ∂ x S.

As mentioned above, the key point to use the duality solutions is that the velocity field satisfies the OSL condition (3.3).

∂ x (a(∂ x S)) = -c 2 φ ′ (c∂ x S)∂ xx S.
With (2.10) and since φ is a nonincreasing function, we deduce from the one-sided estimate of Lemma 4.1

∂ x (a(∂ x S)) ≤ max{c 2 φ ′ L ∞ S, 0}. We conclude thanks to the bound on S in L ∞ .
Finally, we turn to a convergence result for a sequence of such functions S. Lemma 4.3 Let (ρ n ) n∈N be a sequence of measures that converges weakly towards ρ in S M as n goes to +∞. Let S n (t, x) = (K * ρ n (t, •))(x) and S(t, x) = (K * ρ(t, •))(x), where K is defined in (2.12). Then when n → +∞ we have

∂ x S n (t, x) -→ ∂ x S(t, x) for a.e. t ∈ [0, T ], x ∈ R, ∂ x S n (t, x) ⇀ ∂ x S(t, x) in L ∞ t,x weak - * .
Proof. The proof of this result is obtained by regularization of the convolution kernel (see Lemma 3.1 of [START_REF] James | On the hydrodynamical limit for a one dimensional kinetic model of cell aggregation by chemotaxis[END_REF]).

Entropy estimates

In this subsection, we consider now that (ρ, S) satisfy (3.7)-(3.6) in the sense of distributions. We prove first that S satisfies a nonlinear nonlocal equation. Next, following the strategy of [START_REF] Nieto | About uniqueness of weak solutions to first order quasi-linear equations[END_REF], we prove that the above one-sided estimate implies some kind of entropy inequality for

∂ x S. Lemma 4.4 Assume (ρ, S) ∈ C([0, T ]; M b (R))×C([0, T ]; W 1,∞ ) satisfy (3.7)-(3.6), then ∂ x S ∈ C([0, T ], L 1 (R)) ∩ L ∞ ([0, T ], BV (R))
and S is a weak solution of

∂ t S -∂ x K * ∂ x (A(∂ x S)) + ∂ x K * (a(∂ x S)S) = 0. (4.1)
Proof. We have ρ ∈ S M and

∂ xx S = S -ρ. Then ∂ x S ∈ C([0, T ], L 1 (R)) ∩ L ∞ ([0, T ], BV (R)).
We recall that we have S = K * ρ where K(x) = 1 2 e -|x| . Thus taking the convolution by K of (3.7)-(3.6), we get that S is a weak solution of (4.1). Lemma 4.5 Let S be a weak solution in C([0, T ]; W 1,1 (R)) of (4.1) with initial data S ini . We assume moreover that ∂ x S belongs to L ∞ ([0, T ]; BV (R)) and that the one-sided estimate ∂ xx S ≤ S holds in the distributional sense. Then for any twice continuously differentiable convex function η we have

∂ t η(∂ x S) + ∂ x (q(∂ x S)) -η ′ (∂ x S)a(∂ x S)S + η ′ (∂ x S)[K * (-∂ x A(∂ x S) + a(∂ x S)S)] ≤ 0, (4.2)
where the entropy flux q is defined by

q(x) = x 0 η ′ (y)a(y) dy.
Proof. From Lemma 4.4, S satisfies (4.1). By differentiation, and using the property

∂ xx K = K -δ 0 , we get ∂ t ∂ x S + ∂ x A(∂ x S) -a(∂ x S)S + K * (-∂ x A(∂ x S) + a(∂ x S)S) = 0. (4.3)
Consider a sequence of mollifiers

ζ n (x) = nζ(nx), with n ∈ N, ζ ∈ C ∞ 0 (R), ζ ≥ 0 and R ζ(x) dx = 1. We set S n = ζ n * S. Then we have ∂ t ∂ x S n + ∂ x (A(∂ x S) * ζ n ) -ζ n * (a(∂ x S)S) + K * ζ n * (-∂ x A(∂ x S) + a(∂ x S)S) = 0.
We define the commutators R n and Q n as follows:

A(∂ x S) * ζ n = A(∂ x S n ) + R n (t, x), Q n (t, x) = -ζ n * (a(∂ x S)S) + K * ζ n * (-∂ x A(∂ x S) + a(∂ x S)S) + a(∂ x S n )S n -K * (-∂ x A(∂ x S n ) + a(∂ x S n )S n ),
so that the regularized solution satisfies

∂ t ∂ x S n + ∂ x (A(∂ x S n ) + R n ) -a(∂ x S n )S n + K * (-∂ x A(∂ x S n ) + a(∂ x S n )S n ) + Q n = 0. (4.4)
Let us consider η a twice continuously differentiable convex function and let q be the corresponding entropy flux. Multiplying equation (4.4) by η ′ (∂ x S n ), we get

∂ t η(∂ x S n ) + ∂ x (q(∂ x S n ) + η ′ (∂ x S n )R n ) + H n = -η ′ (∂ x S n )Q n + R n ∂ x (η ′ (∂ x S n )), (4.5)
where

H n := -η ′ (∂ x S n )a(∂ x S n )S n + η ′ (∂ x S n )[K * (-∂ x A(∂ x S n ) + a(∂ x S n )S n )].
Due to properties of the convolution product, we have

R n → 0, Q n → 0 in L p loc ((0, ∞) × R), 1 ≤ p < +∞,
so that in the sense of distribution, we have straightforwardly

∂ x (η ′ (∂ x S n )R n ) → 0, η ′ (∂ x S n )Q n → 0 and H n → H := -η ′ (∂ x S)a(∂ x S)S + η ′ (∂ x S)[K * (-∂ x A(∂ x S) + a(∂ x S)S)],
which is precisely the desired term in the limit equation. Now we deal with the term

R n ∂ x (η ′ (∂ x S n ))
on the right-hand side, and we notice that R n ≥ 0 thanks to the Jensen inequality and the convexity of A. Therefore, since η is convex, we have

R n ∂ x (η ′ (∂ x S n )) = R n η ′′ (∂ x S n )∂ xx S n ≤ R n η ′′ (∂ x S n )S n ,
where we have used the one-sided estimate ∂ xx S n ≤ S n to obtain the last inequality. Since S n is bounded in L ∞ independently of n, we can pass to the limit in this last identity thanks to the Lebesgue dominated convergence theorem to get

R n η ′′ (∂ x S n )S n → 0 in L 1 loc ((0, ∞) × R).
Finally, letting n going to +∞ in (4.5), we deduce that (4.2) holds in the distributional sense.

Remark 4.6 This equation relies strongly on the definition of the flux J in (3.6). This fact has already been noticed by the authors in [START_REF] James | A remark on duality solutions for some weakly nonlinear scalar conservation laws[END_REF], which can be viewed as a particular case of the one studied in this paper by replacing the elliptic equation (2.10) for S by the Poisson equation -∂ xx S = ρ. In this case, the product of a(∂ x S) by ρ is naturally defined by a(∂ x S)ρ = -∂ x A(∂ x S), so that equation on S corresponding to (4.3) is given by

∂ t ∂ x S + ∂ x A(∂ x S) = 0.
This equation is a nonlinear hyperbolic conservation law which is local, contrary to (4.3). Therefore uniqueness is ensured by entropy conditions. Since ∂ x S is monotonous (-∂ xx S = ρ ≥ 0), this can be formulated as a chord condition on A (see [5]). If in addition A is convex or concave (i.e. if a is non-decreasing or non-increasing), this selects only increasing or decreasing shocks.

Existence and uniqueness for the hydrodynamical problem

In this Section, we focus on the proof of Theorem 3.9, which can be split in 3 steps. The first one consists in obtaining the dynamics of aggregates, or in other words of combinations of Dirac masses. Next we obtain the existence of duality solutions in the sense of Definition 3.7 by proving first that aggregates define such a solution, then proceeding to the general case by approximation. This is exactly the same strategy as for the pressureless gases in [5]. Finally, uniqueness follows from a careful definition of the flux of the equation. In this respect, we first underline with an example that Definition 3.7 as it stands does not give uniqueness, and how the proper definition of the flux singles out a unique solution.

Indeed, let us consider (2.8)-(2.10) with boundary condition (2.11) where the initial datum is assumed to be a Dirac mass in 0: ρ ini = δ 0 . We have that (δ 0 , K * δ 0 ) is a solution to (2.8)-(2.10) with initial data δ 0 . Actually, the pair

ρ 1 (t, x) = δ x 1 (t) (x); S 1 (t, x) = K * ρ 1 (t, x) = 1 2 e -|x-x 1 (t)| .
(5.1) turns out to define a solution in the sense of duality in Definition 3.7 for several choices of curves x 1 with x 1 (0) = 0. Set b 1 (t, x) = a(∂ x S 1 )(t, x), and notice first that, according to Remark 3.4, ρ 1 is a duality solution if u 1 := x ρ 1 dx = H(x -x 1 (t)) is a duality solution of the transport equation. Now, from Lemma 4.2, b 1 satisfies the OSL condition, therefore u 1 is a duality solution of the transport equation as soon as it is solution in the sense of distributions. As detailed in [START_REF] Bouchut | One-dimensional transport equations with discontinuous coefficients[END_REF], Section 3, this holds true only if u satisfies some admissibility conditions, namely, the characteristics of the velocity field have to enter the discontinuity on both side. Since

lim x→x + 1 b 1 (x) = a(-1/2) and lim x→x - 1 b 1 (x) = a(1/2
), the velocity of the shock should satisfy a(1/2) > x ′ 1 (t) > a(-1/2), which furnishes an infinity of solution. For any of the previous solutions, the generalized flux given by Theorem 3.5-3 is b

1 ∆ρ 1 = -∂ t u 1 = -x ′ 1 (t)δ x 1 (t)
. On the other hand, let us compute the flux J defined by (3.6). For simplicity, we set here α = 0 in the definition (2.3) of Φ. With this convention, we get

a(∂ x S 1 )(t, x) = -λc, x < x 1 (t), λc, x > x 1 (t), A(∂ x S 1 )(t, x) = 1 2 -λce x-x 1 (t) , x < x 1 (t), -λce -x+x 1 (t) , x > x 1 (t).
Obviously we have J = 0, so that the condition aρ = J selects x ′ 1 (t) = 0, which finally implies x 1 ≡ 0 since x 1 (0) = 0.

Dynamics of aggregates

Let us first consider the motion of aggregates. We assume that ρ ini n is given by a finite sum of Dirac masses:

ρ ini n = n i=1 m i δ x 0 i where x 0 1 < x 0 2 < • • • < x 0
n and the m i -s are nonnegative. We look for a couple (ρ n , S n ) solving in the distributional sense ∂ t ρ n + ∂ x J n = 0 where the flux J n is given by (3.6) and S n solves (2.10). We recall that it means that S n = K * ρ n where K is defined in (2.12). Let us set ρ n (t, x) = n i=1 m i δ x i (t) . Such a function is a solution in the sense of distributions of (3.7) if the function u n defined by

u n (t, x) := x ρ n dx = n i=1 m i H(x -x i (t)), (5.2)
where H denotes the Heaviside function, is a distributional solution to

∂ t u n -∂ x A(∂ x S n ) + a(∂ x S n )S n = 0. (5.3)
We have

S n (t, x) = n i=1 m i 2 e -|x-x i (t)| , ∂ x S n (t, x) = - n i=1 m i 2 sign (x -x i (t))e -|x-x i (t)| .
(5.4)

Straightforward computations prove that we have in the distributional sense

∂ x A(∂ x S n ) = a(∂ x S n )S n + n i=1 [A(∂ x S n )] x i δ x i , (5.5) where [f ] x i = f (x + i ) -f (x - i )
is the jump of the function f at x i . Injecting (5.2) and (5.5) in (5.3), we find

- n i=1 m i x ′ i (t)δ x i (t) = n i=1 [A(∂ x S n )] x i δ x i .
Thus the dynamics of aggregates is finally given by

m i x ′ i (t) = -[A(∂ x S n )] x i (t)
, for i = 1, . . . , n. We complement this system of ODEs by the initial data x i (0) = x 0 i . More precisely, recalling that K(x) = 1 2 e -|x| , using (5.4) this latter system can be rewritten :

m i x ′ i (t) = A m i 2 + j =i m j ∂ x K(x j -x i ) -A - m i 2 + j =i m j ∂ x K(x j -x i ) .
(5.6)

Recall that, from the definition of the coefficient a in (2.9) with (2.3), a is nondecreasing and odd, so that A is a convex function. This implies that for i = 1, . . . , n -1, x ′ i ≥ x ′ i+1 , therefore, aggregates can collapse in finite time but an aggregate cannot split. This is a direct consequence of the fact that we are considering positive chemotaxis, i.e. a is nondecreasing. If there exists a time t 1 for which we have for instance x i (t 1 ) = x i+1 (t 1 ), then the dynamics for t > t 1 is defined as above except that we replace m i by m i + m i+1 and x i (t) = x i+1 (t) for t > t 1 . Moreover A is even, then when n = 1, we have x ′ 1 = 0 and x 1 (t) = x 0 1 . Thus if aggregates collapse such that they form a single aggregate of mass i m i , then this aggregate does not move for larger times.

Existence of duality solutions

We have constructed (ρ n , S n ) which is a solution of (3.7)-(3.6)-(2.10) in the distributional sense for the given initial data ρ ini n . We recall the following result due to Vol'pert [START_REF]pert, The spaces BV and quasilinear equations[END_REF] (see also [START_REF] Ambrosio | Functions of Bounded Variation and Free Discontinuity Problems[END_REF]):

if u belongs to BV (R) and f ∈ C 1 (R) with f (0) = 0, then v = f • u belongs to BV (R) and ∃ f u with f u = f ′ (u) a.e. such that (f • u) ′ = f u u ′ .
Together with the fact that A is an antiderivative of a such that A(0) = 0, this result implies that there exists a function a n such that

J n := -∂ x (A(∂ x S n )) + a(∂ x S n )S n = a n ρ n , and a n = a(∂ x S n ) a.e.
Thus ρ n is a solution in the distributional sense of

∂ t ρ n + ∂ x ( a n ρ n ) = 0.
Moreover, we deduce from (5.4) that a(∂ x S n ) is piecewise continuous with the discontinuity lines defined by x = x i , i = 1, . . . , n. We can apply Theorem 3.6 which gives that ρ n is a duality solution and that a n is a universal representative of a(∂ x S n ). Then the flux is given by a

(∂ x S n )∆ρ n = J n .
Let us yet consider the case of any initial data ρ ini ∈ M b (R). We approximate ρ ini by

ρ ini n = n i=1 m i δ x 0 i with ρ ini n ⇀ ρ ini in M b (R)
. By the same token as above, we can construct a solution (ρ n , S n = K * ρ n ) with ρ n (t = 0) = ρ ini n = n i=1 m i δ x 0 i , which solves in the sense of duality

∂ t ρ n + ∂ x (a(∂ x S n )ρ n ) = 0,
in the sense of distributions

∂ t ρ n + ∂ x J n = 0, J n = -∂ x A(∂ x S n ) + a(∂ x S n )S n ,
and which satisfies

a n ρ n = J n , a n = a(∂ x S n ) a.
→ J := -∂ x A(∂ x S) + a(∂ x S)S in D ′ (R) and that a(∂ x S n ) → a(∂ x S)
a.e. By uniqueness of the weak limit, we have b = a(∂ x S). Moreover J = aρ a.e. and ρ satisfies then (3.7). Then (ρ, S) is a solution as in Theorem 3.9, this concludes the proof of the existence.

Uniqueness of solutions

Let us consider yet the study of the uniqueness. As shown above, Definition 3.7 is not sufficient to ensure uniqueness. Therefore, we will use the fact that we have a duality solution ρ that satisfies (3.7) in D ′ ([0, T ] × R) with the initial data ρ ini and with the flux J given by (3.6). This equation leads to the non-local evolution equation on S (4.1) as stated in Lemma 4.4.

Another key point is the one-sided estimate ∂ xx S ≤ S. In fact, if we consider for instance ρ ini = 0, then it is obvious that ρ = 0 is a solution of (2.8)-(2.10). However, if we allow ρ to be nonpositive, i.e. if the corresponding chemoattractant concentration S does not satisfy the one-sided estimate ∂ xx S ≤ S, then we can build a simple example of non-uniqueness. Indeed we have that

ρ(t, x) = δ -x 1 (t) (x) -2δ 0 (x) + δ x 1 (t) (x)
is a duality solution of (2.8)-(2.10) which satisfies (3.7), provided x 1 (0) = 0 and (5.6) is satisfied. This readily gives

x ′ 1 (t) = A 1 2 + e -x 1 + 1 2 e -2x 1 -A - 1 2 + e -x 1 + 1 2 e -2x 1 .
Here by convexity of A, we have x ′ 1 ≥ 0.

Theorem 5.1 Let S 1 and S 2 be two weak solutions in C([0, T ]; W 1,1 (R)) of (4.1) with initial data S ini 1 and S ini 2 respectively. If we assume moreover that ∂ x S 1 and ∂ x S 2 belongs to L ∞ ([0, T ]; BV (R)) and that the one-sided estimate

∂ xx S i ≤ S i , i = 1, 2,
holds in the distributional sense. Then there exists a nonnegative constant C such that

S 1 -S 2 L ∞ ([0,T ];W 1,1 (R)) ≤ C S ini 1 -S ini 2 W 1,1 (R) .
Proof. We start from the entropy inequality (4.2) of Lemma 4.5. Using standard regularization arguments, it is well-known that we can apply this inequality to the family of Kružkov entropies η κ (u) = |u -κ|. Then, the doubling of variables technique developed by Kružkov allows to justify the following computation. Assume S 1 and S 2 are two weak solutions of (4.1), then in the distributional sense, we have

∂ t |∂ x (S 1 -S 2 )| + ∂ x ( sign(∂ x S 1 -∂ x S 2 )(A(∂ x S 1 ) -A(∂ x S 2 ))) ≤ sign(∂ x S 1 -∂ x S 2 ) ∂ x K * (A(∂ x S 1 ) -A(∂ x S 2 )) + a 1 S 1 -a 2 S 2 -K * (a 1 S 1 -a 2 S 2 ) ,
where we denote a 1 = a(∂ x S 1 ) and a 2 = a(∂ x S 2 ). Integrating with respect to x and using the properties of the convolution product, we deduce

d dt R |∂ x (S 1 -S 2 )| dx ≤ ∂ x K ∞ R |A(∂ x S 1 ) -A(∂ x S 2 )| dx + (1 + K ∞ ) R |a 1 S 1 -a 2 S 2 | dx.
The function a being regular, we have

d dt R |∂ x (S 1 -S 2 )| dx ≤ C 0 R |∂ x (S 1 -S 2 )| dx + C 1 R |S 1 -S 2 | dx.
(5.7)

In the same way as for equation (4.1), this leads to

d dt R |S 1 -S 2 | dx ≤ C 2 R |∂ x (S 1 -S 2 )| dx + C 3 R |S 1 -S 2 | dx. (5.8)
Summing (5.8) and (5.7), we deduce that there exists a nonnegative constant C such that

d dt S 1 -S 2 W 1,1 (R) ≤ C S 1 -S 2 W 1,1 (R) .
Applying the Gronwall Lemma allows to conclude the proof.

Proof of uniqueness in Theorem 3.9. Let us assume that we have two duality solutions (ρ 1 , S 1 ) and (ρ 2 , S 2 ) such as in Theorem 3.9. Therefore, from Lemma 4.4, S 1 and S 2 are weak solutions of (4.1). Using Theorem 5.1, we conclude that S 1 = S 2 . Thus

ρ 1 = K * S 1 = K * S 2 = ρ 2 .
6 Convergence for the kinetic model

In this section we investigate the rigorous derivation of (2.8)-(2.10) from the microscopic model (2.4). First we state some estimates on the moments of the solution of the kinetic problem. Lemma 6.1 Let (f ε , S ε ) be a solution of the kinetic problem (2.4)-(2.5). Then for all t ∈ [0, T ] and all ε > 0 we have

R V |v| k f ε dxdv = |v| k |ρ ini |(R) , k ∈ N. Proof. Since v ∈ V = {-c, c}, |v| is constant therefore R V |v| k f ε dxdv = |v| k R ρ ε dx.
The result follows then directly from the mass conservation in (2.4).

Proof of Theorem 3.10. Let (f ε , S ε ) be a solution of (2.4)-(2.5). For fixed ε > 0, we have

f ε ∈ C([0, T ] × R × V ). Define ρ ε := V f ε dv, J ε := V vf ε dv and a(∂ x S ε ) = -cφ(c∂ x S ε ).
We can rewrite the kinetic equation (2.4) as

∂ t f ε + v∂ x f ε = 1 ε (Φ(-v∂ x S ε )ρ ε -2f ε ).
Taking the zeroth and first order moments, we get

∂ t ρ ε + ∂ x J ε = 0, (6.1)
∂ t J ε + v 2 ∂ x ρ ε = 2 ε (a(∂ x S ε )ρ ε -J ε ). (6.2)
From (6.1), we deduce that

∀ t ∈ [0, T ], |ρ ε (t, •)|(R) = |ρ ini |(R). Therefore, for all t ∈ [0, T ] the sequence (ρ ε (t, •)) ε is relatively compact in M b (R) -σ(M b (R), C 0 (R)). Moreover, there exists u ε ∈ L ∞ ([0, T ], BV (R)) such that ρ ε = ∂ x u ε .
From (6.1), we get that ∂ t u ε = -J ε and thanks to Lemma 6.1 we deduce that u ε is bounded in Lip([0, T ], L 1 (R)). This implies the equicontinuity in t of (ρ ε ) ε . Thus the sequence (ρ ε ) ε is relatively compact in S M and we can extract a subsequence still denoted (ρ ε ) ε that converges towards ρ in S M .

We recall that

S ε (t, x) = (K * ρ ε (t, •))(x) where K(x) = 1 2 e -|x| . Denoting S(t, x) := (K * ρ(t, •))(x), since ρ ∈ S M , we have ∂ x S ∈ L ∞ ([0, T ]; BV (R)). From Lemma 4.3, the sequence (∂ x S ε ) ε converges in L ∞ w
- * and a.e. to ∂ x S as ε goes to 0. Lemma 4.2 ensures that both a(∂ x S ε ) and a(∂ x S) satisfy the OSL condition.

From (6.1)-(6.2), we have in the distributional sense

∂ t ρ ε + ∂ x (a(∂ x S ε )ρ ε ) = ∂ x (a(∂ x S ε )ρ ε -J ε ) = ε 2 ∂ x (∂ t J ε + v 2 ∂ x ρ ε ) = R ε . (6.3)
Now, for all ψ ∈ C 2 c ((0, T ) × R), we deduce from Lemma 6.1

(∂ t J ε + v 2 ∂ x ρ ε )∂ x ψ dxdt ≤ |v||ρ ini |(R) ∂ t ∂ x ψ L ∞ + |v| 2 |ρ ini |(R) ∂ xx ψ L ∞ .
This implies that the limit in the distributional sense of the right-hand side R ε of (6.3) vanishes. Now we multiply equation (2.5) by a(∂ x S ε ) and use again the antiderivative A of a to obtain

a(∂ x S ε )ρ ε = -∂ x (A(∂ x S ε )) + a(∂ x S ε )S ε , (6.4)
so that we can rewrite the conservation equation (6.3) as follows, in D ′ (R):

∂ t ρ ε + ∂ x (-∂ x A(∂ x S ε ) + a(∂ x S ε )S ε ) = ε 2 ∂ x (∂ t J ε + v 2 ∂ x ρ ε ). (6.5)
Taking the limit ε → 0 of equation (6.5) in the sense of distributions, we get

∂ t ρ + ∂ x (-∂ x A(∂ x S) + a(∂ x S)S) = 0 in D ′ (R), (6.6)
where S(t, x) = (K * ρ(t, •))(x). Therefore the pair (ρ, S) satisfies (3.7)-(3.6). In addition, ρ is nonnegative as a limit of nonnegative measures, so that Lemma 4.1 implies the one-sided estimate ∂ xx S ≤ S. Thus we are in position to apply Lemma 4.4 and Theorem 5.1, which give uniqueness for S, and consequently for ρ. Therefore the whole sequence ρ ε converges to ρ in S M . We recall that we have chosen the initial data such that

ρ ini ε = η ε * ρ ini where η ε is a mollifier. Therefore ρ ini ε ⇀ ρ ini in M b (R) -σ(M b (R), C 0 (R)
). Thus we have constructed a solution that satisfies (6.6) in the distributional sense, in other words, we have defined a solution of the problem (2.8)-(2.10) thanks to its flux. A natural question is to know whether we can define a velocity corresponding to this flux. From the theory of duality solutions (see Theorem 3.5), it boils down to show that the above constructed solution is a duality solution. From Vol'pert calculus [START_REF]pert, The spaces BV and quasilinear equations[END_REF] we infer the existence of a S such that a S = a(∂ x S) a.e. and Using equation (6.6) we have in the distributional sense

∂ t ρ + ∂ x (a S ρ) = 0. (6.8)
However, we have proved in Section 5.3 that such a solution is unique. We deduce that the solution (ρ, S) obtained by the hydrodynamical limit above is the duality solution of Theorem 3.9. It concludes the proof of Theorem 3.10.

Remark 6.2 In the proof above, the macroscopic flux J defined in (3.6) appears to be the limit of the microscopic flux J ε . Indeed from (6.2) and (6.4) we deduce that, in the distributional sense,

J ǫ -→ J := -∂ x A(∂ x S) + a(∂ x S)S.
This natural definition of the flux allows to get the uniqueness of the solutions of the coupled system (2.8)-(2.10) thanks to equations (4.1)-(4.3). Such a technique to establish the hydrodynamic limit has been proposed in [START_REF] Nieto | High field limit for Vlasov-Poisson-Fokker-Planck equations[END_REF]. But the authors do not state that their limit is a duality solution and do not define a velocity and therefore a flow corresponding to their flux. In the limit of the Vlasov-Poisson-Fokker-Planck system, this result has been investigated in [START_REF] James | A remark on duality solutions for some weakly nonlinear scalar conservation laws[END_REF].

7 Numerical issue

Finite time of collapse

Before focusing on the numerical simulations, let us clarify the dynamics of the model. In the case of n Dirac masses, m i ≥ 0 for i = 1, . . . , n, located at positions x 1 < • • • < x n , we recall that the time evolution is governed by system (5.6):

m i x ′ i (t) = A m i 2 + j =i m j ∂ x K(x j -x i ) -A - m i 2 + j =i m j ∂ x K(x j -x i ) , (7.1)
for i = 1, . . . , n, where we recall that A is an antiderivative of a such that A(0) = 0. We deduce that for all t > 0, and for i = 1, . . . , n,

∃ γ i ∈ - m i 2 + j =i m j ∂ x K(x j -x i ), m i 2 + j =i m j ∂ x K(x j -x i ) such that x ′ i (t) = a(γ i (t)). (7.2)
Proposition 7.1 Let us assume that there exists n ∈ N * such that

ρ ini (x) = n i=1 m 0 i δ x 0 i (x),
with m 0 i ≥ 0, for i = 1, . . . , n. We assume in addition that a is a nondecreasing and odd real function. Then the duality solution ρ of Theorem 3.9 has the following properties :

1. If n = 1, x 1 (t) = x 0
1 for all t > 0. Then ρ(t) = ρ ini for all t > 0. 2. For i = 1, . . . , n -1, x ′ i (t) ≥ x ′ i+1 (t) therefore x i+1 -x i ≤ x 0 i+1 -x 0 i . 3. There exists c * ∈ [x 0 1 , x 0 n ] and T * > 0 such that ρ(t, x) = δ c * (x) for all t > T * . Proof. The first point is a direct consequence of the even character of A whereas the second point comes from the convexity of A. Let us then prove the third point. By convexity of the function A and with (7.1), we have

m 1 x ′ 1 ≥ A m 1 2 + n j=2 m j 2 e x 0 1 -x 0 j -A - m 1 2 + n j=2 m j 2 e x 0 1 -x 0 j > 0,
and

m n x ′ n ≤ A - n-1 j=1 m j 2 e x 0 j -x 0 n + m n 2 -A - n-1 j=1 m j 2 e x 0 j -x 0 n - m n 2 < 0.
As for (7.2), we can rewrite these last inequalities as :

x ′ 1 (t) ≥ a(γ 1 (0)) > 0,
x ′ n ≤ a(γ n (0)) < 0. We deduce that there exists a time T * > 0 such that all masses collapse for t = T * in a single Dirac mass.

Discretization

The numerical resolution of system (2.8)-(2.10) is far from obvious. A first naive idea consists in applying a standard splitting method where we treat separately the scalar conservation law (2.8) and the elliptic equation (2.10). It turns out that such a scheme is unable to recover the correct definition of the flux and therefore of the product a(∂ x S) by ρ. In particular, it leads to stationary Dirac masses.

A second idea consists in solving the distributional conservation law (3.7) by a finite volume method. It involves a discretization of the flux J on the interface of each cell of the mesh, and thus one could expect a correct computation of the flux, and therefore a convenient interpretation of the product. However, this definition of the flux involves the calculation of two derivatives of S. Using a centered scheme to discretize this quantity induces spurious oscillations as it is usually noticed for centered scheme on scalar conservation laws. We can then upwind the scheme depending on the sign of a(∂ x S) computed at previous iteration. But in doing so, we actually specify a value for a(∂ x S) in the definition of the product a(∂ x S) with ρ, and this can lead to capture wrong solutions.

Next, one can think of solving the equation (4.1) on S, motivated by the fact that it plays a key part in the uniqueness, and that ρ can be recovered readily from S. However the equation is non local and its numerical resolution appears to be quite complicated and with a high computational cost (even in the one dimensional setting).

Thus we prefer to use a method based on the dynamics of aggregates, detailed in Section 5.1. We use the principle of a particle method in which we approximate the density by a sum of Dirac masses. Then the motion of these pseudo-particles is approximated by discretizing system (5.6) with an explicit Euler scheme. More precisely, let us assume that we have an approximation of ρ at time t n = n∆t, given by

ρ n (x) = I n i=1 m n i δ y n i (x), (7.5)
where m n i > 0 is the mass allocated to the pseudo-particle at the position y n i with y

n 1 < y n 2 < • • • < y n I n for I n ∈ N * .
Then an approximation of the potential at time t n is given by

S n (x) = I n i=1 m n i e -|x-y n i | .
Using an explicit Euler scheme, we compute the new position

y n+1 i =y n i + ∆t m n i A - i-1 j=1 m n j 2 e y n j -y n i + m n i 2 + I n j=i+1 m n j 2 e y n i -y n j - ∆t m n i A - i-1 j=1 m n j 2 e y n j -y n i - m n i 2 + I n j=i+1 m n j 2 e y n i -y n j .
Next, we test if some pseudo-particles have collided during the time step ∆t. If y n+1 j+1 ≤ y n+1 j for j ≥ 1, then the pseudo-particles j and j + 1 have collapsed and form a unique pseudo-particle which has the mass m n j + m n j+1 . In this case, we decide to set this pseudo-particle at the position for given initial sequences (y 0 i ) i=1,...,I 0 and (m 0 i ) i=1...,I 0 of size I 0 , we can construct (y n i ) and (m n i ) of size I n as above.

Using well-known result on the convergence of Euler scheme, we deduce that, for given initial data (y 0 i ) i=1,...,I 0 , (m 0 i ) i=1...,I 0 and I 0 , y n i defined above converges to the solution x i (t) of (5.6) when ∆t tends to 0 such that t n → t. Using the convergence result in Section 5.2, we deduce that the function ρ n in (7.5) converges in S M to the unique duality solution of Theorem 3.9. Then the method introduced above is convergent provided we discretize the initial data ρ ini in such a way that ρ 0 (x) := I 0 i=1 m 0 i δ y 0 i (x) converges in M b to ρ ini . Moreover, we verify easily that we have

I 0 i=1 m 0 i = I n i=1
m n i , and I n ≤ I 0 , for all n ∈ N, and that the approximation ρ n of ρ(t n ) is nonnegative.

Numerical results

In this Section, we present numerical simulations of model (2.8)-(2.10) using the algorithm described above. We first approximate the initial data ρ ini ≥ 0, which is assumed to be compactly supported for numerical purpose, in the following way: we introduce a discretization x j = x 0 + j∆x of the bounded domain which includes the compact support of ρ ini and we define

m 0 i = x i + ∆x 2 x i -∆x 2 ρ ini (x) dx.
Then the sequence (y 0 j ) j is defined by the nodes (x i ) for which m 0 i is not zero, and I 0 correspond to the number of i ∈ N such that m 0 i is not zero. We construct then the approximation of ρ ini by ρ 0 (x) := I 0 i=1 m 0 i δ y 0 i (x). We present in Figure 1 the dynamics of the density ρ and of the chemoattractant concentration S for an initial data ρ ini given by the sum of two Gaussian functions, more precisely ρ ini (x) = e -20(x-0.5) 2 + e -20(x+0.5) 2 .

As expected, we first observe the formation of two Dirac masses at the position where ∂ x S initially vanishes. Then, the two aggregates collapse in the center. Looking at the time evolution, we notice that the first step of formation of aggregates is fast compared to the time of collapse.

In Figure 2 we display the dynamics for an initial data given by the sum of three Gaussian functions:

ρ ini (x) = e -10(x-1) 2 + e -20(x-0.2) 2 + e -20(x+0.5) 2 . We observe the formation of three Dirac masses that moves according to the dynamical system (7.1). They collapse then in finite time.

Finally, as we have already noticed, we evidence that the center of mass is not fixed. For instance, Figure 3 represents the dynamics of the density and of the potential for an initial data made of one big bump with one small bump: ρ ini (x) = 5e -20(x-1) 2 + 0.5e -20(x+0.5) 2 . The square shows the time dynamics of the center of mass. We observe that the center of mass at the final time is not located at the same position as at the initial time. given by the sum of three Gaussian.

[5] F. Bouchut, F. James, Duality solutions for pressureless gases, monotone scalar conservation laws, and uniqueness, Comm. Partial Differential Eq., 24 (1999), 2173-2189.

[6] F. Bouchut, F. James, S. Mancini, Uniqueness and weak stability for multidimensional 24

Theorem 3 . 6

 36 Let us assume that in addition to the OSL condition (3.3), b is piecewise continuous on ]0, T [×R where the set of discontinuity is locally finite. Then there exists a function b which coincides with b on the set of continuity of b. With this b, ρ ∈ S M is a duality solution to (3.1) if and only if ∂ t ρ + ∂ x ( bρ) = 0 in D ′ (R). Then the generalized flux b∆ρ = bρ. In particular, b is a universal representative of b.

Lemma 4 . 1

 41 Let ρ ∈ C([0, T ], M b (R)). Then the solution S of equation (2.10) satisfies 1. ρ ≥ 0 =⇒ S ≥ 0 2. one-sided estimate: ∂ xx S ≤ S if and only if ρ ≥ 0 3. for all p ∈ [1, +∞], S ∈ C([0, T ], L p (R)) and ∂ x S ∈ C([0, T ], L p (R))

Lemma 4 . 2

 42 Let ρ ∈ S M . Then the coefficient a(∂ x S) defined by (2.9)-(2.10) satisfies the OSL condition (3.3) if and only if ρ ≥ 0 Proof. Straightforward computations lead to

  ∂ x (A(∂ x S)) = a S ∂ xx S.Therefore-∂ x (A(∂ x S)) + a(∂ x S)S = a S ρ a.e. , with a S = a(∂ x S) a.e. (6.7)

1 2

 1 (y n+1 j+1 + y n+1 j ) and set m n+1 j = m n j + m n j+1 , moreover we have therefore I n+1 = I n -1. Finally,

Figure 1 :

 1 Figure 1: Dynamics of the density ρ (top) and of the potential S (bottom) for an initial density given by the sum of two Gaussian.

Figure 2 :

 2 Figure 2: Dynamics of the density ρ (top) and of the potential S (bottom) for an initial density given by the sum of three Gaussian.

Figure 3 :

 3 Figure 3: Dynamics of the density ρ (top) and of the potential S (bottom) with the dynamics of the center of mass represented by a red square. The center of mass moves.

  under the assumptions (3.3), there exists a unique ρ ∈ S M , duality solution to (3.1), such that ρ(0, .)= ρ • . Moreover, if ρ • is nonnegative, then ρ(t,•) is nonnegative for a.e. t ≥ 0. And we have the mass conservation |ρ

  e. Moreover, since ∂ x S n is bounded in L ∞ uniformly with respect to n by construction, we can extract a subsequence of (a(∂ x S n )) n that converges in L ∞ -weak * towards b. Since from Lemma 4.2, a(∂ x S n ) satisfies the OSL condition, we deduce from Theorem 3.5 4) that, up to an extraction, ρ n ⇀ ρ in S M and a n ρ n ⇀ aρ weakly in M b (]0, T [×R), ρ being a duality solution of the scalar conservation law with coefficient b. With Lemma 4.3, we deduce that ∂

x S n → ∂ x S a.e., it implies in particular that J n

Remark 7.2 Notice that we have in addition the following estimate for T * : T * < (x 0 n -x 0 1 )/(a(γ 1 (0)) -a(γ n (0))). Corollary 7.3 Let us assume that 0 ≤ ρ ini ∈ C c (R) with compact support [0, L]. Let us denote ρ the duality solution of Theorem 3.9 with initial data ρ ini . Then there exists c * ∈ [0, L] and T * > 0 such that ρ(t, x) = δ c * (x) for all t > T * .

Proof. Let us approximate ρ ini by

x 0 i ρ ini (dx). From Proposition 7.1, we deduce that there exists c * n ∈ [0, L] and T * n > 0 such that the duality solution of Theorem 3.9 with initial data

where we recall that

and

By stability results on duality solutions in Theorem 3.5 (see also subsection 5.1), we deduce that ρ n ⇀ ρ in S M as n → +∞. Taking the limit in (7.3) and (7.4), we deduce by continuity of ρ ini that

and

Moreover, since ρ ini is continuous with compact support in [0, L] we have ρ ini (0) = ρ ini (L) = 0. We deduce that the sequence (T * n ) n∈N * is bounded. Thus there exists a time T * independent of n such that ρ n (t) = δ c * n for all t > T * . Taking the limit when n → +∞, we conclude that there exists c ∈ [0, L] such that ρ(t) = δ c for all t > T * . Remark 7.4 Taking a = Id, therefore A(x) = x 2 /2, we deduce from (7.1) that

We recover the dynamics of the aggregation equation as noticed by Carrillo et al. in [START_REF] Carrillo | Global-in-time weak measure solutions and finite-time aggregation for nonlocal interaction equations[END_REF]. These authors prove in particular the concentration in finite time of the total mass in the center of mass. In the framework of the present work, which is focused on applications to chemotaxis, a is not assumed to be the identity function, so that the center of mass is not conserved. A numerical evidence of this phenomenon will be proposed in the last subsection of this paper.


L Rose

S M Perlaza

S Lasaulce
email: samson.lasaulce@lss.supelec.fr

M Debbah

Learning Equilibria with Partial Information in Decentralized Wireless Networks

In this article, a survey of several important equilibrium concepts for decentralized networks is presented. The term decentralized is used here to refer to scenarios where decisions (e.g., choosing a power allocation policy) are taken autonomously by devices interacting with each other (e.g., through mutual interference). The iterative long-term interaction is characterized by stable points of the wireless network called equilibria. The interest in these equilibria stems from the relevance of network stability and the fact that they can be achieved by letting radio devices to repeatedly interact over time. To achieve these equilibria, several learning techniques, namely, the best response dynamics, fictitious play, smoothed fictitious play, reinforcement learning algorithms, and regret matching, are discussed in terms of information requirements and convergence properties. Most of the notions introduced here, for both equilibria and learning schemes, are illustrated by a simple case study, namely, an interference channel with two transmitter-receiver pairs.

I. INTRODUCTION

The notion of cognitive radio (CR) has gained momentum in recent years to build flexible and efficient networks. Indeed, CRs are nowadays widely accepted as a suitable solution to rationally exploit shared spectral resources and increase spectral efficiency. The main idea behind CR relies on the capability of a

given radio device to self-configure its own communication parameters in an intelligent, autonomous and decentralized manner, as a result of its interaction with the environment. In this context, the choice of a particular communication configuration by a given CR is highly influenced by the choice of all other radio devices. Within this framework, non-cooperative game theory appears as a suitable paradigm to study and analyse such scenarios. Therefore, the idea of equilibrium, namely, Nash equilibrium (NE), becomes particularly relevant. Indeed, at the NE, the transmit configuration of each CR in the network is optimal with respect to the configuration of all its counterparts. Interestingly, in some cases, an equilibrium can be reached by using particular iterative procedures similar to learning processes [START_REF] Fudenberg | The Theory of Learning in Games, ser[END_REF].

In this article, we first present an overview of various equilibrium concepts. Later, we introduce a set of learning algorithms particularly relevant to achieving equilibrium in wireless networks. For each algorithm, we discuss the required information that each CR must possess at each iteration and the convergence properties.

The rest of the paper is organized as follows. In Sec. II, we briefly present the notations adopted in this paper, as well as usual game-theoretic terminology. In Sec. III, we present and discuss several important solution concepts for games, namely, the coarse correlated equilibrium, the correlated equilibrium, the Nash equilibrium, and the -Nash equilibrium. In Sec. IV, we discuss important learning algorithms which can, under certain conditions, converge to one of the aforementioned solutions. In Sec. V, we present an illustrative case study: the 2 × 2 interference channel, a simple, though very important, communication scenario, which we use as a test-bench for comparing the aforementioned algorithms.

II. DEFINITIONS AND ABBREVIATIONS

In game theory, the normal form is a convenient mathematical representation of a game. Basically, it consists of a triplet: the set of players K = {1, 2, ..., K}, the set of actions A k = {A With a slight abuse of notation, we denote by a -k ∈ A -k the vector of actions of all players except the k-th player and we write the vector a as (a k , a -k ) to stress the k-th component. For instance, the set of players can consist of the set of wireless terminals present in the network, the action set can be any feasible vector of transmit powers, and the utility function can be the spectral efficiency. Other components are also possible for the game representation and they depend on the scope and purpose of the network design. We denote by (A) the set of all possible probability distributions over the whole set of actions A, and by (A k ) the set of all possible probability distributions of user k over its action set. We refer to the elements of the set A k as actions of player k and those of the set (A k ) as strategies of player k. A June 2, 2011 DRAFT given strategy of player k is denoted by

π k = (π k,A (1) k , ..., π k,A (N k ) k ) ∈ (A k ), where π k,A (n k ) k represents
the probability that player k plays action A (nk) K . We indicate by φ = (φ A (1) , ..., φ A (N ) ) ∈ (A), with N = Q K j=1 N j , a given joint probability distribution over the set A, with φ A (n) being the probability of observing A (n) as an outcome of the game.

III. FROM COARSE CORRELATED EQUILIBRIA TO NASH EQUILIBRIA

The most general type of equilibria we use in this paper is the so called coarse correlated equilibrium (CCE) [START_REF] Young | Strategic learning and its limits (arne ryde memorial lectures sereis)[END_REF]. The idea behind CCE is that actions chosen by the players of a game may be correlated. For instance, correlation may appear when a common broadcast signal is observed by several transmitters choosing their transmit configuration, e.g., a power control policy. We call the signals received by the players recommendations. In such a context, a CCE is a probability distribution φ ∈ (A) over the set of action profiles of the game from which no player has interest in unilaterally deviating. The realizations of this joint distribution φ are the recommendations. Mathematically, this can be written as follows.

Definition 1 (Coarse Correlated Equilibrium

): A joint probability distribution φ ∈ (A) is a CCE if ∀k ∈ K and ∀a k ∈ A k it holds that X a∈A u k (a)φ a ≥ X a-k∈A-k u k (a k , a -k )φ -k,a-k , (1)
where φ -k,a-k = P ak∈Ak φ (ak,a-k) is the marginal probability distribution w.r.t. a k . An important remark is that, following the notion of CCE, players are assumed to decide, before receiving the recommendation, whether to commit to follow it or not. At a CCE, all players are willing to commit to follow the recommendation given that all the others also choose to commit. That is, if a single player decides not to commit to follow the recommendations, it experiences a lower (expected) utility. A special case of CCE is the correlated equilibrium (CE, [START_REF] Young | Strategic learning and its limits (arne ryde memorial lectures sereis)[END_REF]). The difference between the CCE and the CE is that, in the latter, players choose whether to follow or not a given recommendation, after it has been received. Therefore, there is not a priori commitment. It follows, in particular, that every CE is a CCE [START_REF] Young | Strategic learning and its limits (arne ryde memorial lectures sereis)[END_REF]. Now, if the players choose their strategy following independent individual probability distributions π k ∈ (A k ), i.e., φ a = Q K j=1 π j,aj in (1), we obtain from Def. 1, the definition of mixed Nash equilibrium (MNE); the MNE is, clearly, a special case of CE and thus, a special case of CCE. A MNE is, therefore, a vector of individual probability distributions π = (π 1 , . . . , π K ) which is stable to unilateral deviations, i.e., if player k decides to use a different probability distribution from the corresponding π k , then it observes a lower (expected) utility. As shown in [START_REF] Fudenberg | Game theory[END_REF], this type of equilibria always exists in games with finite number of players and finite action sets. For more results on the existence and multiplicity of NE, June 2, 2011 DRAFT the reader is referred to [START_REF] Lasaulce | Methodologies for analyzing equilibria in wireless games[END_REF]. The finiteness assumption is especially relevant when a wireless terminal has to select a given communication setting, e.g., a channel, a constellation size, or a transmit power level.

We further introduce the concept of pure NE (PNE). A PNE is obtained by restricting the players to deterministically choose one of their actions instead of choosing it by following a probability distribution.

A PNE is therefore a special case of MNE where the individual probability distribution is a Dirac delta function over a given action. Thus, a PNE is a vector of actions a = (a 1 , . . . , a K ) stable to unilateral deviations, i.e., if player k uses a different action from its corresponding a k , while the others keep their equilibrium action, player k observes a lower (instantaneous) utility.

As a last notion of equilibrium, we introduce the idea of -equilibrium [START_REF] Young | Strategic learning and its limits (arne ryde memorial lectures sereis)[END_REF]. An -equilibrium is a

mixed strategy profile π = (π 1 , . . . , π K ) ∈ (A 1 ) × . . . × (A K )
such that if only one player k uses a different strategy from its corresponding π k , it does not observe a utility improvement greater than > 0. An instance of -NE [START_REF] Young | Strategic learning and its limits (arne ryde memorial lectures sereis)[END_REF] is the logit equilibrium [START_REF] Young | Strategic learning and its limits (arne ryde memorial lectures sereis)[END_REF]. In what follows, some learning algorithms which may converge to CCE, CE, MNE, PNE, or -equilibrium are provided.

IV. LEARNING EQUILIBRIA

The process of learning equilibria is basically an iterative process. Each iteration of the learning process can be broadly divided into three phases: (i) the observation of the environment at iteration n, which gives an idea to the players how well they played in the previous iteration; (ii) the improvement of the strategy π k (n) based on the current observation and (iii) the selection of the action a k (n) according to the strategy π k (n). Hence, we say that players learn to play an equilibrium, if after a given number of iterations, the strategy profile

π(n) = (π 1 (n), . . . , π K (n)) ∈ (A 1 ) × . . . × (A K ) converges to an equilibrium strategy.
The purpose of this section and Sec. V is, under the space limitations for this survey, to introduce the following set of learning algorithms: best response dynamics (BRD), fictitious play (FP), smooth fictitious play (SFP), regret matching (RM), reinforcement learning (RL) and the joint utility and strategy learning estimation reinforcement learning (JUSTE-RL). Then, in Sec. IV-B, we compare such algorithms in terms of relevant features in the context of wireless communications, for instance, type of observations, type of action sets, convergence time, nature of the steady state achieved when convergence is observed and conditions for convergence.

June 2, 2011 DRAFT

A. Informal definition of the learning algorithms under consideration 1) Best Response Dynamics: In its most basic form, the best response dynamics relies on the following assumption: at each game stage n ∈ N, every player k plays the action a k (n) which optimizes its own utility given the actions played by the other players. When all players play simultaneously at each stage (simultaneous-BRD), the optimization of player k is done with respect to the action profile a -k (n -1).

When players play sequentially, only one player at each stage (sequential-BRD) updates its action a k (n),

optimizing it with respect to the action profile (a 1 (n), . . . , a k-1 (n), a k+1 (n -1), . . . , a K (n -1)).

2) Fictitious Play: The fictitious play relies on the assumption that at each stage n, each player k knows all the past actions of all the other players, i.e., a j (0), . . . , a j (n -1), ∀j ∈ K \ {k}. Based on such observations, player k calculates the empirical frequencies with which each player plays its corresponding actions. We refer to these empirical frequencies as beliefs. Let us denote the belief that player k = j has on player j by the vector

f j (n) = f j,A (1) j (n), . . . , f j,A (N j ) j (n) ∈ (A j ).
At each stage, all players (simultaneously or sequentially, as in the BRD) choose their current action by optimizing their expected utility with respect to the beliefs on all the other players, i.e., a k (n

) ∈ argmax ak∈Ak E f (n) [u k (a k , a -k )],
where

f (n) = (f 1 (n), . . . , f K (n)).
3) Smooth Fictitious Play (SFP): The convergence of FP is not ensured in games with cycles and its ability to explore the whole action set is highly constrained. To overcome these issues, a simple variation of the FP has been proposed under the name of smooth fictitious play (SFP). The assumptions on which SFP relies are the same as FP and actions can be updated either simultaneously or sequentially. The main difference between SFP and FP is that, at each stage n, player k does not choose a deterministic action.

It rather builds a probability distribution π k (n) ∈ (A k ) to choose its action a k (n). Such a probability distribution can be interpreted as the one that maximizes a weighted sum of the original expected utility and other continuous strictly concave function. For instance, if such a function is the entropy function [START_REF] Young | Strategic learning and its limits (arne ryde memorial lectures sereis)[END_REF], the resulting probability distribution is given by the logit probability distribution. is defined as the difference between the average utility the player would have obtained by always playing

A (nk) k
and the average utility actually achieved with the current strategy, i.e.,

r k,A (n k ) k (n) = 1 n -1 n-1 X t=1 (u k (A (nk) k , a -k (t)) -u k (a k (t), a -k (t))). (2)
June 2, 2011 DRAFT RM relies on the assumptions that at every stage n, player k is able to both evaluate its own utility, i.e., to calculate u k (a k (n), a -k (n)) and compute the utility it would have obtained if it had played any other action a k , i.e. u k (a k , a -k (n)). Finally, the action to be played at stage n is taken following the probability distribution π k (n), which is obtained by normalizing to one the regret vector

r k (n) = r k,A (1)
k (n), . . . , r k,A (N k ) k (n) .
5) Reinforcement Learning (RL): In the case of reinforcement learning (RL), players are modelled as automata that implement a given behavioural rule. In general, RL techniques rely on the following two conditions: (i) for each player k, the action set A k is finite and for all action profiles a ∈ A, the achieved utility u k (a k , a -k ) is bounded; (ii) each player is able to periodically observe its own achieved utility. Intuitively, the idea behind CRL is that actions leading to higher utility observations in stage n are granted with higher probabilities in the game stage n + 1, and vice versa.

6) Joint Utility and Strategy Estimation based -Reinforcement Learning (JUSTE-RL):

A variant of the former algorithm has been proposed in [START_REF] Perlaza | How can ignorant but patient cognitive terminals learn their strategy and utility?[END_REF]. The joint utility and strategy estimation behavioural rule relies on the same assumptions as the classical RL. The main difference between classical RL and JUSTE-RL is that, in the former, the observation ũk (n) of the utility of player k is used to directly modify the probability distribution π k (n); in the latter, such an observation is used to build an estimation of the expected utility for each of the actions. Such utility estimates are, then, used in the same iteration to finally build a probability distribution π k (n) from which action a k (n) will be drawn. Thus, each player always possesses an estimation of the expected utility it obtains by playing each of its actions.

B. Discussion

The purpose of this section is to provide additional insights about the performance and pertinence of the learning algorithms described above in the context of decentralized wireless networks. In the following, we compare the algorithms in terms of several fundamental features. We summarize this discussion in Table I.

1) Observations: At each iteration of a given learning algorithm, each player must obtain some information about how the other players are reacting to its current action, in order to update their strategy and choose the following action. Broadly speaking, in algorithms such as BRD, FP, SFP and RM, players must observe the actions played by all the other players. This implies that a large amount of additional signaling is required to broadcast such information in wireless networks. In some particular cases, this condition can be relaxed and less information is required [START_REF] Larsson | Game Theory and the Flat-Fading Gaussian Interference Channel: Analyzing Resource Conflicts in Wireless Networks[END_REF], [START_REF] Leshem | Game theory and the frequency selective interference channel -a tutorial[END_REF]. However, this is highly dependent on the topology of the network and the explicit form of the utility function [START_REF] Scutari | Optimal linear precoding strategies for wideband non-cooperative systems based on game theory -part II: Algorithms[END_REF]. Other algorithms, such as RL June 2, 2011 DRAFT and JUSTE-RL, only require that each player observes its corresponding achieved utility at each iteration. This is in fact, their main advantage, since such information requires a simple feedback message from the receiver to the corresponding transmitters [START_REF] Sastry | Decentralized learning of Nash equilibria in multi-person stochastic games with incomplete information[END_REF], [START_REF] Perlaza | How can ignorant but patient cognitive terminals learn their strategy and utility?[END_REF].

2) Knowledge and Calculation Capabilities: Learning algorithms such as BRD, FP, SFP and RM involve an optimization problem at each iteration [START_REF] Fudenberg | The Theory of Learning in Games, ser[END_REF], that is, either the maximization of the (expected or instantaneous) utility or minimization of the regret. Therefore, generally, highly demanding calculation capabilities are required to implement them. More importantly, solving such optimization requires the knowledge of a closed-form expression of the utility function. This implies that each player knows the structure of the game, i.e., set of players, action sets, current strategies, channel realizations, etc. In this respect, RL and JUSTE-RL algorithms are more attractive since only algebraic operations are required to update the strategies. In terms of knowledge, in both RL and JUSTE-RL, players are only required to know, at each iteration, the action they actually played and the corresponding achieved utility. Indeed, one can say that players are not even aware of the presence of other players.

3) Nature of the Action Sets: The nature of the action sets of the game plays an important role.

The BRD can be used for both continuous and discrete action sets, whereas in their standard versions FP, SFP, RM, CRL, and JUSTE-RL are designed for discrete action sets. For instance, action sets are discrete in problems where a channel, constellation size or discrete power levels must be selected, whereas continuous sets are more common in power allocation problems [START_REF] Lasaulce | Methodologies for analyzing equilibria in wireless games[END_REF].

4) Steady State:

When a steady state is achieved by one of the algorithms under consideration, such state may correspond to one of the equilibrium notions presented in Sec. III. In particular, when BRD and FP converge, the strategy of the players at the steady state is a NE. In the case of the RM, it converges to an element of the set of CCE. Here, we highlight the fact that, even though the notion of CCE relies on the idea of the recommendations studied in Sec. I, it does not require the existence of recommendations to converge to an element of the set of CCE. When SFP or JUSTE-RL achieve a steady state, it corresponds to an -NE. On the contrary, in the case of RL, a steady state not necessarily corresponds to a particular notion of equilibrium.

5) Convergence Conditions:

Regarding the conditions for convergence, only sufficient conditions are available. As shown in Table I, the considered algorithms typically converge in certain classes of games [START_REF] Young | Strategic learning and its limits (arne ryde memorial lectures sereis)[END_REF] such as dominance solvable games (DSG), potential games (PG), super-modular games (SMG), 2×N

non-degenerated games (NDG) or zero-sum games (ZSG).

6) Synchronization:

In the particular case of algorithms where each player must observe the actions of the others, e.g., BRD, FP, SFP and RM, certain synchronization is required in order to allow players June 2, 2011 DRAFT to know when to play and when to observe the actions of the others. In wireless communications, this requirement implies the existence of a given protocol for signalling messages exchange. Conversely, when players require only an observation of their individual utility, such a synchronization between all the players becomes irrelevant. Here, only a feedback message from the receiver to the corresponding transmitters per learning iteration is sufficient.

7) Environment: Learning techniques such as the BRD are highly constrained for real system implementations since they require the network to be static during the whole learning processes. On the contrary, all the other techniques allow the dynamics of the network to be captured by their statistics as long as they are stationary. This is basically because, contrary to BRD, all the other techniques determine whether to play or not a particular action based on the expected utility rather than instantaneous utility.

8) Convergence Speed:

The speed of convergence (when it is observed) is highly influenced by the amount of information available for the players. For instance, FP, SFP and RM converge faster than JUSTE-RL since the formers calculate the expected utility relaying on a closed form expression.

Conversely, the latter calculates it as the time-average of the instantaneous observations of the achieved utility. This requires a large number of observations to obtain a reliable approximation to the expected utility. We do not state any particular comment on the speed of convergence of BRD and RL since, in the former the scenario is considered fixed and the latter, it does not necessarily converge to an equilibrium strategy. However, conclusions for a particular case are stated in the following section.

V. CASE STUDY: THE PARALLEL INTERFERENCE CHANNEL

In this section, we introduce a simple but insightful example, which we use as a test-bench to compare the learning algorithms described above. Consider a parallel interference channel, that is, a set of 2 transmitter-receiver pairs sharing a set of S non-overlapping frequency bands. For the ease of presentation, assume that channel gains are time invariant during the whole transmission duration. Each transmitter chooses a single frequency band to transmit aiming to maximize its individual spectral efficiency, i.e., the ratio between the individual Shannon rate and available bandwidth. This problem has been analysed in the context of compact and convex sets of actions in [START_REF] Scutari | Optimal linear precoding strategies for wideband non-cooperative systems based on game theory -part II: Algorithms[END_REF] and in discrete and finite sets in [START_REF] Rose | On the Nash equilibria in decentralized parallel interference channels[END_REF], which is the case of this section.

In Figure 1, we plot the average spectral efficiency of the system as a function of the SNR, in the case where only 2 orthogonal channels are available. Here, all the algorithms iterate the same number of times (40 iterations). In Figure 1, it is interesting to note how algorithms such as FP, SFP and RM converge always very close to the best NE, i.e, the NE associated with the highest network spectral June 2, 2011 DRAFT efficiency. Nonetheless, this performance is achieved at the cost of a lot of information about the game.

In particular, note that RL and JUSTE-RL are less performing, but at the same time, less demanding in terms of information. Interestingly, the BRD demands the same information assumptions than FP, SFP and RM. However, the performance is even worse that RL. This is due to the fact that BRD does not necessarily converge to a NE in this particular game. In Figure 2, we plot the network spectral efficiency of the algorithms as a function of the number of iterations for the case of two channels. Here, RM and BRD appear to be the best performing and worst performing algorithms, respectively. With respect to the BRD, such a performance is due to a ping-pong effect between two particular action profiles. In detail, since players are simultaneously selecting the channels with the highest gain, it may happen that the best channel is the same for both players. Thus, for instance, at odd iterations they both share the same channel and in the next one, they both select different channels. This effect will continue at the infinite preventing the algorithm to converge. In Figure 3, we show how the algorithms perform when a higher number of channels is available, i.e, 4 channels. BRD improves its performance, with respect to the other algorithms. This is mainly because the higher number of channel reduces the probability of the ping-pong effect described above.

In Figure 4, we plot the network spectral efficiency as a function of the number of available channels. Here, the negative slot is due to the fact that we increase the number of available channels but transmitters remain subject to use a single channel. Thus, since S > K, there always exist a number of unused channels. The main observation in this figure is the following, the BRD becomes a very efficient solution when the number of channels is high enough to make the bouncing effect a very improbable event.

Conversely, JUSTE-RL exhibits a lower performance when the number of possible actions increases. This is basically because, in JUSTE, all players play all their actions with non-zero probability in order to improve their utility estimation. Thus, this immediately implies that increasing the number of actions, increases the time that players are playing actions different from the optimal actions. Finally, in Figure 5, we show for the 2-players 2-channel case, the trajectories of the algorithm during the transient phase. In this realization, BRD it can be observed that BRD does not converge. The two transmitters repeatedly select synchronously the same channel. FP and SFP converge to the best performing NE while CRL converges fast to a steady point with no game theoretical meaning. In the trajectory of JUSTE, it is possible to see that it converges to the best performing NE, for that particular channel realization. Similarly, RM also converge very fast to the best NE.

June 2, 2011 DRAFT

VI. CONCLUSION

In this paper, we have presented several notions of equilibrium and several learning dynamics that allow wireless networks to achieve such equilibria. In particular, we have described a general notion of equilibrium, namely, the coarse correlated equilibrium (CCE). Then, we introduced some particular cases of CCE, such as correlated equilibrium (CE) and Nash equilibrium (NE), are also analysed.

Regarding the learning dynamics, we have presented the best response dynamics (BRD), fictitious play (FP), smooth fictitious play (SFP), regret matching (RM), reinforcement learning (RL) and joint utility and strategy estimation based reinforcement learning (JUSTE-RL). We have identified the pertinence of these algorithms for wireless communications in terms of system constraints (continuous/discrete actions, required information, synchronization, signalling, etc.) and the performance criteria (utility achieved at the steady state, convergence speed, etc.). As further work in this direction, we point out that existing results regarding the analysis of equilibrium in wireless networks strongly depend on the topology of the network. Indeed, a general framework for the analysis of equilibria and learning dynamics adapted to time-varying topology networks is still an open problem. Moreover, we must consider that some equilibrium notions, e.g., NE and -NE, might be inefficient from a global point of view. Thus, learning algorithms to achieve Pareto optimal solutions with partial information is a further direction of research.

  , and the utility functions u k (a), where a ∈ A = A 1 × A 2 × ... × A K is an action profile/vector.

4 )

 4 Regret Matching (RM): Contrary to the case of BRD, FP and SFP, where players determine whether to play or not a particular action based on the idea of utility maximization, in RM, such a decision is made considering the notion of regret minimization. The regret that player k associates with action A (nk) k

Fig. 1 .

 1 Fig. 1. Average system spectral efficiency [bps/Hz] as a function of signal to noise ratio (SNR) with 40 iterations for the 2 players and 2 channel case.

Fig. 2 .

 2 Fig. 2. Average system spectral efficiency [bps/Hz] as a function of the number of iterations at a fixed SNR of 10 dB for the 2 players and 2 channel case.

Fig. 3 .

 3 Fig. 3. Average system spectral efficiency [bps/Hz] as a function of the number of iterations at a fixed SNR of 10 dB for the 2 players and 4 channel case.

Fig. 4 .Fig. 5 .

 45 Fig. 4. Average system spectral efficiency as a function of the number of channels, with SNR=10dB and 40 iterations.

TABLE I BENCHMARK

 I OF LEARNING ALGORITHMS.

June 2, 2011 DRAFT

June 2, 2011 DRAFT


Bernard Caron Llacan
email: caron@vjf.cnrs.fr

Polci languages

.

Résumé

Cet article présente la morphologie commune des langues polci, et la compare à celle du zaar. Les langues zaar et polci appartiennent toutes aux langues tchadiques de la branche Sud-Bauchi Oriental, bien que pour leur classification interne, (Shimizu 1978) les a rangées dans des groupes de langues différents

. This language cluster belongs to Chadic, West A; South-Bauchi West languages, Sub-group North. It comprises the following languages: Zùl, Barang, Dììr, Bili, Nyámzax, Lundur, Pos.

From 1995 to 2004, I have done fieldwork on : Dììr, Bili (Buli), Nyámzax (Langas), Pos (Polci) and Luri. Due to difficult conditions of work, the Luri data is very limited 1 ; likewise, the Buli data is of very poor quality and will not be used in this work.

In this paper, I will give a presentation of the common morphology of the Polci language cluster (CP) as a first step to characterise South Bauchi West languages (SBW). I intend to repeat the operation for the other SBW language clusters identified by Shimizu. As a matter of comparison, the Zaar equivalents (Za) are given next to CP. I will concentrate essentially on verbal and pronominal morphology and give only a few examples of the rest of the morphology and the lexicon. As a convention, I will call the Polci cluster 'Polci' and the Polci language 'Po'.

Po and Za are three-tone languages (Lo = à ; Mid = a; Hi = á) ; the others are two-tone languages (Lo = à ; Hi = a). This will make it difficult for the time being to mark tones on CP Abbreviations : ACC: accomplishment; AOR: aorist; COP: copula; CP: Common Polci; Di: Dir; DO: direct object; f: feminine; foc: focus; FUT: future; Hi: High tone; IMPF: imperfect; Lo: Low tone; Lu: Luri; Mid: Middle tone; Ny: Nyamzax; m: masculine; p: plural; PC: Proto-Chadic; Po: Polci; Pp: Predicative particle; PREP: preposition; PRO: pronoun; s: singular; Ri: Rising tone; SBW: South Bauchi West; TAM: Tense-Aspect Marker; Za: Zaar.

1.

Pronouns SBW has lost gender and tends to express number through tone contrast. Polci has not taken that process as far as Za. All different paradigms show little variation. We give individual forms only when they differ from CP.

TAM

Aorist-Perfective

The Perfective is also used as a narrative and a subjunctive (cf. infra). The aspect morpheme is Ø, leaving the person indexes bare. K stands for k/g.  3s Polci is Pro-drop with a Ø person index (cf infra). 3p wu is uniform.

CP

Subjunctive

The paradigm of the Subjunctive is the same as that of the Perfective, with the following exceptions: 3s has tone variations and in Di and Lu, 2p has a -n suffixed to the verb.

2.3.

Imperfective Apart for Lu and Ny which share the same -aa formative for the Imperfective, the forms are variable.

CP

Continuous

In SBW, the Continuous is the grammaticalization of a locative construction based on the paradigm of non-verbal subject pronouns : PRO+COP+PREP. In Polci, the COP is a zero morpheme. The prepositions vary for each language: Po n; Ny p; Di dàn. We give the full paradigm of Di as an example. In Za, the copula is the defective verb yi, 'be' and the preposition ká.

Di

Comments

5.1.

General comment on verb and pronoun morphology Both are quite limited, with a very economic system of pronouns : the same segments are used in the various pronominal functions. The number of aspects is very limited. The core of the system is provided by two underived aspects: Perfective-Aorist and Imperfective. The Continuous is a grammaticalized locative construction, and the Future is derived from an auxiliary construction.

3s & Pro-drop

The proof that 3s yàà which appears with verbs in the various aspects is originally a topic, not a TAM person index, is provided by the Po Negative Perfective. Example (5) shows the normal construction with the first segment of the discontinuous negative morpheme ii … rà occurring on the left of the TAM marker: 7), the 3s Po Imperfective shows the form yàà r where yàà is the Topic (independent pronoun) and Ø is the form of the Imperfective when the subject is a noun. If yàà had been a TAM, it would have been repeated between r and the main verb.

2s ambiguity



  1p Di mù.  2s k is uniform except for Lu g. 2p Ny g, Lu gn.



  1s Po ám ; Di á ; Ny naa ; Lu áá. 1p Po mùú; Di mú V-Ri; Ny maa; Lu màà.  2s Po & Di k ; Ny kaa ; Lu káá. 2p Po k ; Di k V-Ri ; Ny gaa ; Lu gàà.  3p Po & Di wú ; Ny & Lu wùù.

  expressed by the Imperfective. However a second future shows various degrees of grammaticalization of the verb r, 'come' in the Imperfective followed by the main verb in the Aorist. It is still a quasi-serial verb construction in Po, and has become a bona fide TAM in Di. Let us compare the 1p in the three languages where it has been observed, first in Po:

  Polci languages adopt various solutions to avoid the ambiguity between 2s & 2p. :  Ny & Lu contrast 2s = [-Voiced] with 2p = [+Voiced]: k / g ; kn / gn;  Po marks 2p with a Lo tone on the TAM: Perf k vs k ; Imperf k vs k; Cont kn vs kn;  Di marks 2p with a Lo tone on the verb: Perf 2s k vs 2p k Lo-V;  In the genitive, Ny contrasts 2s -gn with 2p -g.

wúr is characteristic of Polci. Ny wúr; Di wúrí; Po wún; Lu wìì. 1.2. Non-verbal Subject The

  segmental forms of Non-verbal Subjects (subjects of predicative particles) are very close to those of Independent subjects. Tones of Nonverbal subjects vary a lot in Polci. For example, Lu has Lo everywhere; Ny has Lo everywhere except for 3s; Di has Hi in 1s and 2s, Lo elsewhere. Tones vary according to number (i.e. Po 2s k & 2p k) but the variations from one language to another are enormous, i.e. Po has Hi except for 1p & 2p = Lo whereas Ny has Lo except for 1p & 2p = Hi when suffixed to monoverbs beginning with a voiced obstruent, although these consonants usually have a depressing influence on tones (cf.Caron, 2005 on Za).

	1.3.	Direct Object
	1.1.	Independent		CP	Zaar
	1s Di -ini.		1s 1s 2s 2s 3s 3s 1p 1p 2p 2p 3p 3p	CP ám -m kí -K yà(x)/tí -T mìì -mi kn -gn wúr -wur	Zaar -m myááni -k kyááni -t yááni -mí myààní -kí kyààní -shí yààshí
	1s Di:ámí. 2s Ny k.
	for common 3s. This gender levelling in favour of the feminine gender has 1.4. Independent Genitive
	been observed by Rudolf Leger in Southern Bole languages (cf. Leger, The base is the Genitive link suffixed with a clitic genitive pronoun : g-Pro.
	2005). Po has kept ti/t as a variant in Independent Pronouns, and as a CP Zaar logophoric pronoun which appears in [+foc] clauses as well: 1s geem gtn
		1 yàà x 3S.PERF say wolé i 2s 3s COMP 3S.LOG take NEG gii gwàà t x /yàà y ka rà. giis gòs 1p geemi gòpm He 1 said that he 1 would not take [it]. 2p giini gwààn
		2 a	gaa	xn t/*yàà yu 3p gsn gwààsn nyen.
	in calabash COP 3S.PERF pour milk Except for 3s, forms are highly variable.
		She poured milk IN THE CALABASH.
	Po has another form, r, which alternates with yàà/tí/t and appears with
	[-human] referents. It is very common in the expression : r xn… 'this is
	why'… It is a grammaticalization of r 'thing' which is found only in Po and
	Zoɗi, a neighbouring SBW language belonging to the Dass cluster (cf.
	Caron, 2002).
	3p /K/
	stands for k/g.
					CP	Zaar
				1s	am	mi
				2s	k	ki
				3s	ya(x)	ci
				1p	mi	mì
				2p	Kn	kì
				3p	wur	cì

2s Ny k. 2p Po kì; Ny & Lu: gn. 3s yà(x) is the most common form and is characteristic of SBW. It contrasts whith PC *si (m.) and *ta (f.). Lu has kept the original PC 3s feminine as tí 1s Lu à. 1p vowels vary: Po mù; Ny mìì; Di mì; Lu m. 2s k is uniform. 2p Ny & Lu gn; Di kn; Po kì. 3s Po & Lu yàà; Ny yáx; Di yàx. 3p Po & Di wúr; Ny wùr; Lu wù. 2s Po & Ny -k ; Lu g ; Di wuu. 2p Ny & Lu gn ; Po k ; Di un. 3s T stands for t/d which are either phonological or morphological variants. 3p Di is reduced to -r. 1s Ny gm; Di gèèmí ; Lu gèèn; Po gn. 1p Di & Lu gèèmì; Po gm; Ny gm. 2s Di gíì; Po g; Lu gèè. 2p Di gèèmí; Po gm; Lu gèèmì. NB: Ny gííg (2s) vs gíígn (2p). 3s Dy & Di gíìs; Lu gs; Po gs. 3p Lu gsn; Po gsn; Ny gíìzn; Di géèznì.

  2S.IMPF come 3S.AOR meet-1S.DO You will meet me (lit. you will come to meet me). In Ny, the verb is no longer conjugated, and r combined to a g morpheme is added to the Imperfective paradigm. In Di, k appears instead of g. Let us see the full paradigm:

	1 2	4 kàà 2S.IMPF FUT rg Po Ny nm nm You will shoot a bird. bsl shoot rop rôp	yààzl bird nyém Di róóp	Lu nm róp	Za nàmbó mbsl
	myeen wóps nantám mááx wósrmyeen wósps nantórops 10 zup 3 4 5 6 7 8 9	CP myáxken wúpséé âr k námtám kr k mwàà yààr k níkí 1p mûr k myéén wùps 1s nàmtám 2s máágà 3s nìgéé wùsséé wússéé 2p kr k 3p wûr k wùnnún vùnnèèm zúp kúsl	míígn wúps námtám ma Za máágà ka nyígé wò wússéé má ká tá áánn zup	máày wups nandam lim wottsmay tá:nta:n tókndam dzúp
	3.	Varia
	/K/ stands for a class of phonetic realisations [k/g/g//x] of a velar
	archiphoneme.
				Po	Ny	Di	Za
		gàà (Ha)	yi	tn	á knì	Kndí
		àkwai (Ha) ree	nrá	nrá	Káy
		Stabilizer	Kn	n	knì	Kn
		Neg		rà	rà	yá h	h
		Gen.Link	K	g	k	K
		VN		-t	-gn	-(tn)í	-Kn
		ACC		wú	wì	wì	-í
	ACC =accomplishment marker (cf. Ha grade 4) suffixed to the verb phrase.
		Def		-ìì	-tù	-sì	-í
		wani (Ha)	glm	gnm	gwónì	gwón
		wasu (Ha)	jílm	díìzì	jénì
		this		bgon	-tn	myéénì	gín
		these	bjen		mnjènì
		that		bgyaa	-tù	méétràà	gíí
		those	bja		mééjùràà
		here		sn	nn	èè	úúni
		there	róósak	rnûrgà	bàrtú	áni
	NB: indefinite and deictic determinants in Po and Di mark number
	agreement through palatalization. Absence of number agreement in Ny may
	be due to incomplete data.
	4.	Lexicon
	Basic vocabulary seems to be quite stable in Polci, and gives a good
	comparative basis.
			Po	Ny	Di		Lu	Za
	human	mbáàm	mbarm	mbrm	mbàrám	zaar

NB: In SBW, constituent order for the thetic particles 'here is' (Ha gàà) & 'there is' (Ha àkwai) is different from Hausa: Ha <gàà X> = Polci & Za <X Pp>; Ha <àkwai X> = Polci & Za <X Pp>. As in Hausa, the stabilizer 'it is' (Ha nee/cee) follows the NP it identifies.

  This indicates that what appears to be the TAM marker in the 3s of the perfective is in fact a topic pronoun, which is compulsory when the [+human] subject is omitted 2 . The Po Future 3s gives another corroboration:

	5 ii NEG 2S.PERF stop NEG k.Ø zler rà.
	You did not stop.
	Example (6) shows the negative 3s Perfective with the same ii occurring on
	the right of yàà.
	6 yàà 3S.TOP NEG PERF stop NEG ii Ø zler rà.
	He/she did not stop.
	7 yàà 3S.TOP come 3S.AOR meet-1S.DO r Ø pa-m
	He will meet me (lit. he will come to meet me).
	to be compared with 2s:
	8 k 2S.IMPF come 3S.AOR meet-1S.DO r k.Ø pa-m
	You will meet me (lit. you will come to meet me).
	In (

For

3s Po yàà/r : cf. Independent pronouns supra.