Sepideh Mirrahimi
email: mir-rahimi@cmap.polytechnique.fr

Benoît Perthame
email: benoit.perthame@upmc.fr

‡ Joe
email: joe@meiji.ac.jp

Yuichiro Wakano

Direct competition results from strong competition for limited resource

Keywords: Ecological competition for resource, Direct competition, Multiscale analysis, Lyapunov functional, Adaptive dynamics. Mathematics Subject Classification: 34E13, 35K57, 47G20, 92D15, 92D40

We study a model of competition for resource through a chemostat-type model where species consume the common resource that is constantly supplied. We assume that the species and resources are characterized by a continuous trait. As already proved, this model, although more complicated than the usual Lotka-Volterra direct competition model, describes competitive interactions leading to concentrated distributions of species in continuous trait space.

Here we assume a very fast dynamics for the supply of the resource and a fast dynamics for death and uptake rates. In this regime we show that factors that are independent of the resource competition become as important as the competition efficiency and that the direct competition model is a good approximation of the chemostat. Assuming these two timescales allows us to establish a mathematically rigorous proof showing that our resource-competition model with continuous traits converges to a direct competition model. We also show that the two timescales assumption is required to mathematically justify the corresponding classic result on a model consisting of only finite number of species and resources (MacArthur, R. Theor. Popul. Biol. 1970:1, 1-11). This is performed through asymptotic analysis, introducing different scales for the resource renewal rate and the uptake rate. The mathematical difficulty relies in a possible initial layer for the resource dynamics.

The chemostat model comes with a global convex Lyapunov functional. We show that the particular form of the competition kernel derived from the uptake kernel, satisfies a positivity property which is known to be necessary for the direct competition model to enjoy the related Lyapunov functional.

Introduction

In order to faithfully capture the dynamics of species competition, a detailed mechanism such as species-resource dynamics should be explicitly modeled. On the other hand, specifying a particular mechanism narrows the applicability of a model. This is why conceptual and simple Lotka-Volterra type models of direct competition are widely and intensively studied. Then a natural question arises: Can we reduce a species-resource dynamics model into a Lotka-Volterra model? If so, how are parameters (e.g., intrinsic growth rates, competition coefficients) determined by those of the original mechanistic model? These questions are central when studying the evolutionary origin of species diversity which has been one of the most important problems in evolutionary ecology. Individuals with similar traits (e.g. body size or shape) face strong competition, which might lead to adaptive radiation. Using models of competition-driven speciation, several theoretical studies have shown that the species distribution in continuous trait space often evolve toward single peak or multiple peaks that are distinct from each other (see [START_REF] Sasaki | The evolutionarily stable phenotype distribution in a random environment[END_REF][START_REF] Diekmann | The dynamics of adaptation: an illuminating example and a Hamilton-Jacobi approach[END_REF][START_REF] Desvillettes | On mutation-selection dynamics[END_REF][START_REF] Perthame | Dirac concentrations in Lotka-Volterra parabolic PDEs[END_REF][START_REF] Jabin | On selection dynamics for competitive interactions[END_REF][START_REF] Mirrahimi | Evolution of species trait through resource competition[END_REF]). Although many previous results are derived from a simple model that assumes direct species competition of Lotka-Volterra type, competitive interaction among species generally occurs in competition for resource such as prey or nutrient. For example, birds with similar beak shapes are in competition because they utilize similar food resource. Another example is found in ecological stoichiometry where consumer species with similar C:N:P (carbon: nitrogen: phosphorus ratio) requirements experience competition for nutrient supply with their optimal C:N:P ratio (see [START_REF] Sterner | Ecological Stoichiometry: The Biology of Elements from Molecules to the Biosphere[END_REF]). Thus, the competitive interaction should be modeled not directly but implicitly through the resource. Recently, we have proposed such a mechanistic model of species competition where species (with continuous trait) compete for common resource (which is characterized by another continuous 'trait' or 'type') which is constantly supplied (chemostat-type model) (see [START_REF] Mirrahimi | Evolution of species trait through resource competition[END_REF]). We have shown that evolutionary branching, which is parallel to adaptive radiation, is possible in this chemostat-type model as well, supporting the results previously obtained by direct competition models. This paper aims the reduction of a mechanistic model of species-resource dynamics to a more conceptual model of direct species competition. In Section 2, we describe our chemostat model of species-resource dynamics and a brief summary of our reduction result. Section 3 is devoted to a rigorous description of this result and the proof. In section 4, we extend our result to include a system with mutation. In section 5, we study the Lyapunov functional property which is useful for evolutionary stability analysis. In section 6, we show some numerical examples to study how the reduced dynamics approximates the original dynamics. In section 7, we show that the classic result on a model of discrete number of species [START_REF] Macarthur | Species packing and competitive equilibria for many species[END_REF] was not fully mathematical and discuss how our framework can be used to solve this problem.

Model and a brief summary of the results

In general, living organisms require several different resource to survive and reproduce. They might undergo strong competition for some resource, while some other resource might be sufficiently supplied so that it might not lead to competition at all. In case of phytoplankton species, resources are light and nutrients. Although tremendous amount of light is supplied from the sun, the competition for light still exists. Nutrient supplied from the bottom is also a limiting resource, and this dynamics might have much slower timescale compared to the competition for light (but slower dynamics do not imply less importance). There might exist some features that determine growth or death rates independently of resource competition. Here we consider a model that allows continuous distribution of species trait and resource type (by an abuse we sometimes refer to it as a trait too) for two reasons: first, a continuous model is more compatible with standard evolutionary models of physiological traits mentioned earlier; second, the mathematical analysis of a continuous model seems more general than a model with the finite and given number of species and resources (Note that our mathematical treatment allows distribution to converge to Dirac masses. Thus, although the rigorous proof is not given here, it implies that our model includes relatively simple ODE models as special cases.)

Inspired by such phytoplankton ecology, our mechanistic model for a chemostat with continuous resource supply and continuous consumer population trait is given by

     ∂ ∂t n(x, t) = n(x, t) b(x) -d(x) + K(x, y)R(y, t)dy , ∂ ∂t R(y, t) = m(y) R in (y) -R(y, t) -R(y, t) K(x, y)n(x, t)dx, (1)
where n(x, t) ≥ 0 is the consumer species density with trait x ∈ R and R(y, t) ≥ 0 is the common resource density with trait y ∈ R. We assume that a death rate d(x) depends on species trait x. Reproduction rate consists of two parts: b(x) denotes a basic reproduction rate independent of the competition for the common resource, and K(x, y)R(y, t)dy denotes a reproduction rate coming from consuming the common resource R. The resource R is supplied into the system with a rate m(y) so that R(y, t) approaches R in (y) > 0. These drive the system (a chemostat type model). Consumption for resource is denoted by a trait dependent uptake kernel K(x, y) ≥ 0 that defines how species with trait x depends on resource with trait y. All coefficients (b(x), d(x), K(x, y), m(y), R in (y); although they are functions of traits, we call them 'coefficients') can play an important role in the full system.

The regime when direct competition is close to (1) arises in some limiting situation. We assume that the dynamics has the following three different timescales (notice however that time can always be rescaled to fix one of them, and as we explain in section 7, only two timescales cannot do the work)

• Very fast dynamics for the common resource supply. This imposes that, in the absence of consumer species, resource distribution R approaches R in .

• Fast dynamics for resource-consumption and the resulting reproduction and death. In other words, common resource dependent coefficients are large. This implies that competition for the common resource is a primary factor for the growth of consumer species population.

• Slow dynamics. Population dynamics of n is also affected by a basic reproduction rate b(x) and a death rate d slow (x), both of which are independent of the common resource.

In order to include these assumptions in the equations, we scale accordingly the coefficients

• m is of order ε -2 , • K is of order ε -1 , • d(x) = K(x, y)R in (y)dy + d slow (x),
and we define a neat growth/death rate (that we take independent of ε for simplicity)

• a(x) = b(x) -d slow (x).
In other words, direct competition is a good approximation of (1) when the death rate is suited to counterbalance fast growth based on resource-consumption (otherwise, the population will grow infinitely). For this purpose, in the third bullet, we divide the death rate into two parts. The first term represents fast dynamics for death events that compensates fast resource-consumption. The second term, d slow (x), represents the remaining slow dynamics for death events independent of the competition for resource. Note that this decomposition of d(x) means that, while the common resource R is at its equilibrium R in , the dynamics of the consumers are determined only by the parameters which are independent of the common resource, that is why we introduce the neat rate a(x).

These result in a new formulation of (1) that is written as

     ∂ ∂t n ε (x, t) = n ε (x, t) a(x) + 1 ε K(x, y) R ε (y, t) -R in (y) dy , ∂ ∂t R ε (y, t) = m(y) ε 2 R in (y) -R ε (y, t) -1 ε R ε (y, t) K(x, y)n ε (x, t)dx, (2)
where new coefficients satisfy m = O(1), K = O(1), and a = O(1). We complement the system with initial data

n ε (x, 0) = n 0 (x) ≥ 0, R ε (y, 0) = R 0 (y) ≥ 0,
As the very fast and fast dynamics become infinitely fast, R should approach R in , but it is not clear which distribution n should approach. When R is not close to R in , the reproduction based on resource-consumption is dominant (fast dynamics with order ε -1 ) so the dynamics of n is primarily determined by R -R in . However, as R -R in approaches to zero, resource-dependent reproduction might become no longer dominant.

In this paper, we will show that an approximation of this dynamics is given by the direct competition model

∂ ∂t n(x, t) = n(x, t) a(x) -c(x, x ′ )n(x ′ , t)dx ′ , (3)
where the binary competition kernel c(x, x ′ ) is related to the coefficients in (2). We will show that it is given by

c(x, x ′ ) = K(x, y) R in (y) m(y) K(x ′ , y)dy.
This equation can be seen as a conversion formula of kernels. The reduced competition-kernel c(x, x ′ ) is very sensitive to R in (y)/m(y) as well as to resource-consumption kernel K(x ′ , y), but not to R in (y) or m(y) separately. Note that this kernel is of order one (recall that resource-consumption kernel is of order ε -1 before rescaling) so the reduced direct competition model describes the slow dynamics of n(x, t). We will later show that the inclusion of mutation in consumer species' trait does not essentially change the result. One biologically interesting point of the equation ( 3) is that the growth rate of consumer species in the absence of competition for resource, which is described by a(x), still has considerable effect on the long-term dynamics of consumer distribution n. This is because as R becomes very close to R in , the dominant factor (fast dynamics) becomes weaker and a basic growth rate a(x) becomes as important as the competition for resource. In this limit, we recover a Lotka-Volterra type competition dynamics from a mechanistic model of a chemostat type. It is natural that we do not have the reduced dynamics of the resource, R, because the reduction is possible when the detailed dynamics of the resource can be neglected and when the effects of competition for the resource can be put into the new competition coefficients in a Lotka-Volterra type system (i.e. c(x, x ′ )).

As already raised in [START_REF] Abrams | Competition-similarity relationships and the nonlinearity of competitive effects in consumer-resource systems[END_REF], another practical question of our interest is the choice of the competition kernel; usually a Gaussian choice is favored, based on heuristic arguments which promotes the coexistence of infinitely many species (continuous distribution over continuous trait axis). Not only this has a particular effect as shown by the structural instability of continuous distribution in result [START_REF] Gyllenberg | On the impossibility of coexistence of infinitely many strategies[END_REF], but also our result shows that this choice is arbitrary because the conversion of resource-consumption kernel into direct-competition kernel does not guarantee that a Gaussian function is converted into another Gaussian function. Take

K(x, y) = e -α(x-y) 2 , R in (y) = e -βy 2 , m(y) ≡ 1.
Then, choosing γ such that γ(2α + β) = α 2 so as to complete a square in the expression

c(x, x ′ ) = e -[αx 2 +α(x ′ ) 2 -γ(x+x ′ ) 2 ] e -[(2α+β)y 2 -2α(x+x ′ )y+γ(x+x ′ ) 2 ] dy = e -[αx 2 +α(x ′ ) 2 -γ(x+x ′ ) 2 ] π 2α+β ,
we find that c(x, x ′ ) is not gaussian because it is proportional to

e -[αx 2 +α(x ′ ) 2 -γ(x+x ′ ) 2 ] = e -(α-γ)(x-x ′ ) 2 when β = 0.
The present study is not the first attempt to derive direct competition Lotka-Volterra equations from a model of species competing for resources. MacArthur [START_REF] Macarthur | Species packing and competitive equilibria for many species[END_REF] proposed a simpler approach where he also chooses a Lotka-Volterra equation for the resources; he chooses a discrete setting rather than continuous but this is irrelevant for our purpose. With our notations MacArthur's model is described as a prey-predator model

     ∂ ∂t n(x, t) = b(x)n(x, t) K(x, y)R(y, t)dy -d(x) , ∂ ∂t R(y, t) = R(y, t) m(y)(1 -R(y,t) Rcc(y) ) -K(x, y)n(x, t)dx , (4)
Assuming b is of order ε and rescaling time accordingly, we end up with a rescaled equation that is close to (2). This seems to provide a simpler approach to obtain the aymptotic behavior. However, the shortcoming is that the limiting equation is NOT under the form (3) but more complicated and with different nonlinearities (e.g., see (27) in section 7.) Thus, more rigorous analysis is necessary.

Mathematical notations and results will follow in the next three sections. Section 3 is devoted to a rigorous derivation of our convergence result. It goes through asymptotic analysis and compactness estimates that allow us to show that n ε converges to n and thus n is the population density. In other words our theory is not a perturbation analysis on n ε while it is on R ε ≈ R in . Mutations are not included in the model equations ( 1)-(3). In section 4, we show how to include them and which new rescaling this leads to perform. Another remarkable property of the chemostat is the Lyapunov functional property already used in [START_REF] Mirrahimi | Evolution of species trait through resource competition[END_REF]. The asymptotic form of this Lyapunov functional is related to that for the direct competition model in section 5 and in particular we explain why, in this context, the corresponding operator is always nonnegative.

Derivation of the direct competition

In order to state our result we need some assumptions

n 0 , R 0 , R in ∈ L 1 ∩ L ∞ (R), ∂ ∂x n 0 dx ≤ C 1 , (5)
a M := a ∞ < ∞, m = min y m(y) > 0, m = max y m(y) < ∞, (6)
K ∈ BU C(R × R), K M := sup x,y K(x, y) < ∞, (7)
∂ ∂x K(x, y) ≤ C 2 , ∂ ∂x a(x) ≤ C 3 . (8)
where BU C stands for the linear space of Bounded Uniformly Continuous functions. With these in mind, we establish that the limiting problem for (2) is the direct competition model

Proposition 3.1 As ε tends to 0 in (2), R ε converges strongly to R in in L 1 (0, T ) × R and n ε con- verges strongly in C (0, T ); L 1 (R)
to n, the solution to (3) with the initial data n 0 and the competition kernel

c(x, x ′ ) = K(x, y) R in (y) m(y) K(x ′ , y)dy. (9)
It is more technical to improve the space-time convergence on R ε . Indeed it leaves place for an initial layer which is needed because, in general, its limit R in is incompatible with the initial data R 0 ε .

Proof. To begin with, we re-write the equation on R ε in (2) as

R ε (y, t) -R in (y) = -ε R ε (y, t) m(y) K(x, y)n ε (x, t)dx - ε 2 m(y) ∂ ∂t R ε (y, t).
We inject this to compute the growth rate for n ε

1 ε K(x, y) R ε (y, t) -R in dy = -K(x, y) R in (y, t) m(y) K(x ′ , y)n ε (x ′ , t)dx ′ dy + I ε (x, t) = -c(x, x ′ )n ε (x ′ , t)dx ′ + I ε (x, t),
as we use c(x, x ′ ) as defined in [START_REF] Champagnat | Convergence to equilibrium in competitive Lotka-Volterra and chemostat systems[END_REF] and with

I ε (x, t) = -ε ∂ ∂t K(x, y) m(y) R ε (y, t)dy + K(x, y) R in (y) -R ε (y, t) m(y) K(x ′ , y)n ε (x ′ , t)dx ′ dy.
Therefore the equation on n ε can also be written

∂ ∂t n ε (x, t) = n ε (x, t) a(x) -c(x, x ′ )n ε (x ′ , t)dx ′ + I ε (x, t) . ( 10
)
Throwing away the terms in ε, we find formally (3).

To justify rigorously this limit, we need (i) estimates for compactness, (ii) explain how we can pass to the limit.

(i) Estimates. We define

M ε (t) := n ε (x, t)dx, N ε (t) := R ε (y, t) -R in (y) dy,
We then notice from the equation on R ε in (2) that we have

R ε (y, t) ≤ R in (y), for all y such that R 0 (y) ≤ R in (y),
and

R ε (y, t) ≤ R in (y) + R 0 (y) -R in (y) exp(- mt ε 2 ),
for all y such that R 0 (y) > R in (y).

It follows in particular that N ε and R ε (•, t) L 1 are uniformly bounded in ε by a constant denoted by R M . Next we write from the equation on n ε in ( 2)

d dt M ε ≤ M ε a M + K M ε exp - mt ε 2 R 0 (y) -R in (y) + dy .
We deduce that, for C some constant independent of ε,

M ε (t) ≤ M ε (0) exp a M t + Cε ,
and thus M ε is uniformly bounded in ε ≤ 1 on each time interval [0, T ] by a constant denoted by M T . Next, we define and write from the equation on R ε in (2)

d dt N ε (t) + m ε 2 N ε (t) ≤ R M ε K M M ε (t).
It follows from this differential inequalitiy and the fact that M ε (t) and N ε (t) are uniformly bounded that 1 ε t 0 N ε (s)ds is also uniformly bounded in ε ≤ 1 on each time interval [0, T ]. One step further, from the bound on M ε and from the equation on N ε , one also concludes that

N ε (t) ε ≤ N (0) ε e -mt/ε 2 + R M K M M T m , ∀t ∈ [0, T ]. ( 11
)
(ii) Compactness in t. From this, and going back to the equation on n ε , we conclude that, still for

t ∈ [0, T ] ∂n ε (x, t) ∂t dx ≤ a M C(T ) + K M N (0) ε e -mt/ε 2 + K M C(T ). ( 12
)
This Lipschitz estimate in time gives us that n ε is uniformly equicontinuous in C (0, T ); L 1 (R) .

(iii) Compactness in x. Dividing equation ( 2) by n ε and differentiating in x, we find

∂ 2 ∂x∂t ln n ε (x, t) = ∂ ∂x a(x) + 1 ε ∂ ∂x K(x, y) (R ε (y, t) -R in (y)) dy.
From ( 8) and [START_REF] Desvillettes | On mutation-selection dynamics[END_REF] we obtain that, for some constant D 1

∂ 2 ∂x∂t ln n ε (x, t) ≤ D 1 + C 2 N (0) ε e -mt/ε 2 .
It follows that, for ε ≤ 1 and for some constant

D 2 ∂ ∂x ln n ε (x, t) ≤ ∂ ∂x ln n 0 (x) + D 2 t, ∂ ∂x n ε (x, t) dx ≤ ∂ ∂x n 0 (x) n 0 (x) n ε (x, t) dx + D 2 t n ε (x, t)dx.
Moreover, from the first equation of ( 2) and ( 11) we obtain that, for some constant D 3 ,

∂ ∂t ln n ε (x, t) ≤ D 3 + K M N (0) ε e -mt/ε 2 ,
and thus: ln n ε (x, t) ≤ ln n 0 (x) + D 4 t, for ε ≤ 1 and some constant D 4 , which gives

n ε (x, t) n 0 (x) ≤ exp(D 4 t).
Using the above arguments and ( 5), we conclude that, for some constant D(T ) and 0 ≤ t ≤ T ,

∂ ∂x n ε (x, t) dx ≤ exp(D 4 t) ∂ ∂x n 0 (x) dx + D 2 t n ε (x, t)dx ≤ C 1 exp(D 4 t) + D 2 tM ε (t) ≤ D(T ).
Using this and step (ii) we conclude from the Arzela-Ascoli Theorem that, after extracting a subsequence, n ε converges in C (0, T ); L 1 (R) .

(iv) Passing to the limit. It remains to pass to the weak (distribution) limit in the equation on n ε written as [START_REF] Champagnat | Polymorphic evolution sequence and evolutionary branching[END_REF]. Because of the strong convergence of n ε and (11), the only difficulty is to pass to the limit in the term

εn ε (x, t) ∂ ∂t K(x, y) m(y) R ε (y, t)dy = ε ∂ ∂t n ε (x, t) K(x, y) m(y) R ε (y, t)dy -ε K(x, y) m(y) R ε (y, t)dy ∂ ∂t n ε (x, t).
The first term converges weakly to 0 (multiplying by a test function, after integration by parts all the terms are bounded and multiplied by ε). For the second term, we use the estimate [START_REF] Diekmann | A beginner's guide to adaptive dynamics[END_REF] to reach the conclusion that it converges in L 1 to 0, thanks again to the multiplying factor ε. Since uniqueness of weak solutions for the direct competition model is proved in [START_REF] Desvillettes | On mutation-selection dynamics[END_REF], we conclude that the full family n ε converges and not only subsequences.

Mutations

In the present context of population equations structured by a physiological trait, there are several possibilities to represent mutations that have been widely used [START_REF] Calsina | Small mutation rate and evolutionarily stable strategies in infinite dimensional adaptive dynamics[END_REF][START_REF] Diekmann | The dynamics of adaptation: an illuminating example and a Hamilton-Jacobi approach[END_REF][START_REF] Desvillettes | On mutation-selection dynamics[END_REF]. Integral operators or diffusion operators can be derived from stochastic individual based models; see for instance [START_REF] Champagnat | Unifying evolutionary dynamics: From individual stochastic processes to macroscopic models[END_REF][START_REF] Champagnat | From individual stochastic processes to macroscopic models in adaptive evolution[END_REF]. Mathematically they have many similar properties, in particular asymptotic analysis can be carried out using similar methods in the regime of small mutations for a long time of observation leading to speciation phenomena [START_REF] Barles | Concentrations and constrained Hamilton-Jacobi equations arising in adaptive dynamics[END_REF][START_REF] Barles | Concentration in Lotka-Volterra parabolic or integral equations: a general convergence result[END_REF][START_REF] Lorz | Dirac mass dynamics in multidimensional nonlocal parabolic equations[END_REF] although stochastic individual methods are also used for the same purpose [START_REF] Champagnat | A microscopic interpretation for adaptive dynamics trait substitution sequence models[END_REF][START_REF] Champagnat | Polymorphic evolution sequence and evolutionary branching[END_REF][START_REF] Méléard | Random modeling of adaptive dynamics and evolutionary branching[END_REF].

Here, we restrict ourselves to representing the mutations by a diffusion operator with intensity µ 2 , a very small rate. According to the mathematical theory in [START_REF] Diekmann | The dynamics of adaptation: an illuminating example and a Hamilton-Jacobi approach[END_REF][START_REF] Perthame | Dirac concentrations in Lotka-Volterra parabolic PDEs[END_REF], it is natural to rescale time so that the new timescale unit is 1/µ, very long timescale compared to the original 'generation' timescale. This leads to the competition model with mutations

     µ ∂ ∂t n ε (x, t) = n ε (x, t) a(x) + 1 ε K(x, y) R ε (y, t) -R in dy + µ 2 ∆n ε , µ ∂ ∂t R ε (y, t) = m(y) ε 2 R in (y) -R ε (y, t) -1 ε R ε (y, t) K(x, y)n ε (x, t)dx, (13)
Because both the uptake rate ε and the mutation rate µ can be considered as small, it is interesting to see how the solutions behave in the different regimes of smallness.

We can formally follow the lines of the analysis in section 3 and find direct competition with mutations as the limit of infinitely fast uptake rate

µ ∂ ∂t n(x, t) = n(x, t) a(x) -c(x, x ′ )n(x ′ , t)dx ′ + µ 2 ∆n. ( 14
)
One can also consider the small mutation rate and, assuming the initial data is well prepared, use the Hopf-Cole unknowns u µ = µ ln(n ε ), u 0 µ = µ ln(n 0 ). This leads now to study the equation on the limit u ε (x, t) of u µ (x, t) and on the limit measure n ε as µ → 0. Following formally [START_REF] Diekmann | The dynamics of adaptation: an illuminating example and a Hamilton-Jacobi approach[END_REF][START_REF] Perthame | Dirac concentrations in Lotka-Volterra parabolic PDEs[END_REF], one finds the constrained Hamilton-Jacobi equation andn ε is supported in the zeroes of u ε (usually points).

     ∂ ∂t u ε = a(x) + 1 ε K(x, y) R ε (y, t) -R in dy + | ∂uε ∂x | 2 , max x∈R u ε (x, t) = 0 ∀t ≥ 0, m(y) ε 2 R in (y) -R ε (y, t) -1 ε R ε (y, t) K(x, y)n ε (x, t)dx = 0,
This can be further analyzed in the regime ε small and leads to

∂ ∂t u = a(x) + c(x, x ′ )n(x ′ , t)dx ′ + ∂u ∂x 2 , max x∈R u(x, t) = 0 ∀t ≥ 0,
still with the information that the measure n(t) is supported by the points where u(t) vanishes. This is also the limit of ( 14) in the regime of small µ.

We can conclude that the formal analysis of small mutations, both for the chemostat model and the direct competition model, is compatible with the multiscale analysis in section 3 that relates both models. Of course a rigorous analysis again requires mathematical developments, in particular appropriate estimates,which are beyond the scope of the present paper. This is the regime of interest that we choose later in section 6 for numerical illustration. In this regime, we recover also, at a population level, the results of standard adaptive dynamics [START_REF] Geritz | Evolutionarily singular strategies and the adaptive growth and branching of the evolutionary tree[END_REF][START_REF] Diekmann | A beginner's guide to adaptive dynamics[END_REF] and the references therein.

Lyapunov functionals for the two competition models

The large time behaviour of solutions to (2) has been studied in [START_REF] Mirrahimi | Evolution of species trait through resource competition[END_REF]. It is proved that steady states cannot be globally positive (n ε , R ε ) and they have to be either Dirac masses (speciation) or continuous with a support of n ε that is small enough (except when the solution goes extinct that might happen if renewal/death rates are too high). When continuous, the steady state globally attracts all trajectories if they satisfy a particular sign property characterized the so-called Evolutionary Stable Distribution (ESD in short), a notion that we recall below. The proof relies on a Lyapunov functional which has also been proved to exist for the direct competition model in [START_REF] Jabin | On selection dynamics for competitive interactions[END_REF] under the condition of positivity of a certain operator (see also [START_REF] Champagnat | Convergence to equilibrium in competitive Lotka-Volterra and chemostat systems[END_REF] for a similar study of a model with finite number of resources and consumer traits).

Our interest here is to understand the relation between the two Lyapunov functionals, for (2) and (3), and to understand why the operator positivity condition is important for direct competition models but does not appear in models of competition for resources.

We first recall that an ESD is defined as Definition 5.1 (Evolutionary Stable Distribution for (3), [START_REF] Jabin | On selection dynamics for competitive interactions[END_REF]) A nonnegative bounded measure n is called an ESD for the direct competition equation (3)

a(x) -c(x, x ′ )n(x ′ )dx ′ = 0 ∀x ∈ Supp n, (15) a
(x) -c(x, x ′ )n(x ′ )dx ′ ≤ 0 ∀x ∈ R \ Supp n. ( 16
)
Definition 5.2 (Evolutionary Stable Distribution for (2), [START_REF] Jabin | On selection dynamics for competitive interactions[END_REF][START_REF] Mirrahimi | Evolution of species trait through resource competition[END_REF]) A state is (n ε , R ε ) is called an ESD for the competition for resources equation (2) if n ε is a nonnegative bounded measure and

a(x) + 1 ε K(x, y)[R ε (y) -R in ]dy = 0 ∀x ∈ Supp n ε , (17)
a(x) + 1 ε K(x, y)[R ε (y) -R in ]dy ≤ 0 ∀x ∈ R \ Supp n ε , (18) m(y)
ε [R in (y) -R ε (y)] = R ε (y) K(x, y)n ε (x)dx ∀y ∈ R. (19)
We also recall the positivity condition which is important for the direct competition model (3) to have a unique ESD and to admit a Lyapunov functional [START_REF] Jabin | On selection dynamics for competitive interactions[END_REF].

For the model with the competition for resources a weaker assumption is enough to prove the uniqueness of ESD.

Proposition 5.4 (Uniqueness of ESD for (2)) Assume (5)- [START_REF] Champagnat | From individual stochastic processes to macroscopic models in adaptive evolution[END_REF]. Let (n 1 , R 1 ) and (n 2 , R 2 ) be two evolutionary stable distributions for [START_REF] Abrams | Competition-similarity relationships and the nonlinearity of competitive effects in consumer-resource systems[END_REF]. Then for all

y ∈ R, R 1 (y) = R 2 (y). If moreover K(x, y) is such that ∀g ∈ M 1 (R) \ {0}, K(x, y)g(x)dx ≡ 0, (21)
then there exists at most one unique evolutionary stable distribution for (2).

Proof. To prove the uniqueness of ESD for (2), we follow the method used in [START_REF] Jabin | On selection dynamics for competitive interactions[END_REF][START_REF] Champagnat | Convergence to equilibrium in competitive Lotka-Volterra and chemostat systems[END_REF] for the direct competition model. Let (n 1 , R 1 ) and (n 2 , R 2 ) two evolutionary steady distributions. Using ( 17)- [START_REF] Macarthur | Species packing and competitive equilibria for many species[END_REF] we write

n 1 a(x) + 1 ε K(x, y)[R 2 (y) -R in ]dy dx ≤ 0, n 2 a(x) + 1 ε K(x, y)[R 1 (y) -R in ]dy) dx ≤ 0, -n i a(x) + 1 ε K(x, y)[R i (y) -R in ]dy dx = 0, for i = 1, 2.
By adding the above inequalities we obtain

K(x, y) (n 1 (x) -n 2 (x)) R 2 (y) -R 1 (y) dydx ≤ 0.
Replacing the values of R 1 and R 2 we obtain

K(x, y) m(y) ε (n 1 (x) -n 2 (x)) R in (y) m(y) ε + K(x ′ , y)n 2 (x ′ )dx ′ - R in (y) m(y) ε + K(x ′ , y)n 1 (x ′ )dx ′ dydx ≤ 0,
and thus

m(y) ε R in (y) m(y) ε + K(x ′ , y)n 2 (x ′ )dx ′ m(y) ε + K(x ′ , y)n 1 (x ′ )dx ′ K(x, y) (n 1 (x) -n 2 (x)) dx 2 dy ≤ 0. It follows that K(x, y)n 1 (x)dx = K(x, y)n 2 (x)dx, a.e. (22)
and thus R 1 (y) = R 2 (y), a.e.. Moreover if K(x, y) satisfies ( 21), we obtain n 1 -n 2 = 0, in the sense of measures.

For an ESD and following [START_REF] Mirrahimi | Evolution of species trait through resource competition[END_REF], we define the Lyapunov functional for the model of competition for resources as

S cr (t) = -n ε (x) ln n ε (x, t)dx -R ε (y) ln R ε (y, t)dy + n ε (x, t)dx + R ε (y, t)dy.
The dissipation associated with this functional is given by the inequality

dScr dt (t) := D cr (t) = - m(y)R in (y) ε 2 Rε(y) Rε(y,t) R ε (y) -R ε (y, t) 2 dy + n ε (x, t) a(x) + 1 ε K(x, y)[R ε (y) -R in (y)]dy dx ≤ 0. ( 23
)
Because we expect that, according to the proof of Proposition 3.1, the expansion holds R ε (y, t) = R in (y) + O(ε), the limiting Lyapunov functional is reduced (up to an additive constant) to S dc (t) = -n(x) ln n(x, t)dx + n(x, t)dx. This is indeed the Lyapunov functional used in for direct competition but d dt S dc (t) is negative only when the positivity condition [START_REF] Mirrahimi | Evolution of species trait through resource competition[END_REF] holds true. This condition appears naturally in our framework because we can compute the dissipation associated with S dc (t)

dS dc dt (t) := D dc (t)
A direct computation of D dc using (3) is of course also possible but is less instructive than an expansion in ε of D cr that uses simply

R ε (y) = R in (y) - εR ε (y) m(y) K(x, y)n ε (x)dx.
In the limit ε → 0, we obtain

D dc (t) = -R in (y) m(y) K(x, y) n(x, t) -n(x) 2 dy + n(x, t) a(x) -K(x, y) R in (y) m(y) K(x ′ , y)n(x ′ )dx ′ dy dx. (24)
Using the expression of c(x, x ′ ) in ( 9) yields the usual dissipation for the direct competition model

D dc (t) = - c(x, x ′ ) n(x, t) -n(x) n(x ′ , t) -n(x ′ ) dx dx ′ + n(x, t) a(x) -c(x, x ′ )n(x ′ )dx ′ dx.
The particular form of c(•, •) in ( 9) together with [START_REF] Perthame | Dirac concentrations in Lotka-Volterra parabolic PDEs[END_REF] ensures that the integral with the quadratic term in n -n is always positive (we referred to that as operator positivity) and the definition of an ESS makes that the linear term also gives a nonpositive contribution.

Numerical illustration

How good is the approximation of competition through resources by direct competition? Beyond the pure theoretical statement in section 3, this can be illustrated thanks to some numerical simulations. We have performed such comparisons in the case with mutations given by [START_REF] Diekmann | The dynamics of adaptation: an illuminating example and a Hamilton-Jacobi approach[END_REF]. We assume that a resource uptake kernel and a distribution of resource supply are Gaussian. A trait-dependent (and competition-independent) growth rate takes the maximum at x = 0. We have used the coefficients given as follows

K(x, y) = 1 σ K √ 2π exp - (x -y) 2 2σ 2 K , R in (y) = M in σ in √ 2π exp(- y 2 2σ 2 in ), a(x) = 1 -x 2 , ( 25
)
and m(y) is taken as a constant. See section 2 for the converted kernel of direct competition. Throughout this section we have taken σ K = σ in = .5, µ = 0.005 and we vary ε, m and M in .

The initial data n 0 is a Gaussian centered at x = -0.8 with its variance equal to the mutation rate µ (in accordance with the analysis in section 4) and R is initially chosen equal to R in . With all our choices of the remaining parameters ε, m, M in below, the solution is always initially monomorphic and undergoes a dimorphic branching, then it stabilizes as depicted in Figure 1.

We first compare the dynamics of the full model [START_REF] Diekmann | The dynamics of adaptation: an illuminating example and a Hamilton-Jacobi approach[END_REF] and that of the approximated model [START_REF] Geritz | Evolutionarily singular strategies and the adaptive growth and branching of the evolutionary tree[END_REF]. To do so, we set m = M in = 1 and studied two different values for the parameter ε, namely ε = 0.1 and ε = 0.001. For ε = 0.1, the relative error max |R-R in | R in = 0.18 was significantly large so the equilibrium distribution of resource R ≈ R in was not achieved in this case. As we decrease ε to ε = 0.001, we obtained max |R-R in | R in = 0.0018 and the resource distribution was well approximated by R ≈ R in ; thus, When the ratio is preserved (even though coefficients differ by a factor 10) the solutions are very close. But a small variation of the coefficients, that also changes the ratio, induces a visible difference on the solutions.

we expect that our reduction to direct competition model should give a good approximation. Numerical comparisons for these cases are depicted in Figure 2, showing that the dimorphic distributions are well conserved in both solutions even though the total population is under-estimated in the direct competition model compared to ε = 0.1 by a factor of approximately 25%.

The competition kernel [START_REF] Champagnat | Convergence to equilibrium in competitive Lotka-Volterra and chemostat systems[END_REF] in the direct competition approximation has a remarkable property that it only depends upon the ratio R in /m. It implies that solution to [START_REF] Diekmann | The dynamics of adaptation: an illuminating example and a Hamilton-Jacobi approach[END_REF] depends only mildly on this ratio. This prediction from our analysis is confirmed by numerical calculations (Figure 3).

The scales in McArthur's asymptotics

After rescaling of (4), we consider the limit of

     ∂ ∂t n ε (x, t) = b(x)n ε (x, t) K(x, y)R ε (y, t)dy -d(x) , ε ∂
∂t R ε (y, t) = R ε (y, t) m(y)(1 -Rε(y,t) Rcc(y) ) -K(x, y)n ε (x, t)dx ,

Putting ε = 0, McArthur in [START_REF] Macarthur | Species packing and competitive equilibria for many species[END_REF] builds on the formal limit 0 = m(y)(1-Rε(y,t) Rcc(y) )-K(x, y)n ε (x, t)dx. However, as noticed already in [START_REF] Abrams | Coexistence and limiting similarity of consumer species competing for a linear array of resources[END_REF][START_REF] Abrams | Competition-similarity relationships and the nonlinearity of competitive effects in consumer-resource systems[END_REF], this is not correct because when this rate is negative, R ε (y, t) vanishes and thus the asymptotic expression is R(y, t) = R cc (y) 1 -K(x, y) m(y) n(x, t)dx

As a consequence, [START_REF] Abrams | Coexistence and limiting similarity of consumer species competing for a linear array of resources[END_REF][START_REF] Abrams | Competition-similarity relationships and the nonlinearity of competitive effects in consumer-resource systems[END_REF] concluded that the behaviour of the resource-competition model and of the Lotka-Volterra one can differ significantly but did not attempt to clarify the conditions for the timescaling argument to work. Here we propose another route which is to introduce another timescale for main resource consumption and guarantee it will not get extinct.

To fix this shortcoming, we may agin introduce two different timescales, as we proposed earlier

Then the first order expansion in the equation on R ε is positive for ε small enough R ε (y, t) = R cc (y) 1 -ε K(x, y) m(y) n ε (x, t)dx + O(ε 2 ).

Once inserted in equation (29), we find the correct asymtotics ∂ ∂t n ε (x, t) = b(x)n ε (x, t) a(x) -c(x, x ′ )n ε (t, x ′ )dx ′ with c(x, x ′ ) as defined in (28).

Definition 5 . 3 (

 53 Operator positivity condition) The function c(x, y) satisfies a positivity condition, if ∀g ∈ M 1 (R) \ {0}, c(x, y)g(x)g(y)dxdy > 0.

Figure 1 :

 1 Figure1: With our choice of parameters later (here ε = 0.001, m = 10, M in = 10), the dynamics always undergo a branching from a monomorphic to a dimorphic population. This figure depicts the typical contour lines of the solution to (13) (horizontal axis is x, vertical axis is time).

Figure 2 :

 2 Figure 2: Comparisons between the model of competition for resources, with m = M in = 1 and ε = 0.1, (dotted curve) and the direct competition model (continuous line, in fact ε = 0.001). Left: the dimorphic population density as a function of the trait x for large times. Right: total population n(x, t)dx as a function of time.

Figure 3 :

 3 Figure3: These figures illustrate that the direct competition kernel only depends on the ratio R in /m and thus we can expect that the solutions to the model of competition for resource also does so. (Left) we compare for ε = 0.05, the population density solutions with m = M in = 1 (dotted line) and with m = M in = 10 (continuous line). (Right) we compare for ε = 0.05 the solutions with m = M in = 1 (dotted line) and with m = 1.5, M in = 1 (continuous line). When the ratio is preserved (even though coefficients differ by a factor 10) the solutions are very close. But a small variation of the coefficients, that also changes the ratio, induces a visible difference on the solutions.

+

  where |a| + denotes the positive part of a. Inserting this formula in the equation for n ε gives us the asymptotic model∂ ∂t n(x, t) = b(x)n(x, t) K(x, y)R cc (y) 1 -K(x ′ , y) m(y) n(x ′ , t)dx ′ + dy -d(x) .(27)Only in the regime where resources are never exhausted (but there is no easy a priori characterization; this depends on the initial data and may change along the dynamics) one recovers direct competition (3) with c(x, x ′ ) = K(x, y) R cc (y) m(y) K(x ′ , y)dy, a(x) = 1 ε K(x, y)R cc (y)dy -d(x).

  ε (x, t) = b(x)n ε (x, t) 1 ε K(x, y)R ε (y, t)dy + a(x) -1 ε K(x, y)R cc (y, t)dy , ε 2 ∂ ∂t R ε (y, t) = R ε (y, t) m(y)(1 -Rε(y,t) Rcc(y) ) -ε K(x, y)n ε (x, t)dx ,

Acknowledgment The three authors thank Readilab, LIA 197 CNRS, for supporting their collaborations and also Meiji University and UPMC. J.Y.W. is partly supported by Glocal COE program "Formation and Development of Mathematical Sciences Based on Modeling and Analysis". S. M. benefits from a 2 year "Fondation Mathématique Jacques Hadamard" (FMJH) postdoc scholarship. She would like to thank Ecole Polytechnique for its hospitality.

The authors would like also to thank Géza Meszéna for careful review of this paper, valuable comments, several references and interpretations. We borrowed some sentences from the report.


Antonia Maria Masucci
email: antonia.masucci@inria.fr

Alonso Silva
email: alonso.silva@alcatel-lucent.com

Strategic Resource Allocation for Competitive Influence in Social Networks

One of the main objectives of data mining is to help companies determine to which potential customers to market and how many resources to allocate to these potential customers. Most previous works on competitive influence in social networks focus on the first issue. In this work, our focus is on the second issue, i.e., we are interested on the competitive influence of marketing campaigns who need to simultaneously decide how many resources to allocate to their potential customers to advertise their products. Using results from game theory, we are able to completely characterize the optimal strategic resource allocation for the voter model of social networks and prove that the price of competition of this game is unbounded. This work is a step towards providing a solid foundation for marketing advertising in more general scenarios.

Introduction

In contrast to mass marketing, where a product is promoted indiscriminately to all potential customers, direct marketing promotes a product only to customers likely to be profitable. The groundbreaking works of Domingos and Richardson [START_REF] Domingos | Mining the network value of customers[END_REF][START_REF] Richardson | Mining knowledge-sharing sites for viral marketing[END_REF] incorporated the influence of peers on the decision making process of potential customers deciding between different products or services promoted by competing marketing campaigns through direct marketing. This aggregated value of a customer has been called the network value of a customer. If each customer was making a buying decision independently of all other customers, then we should only consider the intrinsic value of a customer (i.e., the expected profit from sales to him). However, an individual's decision to buy a product or service is often strongly influenced by his friends, acquaintances, etc. A customer whose intrinsic value is lower than the cost of marketing may be worth marketing to when his network value is considered. Conversely, marketing to a profitable consumer may be redundant if network effects already make him very likely to buy [START_REF] Domingos | Mining the network value of customers[END_REF].

Most of the existing literature assumes there is an incumbent that holds the market and a challenger who needs to allocate advertisement through direct marketing for certain individuals in order to promote the challenger product or service. Notable exceptions to that trend are the works on competitive influence in social networks of Bharathi et al. [START_REF] Bharathi | Competitive influence maximization in social networks[END_REF], Sanjeev and Kearns [START_REF] Goyal | Competitive contagion in networks[END_REF], He and Kempe [START_REF] He | Price of anarchy for the n-player competitive cascade game with submodular activation functions[END_REF], Borodin et al. [START_REF] Borodin | Threshold models for competitive influence in social networks[END_REF] and Chasparis and Shamma [START_REF] Chasparis | Control of preferences in social networks[END_REF]. Bharathi et al. [START_REF] Bharathi | Competitive influence maximization in social networks[END_REF] proposed a generalization of the independent cascade model [START_REF] Goldenberg | Talk of the network: A complex systems look at the underlying process of word-ofmouth[END_REF] and gave a (1 -1/e) approximation algorithm for computing the best response to an already known opponent's strategy and proved that the price of competition of the game (resulting from the lack of coordination among the agents) is at most 2. Sanjeev and Kearns [START_REF] Goyal | Competitive contagion in networks[END_REF] considered two independent functions denoted switching function and selection function. The switching function takes into account the probability of a consumer switching from non-adoption 1 to adoption and the selection function specifies, conditional on switching, the probability that the consumer adopts one of them. Both players simultaneously choose some number of nodes to initially seed. The authors make the simplifying assumption that once a node is infected, it never switches again, and proceed to study some specific families of switching and adoption functions. He and Kempe [START_REF] He | Price of anarchy for the n-player competitive cascade game with submodular activation functions[END_REF] motivated by [START_REF] Goyal | Competitive contagion in networks[END_REF] studied the price of anarchy of that framework and found an upper bound of 2 on that price. Borodin et al. [START_REF] Borodin | Threshold models for competitive influence in social networks[END_REF] showed that for a broad family of competitive influence models is NP-hard to achieve an approximation that is better that the square root of the optimal solution. Chasparis and Shamma [START_REF] Chasparis | Control of preferences in social networks[END_REF] found optimal advertising policies using dynamic programming based on the models of [START_REF] Dubey | Competing for customers in a social network[END_REF] and [START_REF] Friedkin | Norm formation in social influence networks[END_REF].

In the present work, our focus is different from previously described works where the focus was to which potential customers to market, assuming that we have knowledge about the cost of adoption of potential customers, while the focus in our work is on how many resources to allocate to potential customers for them to prefer one product or service versus another. We are interested on the scenario when two competing marketing campaigns need to simultaneously decide how many resources to allocate to potential customers to advertise their products. The process and dynamics by which influence is spread is given by the voter model.

Under that model, our main results are the following:

Theorem 1. Given a graph G = (V, E) representing a social network of n potential customers. The symmetric strategic resource allocation problem by only taking into account the intrinsic value of the customers, for any target time τ , is given by a probability distribution function F * of x ∈ ∆ n-1 , such that each vector coordinate x i is uniformly distributed on [0, 2B/n] for i ∈ {1, . . . , n}, where B is the available budget and ∆ n-1 is the set of available allocations.

Theorem 2. Given a graph G = (V, E) representing a social network of n potential customers. The symmetric strategic resource allocation problem for target time τ has a solution given by a probability distribution function F * τ of x ∈ ∆ n-1 , such that each vector coordinate x i is uniformly distributed on [0, 2B n j=1 M τ (i, j)] for i ∈ {1, . . . , n}, where B is the available budget, M is the normalized transition matrix and ∆ n-1 is the set of available allocations. Moreover, the long term case has a solution given by a probability distribution function F * ∞ of x ∈ ∆ n-1 , such that each vector coordinate x i is uniformly distributed on [0, Bd i /|E|] for i ∈ {1, . . . , n}, where B is the available budget, d i is the degree of potential customer i, |E| is the total number of edges of the graph and ∆ n-1 is the set of available allocations.

Theorem 3. The price of competition of the game (resulting from lack of coordination among the agents) is unbounded.

Theorem 1 gives an optimal policy for the allocation of resources in the case when we consider potential customers in isolation or their intrinsic value, while Theorem 2 gives an optimal policy for the allocation of resources in the case when we also include the network value of potential customers. Theorem 3 gives the price of competition (resulting from the lack of coordination among the agents) for the strategic allocation problem. We notice that this is a very different result than the one obtained by Bharathi et al. [START_REF] Bharathi | Competitive influence maximization in social networks[END_REF] where they found that the price of competition is at most a factor of 2 when the focus is on which potential customers to recruit.

Related Work

The (meta) problem of influence maximization was first defined by Domingos and Richardson [START_REF] Domingos | Mining the network value of customers[END_REF][START_REF] Richardson | Mining knowledge-sharing sites for viral marketing[END_REF]. They studied this problem in a probabilistic setting and provided heuristics to compute an influence maximizing set. Following this work, Kempe et al. [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF] and Mossel and Roch [START_REF] Mossel | On the submodularity of influence in social networks[END_REF], based on the results of Nemhauser et al. [START_REF] Nemhauser | An analysis of approximations for maximizing submodular set functions i[END_REF] and Vetta [START_REF] Vetta | Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions[END_REF], proved that for very natural activation functions (monotone and submodular or in economic terms, with decreasing marginal utility), the function of the expected number of active nodes at termination is a submodular function and thus can be approximated through a greedy approach with a (1-1/e-ε)-approximation algorithm for the spread maximization set problem. A slightly different model but with similar flavor, the voter model, was introduced by Clifford and Sudbury [START_REF] Clifford | A model for spatial conflict[END_REF] and Holley and Liggett [START_REF] Holley | Ergodic theorems for weakly interacting infinite systems and the voter model[END_REF]. In that model of social network, Even-Dar and Shapira [START_REF] Even-Dar | A note on maximizing the spread of influence in social networks[END_REF] found an exact solution to the spread maximization set problem when all the nodes have the same cost and provided an FPTAS (Fully Polynomial Time Approximation Scheme is an algorithm that for any ε approximates the optimal solution up to an error (1 + ε) in time poly(n/ε)) for the case in which different nodes may have different costs.

In this work, we study the case when two marketing campaigns competing to promote a product or service need to decide how many resources to allocate to potential customers to advertise their product or service. Other works related to competitive influence where the already described [START_REF] Bharathi | Competitive influence maximization in social networks[END_REF][START_REF] Borodin | Threshold models for competitive influence in social networks[END_REF][START_REF] Chasparis | Control of preferences in social networks[END_REF][START_REF] Goyal | Competitive contagion in networks[END_REF][START_REF] He | Price of anarchy for the n-player competitive cascade game with submodular activation functions[END_REF].

To study this case, we use recent advances of game theory, and in particular of Colonel Blotto games. In the simplest version of the Colonel Blotto game, two generals want to capture three equally valued battlefields. Each general disposes of one divisible unit of military resources. The generals have to simultaneously allocate these resources across the three battlefields. A battlefield is captured by a general if he allocates more resources there than his opponent. The goal of each general is to maximize the number of captured battlefields.

The relationship between Colonel Blotto games and our work is the following. We establish a parallel between the marketing campaigns and the generals; and between the potential customers and the battlefields. Each marketing campaign needs to strategically allocate advertising resources to outperform the competing marketing campaign. This needs to be done while knowing that the competing marketing campaign is trying to do the same. It is thus a typical situation in which game theory comes into play. In our case, of course, we will not be dealing with three potential customers so we need to extend this case to include any number of potential customers. By including the network value of customers, each potential customer will not be equally valued so we will need also to consider different payoffs for different potential customers.

The Colonel Blotto game, was first solved for the case of three battlefields by Borel [START_REF] Borel | La théorie du jeu et les équations intégrales à noyau symétrique[END_REF][START_REF] Borel | Application de la théorie des probabilités aux jeux de hasard[END_REF]. For the case of equally valued battlefields, also known as homogeneous battlefields case, this result was generalized for any number of battlefields by Gross and Wagner [START_REF] Gross | A continuous colonel blotto game[END_REF]. Roberson [START_REF] Roberson | The colonel blotto game[END_REF] focused on the case of homogeneous battlefields and different budgets (also known as asymmetric budgets case). Gross [START_REF] Gross | The symmetric blotto game[END_REF] proved the existence and a method to construct the joint probability distribution. Laslier and Picard [START_REF] Laslier | Distributive politics and electoral competition[END_REF] and Thomas [START_REF] Thomas | N-dimensional blotto game with asymmetric battlefield values[END_REF] provided alternative methods to construct the joint distribution by extending the disc method proposed by Gross and Wagner [START_REF] Gross | A continuous colonel blotto game[END_REF]. We will extensively use the work of Gross [START_REF] Gross | The symmetric blotto game[END_REF] to derive our results.

The plan of this work is as follows. In Section 2, we provide some preliminaries about the tools we use to find the optimal strategy. The reader acquainted with game theory and Colonel Blotto games can skip this section. In Section 3, we explain the voter model of social networks. In Section 4, we derive the main results of this work, and in Section 5, we conclude this work and provide future perspectives for continuing our work.

Preliminaries on game theory

Colonel Blotto games (or Divide a Dollar games) in their classic version are a class of two-person zerosum games, in which both players need to simultaneously allocate limited resources over several objects. Colonel Blotto games are usually described in a military context where the limited resources are troops and the objects are battlefields. In that context, the player devoting the most troops (or resources) to a battlefield (or object) captures that battlefield (and the payoff associated with that battlefield) and its total payoff is the sum of the individual payoffs across captured battlefields. To analyze these games, we need to introduce some basic concepts in game theory.

In this subsection, we follow the notation of [START_REF] Vetta | Nash equilibria in competitive societies, with applications to facility location, traffic routing and auctions[END_REF]. Consider we have two agents (or players) and disjoint groundsets V 1 and V 2 . Each element in V i represents an act that agent i may make, i ∈ {1, 2}, in our case, the allocation of troops to a battlefield. Let a i ⊆ V i be an action (set of acts) available to agent i, for example, the set of troops allocations across battlefields. We want to restrict the set of actions an agent may make; thus we may not allow every subset of V i to be a feasible action. We let A i = {a i ⊆ V i : a i is a feasible action} be the set of all available actions to agent i. In our case, the set of possible allocations is limited by the budget of the agents. We call A i the action space for agent i.

A pure strategy is one in which the agent decides to carry out a specific action. A mixed strategy is one in which the agent decides upon an action according to some probability distribution. The strategy space S i of agent i is the set of mixed strategies. We let

A = A 1 × A 2 , S = S 1 × S 2 , and V = V 1 ∪ V 2 .
Given an action set A ∈ A, let A⊕a ′ i denote the action set obtained if agent i changes its action from a i to a ′ i . Similarly, given a strategy set S ∈ S, let S ⊕ s ′ i denote the strategy set obtained if agent i changes its strategy from s i to s ′ i . For every agent i, there is a private utility function α i : 2 V → R. The expected value of α i (S) on the strategy set S, denoted ᾱi (S), is given by ᾱi (S) = A∈A α i (A)P(A|S), where P(A|S) is the probability that action set A is implemented given that the agents are using the strategy set S. The goal of each agent is to maximize its expected private utility. We say that a set of strategies S ∈ S is a Nash equilibrium if no agent has an incentive to change strategy. That is, for any agent i,

ᾱi (S) ≥ ᾱi (S ⊕ s ′ i ) ∀s ′ i ∈ S i .
We say that a Nash equilibrium is a pure strategy Nash equilibrium if, for each agent i, s i is a pure strategy. Otherwise, we say that the Nash equilibrium is a mixed strategy Nash equilibrium. Throughout this work the term equilibrium refers to Nash equilibrium, although, since the game is a zero sum game, these equilibrium strategies are also optimal strategies.

The following result, due to Nash [START_REF] Nash | Non-cooperative games[END_REF], shows that there exists at least one Nash equilibrium for any finite game.

Theorem 4 (Nash [START_REF] Nash | Non-cooperative games[END_REF]). Any finite, k-person, non-co-operative game has at least one Nash equilibrium.

Colonel Blotto games

In this subsection, we include the notation of [START_REF] Thomas | N-dimensional blotto game with asymmetric battlefield values[END_REF]. As previously said in Section 1, in the simplest version of the Colonel Blotto game, two generals want to capture three equally valued battlefields. Each general disposes of one divisible unit of military resources and the generals have to simultaneously allocate these resources across the three battlefields.

A battlefield is captured by a general if he allocates more resources there than his opponent and the goal of each general is to maximize the number of captured battlefields.

In that game, a pure strategy for a player, denoted X, is a 3-dimensional allocation vector x = (x 1 , x 2 , x 3 ) where x i is the amount of resources allocated to the ith battlefield for i ∈ {1, 2, 3}. The set of pure strategies is the 2-dimensional unit simplex

∆ 2 = {(x 1 , x 2 , x 3 ) : x 1 , x 2 , x 3 ≥ 0 and x 1 +x 2 +x 3 = 1}. A mixed strategy is a tri- variate distribution function F : ∆ 2 → [0, 1].
Similarly for his enemy, denoted Y , we define y the allocation vector, y i the proportion of resources allocated to the ith battlefield for i ∈ {1, 2, 3}, ∆ 2 the set of pure strategies and G : ∆ 2 → [0, 1] a mixed strategy.

The natural extension of the classic version of the Colonel Blotto game is to study the case with n battlefields where each captured battlefield gives a different payoff. Consider that we have two players, denoted X and Y , and n objects. Player X has budget B X and it can allocate for an object i a proportion of his budget x i for 1 ≤ i ≤ n. Similarly, player Y has budget B Y and it can allocate for an object i a proportion of his budget y i for 1 ≤ i ≤ n. In this work, we limit ourselves to the case when both players have the same total divisible budget, i.e., B X = B Y , and without loss of generality we consider this budget to be equal to 1. We consider this to simplify the derivations, however it is easy to derive the results by considering the budgets to be equal to B instead of 1.

For the general case, a pure strategy for player X can be written as an n-dimensional

allocation vector x = (x 1 , x 2 , . . . , x n ) with n i=1 x i = 1, x i ∈ [0, 1],
where x i represents the fraction of budget allocated to front i. Thus, the set of pure strategies is the (n -1)-dimensional simplex

∆ (n-1) = {(x 1 , . . . , x n ) : x i ≥ 0, 1 ≤ i ≤ n and n i=1 x i = 1}. A mixed strategy is an n- variate distribution function F : ∆ (n-1) → [0, 1]
. Let F i denote the ith onedimensional marginal of F , i.e., the unconditional distribution of x i .

The object i has an associated non-negative payoff A i for 1 ≤ i ≤ n. We denote the sum of the payoffs of all objects by A, i.e.,

A = n i=1 A i .
For all i, let us define

a i = A i A ,
which represents the relative value of object i and note that

n k=1 a i = 1.
We assume that the player devoting the most resources to a battlefield captures that battlefield. Ties are resolved by flipping a coin.

For any pair (x, y) of pure strategies, the excess aggregate value for player X, denoted by g(x, y), of objects captured by player X if he plays the pure strategy x while player Y plays the pure strategy y is given by

g(x, y) = n i=1 a i sgn(x i -y i ), (1)
where sgn(•) is the sign function defined as

sgn(u) =    1 if u > 0, 0 if u = 0, -1 if u < 0. (2)
The excess aggregate value g(x, y) is the gain for pure strategy x against pure strategy y. Definition 1. We define the Colonel Blotto game as the two-player, zero-sum game defined by the payoff function g.

If F and G are two mixed strategies the payoff to mixed strategy F against mixed strategy G is:

K(F, G) = x∈∆ (n-1) y∈∆ (n-1)
g(x, y) dF (x) dG(y).

(3)

The expected payoff for mixed strategy F against pure strategy y is given by

K(y) = x∈∆ (n-1) g(x, y) dF (x). ( 4
)
The game is symmetric so to prove that a strategy is optimal we only need to show that K(y) ≥ 0 for every y.

From eq. ( 1) and eq. ( 4), we have that

K(y) = n i=1 a i (P(x i > y i ) -P(y i > x i )) . (5)
We assume n ≥ 2 otherwise the game always ends in a tie.

We observe the following:

(a) For the case n = 2 (originally solved in [START_REF] Gross | A continuous colonel blotto game[END_REF]), it is optimal to put all the budget in the object of maximum value, i.e., in i * ∈ {1, 2} such that a i * = max{a 1 , a 2 }. In case a 1 = a 2 , choose any of them. Indeed, without loss of generality assume the second object gives higher payoff than the first one, i.e. a 2 ≥ a 1 , then the expected payoff against a strategy y = (y, 1 -y) will be a 1 sgn(-y) + a 2 sgn(y) ≥ 0, which always gives a non-negative payoff for all y ∈ [0, 1].

(b) For the case when there exists an object i with relative value a i ≥ 1/2, then the optimal strategy is to put all the budget in object i. Indeed, without loss of generality assume the last object has relative value a n ≥ 1/2, then the expected payoff against a strategy y = (y 1 , y 2 , . . . , y n ) will be

n-1 i=1 a i sgn(-y i ) + a n sgn n-1 i=1 y i ≥ 0,
which always gives a non-negative payoff.

(c) For the case when there exists an object i with relative value a i = 0, then from the payoff function, the optimal strategy is not to put any budget in object i.

From (b) and (c), in the following we assume that 0 < a i < 1/2, ∀i ∈ {1, . . . , n},

or equivalently that

0 < A i < j =i
A j , ∀i ∈ {1, . . . , n}.

It can be shown that under the previous assumption for n > 2 there is no pure strategy Nash equilibrium in the general case. Indeed, consider a pure strategy x, select the object of minimum value where the pure strategy is not zero. Then x will lose with respect to the strategy y that allocates no resources to the i-th object and more resources to all the other objects, i.e.,

y i = 0, y j = x j + x i n -1 ∀j = i.
Therefore, we need to search for optimal mixed strategies. For the case of three battlefields, Gross and Wagner [START_REF] Gross | A continuous colonel blotto game[END_REF] proved the existence of a mixed strategy solution given as follows.

Theorem 5 (Gross and Wagner [START_REF] Gross | A continuous colonel blotto game[END_REF]). For n = 3, the Colonel Blotto game with heterogeneous battlefield values has a mixed strategy equilibrium in which the marginal distribution over front i is uniform on [0, 2a i ] for i ∈ {1, 2, 3}.

We need to construct a joint distribution such that each marginal distribution is uniform on [0, 2a i ] for i ∈ {1, 2, 3} and such that the sum of the values given by the marginal distributions is equal to 1. The difficulty comes from this last condition, otherwise we could always define a joint distribution from its marginal distributions. In the following, we show how this joint distribution can be constructed. In the case of three battlefields, there is a geometric construction of the joint n-variate distribution function with uniform marginal distribution functions.

Proof. We construct a non-degenerate triangle having sides of length a 1 , a 2 and a 3 (see Fig. 1), and then inscribe a circle within it and erect a hemisphere upon this circle. We notice that we can construct a non-degenerate triangle since a degenerate triangle would violate the assumption given by eq. ( 6). Then, we choose a point from a density uniformly distributed over the surface of the hemisphere and project this point straight down into the plane of the triangle (we denote by P the projected point over the plane). We then divide the forces in respective proportion to the triangular areas subtended by P and the sides, i.e., x 1 : x 2 : x 3 = A 1 : A 2 : A 3 (see Fig. 1).

Let F i (x i ) denote the respective marginal distribution function of Blotto's continuous mixed strategy F . Blotto's expectation from battlefield i is given by

a i [1 -F i (y i )] -a i F i (y i ) = a i [1 -2F i (y)],
and hence his total expectation is given by

K(y) = 3 i=1 a i [1 -2F i (y i )]. (7)
Let h i denote the altitude of the triangle of area A i subtended by P . From a well-known property of the surface area of a sphere, we see that h i is uniformly distributed over (0, 2r), r being the radius of the sphere. Now, A i = 1 2 a i h i , and hence A i is uniformly distributed over (0, a i r). Also, since x 1 + x 2 + x 3 = 1 and x 1 : x 2 : x 3 = A 1 : A 2 : A 3 , it follows that x i = Ai ∆ where ∆ is the area of the originally constructed triangle. Thus x i is uniformly distributed over (0, air ∆ ). But ∆ = 1 2 (a 1 r + a 2 r + a 3 r), hence x i is uniformly distributed over 0, 2ai a1+a2+a3 , i.e.,

F i (x i ) = min 1, a 1 + a 2 + a 3 2a i x i .
Consequently, from eq. ( 7),

K(y) = 3 i=1 a i 1 -2 min 1, a 1 + a 2 + a 3 2a i y i .
Note that if α > 0, y ≥ 0, then min(1, αy) ≥ αy, and hence For the case of any number of battlefields n, Gross [START_REF] Gross | The symmetric blotto game[END_REF] proved the existence and a method to construct such joint distributions.

K(y) ≥ 3 i=1 a i 1 - a 1 + a 2 + a 3 a i y i , = a 1 + a 2 + a 3 -(a 1 + a 2 + a 3 ) 3 i=1 y i = 0 since 3 i=1 y i = 1. a 2 a 1 a 3 h 1 A 2 P A 1 A 3
Theorem 6 (Gross [START_REF] Gross | The symmetric blotto game[END_REF]). Consider the Colonel Blotto Game with heterogeneous battlefield values. Let F * be a probability distribution of x ∈ ∆ n-1 such that each vector coordinate x i is uniformly distributed on [0, 2a i ] for i ∈ {1, . . . , n}. Then (F * , F * ) constitutes a symmetric Nash equilibrium.

We notice that Friedman [START_REF] Friedman | Game-theory models in the allocation of advertising expenditures[END_REF] used this solution for advertisement expenditures without considering the network value of customers. Robertson [START_REF] Roberson | The colonel blotto game[END_REF] showed that for homogeneous battlefield values (a i = 1/n, ∀i ∈ {1, . . . , n}) uniform univariate marginals are also a necessary condition for equilibrium. Laslier and Picard [START_REF] Laslier | Distributive politics and electoral competition[END_REF] and Thomas [START_REF] Thomas | N-dimensional blotto game with asymmetric battlefield values[END_REF] provided alternative methods to construct the joint distribution. In the following we will use Theorem 6 to the strategic resource allocation on the voter model of social networks.

Voter model

The voter model is one of the most natural probabilistic models to represent the diffusion of opinions in social networks. In each step, each potential customer changes its opinion by choosing one of its neighbors at random and adopting its neighbor's opinion.

The voter model is quite different from the threshold model [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Kempe | Influential nodes in a diffusion model for social networks[END_REF], however it still has the same key property that a person is more likely to change its opinion to the one held by most of its neighbors. It has another characteristic to its advantage, the fact that in the threshold models once a node adopts a product or service it stays with that product or service forever. These models are called monotone models of diffusion. However, the voter model allows to change preferences, which may be more suitable for non-monotone processes.

Let G = (V, E) be an undirected graph with selfloops where V is the set of nodes in the graph which represent the potential customers of the competing marketing campaigns and E is the set of edges which represent the influence between individuals. We consider that the graph G has n nodes, i.e. |V | = n. As we will see in the following, the use of the same notation n, as for the number of battlefields, is not a coincidence since each potential customer will represent a battlefield for competing marketing campaigns.

For a node v ∈ V , we denote by

N (v) the set of neighbors of v in G, i.e. N (v) = {u ∈ V : {u, v} ∈ E} and by d v the degree of node v, i.e. d v = |N (v)|.
We recall that the players of the game are the competing marketing campaigns and the nodes of the graph correspond to the potential customers. We label a node v ∈ V by its initial preference between different players, X or Y , denoted by function f 0 . We denote by f 0 (v) = 1 when node v ∈ V prefers the product promoted by marketing campaign X, f 0 (v) = -1 when node v prefers the product promoted by marketing campaign Y , and f 0 (v) = 0 when node v is indifferent between both products.

We assume that the quantity of marketing budget allocated to node i determines its initial preference, i.e.,

f 0 (i) =    1 if x i > y i , 0 if x i = y i , -1 if x i < y i .
We notice that f 0 (i) corresponds to sgn(x i -y i ) where sgn(•) is given by eq. ( 2). We also observe that since the bids are real numbers, ties have measure zero. However, in the unlikely event that bids coincide in the maximum, we choose uniformly at random the winner between both players. This defines a new function and for simplicity we use the same notation,

f 0 (i) =        1 if x i > y i , 1 if x i = y i and R = 1, -1 if x i = y i and R = 0, -1 if x i < y i ,
where R is a Bernoulli random variable with success probability equal to 1/2.

The evolution of the system will be described by the voter model. Starting from any arbitrary initial preference assignment to the vertices of G, at each time t ≥ 1, each node picks uniformly at random one of its neighbors and adopts its opinion. More formally, starting from any assignment f 0 : V → {-1, 1}, we inductively define

f t+1 (v) = 1 with prob. |{u∈N (v):ft(u)=1}| |N (v)| , -1 with prob. |{u∈N (v):ft(u)=-1}| |N (v)|
.

The objective function for player X is to maximize at a certain target time τ the expected number of nodes:

E v∈V f τ (v) .
We thus define the strategic resource allocation problem as follows.

Definition 2 (Competitive Influence). Let G = (V, E) be a graph with n nodes representing a social network with n potential customers. Consider two players, X and Y , which represent two competing marketing campaigns with equal budget B which need to simultaneously allocate resources across potential customers. A node i ∈ V with respective allocations x i and y i such that x i > y i (or y i > x i ) will choose the product or service proposed by player X (or Y ). Otherwise, if x i = y i , it will flip a coin to decide between both marketing campaigns. Then the strategic resource allocation problem is the problem of finding an initial assignment of resources x = (x 1 , x 2 , . . . , x n ) for player X that will maximize at a target time τ the expectation

E v∈V f τ (v) subject to the budget constraint v∈V x v ≤ B.

Results

In this section, we establish the main results of our work, we find the optimal marginal probability density function when we consider the intrinsic value of potential customers and when we consider the total value of potential customers by incorporating their network value. We also give a distance to compare both probability density functions.

We notice that in the voter model, the probability that node v adopts the opinion of one its neighbors u is precisely 1/|N (v)|. Equivalently, this is the probability that a random walk of length 1 that starts at v ends up in u. Generalizing this observation by induction on t, we obtain the following proposition.

Proposition 1 (Even-Dar and Shapira [START_REF] Even-Dar | A note on maximizing the spread of influence in social networks[END_REF]). Let p t u,v denote the probability that a random walk of length t starting at node u stops at node v. Then the probability that after t iterations of the voter model, node u will adopt the opinion that node v had at time t = 0 is precisely p t u,v .

Let M be the normalized transition matrix of G, i.e.

M (v, u) = 1/|N (v)| if u ∈ N (v).
By linearity of expectation, we have that for player X

E v∈V f τ (v) = v∈V (P[f τ (v) = 1] -P[f τ (v) = -1]) .
For a subset S ⊆ {1, . . . , n}, we denote by 1 S the 0/1 column vector whose ith entry is 1 if and only if i ∈ S. Then, the probability that a random walk of length t starting at u ends in v, is given by the (u, v) entry of the matrix M t , or equivalently, by 1 T {u} M t 1 {v} . Then

P[f t (v) = 1] = u∈V p t u,v P[f 0 (u) = 1] = u∈V 1 T {u} M t 1 {v} P[x u > y u ].
Similarly,

P[f t (v) = -1] = u∈V 1 T {u} M t 1 {v} P[x u < y u ].
Then

E v∈V f t (v) = v∈V u∈V 1 T {u} M t 1 {v} (P[x u > y u ] -P[x u < y u ]) . (8)
If we are interested only on the intrinsic value of potential customers, this case is equivalent to consider that each node is influenced only by itself, i.e.,

M (u, v) = 1 u = v, 0 u = v.
Equivalently, that M = I n×n , where I n×n is the n × n identity matrix. Then, for every target time τ we have that

E v∈V f τ (v) = u∈V (P[x u > y u ] -P[x u < y u ]) .
From equation ( 5), we notice that this case is equivalent to the homogeneous Colonel Blotto, i.e., with relative values a i = 1/n for 1 ≤ i ≤ n, and from Theorem 6, we are able to conclude Theorem 1.

If we consider a complete graph, then the normalized transition matrix is given by

M = 1 n      1 1 . . . 1 1 1 . . . 1 . . . . . . . . . 1 1 1 . . . 1      .
We notice that M t = M for all t ∈ N. Thus independently of the target time τ , the objective function for player X is to maximize:

E v∈V f τ (v) = u∈V (P[x u > y u ] -P[x u < y u ]) .
Similarly to the previous case, from eq. ( 5), we see that this particular case is equivalent to the homogeneous Colonel Blotto game and the solution is the same as in the intrinsic value case.

If we could only solve this challenge in the intrinsic case and the complete graph it would not be a compelling model. However, as we will see we can compute this when we are interested on much more general cases. Indeed, from eq. ( 8), redefining

a u = v∈V M t (u, v),
we have the optimal strategy from Theorem 6 and we conclude the first part of Theorem 2.

Recall the well known fact that for any graph G with self-loops, a random walk starting from any node v, converges to the steady state distribution after O(n 3 ) steps (see [START_REF] Motwani | Randomized Algorithms[END_REF]). Then the (unique) steady state distribution is that the probability of being at node u is d u /2|E|. In other words, if t ≫ n 3 then M t u,v = (1 + o(1))d u /2|E|. If we have t ≫ n 5 , the error in each entry is within a factor of 1 + o(1/n 2 ) of the exact value. Then

K(y) = o 1 n + n i=1 d i 2|E|
(P(x i > y i )-P(x i < y i )).

(9) Then, in the long term, i.e., when t → +∞, from Theorem 6, the optimal strategy is to play a mixed strategy such that the vector coordinate x i is uniformly distributed between 0 and d i /|E|, which concludes Theorem 2.

Distance measure between the intrinsic value and the total value of potential customers

In this subsection, we are interested to find the distance measure between the intrinsic value of po- tential customers and the total value of potential customers. From Theorem 1, we know that if we only take into account the intrinsic value of customers, the optimal strategy for the long term is to choose from marginal distributions uniform x

x f (x) |E|/d i d i /|E|
(1) i ∼ U(0, 2/n) (see Fig. 2). From Theorem 2, we know that, by also taking into account the network value of the customers, the optimal strategy is to choose from marginal distributions uniform x

(2) i ∼ U(0, d i /|E|) (see Fig. 3). The marginal distribution of the difference, Z = x

(1) i -x (2)
i , is given by:

• For the case di |E| ≤ 2 n : f Z (z) =      |E| di + n 2 |E| di z -2 n ≤ z ≤ di |E| -2 n , n 2 di |E| -2 n ≤ z ≤ 0, -n 2 |E| di z + n 2 0 ≤ z ≤ di |E| . • For the case di |E| ≥ 2 n : f Z (z) =      |E| di + n 2 |E| di z -2 n ≤ z ≤ 0, |E| di 0 ≤ z ≤ di |E| -2 n , -n 2 |E| di z + n 2 di |E| -2 n ≤ z ≤ di |E| .
We notice that in both cases f Z is a trapezoidal distribution of mean

µ Z = 1 2
d i |E| - 2 n ,
and variance

σ 2 Z = 1 12 2 n 2 + d i |E| 2 .
However, the marginal distribution of the difference is not a good distance measure since one of the properties that one would like to have is the identity of indiscernibles, i.e., that the distance between two equal probability distributions is zero. Because of that, we consider the total variation distance of probability measures. Definition 3. For µ and ν probability measures on R. The total variation distance between µ and ν is defined as

δ(µ, ν) = 1 2 sup f f (t) dµ(t) -f (t) dν(t) ,
where the supremum is taken over continuous functions which are bounded by 1 and vanish at infinity.

Informally, the total variation distance is the largest possible difference between the probabilities that the two probability distributions can assign to the same event (see Fig. 4).

Thus, we have the following two cases:

• For the case di |E| ≤ 2 n : δ(x (1)
i , x

i ) = 1 - n 2 d i |E| ≥ 0. • For the case di |E| ≥ 2 n : δ(x (2)
i , x

i ) = 1 - |E| d i 2 n ≥ 0. (2)
We define the average total variation between both strategies across all the nodes as

δ = 1 n n i=1 δ(x (1)
i , x

i ).

This distance has some good properties (nonnegativity, identity of indiscernibles, symmetry, triangle inequality). For the long term, it can be seen that for any k-regular graph, δ = 0. Give the particular probability densities considered, the effect of δ will be given by how much different are n . For example, for n ≥ 2, a graph with selfloops where all other edges are given by one node connected to every other node, there is one node of degree (n + 1) and (n -1) nodes of degree 3. The total number of edges in the graph is 2n -1. Therefore, the average variation is given by

di |E| x f (x) |E|/d i n/2 d i /|E| 2/n
1 n (n -1) 1 - n 2 3 2n -1 + 1 - 2 n 2n -1 n + 1 = (n -1)(n -2)n(n + 1) + 2(2n -1)(n -1)(n -2)
2(2n -1)n 2 (n + 1) , which converges to 1/4 when n → ∞. As we have seen, this is very different for other graphs, for example for k-regular graphs.

Price of competition

In this subsection, we study the price of competition in the strategic resource allocation problem for competitive influence. We define the price of competition as the ratio of the total cost to a competitive duopoly to that of a monopoly. Informally, it is the price resulting from the lack of coordination among the agents [START_REF] Bharathi | Competitive influence maximization in social networks[END_REF].

Until now, we have considered that for any ǫ > 0 such that x i -y i ≥ ǫ user i will choose the product or service of player X versus the product or service of player Y . Under that scenario the price of competition will be unbounded. Indeed, the cost for two marketing campaigns cooperating (as in a monopoly) could put together for each user ε/n (thus ε for the whole population), while for the non-cooperating scenario each marketing campaign needs to invest a budget of B > 0 for the whole population, thus the price of competition is B/ε which is unbounded for ε → 0.

We notice that this is a very different result than the one obtained by Bharathi et al. [START_REF] Bharathi | Competitive influence maximization in social networks[END_REF] where they found that the price of competition is at most a factor of 2 when the focus is on which potential customers to recruit. We have thus obtained Theorem 3.

5 Conclusions and Future Work

Conclusions

In this work, we were interested on the strategic resource allocation of competing marketing campaigns who need to simultaneously decide how many resources to allocate to potential customers to advertise their products. Using game theory, and in particular Colonel Blotto games, we were able to completely characterize the optimal strategic allocation of resources for the voter model of social networks. We were able to prove that for this case the price of competition is unbounded.

Future Work

One generalization to several marketing campaigns consists on the simple case of analyzing pairwise competitions as previously described. This case has the advantage that we already know the solution, given by the results of the previous section. However, this is not a realistic case for competitions in which each customer chooses only one product from the competing marketing campaigns. To see this, consider the example of three competing marketing campaigns X, Y , and Z and four customers (for the sake of simplification). Consider the pure strategies x = (0.2, 0.2, 0.2, 0.2, 0.2), y = (0, 0, 0, 0.5, 0.5) and z = (0.5, 0.5, 0, 0, 0). In that case, the pairwise competition gives that X has captured 3 out of 5 potential customers to Y , and that X has captured 3 out of 5 potential customers to Z, thus winning in a pairwise competition against both competitors. However, since each customer will only choose one product, the final outcome will be 2 customers for Y , 2 customers for Z, while only 1 customer for X.

For exploring this generalization, we need to search for another framework. We notice that there is a tight relationship between Colonel Blotto games and auctions. A Colonel Blotto game can be seen as a simultaneous all-pay auction of multiple items of complete information. An all-pay auction is an auction in which every bidder must forfeit its bid regardless of whether it wins the object which is awarded to the highest bidder. It is an auction of complete information since the value of the object is known to every bidder. In another context, this was already noted by Szentes and Rosenthal [START_REF] Szentes | Three-object two-bidder simultaneous auctions: chopsticks and tetrahedra[END_REF], Roberson [START_REF] Roberson | The colonel blotto game[END_REF] and Kvasov [START_REF] Kvasov | Contests with limited resources[END_REF].

Through this new perspective, we can generalize Colonel Blotto games to more than two players, where the winner of an object will be the highest bidder for that object. We notice that this is a different generalization than the work of Goldman and Page [START_REF] Golman | General blotto: games of allocative strategic mismatch[END_REF] who consider another payment function. This general framework does not have yet a known solution and we consider it an interesting extension to study.

Figure 1 :

 1 Figure 1: Triangle of lengths a 1 , a 2 and a 3 .

Figure 2 :

 2 Figure 2: Probability density function for the optimal marginal allocation for the intrinsic value case.

Figure 3 :

 3 Figure 3: Probability density function for the optimal marginal allocation for the total value case.

Figure 4 :

 4 Figure 4: Total variation between both probability density functions (shaded region).

Acknowledgments

The work presented in this paper has been partially carried out at LINCS (http://www.lincs.fr).