Alonso Silva

Hamidou Tembine

Eitan Altman

Mérouane Debbah

Optimum and equilibrium in assignment problems with congestion: mobile terminals association to base stations

The classic optimal transportation problem consists in finding the most cost-effective way of moving masses from one set of locations to another, minimizing its transportation cost. The formulation of this problem and its solution have been useful to understand various mathematical, economical, and control theory phenomena, such as, e.g., Witsenhausen's counterexample in stochastic control theory, the principal-agent problem in microeconomic theory, location and planning problems, etc. In this work, we incorporate the effect of network congestion to the optimal transportation problem and we are able to find a closed form expression for its solution. As an application of our work, we focus on the mobile association problem in cellular networks (the determination of the cells corresponding to each base station). In the continuum setting, this problem corresponds to the determination of the locations at which mobile terminals prefer to connect (by also considering the congestion they create) to a given base station rather than to other base stations. Two types of problems have been addressed: a global optimization problem for minimizing the total power needed by the mobile terminals over the whole network (global optimum), and a user optimization problem, in which each mobile terminal chooses to which base station to connect in order to minimize its own cost (user equilibrium). This work combines optimal transportation with strategic decision making to characterize both solutions.

I. INTRODUCTION

Optimal transportation problems have their origins in planning problems (e.g., optimally transporting coal from mines to steel factories). In the classic optimal transportation problem (centralized scenario), a central planner has to find some transportation plan between two nonnegative probability measures so as to minimize the average transportation cost. Such problems have been very much studied in recent years for their various applications in, for example, partial differential equations, control theory, probability theory, microeconomic theory, etc. Typical applications of these problems are optimal allocation of resources or assignment problems that are frequently met in economics as well as in engineering.

The most common cost functions considered in optimal transportation depend basically on some distance between two probability measures (Monge-Kantorovich distance, Lévy-Prokhorov metric, Wasserstein distance, total variation distance, etc.). However, in many situations the decision of which assignment to choose not only depends on the distance but it heavily depends on the congestion that the assignment generates. For example, one of many cases where this situation arises is in the mobile association problem in cellular networks. This problem is basically an assignment problem and it consists on the determination of cells corresponding to each base station of the network. In the continuum setting, this problem corresponds to the determination of the locations at which mobile terminals prefer to connect (by also considering the congestion they create) to a given base station rather than to other base stations. We consider the case where mobile terminals within a cell share the same spectrum, and consequently, mobile terminals decisions to which base station to connect affect the decision making process of other mobile terminals in the network due to network congestion. From these interactions, mobile terminals learn their optimal access point until they reach an equilibrium, where the user optimization (equilibrium) depends upon the context (type of service, bit rate, delay, etc.). Within this context, two types of problems Part of this work has been presented at the 49th IEEE Conference on Decision and Control. Alonso Silva is with UC Berkeley. Email: asilva@eecs.berkeley.edu Eitan Altman is with INRIA. Email: eitan.altman@inria.fr Hamidou Tembine and Mérouane Debbah are with Supélec. Email: Name.Surname@supelec.fr have been considered: a global optimization problem for minimizing the total power needed to satisfy a certain throughput for the mobile terminals of the network (global optimum), and a user optimization (equilibrium), in which each mobile terminal chooses to which base station to connect in order to minimize its own expected cost.

From a game theory perspective, in the decentralized scenario, the assignment problem consists on each mobile terminal (player) choosing the base station that best serve its needs. This game corresponds to an anonymous game since each player's utility depends on how many of his peers choose which strategy (in this particular case, the strategy of each player corresponds to which base station to connect). Roughly speaking, this is translated into the fact that the utility function is invariant by permutation of the index of the players. This property is sometimes referred as exchangeability or indistinguishability property.

Starting from the seminal paper of Hotelling [START_REF] Hotelling | Stability in competition[END_REF] a large area of research on location games has been developed. In [START_REF] Hotelling | Stability in competition[END_REF], the author introduced the notion of spatial competition in a duopoly situation. Plastria [START_REF] Plastria | Static competitive facility location: An overview of optimisation approaches[END_REF] presented an overview of the research on locating one or more new facilities in an environment where competing facilities already exist. Gabszewicz and Thisse [START_REF] Gabszewicz | Location[END_REF] provided another general survey on location games. Altman et al. [START_REF] Altman | Spatial SINR games combining base station placement and mobile association[END_REF] studied the duopoly situation in the uplink scenario of a cellular network where the users are placed on a line segment. The authors realized that, considering the particular cost structure that arises in the cellular context, complex cell shapes are obtained at the equilibrium. Other works incorporating congestion in optimal transportation are [START_REF] Carlier | Optimal transportation with traffic congestion and Wardrop equilibria[END_REF] and [START_REF] Crippa | Optimum and equilibrium in a transport problem with queue penalization effect[END_REF]. In [START_REF] Carlier | Optimal transportation with traffic congestion and Wardrop equilibria[END_REF], the authors incorporate the Wardrop equilibrium in a congested network by assigning probabilities to the used routes. The work of [START_REF] Crippa | Optimum and equilibrium in a transport problem with queue penalization effect[END_REF] is more related to our work where the authors consider an additive congestion cost on the objective function. Our work focuses on the additive and multiplicative congestion cost on the objective function, and the Wardrop equilibrium in the decentralized scenario. As an application of our work, we consider the mobile association problem in the downlink scenario (transmission from base stations to mobile terminals) and in a more general situation in a one-dimensional and two-dimensional scenarios without making any assumption on the symmetry of the users location. In order to do that, we propose a framework for the mobile association problem using optimal transportation (see the recent books of Villani [START_REF] Villani | Optimal transport, ser. Grundlehren der Mathematischen Wissenschaften[END_REF], [START_REF]Topics in optimal transportation[END_REF] and references therein). This theory was pioneered by Monge [START_REF] Monge | Mémoire sur la théorie des déblais et des remblais[END_REF] and Kantorovich [START_REF] Kantorovich | On the transfer of masses[END_REF] and it has been proven to be useful in many mathematical, economical, and control theory contexts (see, e.g., [START_REF] Buttazzo | A model for the optimal planning of an urban area[END_REF], [START_REF] Carlier | The structure of cities[END_REF], [START_REF]Equilibrium structure of a bidimensional asymmetric city[END_REF]). There is a number of works on "optimal transportation" (see [START_REF] Yu | Optimal transport on wireless networks[END_REF], and references therein) however the authors in [START_REF] Yu | Optimal transport on wireless networks[END_REF] consider only an optimal selection of routes but do not use the rich theory of optimal transportation. The works on stochastic geometry are similar to our analysis of wireless networks (see, e.g., [START_REF] Baccelli | Stochastic Geometry and Wireless Networks, Volume I -Theory[END_REF] and references therein) but in our case we do not consider any particular deployment distribution function. Note that the optimization aspect is not especially exploited in [START_REF] Baccelli | Stochastic Geometry and Wireless Networks, Volume I -Theory[END_REF]. Fluid models allow one to have this general deployment distribution function.

Optimal transportation is a general framework that allows one to better understand the deployment of large-scale congested networks in a more efficient way. This framework also explains the cell-formation and user distribution over the wireless network.

In summary, in the current work, we study the centralized and decentralized optimal transportation problem by incorporating the congestion that the assignment generates over the network. As an application of our work, we focus on the minimization of the total power of the network in both the centralized and decentralized mobile association problems, while maintaining a certain level of throughput for each user connected to the network (this focus can be considered as an energy-efficient objective). We propose the rich theory of optimal transportation as the main tool of modelization of these mobile association problems. Thanks to this approach, we are able to characterize these mobile associations under different policies and give illustrative examples of this technique.

The remaining of this paper is organized as follows. In Section II we give some basic concepts and results in optimal transportation. Then we incorporate the congestion in this setting and give closed form expressions for its solution. Section III outlines the problem formulation for minimizing the total power of a wireless network under quality of service constraints (to maintain a certain level of throughput for each user connected to the network). We address the problem for the downlink case. Two different policies are considered: round robin scheduling policy (also known as time fair allocation policy) and rate fair allocation policy. Round robin scheduling policy and rate fair allocation policy are studied in detail in Section IV and Section V respectively. In Section VI we study the price of anarchy or performance gap between the centralized and decentralized scenarios. In Section VII we give numerical examples for one-dimensional and two-dimensional mobile terminals deployment distribution functions. Section VIII concludes this work.

II. BASICS IN OPTIMAL TRANSPORTATION

Optimal transportation, also called theory of mass transportation, goes back to the original works by Monge in 1781 [START_REF] Monge | Mémoire sur la théorie des déblais et des remblais[END_REF], and later in 1942 by Kantorovich [START_REF] Kantorovich | On the transfer of masses[END_REF]. The work of Brenier in 1987 [START_REF] Brenier | Décomposition polaire et réarrangement monotone des champs de vecteurs[END_REF] has renewed the interest for the subject and since then many different works have been written in this topic (see e.g. the recent books of Villani [START_REF] Villani | Optimal transport, ser. Grundlehren der Mathematischen Wissenschaften[END_REF], [START_REF]Topics in optimal transportation[END_REF] and references therein).

The original problem of Monge was:

"What is the optimal way to move piles of sand to fill up given holes of the same total volume?"

New approaches to formulate and to tackle this problem have lead to applications in many different fields such as partial differential equations, microeconomics, control theory, etc. Through this work, we will see how to incorporate the network congestion in this problem and how its solution can be applied to cellular networks.

In uplink transmissions in cellular networks, we have mobile terminals sending information to base stations and we are interested to know the optimal way to "move" information from mobile terminals to base stations. As we will see, it turns out that even if both questions are quite different, they also share some similarities. Through this section we will refer to this example to fix some ideas and it will also help us to the development of the following sections.

The mathematical framework for this problem is the following: we consider a domain (connected open subset of a finite-dimensional vector space), denoted by D, two probability measures µ and ν on that domain, defined over a probability space (D, F , P).

For example, assume that the probability measure µ has a density function f , and that the probability measure ν has a density function g 1 . The density function f could represent the density function of the sandpiles in the one-dimensional space. The density function g could represent the density function of the holes in the one-dimensional space. 1 Not every probability measure has a density function. The condition to have a probability density function is that the probability measure to be absolutely continuous with respect to Lebesgue measure. A function T which relates both probability density functions is called a transport map if the following condition is satisfied:

A F (y)g(y) dy = {x∈X : T (x)∈A} F (T (x))f (x) dx, (1)
for all continuous function F , where X is the support 2 of the probability density function f and we denote this condition (following the optimal transportation notation) as

T #µ = ν. (2)
In the previous example, the transport map would be the transfer of information from location s to location t. It basically associates mobile terminals to base stations and transports information between them. The condition (1) is an equation of conservation of the information. Notice that, in communication systems there exists packet loss so in general this condition may never be satisfied, but considering an estimation of the packet loss (for example, by sending standard packets test), this condition can be satisfied by modifying the reception measure ν. If we can not obtain a good estimation of this reception measure, we can consider it in its current form as a conservative policy.

In the original problem, Monge considered that the cost of moving a commodity from position x to a position y depends on the distance |x -y|, i.e., the cost function c ≡ c(|x -y|). The cost of moving a commodity from position x through T to its new position T (x) will then be given by c(|x -T (x)|). For the global optimization problem, we need to consider the additive total cost over the network multiplied by the quantity of information that it is being transferred, which in the continuum setting will be:

Min D c(|x -T (x)|) f (x) dx such that T #µ = ν, (3)
where µ and ν are probability measures and T : D → D is an integrable function. This problem is known as Monge's problem in optimal transportation. Not only Monge's problem is a difficult problem because of the highly non-linear structure of its objective function, but it also presents several limitations in its formulation. Examples of the limitations in Monge's formulation can be found in [START_REF] Villani | Optimal transport, ser. Grundlehren der Mathematischen Wissenschaften[END_REF]. As a simple example, consider the interval D = [0, 2], the probability function µ = δ 1 (the Dirac delta function concentrated at 1) 3 and the probability function ν = 2 The support of a function f is the closure of the set of points where the function is not zero, i.e., support (f ) = {t : f (t) = 0} 3 The Dirac delta function concentrated at point a can be thought of as a function such that

δa(x) = +∞, x = a 0, x = a (4) 1 2 (δ 0 + δ 2 )
(the semisum of two Dirac delta functions one concentrated at 0 and the other one concentrated at 2). Since in Monge's formulation, there is no splitting of mass, i.e., everything that is transmitted from one location x has to go to another location T (x), this simple problem doesn't have a transport map (see Fig. 3). This limitation is due in part to the original considered problem, but as we will see this limitation is overcome in Kantorovich's formulation. Kantorovich considered another formulation of this problem in [START_REF] Kantorovich | On the transfer of masses[END_REF]. Kantorovich noticed that the problem of transportation from one location to another can be seen as "graphs of functions" (called transport plans) in the product space (See Fig. 4). The idea is to minimize the objective function over the space of graphs g = (Id×T ) in the product space. Then with the condition that each mobile terminal satisfies its uplink demand and that the information is constrained to satisfy the identity

+∞ -∞ δa(x) dx = 1. (5)
This is a heuristic definition. However the Dirac delta function can be rigorously defined either as a distribution or as a measure. For a rigorous definition, see [START_REF] Brezis | Functional analysis, Sobolev spaces and partial differential equations[END_REF].

received at the base stations, Kantorovich's problem reads

Min g∈Π(µ,ν) D×D c(x, y) dg(x, y), (6)
where

Π(µ, ν) = {g : π 1 #g = µ and π 2 #g = ν}, (7)
is denoted the ensemble of transport plans g, π 1 (x, y) stands for the projection on the first axis x, and π 2 (x, y) stands for the projection on the second axis y.

The relationship between Monge and Kantorovich problems is that every transport map T of Monge's problem determines a transport plan g T = (Id×T )#µ in Kantorovich's problem with the same cost (where Id denotes the identity). However, Kantorovich's problem considers more functions than the ones coming from Monge's problem (which can always be viewed as the product of the identity and the map T ), so we can choose from a bigger set Π(µ, ν).

Then, every solution of Kantorovich's problem is a lower bound to Monge's problem, i.e.,

Min g∈Π(µ,ν) D×D c(x, y) dg(x, y) ≤ Min T #µ=ν D c(|x -T (x)|) f (x) dx. (8)
The Theorem below provides an equivalence result between the two problems for the cost function |x -y| p , p > 1 and a continuous measure.

Theorem 2.1: Consider the cost function c(|x -y|) = |x -y| p . Let µ and ν be probability measures in D and fix p ≥ 1. We assume that µ can be written 4 as dµ = f (x) dx. Then the optimal value of Monge's problem coincides with the optimal value of Kantorovich's problem, i.e., M p (µ, ν) = W p (µ, ν) and there exists an optimal transport map from µ to ν, which is also unique almost everywhere if p > 1.

This result is very difficult to obtain and it has been proved only recently (see [START_REF] Brenier | Décomposition polaire et réarrangement monotone des champs de vecteurs[END_REF] for the case p = 2, and the references in [START_REF] Villani | Optimal transport, ser. Grundlehren der Mathematischen Wissenschaften[END_REF] for the other cases).

The case that we are interested in can be characterized because the image of the transport plan is a discrete finite set.

Thanks to optimal transport theory we are able to characterize the partitions considering general settings. To this purpose, consider locations (x 1 , y 1 ) . . . , (x K , y K ), the Euclidean distance

d i (x, y) = (x -x i ) 2 + (y -y i ) 2
, and F a continuous function. Theorem 2.2: Consider the problem

(P1) Min C i K i=1 C i F (d i (x, y)) + s i C i f (ω, z) dω dz f (x, y) dx dy, (9)
where C i is the cell partition of D. Suppose that s i are continuously differentiable, non-decreasing, and convex functions. The problem (P1) admits a solution that verifies

(S1)    C i = (x, y) : F (d i (x, y)) + s i (N i ) + N i • s ′ i (N i ) ≤ F (d j (x, y)) + s j (N j ) + N j • s ′ j (N j ) N i = C i f (ω, z) dω dz. (10)
Proof.-See Appendix A Note that the system (10) provides a fixed-point system between C i and N i , and can be interpreted as follows: the distribution of users in C i , generates the number N i and which affects the congestion term via the function s i (.), which in consequence influences the set C i . 4 The exact condition is that µ is absolutely continuous with respect to the Lebesgue measure. A probability measure µ is absolutely continuous with respect to the Lebesgue measure if the function F (x) = µ((-∞, x]) is locally an absolutely continuous real function. A function f is an absolutely continuous real function if there exists an integrable function g such that f

(x) = f (a) + x a g(t) dt
(P2) Min C i K i=1 C i F (d i (x, y)) • m i C i f (ω, z) dω dz f (x, y) dx dy, (11)
where C i is the cell partition of D. Suppose that m i are derivable. The problem (P2) admits a solution that verifies

(S2)        C i = {(x, y) : m i (N i )F (d i (x, y)) f (x, y) + U i (x, y) ≤ m j (N j )F (d j (x, y)) f (x, y) + U j (x, y)} U i = m ′ i (N i ) C i F (d i (x, y))f (x, y) dx dy N i = C i f (ω, z) dω dz. (12)
Proof.-See Appendix B

BS2

Cell Boundaries when BS1 is at 0 BE : Cell Boundaries when BS1 is at 0 vs position of BS2 Fig. 7: Wardrop Equilibrium: Thresholds determining the cell boundaries as a function of the location of the base stations. The network is deployed over the interval [-10, 10] (one-dimensional case) presented here vertically. We consider a uniform distribution of mobile terminals and we find the threshold (solid line) determining the cell boundaries as a function of the base stations positions (dotted lines) by changing the position of one of them. BS 1 is fixed at position 0 and we change the position of BS 2 from -10 to +10. Notice that in problem (P1) if the functions s i ≡ 0 the solution of the system (S1) becomes the well known Voronoi cells. In problem (P2) if we have that the functions h i ≡ 1 we find again the Voronoi cells. In general however, the Voronoi configuration is far from being optimal.

III. THE SYSTEM MODEL AND PROBLEM FORMULATION

A summary of the notation used on this work can be found in Table I. We consider a network deployed on a region, denoted by D5 , over the two-dimensional plane. The mobile terminals (MTs) are distributed

The number of mobile terminals in a sub-region of the network A ⊆ D, denoted by N(A), can be approximated by

N(A) = N A f (x, y) dx dy , ( 14
)
where N is the total number of mobile terminals in the network. The integral on the right hand side between brackets takes into account the proportion of mobile terminals distributed over the network area A. The equation 14 does not give necessarily an integer. We will take integer part (floor) if needed. Examples of mobile terminals distributions f (x, y):

1) If the mobile terminals are distributed uniformly over the network, then the probability density function of the mobile terminals is given by

f (x, y) = 1 |D| , ( 15
)
where |D| is the total area of the network. 2) If the mobile terminals are distributed according to different levels of population density, then the probability density function of the mobile terminals is given by

f (x, y) =    f HD if (x, y) is at a High Density region, f ND if (x, y) is at a Normal Density region, f LD if (x, y) is at a Low Density region, (16)
where f HD > f ND > f LD are defined similarly to equation [START_REF] Baccelli | Stochastic Geometry and Wireless Networks, Volume I -Theory[END_REF] with constants of normalization K HD , K ND , K LD , such that K HD > K ND > K LD . 3) If the mobile terminals are distributed in a circle with more mobile terminals in the center of the network area and less mobile terminals towards the boundary, then we can consider that the probability density function of the mobile terminals is given by

f (x, y) = R 2 D -(x 2 + y 2 ) K D , ( 17
)
where R D is the radius of the network and K D is a coefficient of normalization. In the network, we consider K base stations (BSs), denoted by BS i , i ∈ {1, . . . , K}, located at fixed positions (x i , y i ) , i ∈ {1, . . . , K}. We assume that the neighbouring BSs transmit their signals in orthogonal frequency bands. Furthermore, we assume that interference between BSs that are far from each other is negligible. Consequently, instead of considering the SINR (Signal to Interference plus Noise Ratio), we consider as performance measure the SNR (Signal to Noise Ratio). We consider the downlink case (transmission from base stations to mobile terminals) and assume that each BS is going to transmit only to mobile terminals associated to it. We denote by C i the set of mobiles associated to the i-th BS, and by N i the number of mobiles within that cell, i.e., the cardinal of the set C i , to be determined.

Since the probability density function of the mobile terminals f (x, y) considered in our work is general, instead of considering a particular probability density function, e.g., f (x, y), and an average throughput, e.g., θ(x, y), in each location (x, y), we can consider a constant throughput θ > 0 and redefine the distribution of mobile terminals f (x, y) as

f (x, y) := f (x, y) θ(x, y) θ . (18)
In order to do that, we notice that since f (x, y) must be a probability density function, we should impose

f (x, y) dx dy = 1. ( 19
)
This equation is equivalent to f (x, y) θ(x, y)

θ dx dy = 1. (20)
Since we are considering a constant throughput θ > 0, this equation is equivalent to

1 θ f (x, y) θ(x, y) dx dy = 1. (21)
For this equation to hold, we consider

θ := f (x, y) θ(x, y) dx dy. (22)
In consequence, the following equation holds:

f (x, y)θ = f (x, y) θ(x, y). ( 23
)
Last equation simply translates in the fact that, e.g., mobile terminals with double demand than others would be considered as two different mobile terminals with the same demand than other mobile terminals at the same location.

If the number of mobile terminals is greater than the maximum number of carriers available in the i-th cell, denoted by MAX i , we consider a penalization cost function given by

κ i (N i ) = 0 if N i ≤ MAX i , κi (N i -MAX i ) if N i > MAX i . ( 24
)
We assume that κi can be either a constant function or at least a non-decreasing function in the number of used carriers above the limit MAX i6 . We first study the case N i ≤ MAX i and we study the general case in Section V-A.

The power transmitted P T from a base station BS i to a mobile terminal located at position (x, y) is denoted by

P T i (x, y) = P i (x, y). (25)
The received power P R at a mobile terminal located at position (x, y) served by a base station BS i is given by P

R i (x, y) = P i (x, y)h i (x, y), (26)
where h i (x, y) is the channel gain between base station BS i and a mobile terminal located at position (x, y).

We shall further assume that the channel gain corresponds to the path loss given by

h i (x, y) = ( R 2 + d 2 i (x, y)) -ξ , ( 27
)
where ξ is the path loss exponent, R is the height of the base station, and d i (x, y) is the distance between a mobile terminal at position (x, y) and BS i located at (x i , y i ), i.e.,

d i (x, y) = (x i -x) 2 + (y i -y) 2 . ( 28
)
The SNR received at mobile terminals at position (x, y) in cell C i is given by

SNR i (x, y) = P i (x, y)h i (x, y) σ 2 , ( 29
)
where σ 2 is the noise power. We assume that the instantaneous mobile throughput is given by the following expression, which is based on Shannon's capacity theorem:

θ i (x, y) = log(1 + SNR i (x, y)). (30)
We want to satisfy an average throughput for mobile terminals located at position (x, y) given by θ(x, y) > 0. We shall consider for this objective two policies defined in [START_REF] Kasbekar | A hierarchical spatial game over licenced resources[END_REF]: (A) Round robin scheduling policy: where each base station devotes an equal fraction of time for transmission to each mobile terminal associated to it, and (B) Rate fair allocation policy: where each base station maintains a constant power sent to mobile terminals within its cell but modifies the fraction of time allowed to mobile terminals with different channel gains, so that the average transmission rate demand is satisfied. For more information about this type of policies in the one dimensional case, see [START_REF] Kasbekar | A hierarchical spatial game over licenced resources[END_REF].

A. Round robin scheduling policy: Global Optimization

Following this policy, a base station devotes an equal fraction of time for transmission to mobile terminals located within its cell. The set of mobile terminals associated to the i-th base station BS i , denoted by C i , and the number of mobile terminals within that cell N i (which is equal to the cardinal of the set C i ) are to be determined. Since a base station BS i divides its time of service proportional to the number of mobile terminals within its cell, then the throughput of a mobile terminal located at position (x, y) under the round robin scheduling policy is given by

θ RR i (x, y) = 1 N i θ i (x, y), (31)
where N i is the number of mobile terminals within the i-th cell and θ i (x, y) is the instantaneous mobile throughput at mobile terminals located at positions (x, y) from base station BS i . In order to satisfy an instantaneous throughput θ(x, y), we need to have

θ RR (x, y) = 1 N i θ i (x, y) ≥ θ(x, y), (32)
or equivalently, by replacing in the previous equation θ i (x, y) from equations ( 29) and (30),

1 N i log 1 + P i (x, y)h i (x, y) σ 2 ≥ θ(x, y). ( 33
)
Rewriting last equation, we obtain

P i (x, y) ≥ σ 2 h i (x, y) (2 N i θ(x,y) -1). ( 34
)
where h i (x, y) > 0. Since our objective function is to minimize the total power of the network, this constraint will be reached, and from equation ( 27) we obtain

P i (x, y) = σ 2 (2 N i θ(x,y) -1)([R 2 + d 2 i (x, y)] 1/2 ) +ξ . ( 35
)
From equation ( 35), we remark that: (a) If the number of mobile terminals increases within a cell, i.e., the base station has more mobile terminals assigned to it, the base station will need to transmit more power to each of the mobile terminals within its cell, to satisfy the throughput constraint in equation ( 32). (b) The function ([R 2 +d 2 i (x, y)] 1/2 ) +ξ on the right hand side give us the dependence of the power needed to satisfy the throughput constraint in equation ( 32) with respect to the distance between the base station and the mobile terminal located at position (x, y). Our objective is to find the optimal mobile association in order to minimize the total power of the network while maintaining the throughput constraint given by equation (32), or equivalently by equation (35). The total power of the network is equal to the sum of the power used in each cell in the network, i.e.,

P total = K i=1 P intra i , (36)
where

P intra i = C i P i (x, y)f (x, y) dx dy, (37)
P intra i
is the intracell power consumption in cell C i . The global optimization for the mobile association problem is to determine the cells C i , i ∈ {1, . . . , K}, to minimize the total power of the network:

(RR) min K i=1 C i P i (x, y)f (x, y) dx dy, (38)
subject to (35), where f (x, y) is the probability density function of the mobile terminals. We solve this problem in Section III-A.

B. Rate fair allocation policy: User Optimization

In the rate fair allocation policy, each base station will maintain a constant power sent to mobile terminals within its cell, i.e., P i (x, y) = P i for each mobile terminal at location (x, y) inside cell C i .

(39)

However, the base station modifies the fraction of time allotted to mobile terminals, set in such a way that the average transmission rate to each mobile terminal with different channel gain is the same, denoted by θ(x, y), for each mobile terminal located at position (x, y). Let r i be the fixed rate of mobile terminals located inside the cell C i . The fraction of time that a mobile terminal located at position (x, y) ∈ C i receives positive throughput is

r i log(1 + SNR i (x, y)) . ( 40
)
Then, the fixed rate r i is the solution to equation

C i r i log(1 + SNR i (x, y)) f (x, y) dx dy = β, ( 41
)
where β is the fraction of time guaranteed from the regulator to have no interference from the other BSs. Then, the rate

r i = C i 1 log(1 + SNR i (x, y)) f (x, y) dx dy -1 β. ( 42
)
We study the equilibrium states where each mobile terminal chooses the base station which will serve it, i.e., the situation where given the interactions with other mobile terminals, each mobile terminal doesn't have any incentive to unilaterally change its strategy. A similar notion of equilibrium has been studied in the context of large number of small players in road-traffic theory by Wardrop [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF]. A Wardrop equilibrium is the analog of a Nash equilibrium for the case of a large number of small players. In the following, we give an equilibrium notion that we also denote Wardrop equilibrium by analogy to the notion given in [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF].

Definition.-The Wardrop equilibrium is given in the context of cellular systems by:

If C i f (x, y) dx dy > 0, then θ i = max 1≤j≤K θ j (C j ), (43a)
else if

C i f (x, y) dx dy = 0, then θ i ≤ max 1≤j≤K θ j (C j ). (43b)
As we previously mentioned, a Wardrop equilibrium is the analog of a Nash equilibrium in the case of a large number of small players, where, in our case, we consider the mobile terminals as the small players. In this setting, the Wardrop equilibrium indicates that if there is a strictly positive proportion of mobile terminals associated to the i-th base station (the left-hand side condition in equation (43a)), then the throughput that the mobile terminals associated to the i-th base station obtain is the maximum that they would obtain from any other base station (right-hand side consequence in equation (43a)). The second condition indicates that if there is one base station that doesn't have any mobile terminal associated to it (left-hand side condition in equation (43b)), it is because the mobile terminals can obtain a higher throughput by connecting to one of the other base stations (right-hand side consequence in equation (43b)).

We assume that each base station is serving at least one mobile terminal, (if that is not the case, we could remove the base stations which are not serving any mobile terminal and find an equivalent situation). Then, the equilibrium is given by the situation when

θ 1 = θ 2 = . . . = θ K . ( 44
)
To understand this equilibrium situation, consider as an example the simple case of two base stations: BS 1 and BS 2 . Assume that the base station BS 1 offers more throughput than the base station BS 2 . Then, the mobile terminals being served by the base station BS 2 will have an incentive to connect to the base station BS 1 . From equation (35), we previously remarked that the transmitted throughput depends inversely on the number of mobile terminals connected to the base station. As more mobile terminals try to connect to base station BS 1 the throughput of each mobile terminal will diminish until arriving to the equilibrium where both base stations will offer the same throughput.

The condition given by equation ( 35) is equivalent in our setting to the condition

SNR 1 = SNR 2 = . . . = SNR K . (45)
Let us denote by β the SNR offered by the base stations at the equilibrium, i.e.,

β = SNR 1 = SNR 2 = . . . = SNR K . (46)
From equation (29) we know that

P i (x, y) = σ 2 SNR i (x, y) h i (x, y) . (47)
with h i (x, y) > 0.

At the equilibrium, from equations ( 46) and ( 29) we obtain

P i (x, y) = σ 2 β h i (x, y) . (48)
Replacing the term P i (x, y) in equation ( 37)

P intra i = C i σ 2 β h i (x, y) f (x, y) dx dy, (49)
Replacing the channel gain h i (x, y) from equation ( 27), we obtain

P intra i = β C i σ 2 ([R 2 + d 2 i (x, y)] 1/2 ) +ξ f (x, y) dx dy. (50)
We want to choose the optimal mobile assignment in order to minimize the total power of the network under the constraint that the mobile terminals have an average throughput of θ, i.e.,

Min

C i P total = K i=1 P intra i . (51)
Then our problem reads

(RF) Min C i K i=1 C i βσ 2 (R 2 + d 2 i (x, y)) ξ/2 f (x, y) dx dy. (52)
We will solve this problem in Section V. Thanks to optimal transport theory we are able to characterize the partitions considering a general setting. In the following section, we will briefly describe optimal transport theory and motivate the solution of the previously considered mobile association problems.

IV. ROUND ROBIN SCHEDULING POLICY

We assume that a service provider wants to minimize the total power of the network while maintaining a certain average throughput of θ to each mobile terminal of the system using the round robin scheduling policy given by problem

(RR) Min C i K i=1 C i σ 2 (R 2 + d i (x, y) 2 ) ξ/2 (2 N i θ -1)f (x, y) dx dy. (53)
We see that this problem is an optimal transportation problem like the one in (P1) with cost function given by

F (d i (x, y)) = σ 2 (R 2 + d i (x, y) 2 ) ξ/2 and
(54)

m i (x, y) = (2 N i θ -1). (55)
From the previous theorem, we can derive an explicit expression for this configuration.

Proposition.-There exist a unique optimum given by

C i = x 0 ∈ D : d i (x 0 , y 0 ) p + h i (N i ) + N i h ′ i (N i ) ≤ d j (x 0 , y 0 ) p + k j (N j ) + N j k ′ j (N j ), ∀j = i (56)
N i = C i f (x 0 , y 0 ) dx 0 dy 0 . (57)
Let's see a direct application of our results: Example 4.1: Consider a network of N = 2500 mobile terminals distributed according to f (x) in [0, L] (for example, with L = 5.6 miles for WiMAX radius cell). We consider two base stations at position BS 1 = 0 and BS 2 = L and R = 1. Then, the mobile association threshold (the boundary between both cells, i.e., the location at which the mobile terminals obtain the same throughput by connecting to any of both base stations) is reduced to find x such that the following equality holds:

(2 N 1 θ -1)(1 + x 2 )f (x) + 2 N 1 θ θ log 2 x + x 3 3 = (2 N 2 θ -1)(1 + (1 -x) 2 )f (x) + 2 N 2 θ θ log 2 4 3 -2x + x 2 - x 3 3 (58)
Notice that this is a fixed point equation on x. If the mobile terminals are distributed uniformly, the optimal solution is given by

C 1 = [0, 1/2 L) and C 2 = [1/2 L, L],
which is the solution that Voronoi cells would give us and in that case the number of mobile terminals connected to each base station would be given by

N 1 = N 2 = 1250. (59)
However, if the deployment distribution of the mobile terminals is more concentrated near BS 2 than BS 1 , consider for example f (x) = 2x, the optimal solution is given by C 1 = [0, q) and C 2 = [q, L] with q = 0.6027 L and N 1 = 908 and N 2 = 1592.

Notice that in the global optimization solution, the number of mobile terminals connected to BS 1 is smaller that the number of mobile terminals connected to BS 2 . However, the cell size is bigger.

V. RATE FAIR ALLOCATION POLICY In this framework, we give the possibility to mobile terminals to associate to the base station they prefer in order to minimize their power cost function while maintaining, as quality of service measurement, an average throughput of θ.

As we presented in Section III, this problem is equivalent to

(RF) Min C i K i=1 C i σ 2 (R 2 + d 2 i (x, y)) ξ/2 f (x, y) dx dy. (61)
Notice that this problem is equivalent to (P1) where the functions

F (d i (x, y)) = σ 2 (R 2 + d i (x, y) 2 ) ξ/2 , (62)
and s i ≡ 1. The problem has then a solution given by Proposition.-There exist a unique optimum given by

C i = x ∈ D : σ 2 (R 2 + d 2 i (x 0 , y 0 )) ξ/2 ≤ σ 2 (R 2 + d 2 j (x 0 , y 0 )) ξ/2 , ∀j = i N i = C i f (x 0 , y 0 ) dx 0 dy 0 , (63)
which is represented by the Voronoi cells.

BS2

Cell Boundaries when BS1 is at 0 BE : Cell Boundaries when BS1 is at 0 vs position of BS2 Fig. 10: Wardrop Equilibrium in the Non-homogeneous case: The network is deployed over the interval [-10, 10] (one-dimensional case) presented here vertically. We find the threshold (solid line) determining the cell boundaries as a function of the base stations positions (dotted lines) by changing the position of one of them. BS 1 is fixed at position 0 and we change the position of BS 2 from -10 to +10. The deployment distribution of the mobile terminals is given by f (x) = (Lx)/2L 2 .

A. Penalization function

Notice that the penalization function or the case when the number of mobile terminals is greater than the number of carriers available in the cell in the rate fair allocation policy case is equivalent to (P1) where the functions

F (d i (x, y)) = σ 2 (R 2 + d i (x, y) 2 ) ξ/2 . ( 64
)
s i (N i ) = κ i (N i ) = 0 if N i ≤ MAX i , κi (N i -MAX i ) if N i > MAX i . ( 65
)
The problem has then a solution given by Proposition.-There exist a unique optimum given by

   C i = (x, y) : σ 2 (R 2 + d 2 i (x 0 , y 0 )) ξ/2 + s i (N i ) + N i • s ′ i (N i ) ≤ σ 2 (R 2 + d 2 i (x 0 , y 0 )) ξ/2 + s j (N j ) + N j • s ′ j (N j ) N i = C i f (ω, z) dω dz. (66)
VI. PERFORMANCE GAP As a second example consider again the case when the mobile terminals are uniformly distributed on D = [0, 1] but this time the two antennas are located at coordinates x 1 = 0 and x 2 = 1. Consider the case when p = 1 and s 1 (x) = 100 and s 2 (x) = 0 for 0 ≤ x ≤ 0.999 1 for 0.999 ≤ x ≤ 1.

Then the equilibrium cell configuration

(C E 1 , C E 2 ) is given by C E 1 = ∅ and C E 2 = [0, 1]
, and the optimum cell configuration

(C * 1 , C * 2 ) is C * 1 = [0, 001[ and C * 2 =]0.001, 1
]. The optimum is very unfair for mobile terminals living in the first cell C * 1 , who pay x + 100, whereas the other mobile terminals just pay the distance from 1. This is a toy example but it gives an idea of the performance gap between the centralized and the decentralized scenarios, also known as Price of Anarchy.

VII. NUMERICAL SIMULATIONS

In this section, we present several numerical results that validate our theoretical model.

A. One-dimensional case

We first consider the one-dimensional case and we consider a uniform distribution of mobile terminals in the interval [-10, 10]. We set the noise parameter σ = 0.3. In Fig. 7, we fix one base station BS 2 at position 0 and take as parameter the position of base station BS 1 . We consider as path loss exponent ξ = 2. Red lines shows the positions of the BSs. We are able to determine the cell boundary (solid blue curve) from BS 1 and BS 2 at different positions. In Fig. 11, we fix two base stations BS 1 = -10 and BS 2 = 10 and we take as parameter the position of base station BS 3 . Red lines shows the positions of the BSs. We determine the cell boundary (solid blue curve) from BS 1 and BS 3 and the cell boundary (dotted blue curve) from BS 2 and BS 3 .

B. Two-dimensional case: Uniform and Non-Uniform distribution of mobile terminals

We consider the two-dimensional case. We consider the square [-4, 4] × [-4, 4] and the noise parameter σ = 0.3. We set five base stations at positions BS 1 = (-3, -3), BS 2 = (3, -3), BS 3 = (-3, 3), BS 4 = (3, 3), and BS 5 = (0, 0). We determine the cell boundaries for the uniform distribution of mobile terminals (see Fig. 13) and we compare it to the cell boundaries for the non-uniform distribution of mobile terminals given by f (x, y) = (L 2 -(x 2 + y 2 ))/K where K is a normalization factor. The latter situation can be interpreted as the situation when mobile terminals are more concentrated in the center and less concentrated in suburban areas as in Paris, New York or London. We observe that the cell size of the base -4, 4]. We set the noise parameter σ = 0.3 and we set four BSs at positions BS 1 = (-3, -3) BS 2 = (3, -3) BS 3 = (3, 3) BS 4 = (-3, 3) and one at the origin BS 5 = (0, 0). We determine the cell boundaries (deep lines) for the non-uniform distribution of mobile terminals given by f (x, y) = (L 2 -(x 2 + y 2 ))/K where K is a normalization factor. The latter situation takes into account when mobile terminals are more concentrated in the center and less concentrated in suburban areas.

station BS 5 at the center is smaller than the others at the suburban areas. This can be explained by the fact that as the density of mobile terminals is more concentrated in the center the interference is greater in the center than in the suburban areas and then the SINR is smaller in the center. However the quantity of mobile terminals is greater than in the suburban areas.

VIII. CONCLUSIONS AND FUTURE PERSPECTIVES

In the present work, we have studied the mobile association problem in the downlink scenario. The objective is to determine the spatial locations at which mobile terminals would prefer to connect to a given base station rather than to other base stations in the network if they were offered that possibility (denoted decentralized scenario). We are also interested in the spatial locations which are more convenient from a centralized or from a network operator point of view. In both approaches, the optimality depends upon the context. In the considered cases, we consider the minimization of the total power of the network, which can be considered as an energy-efficient objective, while maintaining a certain level of throughput for each user connected to the network. We have proposed a new approach using optimal transport theory for this mobile association problems and we have been able to characterize these mobile associations under different policies.

The present work can be extended in several different directions. One of these possible directions is to study the price of anarchy between the centralized and decentralized scenario. As we presented in Section VI, the considered example give us an indication that the price of anarchy should be unbounded but currently we don't have precise bounds. The price of anarchy should be studied in both scenarios: the sum of a function and the multiplication. It should be interesting to study the application in the particular case when the network is an LTE network. Since our model is quite simplified in order to obtain exact solutions we could include the cases for the fading and shadowing effects. It is implicitly considered that the number of mobile terminals in the network is stationary, but since at different times of the day there are different number of mobile terminals, this management capabilities should be taken into account.

From Theorem 2.1, we deduce that The function F : S → R defined by F (c 1 , . . . , c k ) = W p p µ, k i=1 c i δ x i is continuous and convex. If the functions s i are lower semi-continuous, then there exists an optimum and if in addition the maps η i (t) := th i (t) are strictly convex, the optimum is unique.

We can then characterize the solution. If (A i ) i=1,...,k is an optimum, and s i are differentiable in ]0, 1] and continuous in 0, then the following holds:

C i = x ∈ D : |x -x i | p + s i (N i ) + N i s ′ i (N i )
≤ |xx j | p + s j (N j ) + N j s ′ j (N j ), ∀j = i (76)

N i = C i f (x) dx. ( 77
)
APPENDIX B Consider the problem (P2)

Min C i K i=1 C i F (d i (x, y)) • m i C i f (ω, z) dω dz • f (x, y) dx dy, (78)
where C i is the cell partition of D. Suppose that m i are derivable. The problem (P2) admits a solution that verifies (79)

Proof.-The proof is similar to Appendix A. The problem (P2) can be rewriten as follows:

inf W c i f dx, k i=1 c i δ x i : c i ≥ 0, k i=1 c i = 1 , (80)
where

W c i f dx, k i=1 c i δ x i = inf (A i ) k i=1 k i=1 A i F (|x -x i |) • m i (c i )f (x) dx : A i f dx = c i , (A i ) k i=1 partition de D .
(81) Let γ be optimal for Monge-Kantorovich problem, then one can consider

γ(x, y) = k i=1 γ i (x) ⊗ δ x i (y), c i = γ i (D), (82)
where γ i is a positive measure such that γ i ≤ f dx The function F : S → R defined by F (c 1 , . . . , c k ) = W p p µ, k i=1 c i δ x i is lower semi-continuous. Then there exists a solution and it is unique almost surely.

Let (c i ) k i=1 be a solution of (P2) and (A i ) k i=1 the associated optimal partition. Let us fix two indices i 0 , j 0 and a point x 0 ∈ A i 0 . Let ε ≥ 0. Let us consider the open ball of radius ε and center x 0 that we denote as B ǫ . We denote its measure as c ǫ . We make a small variation of the optimal partition by taking from A i 0 the ball B ǫ and adding it to A j 0 . Since the partition (A i ) k i=1 is optimal then

A i 0 F (|x -x i 0 |)h i 0 (c i 0 )f (x) dx + A j 0 F (|x -x j 0 |)h j 0 (c j 0 )f (x) dx ≤ A i 0 \Bǫ F (|x -x i 0 |)h i 0 (c i 0 -c ǫ )f (x) dx + A j 0 ∪Bε F (|x -x j 0 |)h j 0 (c j 0 + c ε )f (x) dx, (83)
which is equivalent to

A i 0 F (|x -x i 0 |)(h i 0 (c i 0 ) -h i 0 (c i 0 -c ǫ ))f (x) dx + Bǫ F (|x -x i 0 |)h i 0 (c i 0 -c ǫ )f (x) dx ≤ A j 0 F (|x -x i 0 |)(h j 0 (c j 0 + c ǫ ) -h j 0 (c j 0 ))f (x) dx + Bε F (|x -x j 0 |)h j 0 (c j 0 + c ε )f (x) dx. ( 84
)
Dividing the previous equation by c ǫ and taking the limit when ǫ → 0, we obtain

A i 0 F (|x -x i 0 |)h ′ i 0 (c i 0 )f (x) dx + F (|x -x i 0 |)h i 0 (c i 0 )f (x 0 ) ≤ A j 0 F (|x -x j 0 |)h ′ j 0 (c j 0 )f (x) dx + F (|x -x j 0 |)h j 0 (c j 0 )f (x 0 ). (85)
Reorganizing the terms we obtain the desired result.

Fig. 1 :

 1 Fig. 1: Monge's problem.

Fig. 2 :

 2 Fig. 2: Monge's problem can not model a simple scenario of two mobile terminals and one base station. Kantorovich's problem however can model very general scenarios.

Fig. 3 :

 3 Fig. 3: Monge's problem can not model a simple scenario of two mobile terminals and one base station. Kantorovich's problem however can model very general scenarios.

Fig. 4 :

 4 Fig. 4: Kantorovich considered "graphs" where the projection in the first axis coincide with the mobile terminal position (MT 1 = 3.5, MT 2 = 5 and MT 3 = 6.5) and the second axis coincides with the base station position (BS 1 = 4 and BS 2 = 6).

10 Fig. 5 :

 105 Fig. 5: Interference as a function of location of mobile terminals when BS 1 is at position 0 (solid line) and BS 2 at -10 (dotted line).

10 Fig. 6 :

 106 Fig.6: SINR as a function of location of mobile terminals when BS 1 is at position 0 (solid line) and BS 2 at -10 (dotted line).

Fig. 8 :

 8 Fig.8: Worst Equilibrium: Thresholds determining the cell boundaries (vertical axis) that give the worst equilibrium in terms of the SINR as a function of the location of BS 2 for BS 1 at position 0.

N

  Total number of mobile terminals in the network K Total number of BSs f Deployment distribution of mobile terminals (xi, yi) Position of the i-th BS Ci Cell determined by the i-th BS Ni Number of mobile terminals associated to the i-th BS MAXi Number of carriers offered by the i-th BS κi Penalization function of non-service hi Channel gain function in the i-th cell ξi Path loss exponent in the i-th cell according to a given probability density function f (x, y). The proportion of mobile terminals in the sub-region A ⊆ D is given by A f (x, y) dx dy.

Fig. 9 :

 9 Fig.9: Thresholds determining the cell boundaries (vertical axis) of the best equilibrium in terms of the SINR as a function of the location of BS2 for BS1 at position 0 when we consider a non-homogeneous distribution given by f (x) = (L-x)/2L 2 . Example: equilibrium when then distribution of mobile terminals is given by f (x) = 2x in the interval [0, L] and the positions of the base stations are BS 1 = 0 and BS 2 = L.

  Fig. 11: Wardrop Equilibrium with Multiple Base Stations: The grid area network is the interval [-10, 10]presented here vertically. We consider a uniform distribution of mobile terminals. We find the threshold (solid and dashed lines) determining the cell boundaries as a function of the base stations positions (dotted lines) by changing the position of one of them. BS 1 is fixed at position -10 and BS 2 is fixed at position 10 and we change the position of BS 3 from -10 to +10.

Fig. 12 :

 12 Fig. 12: Wardrop Equilibrium in the 2D case: The grid area network is the square [-4, 4] ×[-4, 4]. We set the noise parameter σ = 0.3 and we set four BSs at positions BS 1 = (-3, -3) BS 2 = (3, -3) BS 3 = (3, 3) BS 4 = (-3, 3) and one at the origin BS 5 = (0, 0). We determine the cell boundaries (deep lines) for the uniform distribution of mobile terminals

Fig. 13 :

 13 Fig. 13: 2D case: Cell contours of the best equilibrium with uniform distribution of mobile terminals.

Fig. 14 :

 14 Fig. 14: Wardrop Equilibrium in 2D Non-Uniform Case: The grid area network is the square [-4, 4] × [-4, 4]. We set the noise parameter σ = 0.3 and we set four BSs at positions BS 1= (-3, -3) BS 2 = (3, -3) BS 3 = (3, 3) BS 4 = (-3, 3) and one at the origin BS 5 = (0, 0). We determine the cell boundaries (deep lines) for the non-uniform distribution of mobile terminals given by f (x, y) = (L 2 -(x 2 + y 2 ))/K where K is a normalization factor. The latter situation takes into account when mobile terminals are more concentrated in the center and less concentrated in suburban areas.

Fig. 15 :

 15 Fig. 15: 2D Non-Uniform: Cell contours of the best equilibrium with non-uniform distribution of mobile terminals.

inf(

  Ai) i∈{1,...,k} partition of D k i=1 Ai |xx i | p + s i Ai f (x) dx f (x) dx = inf c∈S

C

  i = {x : m i (N i )F (d i (x, y)) f (x, y) + U i (x, y) ≤ m j (N j )F (d j (x, y)) f (x, y) + U j (x, y)} U i = m ′ i (N i ) C i F (d i (x, y))f (x, y) dx dy N i = C i f (ω, z) dω dz.

TABLE I :

 I Notation

The domain D is considered bounded.

For example, the maximum number of possible carriers in WiMAX is around 2048, so by using this technology we have MAXi = 2048.

ACKNOWLEDGEMENTS

The authors would like to warmly thank Chloé Jimenez from Université de Brest for interesting discussions. The last author was partially supported by Alcatel-Lucent within the Alcatel-Lucent Chair in Flexible Radio at Supélec.

APPENDIX A Consider the problem (P1)

where C i is the cell partition of D. Suppose that s i are continuously differentiable, non-decreasing, and convex functions. The problem (P1) admits a solution that verifies

Proof.-The proof is based on Proposition 3.5 of Crippa et al. [START_REF] Crippa | Optimum and equilibrium in a transport problem with queue penalization effect[END_REF]. We include the proof for completeness and because part of it (mainly the existence of the solution) will be used in the proof of the following theorem. Notice that we have considered the case F (d i (x, y)) = |(x, y) -(x i , y i )| p , but this holds for any continuous function F .

From Section II, let us recall that Monge's problem can be stated as follows: given two probability measures, µ and ν, and a constant p ≥ 1 we consider the minimization problem (denoted by M p (µ, ν)):

The relaxed formulation of Monge's problem (denoted by W p (µ, ν)) can be stated as follows

where Π(µ, ν) is the set of probability measures such that π 1 (γ) = µ and π 2 (γ) = ν where π 1 is the projection on the first component and π 2 is the projection on the second component.

If the probability measure µ can be written as dµ = f (x) dx (i.e. it is absolutely continuous with respect to the Lebesgue measure), then the optimal values of both problems coincide M p (µ, ν) = W F (µ, ν), and there exists an optimal transport map from µ to ν which is unique f -a.e. if p > 1. Another important characteristic of this relaxation is that it admits a dual formulation:

Moreover, there exists an optimal pair (u, v) for this dual formulation, and when ν is an atomic probability measure (it can be written as ν = i∈N b i δ y i ) the dual formulation becomes

.

(72) There exists another interesting characteristic when one of the measures is absolutely continuous with respect to the Lebesgue measure and the other measure is an atomic measure. If the probability measure µ can be written as dµ = f (x) dx where f is a nonnegative function, (y i ) i∈N is a sequence of points in the domain D such that ν = i∈N b i δ y i , (B i ) i∈N is a partition of the domain such that the map T (x) = i∈N y i 1 B i (x) is an optimal transport map from µ to ν, the pair (u, v) is a solution of the dual formulation (71), then

We also have a similar converse characteristic.

, and there exists two functions u ∈ L 1 µ (D), v ∈ L 1 ν (D) satisfying the condition (73), then T is optimal for M p (µ, ν) and the pair (u, v) is optimal for the dual formulation (71).

In order to prove the existence and uniqueness of the solution we need to consider the following: We denote by S the unit simplex in R k :

(74)


Olivier Roux

Vivien Rossi

Régis Céréghino

Arthur Compin

Jean-Michel Martin

Alain Dejean
email: alain.dejean@wanadoo.fr

How to coexist with fire ants: The roles of behaviour and cuticular compounds

Keywords:

Because territoriality is energetically costly, territorial animals frequently respond less aggressively to neighbours than to strangers, a reaction known as the "dear enemy phenomenon" (DEP). The contrary, the "nasty neighbour effect" (NNE), occurs mainly for group-living species defending resource-based territories. We studied the relationships between supercolonies of the pest fire ant Solenopsis saevissima and eight ant species able to live in the vicinity of its nests plus Eciton burchellii, an army ant predator of other ants. The workers from all of the eight ant species behaved submissively when confronted with S. saevissima (dominant) individuals, whereas the contrary was never true. Yet, S. saevissima were submissive towards E. burchellii workers. Both DEP and NNE were observed for the eight ant species, with submissive behaviours less frequent in the case of DEP. To distinguish what is due to chemical cues from what can be attributed to behaviour, we extracted cuticular compounds from all of the nine ant species compared and transferred them onto a number of S. saevissima workers that were then confronted with untreated conspecifics. The cuticular compounds from three species, particularly E. burchellii, triggered greater aggressiveness by S. saevissima workers, while those from the other species did not.

Introduction

The territoriality of a species is regulated by the cost of defending a territory from both neighbours and "strangers" (i.e., individuals from distant territories) and by benefits that can include access to resources such as food and nesting sites. Strangers can represent the greatest threat as they might seek to take the territory from the current holders, while neighbours already possess a territory and so have less to gain from engaging in conflict. This result in less aggressive responses towards neighbours than towards strangers which is known as the "dear enemy phenomenon" (DEP) [START_REF] Fisher | Evolution and bird sociality[END_REF][START_REF] Temeles | The role of neighbours in territorial systems: when are they "dear enemies[END_REF]. Yet, the opposite of DEP, or the "nasty neighbour effect" (NNE) with greater aggressiveness towards neighbours than towards strangers, occurs particularly for group-living species defending resource-based territories [START_REF] Müller | Nasty neighbours' rather than 'dear enemies' in a social carnivore[END_REF].

Both DEP and NNE have been noted in ants [START_REF] Temeles | The role of neighbours in territorial systems: when are they "dear enemies[END_REF] whose recognition of colony mates and rejection of aliens is based on the chemical cues (CCs) encoded in a complex mixture of low-volatile cuticular hydrocarbons that constitute a genetically determined "colony odour". The latter can be influenced by environmental factors such as diet and nesting material (d'Ettorre and Lenoir, 2010). DEP, which limits the escalation of fighting during the frequent encounters between homo-and heterospecific neighbours, is based on habituation related to learning the colony odour of encountered individuals and/or their behaviour [START_REF] Jutsum | Intra-specific aggression in the leaf-cutting ant Acromyrmex octospinosus[END_REF][START_REF] Heinze | Apparent dear-enemy phenomenon and environment-based recognition cues in the ant Leptothorax nylanderi[END_REF][START_REF] Dimarco | Dear enemy phenomenon in the leaf-cutting ant Acromyrmex lobicornis: behavioral and genetic evidence[END_REF][START_REF] Pirk | Intranest relatedness and nestmate recognition in the meadow ant Formica pratensis (R.)[END_REF]. NNE, noted intra-and interspecifically, can occur when an alien ant from a species representing a particularly high level of threat belonging to a neighbouring colony is perceived as the vanguard of a competitive force. This leads to a higher level of aggressiveness than for a stranger [START_REF] Knaden | Nest defense and conspecific enemy recognition in the desert ant Cataglyphis fortis[END_REF][START_REF] Sanada-Morimura | Encounter-induced hostility to neighbors in the ant Pristomyrmex pungens[END_REF][START_REF] Boulay | Intraspecific competition in the ant Camponotus cruentatus: should we expect the 'dear enemy' effect?[END_REF][START_REF] Thomas | Contact between supercolonies elevates aggression in Argentine ants[END_REF][START_REF] Van Wilgenburg | The influence of relatedness, neighbourhood and overall distance on colony mate recognition in a polydomous ant[END_REF][START_REF] Newey | Weaver ants Oecophylla smaragdina encounter nasty neighbors rather than dear enemies[END_REF]. Escalating conflicts leading to injury or death are limited through avoidance, ritualized fights or when ant species with different rhythms of activity share food sources [START_REF] Hölldobler | The Ants[END_REF][START_REF] Orivel | Ant activity rhythms in a pioneer vegetal formation of French Guiana (Hymenoptera: Formicidae)[END_REF][START_REF] Van Wilgenburg | Conflict resolution strategies in meat ants (Iridomyrmex purpureus): ritualised displays versus lethal fighting[END_REF]. Also, by frequently displaying submissive behaviour or feigning death (thanatosis), dominated workers from species coexisting with very aggressive dominant ants suffer only brief and less harmful attacks [START_REF] Langen | The red and the black: habituation and the dear-enemy phenomenon in two desert Pheidole ants[END_REF][START_REF] Grangier | Coexistence between Cyphomyrmex ants and dominant populations of Wasmannia auropunctata[END_REF][START_REF] Abril | Ascertaining key factors behind the coexistence of the native ant species Plagiolepis pygmaea with the invasive Argentine ant Linepithema humile (Hymenoptera: Formicidae)[END_REF][START_REF] Menzel | Behavioural and chemical mechanisms behind a Mediterranean ant-ant association[END_REF].

As opposed to typical, multicolonial ant species with "closed" colonies, "unicolonial" invasive species are "ecologically dominant" (i.e., both numerically and behaviourally dominant) and develop "open" supercolonies extending over hundreds of kilometres in their introduced range [START_REF] Hölldobler | The Ants[END_REF][START_REF] Davidson | Resource discovery versus resource domination in ants: a functional mechanism for breaking the trade-off[END_REF][START_REF] Holway | The causes and consequences of ant invasions[END_REF]. Intraspecific aggressiveness occurs along the border between the territories of two supercolonies because here, too, outsiders are distinguished from colony mates through CCs [START_REF] Thomas | Contact between supercolonies elevates aggression in Argentine ants[END_REF]Moffett, 2012a). Certain of these species also present the supercolony syndrome in their native range, but here the expansion of their territories is much lower due to intra-and interspecific competition [START_REF] Orivel | Ecologically heterogeneous populations of the invasive ant Wasmannia auropunctata within its native and introduced ranges[END_REF][START_REF] Fournier | Genetic structure, nestmate recognition and behaviour of two cryptic species of the invasive big-headed ant Pheidole megacephala[END_REF]Moffett, 2012a,b).

In this study, we focused on the relationships between the red fire ant Solenopsis saevissima (Smith) and its sympatric ant species in forest edges in French Guiana, a part of its native range that extends from Suriname to northern Amazonia. This species belongs to an assemblage of recently diverged taxa, including the wellknown invasive fire ants S. invicta (Buren), S. richteri (Forel) and Solenopsis geminata (Fabricius) [START_REF] Ross | Species delimitations: a case study in a problematic ant taxon[END_REF]. It has been little studied although considered a major pest in human-disturbed areas of its native range where it forms supercolonies that displace other ant species [START_REF] Trager | A revision of the fire ants, Solenopsis geminata group (Hymenoptera: Formicidae: Myrmicinae)[END_REF][START_REF] Taber | Fire Ants[END_REF][START_REF] Martin | A type of unicoloniality within the native range of the fire ant Solenopsis saevissima[END_REF]). Yet, still other species resist, competing for food and/or nesting sites. Moreover, S. saevissima is, like many ant species in the Neotropics, under predation pressure from the army ant Eciton burchellii (Westwood) [START_REF] Gotwald | Army ants[END_REF].

The aim of this study was to identify how workers from certain ant species are able to coexist with S. saevissima supercolonies. We hypothesized that during encounters between S. saevissima and workers from these ant species, DEP or NNE can occur along with submissive behaviour. We investigated this question through confrontation tests between S. saevissima workers and those from sympatric species and by manipulating the ants' CCs (see [START_REF] Roux | A non-lethal water-based removal-reapplication technique for behavioral analysis of cuticular compounds of ants[END_REF]. We also conducted confrontations using the army ant E. burchellii because it is prevalent in French Guiana [START_REF] Delabie | Ants as biological indicators of Wayana Amerindians land use in French Guiana[END_REF] and has been successfully observed raiding S. saevissima colonies.

Methods

Sampling S. saevissima and other ant species

This study was conducted in French Guiana between March and June 2007. The ants were collected from forest edges near Petit Saut (4 • 59 ′ N; 53 • 08 ′ W) and the city of Sinnamary (5 • 22 ′ N; 52 • 57 ′ W) corresponding to parts of the territories of two different S. saevissima supercolonies. Supercolony "A" extended over 54 km from Petit Saut to Paracou (05 • 16 ′ N; 52 • 55 ′ W), while supercolony "B" extended from Paracou to Sinnamary [START_REF] Martin | A type of unicoloniality within the native range of the fire ant Solenopsis saevissima[END_REF].

During studies related to the breadth of the S. saevissima supercolonies [START_REF] Martin | A type of unicoloniality within the native range of the fire ant Solenopsis saevissima[END_REF], we noted that only eight ant species nest within a radius of 3 m from a S. saevissima nest, namely: Atta sexdens (Linnaeus), Crematogaster tenuicula (Forel), Pheidole fallax (Mayr), S. geminata (Fabricius) and Wasmannia auropunctata (Roger) (all Myrmicinae); Camponotus melanoticus (Emery) and Camponotus blandus (Smith) (both Formicinae); and Dorymyrmex pyramicus guianensis (Santschi) (a Dolichoderinae). A. sexdens, frequent along roads and tracks, is a leaf-cutting, fungus-growing species that, therefore, competes with S. saevissima only for nesting space, while other species compete for both nesting space and food.

To collect individuals from the S. saevissima colonies, we used a shovel to gather the upper parts of the mound-shaped nests. For the other species, we first located the nests or the nest entrances that were within a ca. 3 m radius from a S. saevissima mound, and then we again used a shovel to gather the ants. Because we gathered them the day before the confrontation tests, we put them and the earth into several large plastic boxes whose walls were coated with Fluon ® to prevent the workers from climbing out and then placed two small test-tubes in each box, one of which contained cotton imbibed with water and the other cotton imbibed with honey. The plastic boxes were then transported to the laboratory. We left the ants overnight to allow them to calm down prior to the experiments.

E. burchellii is prevalent in the area studied [START_REF] Delabie | Ants as biological indicators of Wayana Amerindians land use in French Guiana[END_REF]) and able to attack S. saevissima (J-MM, AD, pers. com.). We followed columns at dusk that had foraged within the range of the S. saevissima supercolonies until we located the bivouac and then proceeded in the same manner as above. Using a shovel, we gathered part of the workers as well as some of the ground around the bivouac. We then put the earth and the ants into large plastic boxes whose walls were coated with Fluon ® and placed a small test-tube containing cotton imbibed with water into each plastic box.

Confrontations between S. saevissima workers and those from the other ant species

Our aim was to determine if the relationships between S. saevissima workers from each supercolony and the neighbours and strangers collected from the eight species able to nest in its vicinity were based on DEP or on NNE. The experiments were set up so that S. saevissima supercolony A served as a reference (the colonies from the eight other species situated within a radius of 3 m from its nests are "neighbours"), while supercolony B served as a reservoir of "strangers" for the first 30 confrontation tests (the colonies from the eight other species situated within a radius of 3 m from its nests are "strangers" for the S. saevissima workers from supercolony A). The contrary set up was used for the 30 other tests (60 tests in each case). Note that for each of these eight species, workers were taken from six different nests situated in the vicinity of six different S. saevissima mounds (10 workers tested for each S. saevissima mound).

We employed the standard behavioural tests commonly used in studies dealing with the relationships between ant individuals whether they are conspecific or not [START_REF] Suarez | Behavioral and genetic differentiation between native and introduced populations of the Argentine ant[END_REF][START_REF] Tsutsui | Genetic diversity asymmetrical aggression, and cooperation in a widespread invasive species[END_REF]. Two workers were placed together for 5 min in a neutral arena (a Petri dish; 60 mm in diameter and 20 mm deep) whose walls were previously coated with Fluon ® . Each worker was used only once. We observed the interactions and scored them as follows: 1 = antennal contact (physical contact without an aggressive response; may include trophallaxis), 2 = retreat (brief contact inducing a sudden U-turn and one or both of the ants quickly running away; the confronted individual is likely recognized as a non-colony mate), 3 = aggressiveness (brief biting by one or both of the workers; may include jerking and opening the mandibles), and 4 = fighting (prolonged aggressiveness, including prolonged biting and stinging or venom spraying) (see Fig. 1). Each time, we noted the maximal level reached (regardless of the species). The species retreating (level 2) or initiating the aggressive acts (levels 3 and 4) was also noted. All of the possible dyadic interactions between S. saevissima and the eight ant species able to nest in its vicinity were examined (16 kinds of confrontations). In addition, we set up confrontations between S. saevissima and E. burchellii workers. E. burchellii can neither be considered a neighbour nor a stranger due to the nomadic behaviour of the species [START_REF] Gotwald | Army ants[END_REF]. Control confrontations were set up between S. saevissima nestmates (taken from the nests of supercolony A for 30 cases and supercolony B for the 30 remaining cases) as well as between "strangers" (one taken from a nest of supercolony A, the other from supercolony B).

Furthermore, during these experiments, each time we noted what worker displayed any clearly submissive behaviour (i.e., an all or nothing response: a curled-up position with the legs and antennae folded back against the body, thanatosis; see Fig. 1) and recorded the number of interactions that resulted in at least one submissive behaviour.

The species were defined as responding according to DEP when the level of aggressiveness was lower during confrontations between neighbours than between "strangers" (non-neighbours). Conversely, species were defined as responding according to NNE when the level of aggressiveness was higher in interactions between neighbours than between "strangers".

Testing the effect of semiochemicals from sympatric ant species on the behaviour of S. saevissima workers

To suppress the behavioural component of the responses in the above-mentioned experiments, we set up confrontations between pairs of S. saevissima workers, one of which was "made-up" with CCs taken from heterospecific workers belonging to colonies situated within a 3 m radius from a S. saevissima mound. The "make-up" was created using a water-based method consisting in emulsifying the CCs of workers from the other ant species and applying them onto the cuticle of the S. saevissima workers after the latter were themselves rinsed with water to reduce the quantity of their own CCs (the details concerning Ca. blandus are provided in [START_REF] Roux | A non-lethal water-based removal-reapplication technique for behavioral analysis of cuticular compounds of ants[END_REF]. About 70 individuals from each species were rinsed separately in a 30 mL glass vial containing 20 mL of ultra pure water (at room temperature or ca. 27 • C) and vigorously shaken by hand for 5 min with the aim of emulsifying the CCs. The ants were then removed. To apply the CC emulsion (i.e., the "make-up"), we used S. saevissima workers having undergone a similar treatment as above, but they were then placed into glass containers whose floor was lined with absorbent paper on which they dried. These rinsed workers were then placed directly into the CC emulsion obtained from one of the neighbour ant species, shaken for 10 s, and then left in the emulsion for 5 min. They were then removed and returned to a glass container where they again dried for 30 min before the behavioural confrontations were conducted.

Note that this method is possible because many ground-nesting ant species are adapted to flooding and do not drown when they are immersed [START_REF] Mlot | Fire ants self-assemble into waterproof rafts to survive floods[END_REF] and because ants are able to discriminate the presence of low levels of heterocolonial cuticular hydrocarbons [START_REF] Ichinose | Hydocarbons detection levels in ants[END_REF]. This permitted us to investigate if the CCs from the tested ant species can influence the behaviour of S. saevissima workers during confrontations between two strangers that usually result in a high level of aggressiveness.

Two types of confrontations were conducted in order to determine if some CCs can reduce or, on the contrary, increase the aggressiveness of S. saevissima workers.

First, to search for the CCs potentially responsible for low aggressive responses, we set up 60 confrontations between two S. saevissima workers from different supercolonies (strangers), one of them being untreated, the other being "made-up". The first control tests concerned untreated S. saevissima workers from different supercolonies to evaluate their natural aggressiveness level. In the second control tests, we intended to reproduce the stress inflicted on workers when they were "made-up". Here, an untreated worker was confronted with a conspecific stranger that, after being rinsed, was placed into water (rather than into the CC emulsion obtained from another species). All of the behavioural tests were conducted and scored as previously described.

Second, to search for the CCs potentially responsible for highly aggressive responses, we set up confrontations between two S. saevissima workers from the same nests (30 cases for supercolony A; 30 other cases for supercolony B); indeed, nestmates do not attack each other. Here, too, one of them was "made-up" with CCs from workers belonging to another neighbour ant species as previously described. Two controls were conducted as previously, but this time with nestmates.

Statistical analysis

To compare the levels of aggressiveness between S. saevissima workers and workers from the sympatric species, we firstly modelled the link between the scores assigned to each confrontation taking into account if the workers were neighbours or strangers using a generalized linear model (GLM) with an ordinal probit link [START_REF] Agresti | Categorical Data Analysis[END_REF]. This model respected the ordinal qualitative Fig. 2. Interactions between S. saevissima workers and those from the eight ant species able to live in the vicinity of S. saevissima nests. The values presented on the Y-axis correspond to the effect of "being a stranger" on the inverse probit of the scores (plots show means and 95% CI). As the inverse probit is an increasing function, positive values imply higher probabilities for higher scores and negative values imply higher probabilities for lower scores. Statistical comparisons: different letters indicate significant differences at P < 0.05. NNE: greater aggressiveness towards familiar ants (neighbours). DEP: greater aggressiveness towards unfamiliar ants (strangers). nature of the scores which were equal to 1, 2, 3 or 4 depending on the level of aggressiveness of the confrontation. The significance of being a neighbour or a stranger was assessed through likelihood ratio effect tests. Secondly, to identify homogeneous groups of species according to the level of aggressiveness noted during the confrontations, we carried out likelihood ratio effect tests on pairs of species to assess their differences. For each pair of species, we compared the general model with the GLM probit, integrating the variable "neighbour" or "stranger" and assuming (1) that each species had a different effect, and (2), on the contrary, that the two species had an identical effect. Multiple comparisons were adjusted using the false discovery rate (FDR) ("BY" correction; [START_REF] Benjamini | The control of the false discovery rate in multiple testing under dependency[END_REF]; Fig. 2). We did not find a colony effect.

To compare the percentage of submissive behaviours by neighbours and strangers for each species tested, we conducted proportion tests (Fig. 3). 4. Aggressiveness noted during interactions between "stranger" S. saevissima workers (plots show means and 95% CI). The values presented on the Y-axis correspond to the effect of the CCs from the tested ant species on the inverse probit of the scores (see also the legend for Fig. 2). The first control group corresponds to the interactions between untreated S. saevissima. The horizontal line corresponds to the second control group, or confrontations between alien S. saevissima workers, one of them having been rinsed. The experimental groups correspond to confrontations between alien S. saevissima workers, one of them having been "made-up" with the cuticular extracts from a sympatric ant species. Statistical comparisons: different letters indicate significant differences at P < 0.05.

For confrontations between S. saevissima workers when one of them was "made-up" with CCs from a sympatric ant species (and for the controls), we also modelled the link between the scores assigned to each confrontation between two workers and the ant species using a GLM with an ordinal probit link. To identify homogeneous groups of species according to the impact of their CCs on the level of aggressiveness during these confrontations, we carried out likelihood ratio effect tests on the CCs of pairs of species to assess their differences. For each pair of species, we compared the general model with the GLM probit and assumed (1) that the CCs of each species had a different effect, and (2), on the contrary, that the CCs of the two species had an identical effect. Here, too, multiple comparisons were adjusted using the BY FDR correction (Fig. 4).

The statistics were carried out using R (v. 2.14.2) software (R Development Core Team, 2011). The ordinal probit regression was carried out using the package MASS.

Results

Confrontations between S. saevissima workers and those from the other ant species

Among the eight ant species able to live in close vicinity to S. saevissima mounds, only Ca. melanoticus, S. geminata and D. pyramicus workers elicited a significant DEP during aggressiveness tests as interactions between neighbours resulted in a lower level of aggressiveness than interactions between non-neighbours (values above 0 in Fig. 2). The contrary was true, illustrating NNE, for A. sexdens, Ca. blandus and W. auropunctata (values above 0 in Fig. 2), while interactions with P. fallax and Cr. tenuicula revealed the same level of aggressiveness regardless of whether the workers were neighbours or "strangers".

During dyadic confrontations with these eight ant species, S. saevissima workers, which never escaped (level 2 of scoring) and never displayed submissive behaviours, were always the aggressor when scoring levels 3 and 4 were noted. Among the eight confronted ant species three trends appeared (Fig. 3): (1) only D. pyramicus workers displayed significantly more submissive behaviours when they were neighbours than when they were "strangers"; (2) A. sexdens, Ca. blandus, P. fallax and Cr. tenuicula displayed a similar rate of submissive behaviours whether they were neighbours or "strangers"; and (3) W. auropunctata, Ca. melanoticus and S. geminata displayed significantly more submissive behaviours when they were "strangers" (Fig. 3). Overall, species eliciting DEP tended to display fewer submissive behaviours than others regardless of whether they were neighbours or "strangers" (Fig. 3).

Contrarily to the previous cases, submissive behaviours were noted only on the part of the S. saevissima individuals when they were confronted with E. burchellii individuals; the latter were the aggressors in all cases. Note that intraspecific submissive behaviours were also observed for S. saevissima (Fig. 3).

Testing semiochemicals on "stranger" and nestmate S. saevissima workers

Dyadic confrontations between "stranger" (non-colony mate) S. saevissima workers where one of them was "made-up" with the CCs from Cr. tenuicula, W. auropunctata, Ca. melanoticus, A. sexdens, D. pyramicus and P. fallax resulted in a lower, but non-significant, level of aggressiveness compared to the second control group (where one S. saevissima was rinsed; Fig. 4). All previous levels of aggressiveness were significantly lower than those for the first control group (i.e., untreated S. saevissima workers) or when one of the workers was "made-up" with extracts from S. geminata, Ca. blandus or E. burchellii (Fig. 4).

The same experiments conducted between S. saevissima nestmates produced a significant increase in the level of aggressiveness only for extracts taken from Ca. blandus and E. burchellii (P < 0.01; figure not shown). Here, the aggressiveness values for confrontations between two untreated S. saevissima (first control) and between one untreated S. saevissima worker and another rinsed (second control) were identical and equal to 1.

Discussion

DEP, NNE and the biological and ecological traits of the different ant species

Because a similarity in colony odour can be excluded as the confronted workers belong to different species, DEP can only result from habituation or a type of learning of the neighbour's odour leading dominant ants to tolerate workers from certain other species [START_REF] Peeke | Habituation and the maintenance of territory bounderies[END_REF]. Nevertheless, the decision to fight or not with a neighbour resides in (1) colony-mate recognition (the role of the CCs), (2) the behaviour of the workers (submissive or not) and (3) ecological characteristics of each species based on their propensity to compete for the same resources and the threat they represent. Indeed, DEP and NNE occur based on the potential costs and benefits related to foraging for food and territorial defence [START_REF] Langen | The red and the black: habituation and the dear-enemy phenomenon in two desert Pheidole ants[END_REF][START_REF] Grangier | Coexistence between Cyphomyrmex ants and dominant populations of Wasmannia auropunctata[END_REF][START_REF] Abril | Ascertaining key factors behind the coexistence of the native ant species Plagiolepis pygmaea with the invasive Argentine ant Linepithema humile (Hymenoptera: Formicidae)[END_REF][START_REF] Menzel | Behavioural and chemical mechanisms behind a Mediterranean ant-ant association[END_REF].

One might expect that species eliciting DEP have "appeasing" CCs, while those eliciting NNE have CCs that trigger greater aggressiveness, yet our results did not bear this out (Fig. 4). This is likely due to the interference between the traits we studied here and the biological and ecological characteristics of each species studied, presented below.

Among the eight ant species able to live in the vicinity of S. saevissima nests, S. geminata and W. auropunctata are also supercolonial and their workers are known for their interspecific aggressiveness [START_REF] Holway | The causes and consequences of ant invasions[END_REF]; however we noted DEP in the former case and NNE in the latter case. Because they share several traits such as nest site selection, means of defending food resources, high nest density, and the quick colonization of open, disturbed areas, S. saevissima and S. geminata are in close competition [START_REF] Perfecto | Dynamics of Solenopsis geminata in a tropical fallow field after ploughing[END_REF][START_REF] Perfecto | Foraging behavior as a determinant of asymmetric competitive interaction between two ant species in a tropical agroecosystem[END_REF][START_REF] Trager | A revision of the fire ants, Solenopsis geminata group (Hymenoptera: Formicidae: Myrmicinae)[END_REF]. This explains the high levels of aggressiveness depicted in Fig. 4. Although small, W. auropunctata workers are fierce competitors for food resources and are able to displace most other ants [START_REF] Holway | The causes and consequences of ant invasions[END_REF][START_REF] Orivel | Ecologically heterogeneous populations of the invasive ant Wasmannia auropunctata within its native and introduced ranges[END_REF]). Yet, they share foraging areas with S. saevissima thanks to a high rate of submissive behaviour (Fig. 3), and their CCs do not trigger greater aggressiveness (Fig. 4). Unexpectedly, the same was true for the leaf-cutting ant A. sexdens (Figs. 3 and4) that has populous colonies containing 5-8 million workers [START_REF] Hölldobler | The Ants[END_REF].

Very frequent in the area studied, the diurnal workers from the large, polydomous Ca. blandus colonies are dominated at dawn and dusk by the nocturnal S. saevissima individuals [START_REF] Orivel | Ant activity rhythms in a pioneer vegetal formation of French Guiana (Hymenoptera: Formicidae)[END_REF]. Accordingly, they very frequently behaved submissively (Fig. 3), while their CCs elicited aggressiveness by S. saevissima individuals (Fig. 4).

Ca. melanoticus forms large, polydomous colonies extending over ca. 200 m and the workers, nocturnal, dominate S. saevissima individuals in natural conditions [START_REF] Orivel | Ant activity rhythms in a pioneer vegetal formation of French Guiana (Hymenoptera: Formicidae)[END_REF]. Correspondingly, they only rarely displayed submissive behaviours in this study (Fig. 3), so that the low level of aggressiveness noted was likely due to DEP in addition to CCs that do not trigger greater aggressiveness (Fig. 4). The same was true for D. pyramicus although the colonies are small and the workers are typically opportunist, discovering food resources quickly but not conducting mass recruitment, and, so, not defending these resources (AD, pers. obs.).

We noted neither DEP nor NNE for P. fallax and Cr. tenuicula (Fig. 4), both having small colonies [START_REF] Itzkowitz | The food retrieval tactics of the ant Pheidole fallax (Mayr)[END_REF][START_REF] De Oliveira | Ant species distribution along a topographic gradient in a "terra-firme" forest reserve in Central Amazonia[END_REF]. Active all around the clock, P. fallax workers are generalist foragers that use mass recruitment [START_REF] Itzkowitz | The food retrieval tactics of the ant Pheidole fallax (Mayr)[END_REF]. They likely attenuated S. saevissima aggressiveness through their high rate of submissive behaviour aided by their CCs that do not trigger greater aggressiveness (Figs. 3 and4), whereas Cr. tenuicula workers were likely tolerated by S. saevissima thanks to their CCs as they were very rarely submissive (Figs. 3 and4).

Colonies of the army ant E. burchellii are quite large with up to 2 million polymorphic workers that capture a wide range of prey, including the brood of other ants [START_REF] Gotwald | Army ants[END_REF]. This time it was the S. saevissima workers that behaved submissively (Fig. 3), explaining, at least in part, how they survive army ant raids even though the latter plunder larvae, pupae and some callow workers (AD, pers. obs.; see similar cases in [START_REF] Gotwald | Army ants[END_REF].

CCs affecting the level of aggressiveness of S. saevissima workers

Ant cuticular hydrocarbon profiles are composed of more than 100 linear alkanes and methyl-branched alkanes and alkenes whose chains range from 20 carbons to 40 carbons [START_REF] Guerrieri | Ants recognize foes and not friends[END_REF][START_REF] Martin | A review of ant cuticular hydrocarbons[END_REF][START_REF] Van Wilgenburg | Learning and discrimination of cuticular hydrocarbons in a social insect[END_REF]. It is generally assumed that workers discriminate their nestmates from strangers by qualitatively and quantitatively comparing their own CCs (i.e., their "colony odour" that they learned and that represents a neural template) with the CCs of encountered individuals. A mismatch generally results in aggressiveness (d'Ettorre and Lenoir, 2010). Yet, it appears that overall only one subset of cuticular hydrocarbons are likely used as recognition cues, while the discrimination of a stranger does not obligatorily elicit aggressiveness [START_REF] Guerrieri | Ants recognize foes and not friends[END_REF]d'Ettorre and Lenoir, 2010;[START_REF] Van Wilgenburg | Deciphering the chemical basis of nestmate recognition[END_REF][START_REF] Van Wilgenburg | Learning and discrimination of cuticular hydrocarbons in a social insect[END_REF].

S. saevissima workers "made-up" with the CCs from Ca. blandus, S. geminata and E. burchellii triggered greater aggressiveness (Fig. 4 and experiments involving S. saevissima nestmates). This means that individuals from these three species were likely recognized as potential threats by S. saevissima workers based on their CCs (or a part of their CCs). This is reminiscent of experiments where hydrocarbons were added to natural profiles where only some of them elicited aggressiveness in Ca. herculeanus and the argentine ant [START_REF] Guerrieri | Ants recognize foes and not friends[END_REF][START_REF] Van Wilgenburg | Deciphering the chemical basis of nestmate recognition[END_REF]. Note that only Ca. blandus shares foraging areas with S. saevissima, but with different rhythms of activity, whereas S. geminata rather competes with S. saevissima for territories and E. burchellii preys on all of them.

In the present study, rinsing one individual before dyadic confrontation tests between stranger S. saevissima workers (second control) resulted in a significantly lower level of aggressiveness than during confrontations between untreated individuals (first control) (Fig. 4). This is likely because the rinsed individual loses a part of its CCs (a threshold is not reached that discriminates it as a "true" stranger), while the modification of its "template" lowers its own reactions. The addition of the CCs from Cr. tenuicula, W. auropunctata, Ca. melanoticus, A. sexdens, D. pyramicus and P. fallax had no effect on the level of aggressiveness by S. saevissima workers (values not significantly different than those from the second control group; Fig. 4). It is as if these tested S. saevissima workers were unable to recognize that they are "true" strangers due to the rinsing (second control) or due to the rinsing plus the addition of the CCs from these six ant species. At least in part, this permits the workers of these ant species to share territories with S. saevissima individuals without triggering aggressiveness (Fig. 4), while explaining why in nature interspecific encounters between ants result mostly in reciprocal avoidance (the other is recognized but not attacked).

Conclusion

In addition to DEP or NNE, ant species able to live in the vicinity of S. saevissima lessened its workers' aggressiveness either through submissive behaviours (essential when species' CCs trigger a greater level of S. saevissima aggressiveness) and/or, for certain species, the properties of their CCs that do not trigger aggressiveness by the S. saevissima workers. Also, our results bring new insights to the patterns related to colony-mate recognition in S. saevissima, something that may also be true for invasive fire ants.

Fig. 1 .

 1 Fig. 1. Some of the behaviours noted during confrontations. (A) An A. sexdens media worker feigning death (thanatosis) during a confrontation set up with a Solenopsis saevissima worker. The scale bar represents 1 mm. (B) Fighting between two S. saevissima workers; one of them is biting a leg (arrow) of its opponent. (C) Reciprocal full attack between two S. saevissima workers (they bite and sting each other).

Fig. 3 .

 3 Fig. 3. Probability of submissive behaviours being displayed by the different ant species during confrontations with S. saevissima (plots show means and 95% CI). Note that S. saevissima workers presented submissive behaviours only during intraspecific confrontations or when they were confronted with E. burchellii individuals. Statistical comparisons between neighbouring colonies of an S. saevissima nest (n) and "stranger" colonies (s): the P-values are indicated above the name of the ant species.

Fig.

  Fig.4. Aggressiveness noted during interactions between "stranger" S. saevissima workers (plots show means and 95% CI). The values presented on the Y-axis correspond to the effect of the CCs from the tested ant species on the inverse probit of the scores (see also the legend for Fig.2). The first control group corresponds to the interactions between untreated S. saevissima. The horizontal line corresponds to the second control group, or confrontations between alien S. saevissima workers, one of them having been rinsed. The experimental groups correspond to confrontations between alien S. saevissima workers, one of them having been "made-up" with the cuticular extracts from a sympatric ant species. Statistical comparisons: different letters indicate significant differences at P < 0.05.

Acknowledgments

We are grateful to Andrea Yockey-Dejean for proofreading the manuscript, to Frédéric Azémar for technical support and to the Laboratoire Environnement de Petit Saut for furnishing logistical assistance. Financial support for this study was provided through the French Fondation pour la Recherche sur la Biodiversité (research agreement no AAP-IN-2009-050) and a Investissement d'Avenir grant from the French Agence Nationale de la Recherche (CEBA, ref. ANR-10-LABX-0025).