B Marcos
email: bruno.marcos@unice.fr

A Gabrielli

M Joyce

Relaxation of quasi-stationary states in long range interacting systems and a classification of the range of pair interactions Research Article

Keywords: y, 05.45.-a, 04.40.-b long range interacting systems, Vlasov equation, collisional relaxation

Systems of particles interacting with long range interactions present generically "quasi-stationary states" (QSS), which are approximately time-independent out of equilibrium states. In this proceedings, we explore the generalization of the formation of such QSS and their relaxation from the much studied case of gravity to a generic pair interaction with the asymptotic form of the potential v(r) ∼ 1/r γ with γ > 0 in d dimensions. We compute analytic estimations of the relaxation time calculating the rate of two body collisionality in a virialized system approximated as homogeneous. We show that for γ < (d -1)/2, the collision integral is dominated by the size of the system, while for γ > (d -1/2), it is dominated by small impact parameters. In addition, the lifetime of QSS increases with the number of particles if γ < d -1 (i.e. the force is not integrable) and decreases if γ > d -1. Using numerical simulations we confirm our analytic results. A corollary of our work gives a "dynamical" classification of interactions: the dynamical properties of the system depend on whether the pair force is integrable or not.

Introduction

Long range interacting particle systems are usually defined (see e.g. [1]) such that the interparticle potential v(r)

is not integrable because of its large scale behavior, i.e., in d dimensions lim R→∞ R d d r v(r) → ∞.

(1)

v(r → ∞) ∼ 1 r γ , (2)
with γ < d. There are many such systems in nature, like gravitational ones, two-dimensional vortices, cold atoms, etc. Using an appropriate N → ∞ prescription (see section 2 for a discussion about the different prescriptions to perform this limit), it is possible to compute the thermal equilibrium properties of this systems [2]. They present unusual features compared to short range systems, like ensemble inequivalence, negative specific heat in the microcanonical ensemble, non-homogeneous spatial distributions, etc.

However, on the timescales of typical interest (e.g. the formation and evolution of galaxies in astrophysics), the system has usually not reached thermal equilibrium [START_REF] Binney | Galactic Dynamics[END_REF]. Actually, the scenario of their evolution is peculiar compared to short range systems: in a characteristic time τ mf , there is the generic formation of long lived states which are not in thermal equilibrium, called Quasi Stationary States (hereafter QSS), and in a much longer timescale τ coll , the relaxation towards thermal equilibrium. For example, for a gravitational system in d = 3

dimensions, if we choose our units in such a way that τ mf ∼ 1, then τ coll ∼ N/ log(N ). Indeed, in the N → ∞ limit, the system becomes mean field and it remains trapped in the QSS (which becomes stable). Finite N effects are totally suppressed, which are the mechanism (as in short range systems) which lead the system to thermal equilibrium [START_REF] Binney | Galactic Dynamics[END_REF]. The appropriate equation to describe such systems is the Boltzmann equation

∂f ∂t + v(r, t) • ∂f ∂r + F[f ] • ∂f ∂v = CN [f ], (3)
where f (r, v, t) is the one-point distribution function, i.e., the probability to find a particle at the position r with velocity v at time t. The term F[f ] is the mean field force which, for an interaction potential of the form (2), is

F[f ] = g f (r ′ , v, t) |r -r ′ | γ+2 (r -r ′ )dr ′ dv. (4)
In order that a mean-field (or collisionless limit) exist -which leads to the scenario described above -the r.h.s.

of Eq. ( 3) should satisfy

lim N→∞ CN [f ] = 0, (5)
where the prescription to perform the limit will be described in section 2. Under this hypothesis, the l.h.s. of Eq. (3) describes the N → ∞ dynamics of the systems (the mean-field part), while the r.h.s. finite N effects (which is commonly called "collision term"). In this limit, the Boltzmann equation is called Vlasov equation. It becomes apparent at this stage that the limits t → ∞ and N → ∞ do not commute: the limit t → ∞, N → ∞ leads the system to thermal equilibrium, while N → ∞, t → ∞ maintains the system in the QSS forever.

In this proceedings we explore the conditions under which the condition ( 5) is satisfied (and, more specifically, how it depends on the exponent γ of the power law of the interaction potential (2)). It would depend on the collisional dynamics described by the term CN [f ], which is in general a very complicated function of the N -point particle density. It is assumed, (e.g. [START_REF] Binney | Galactic Dynamics[END_REF]), however, that its dominant contribution comes from two body collisions.

We will use this assumption when estimating the collisional relaxation rate in section 3.

At this point, we would remark that in long range interacting systems, QSS exist because τ mf ≪ τ coll , which is a dynamical property of the system. However, the definition of long range interacting systems (1) is based on the integrability property of the interaction potential, which is not directly related to the dynamics. For instance, the integrability condition for the force is γ > d -1 in Eq. ( 2), which is not the same than the one for the potential.

As the dynamics is related to the force, we can suspect that the existence of the QSS would be conditioned by the non-integrability of the force. We will provide evidence in this proceedings that it is indeed the case, which will lead to a dynamical classification of interactions.

In this proceedings we present an extension of [START_REF] Gabrielli | [END_REF]. It is structured as follows: in the next section we will describe the appropriate N → ∞ limit for long range interacting systems. In the next section we will describe a generalization of the Chandrasekhar approach to estimate the collisional relaxation rate of particle systems interacting with the potential (2). Using the scaling dependence of this estimate, we will present a dynamical classification of interacting systems, and show numerical evidence of our results. We will then give some conclusions and directions which we would like to investigate in future.

The N → ∞ limit in long range systems

In order to study the thermal equilibrium properties of a system of interacting particles, the important quantity to keep constant performing the infinite N limit (up to finite N effects), is the (potential) energy of the particles, in order that the total energy is extensive. Let us compute the potential energy φ per particle of a particle located inside a sphere of radius R with typical density n0 and interaction potential (2):

φ ∼ R ℓ d d rn0 g r γ ∼ gn0 R d-γ -ℓ d-γ , (6)
where we have approximated a sum over all the particles by an integral, and ℓ is some small characteristic scale.

For short range systems (γ > d), Eq. ( 6) is dominated by the second term of its r.h.s. In this case, the limit N → ∞ is performed taking V → ∞ and keeping N/V = constant, where V is the volume of the system. This is an appropriate manner to perform the limit because the scale ℓ is kept invariant performing the limit, and hence the potential energy φ remains constant (up to finite N effects). For long range systems, the integral is dominated by the first term of the r.h.s. If the limit is performed in the same way 1 , the potential energy φ diverges with N ,as we can explicitly see using that R ∝ N 1/d in Eq. ( 6). Then:

φ ∼ gn0N 1-γ/d . (7)
The usual way to overcome this problem (see e.g [1]) consists in scaling the coupling constant with an appropriate power of the volume or, equivalently, of the number of particles:

g → gn0N γ/d-1 . (8)
This is an extension of the Kac prescription [6], and sometimes also called the dilute limit . The energy becomes then extensive. However, if we are interested in the dynamics of the system, the force should be independent of N (up to finite size effects). The typical force f is:

f ∼ R ℓ d d rn0 g r γ+1 ∼ gn0 R d-γ-1 -ℓ d-γ-1 . ( 9
)
If we use the rescaling of the coupling constant ( 8), the force (9) becomes

f ∼ n0N -1/d , (10)
and then in the infinite N limit, lim

N→∞ f = 0, ( 11
)
which means that the dynamics disappears. If one decides to scale the coupling constant with N in such a way that the force (9) becomes independent of N , then the potential would be badly defined, and the system would relax to a badly defined configuration. The conclusion of this analysis is that it is not possible to find an appropriate scaling of the coupling constant which makes the potential and the force independent on N at the same time, when we scale the system with the procedure given above2 .

In this work, we will consider the so-called Vlasov limit, in which the N → ∞ limit is taken keeping R constant.

It corresponds exactly to the limit in which, for gravitational systems, the relation ( 5) holds, maintaining constant the mean-field dynamical time τ mf . In this limit, it is possible to rescale g in such a way to maintain both the typical potential and force independent of N , for any value of γ. The physical meaning of this limiting procedure is the following: imagine a QSS with fixed typical size R (e.g. a galaxy) which we would like to describe more and more precisely, with larger and larger number of particles. Let us compute the typical energy and force over a particle i:

φi = g N j =i 1 |ri -rj | α ∝ gN (12a) fi = g N j =i ri -rj |ri -rj | α+2 ∝ gN. ( 12b
)
Because the size of the system is fixed, both sums are proportional to the number of terms in the sum. In order to both the potential and the force be independent of N it suffices to scale the coupling constant using

g → g N . ( 13
)

A generalization of the Chandrasekhar estimate of the relaxation rate

Chandrasekhar introduced a very successful way to estimate the relaxation rate in gravitational systems [7].

We will summarize below the main ingredients, including also an improvement which takes into account the boundaries of the system, similar to the one due to Hénon [8].

Consider a homogeneous system of particles, in which a test particles crosses the system in a typical time τ mf .

Let us begin our analysis studying the scattering of the test particle with another particle with impact factor b, for the well-known case γ = 1 (which corresponds to Rutherford scattering) . The change in velocity of the test particle because of multiple scattering will give rise to a randomization of the velocities, which is assumed to be the dominant relaxation process towards thermal equilibrium. It has been shown (see e.g. [START_REF] Binney | Galactic Dynamics[END_REF]), that the main contribution to the change of the velocity is the perpendicular component of the relative velocity V0 between the two particles. Assuming that the particles have the same mass m, a simple calculation gives (e.g. [START_REF] Binney | Galactic Dynamics[END_REF]):

|∆v ⊥ | = mbV 3 0 /2g 1 + (mbV 2 0 /2g) 2 , (14)
where V0 = |V0|. There is a natural cutoff for small impact factors at

bmin = g mV 2 0 . (15)
A very good approximation to Eq. ( 14) consists in using the so-called weak collision approximation

|∆v ⊥ | ≃ 2g mbV 2 0 (16)
and neglecting the collisions with impact factor b < bmin. It is not possible to calculate analytically a generalization of Eq. ( 14) for any γ = 1, but it is possible to obtain a generalization of the Chandrasekhar estimate using the weak collision approximation and a cutoff for the minimal impact factor. Such a generalization is computed assuming that the collision is sufficiently weak in order the deflection of the test particle to be negligible. The component of the force perpendicular to the trajectory can be calculated as

F ⊥ = γgb (b 2 + x 2 ) γ/2+1 = γg b γ+1 1 + vt b 2 -(γ/2+1) , (17)
where we have assumed in the last equality that the particle velocity is constant. By Newton's law, we have

|∆v ⊥ | = ∞ -∞ dt F ⊥ m = ∞ -∞ dt γg mb γ+1 1 + vt b 2 -(γ/2+1) = γg mb γ v ∞ -∞ ds(1 + s 2 ) -(γ/2+1) . (18)
In Eq. ( 18) the integration limits are approximated to s = vt/b = ±∞ (instead of being s ≃ ±R/b, where R is the size of the system), in order to be able to compute the integral analytically. This is a very good approximation if b ≪ R (which is typically the case), because the integral converges rapidly. Performing the integration we obtain:

|∆v ⊥ | ≃ Aγ g mvb γ , (19)
with

Aγ = γ √ π Γ 1+γ 2 Γ 1 + γ 2 , ( 20
) if γ = 1. The cutoff is now at bmin = mV 2 0 g 1/γ . ( 21
)
We checked numerically that Eqs. ( 19), ( 20) and ( 21) are a very good approximation, comparing an exact calculation of |∆v ⊥ | with the weak collision approximation, as shown in Fig. 3.

z Figure 2.
The QSS is approximated by a perfectly spherical distribution of particles with radius R.

The equation ( 19) gives an expression for the change in velocity due to one collision. We have now to integrate over all the possible collisions, i.e., over all the impact parameters b. In order to be able to obtain an analytical expression we will do further approximations: (i) the system is a perfect d dimensional homogeneous sphere of radius R, (ii) we consider a test particle with zero angular momentum, and (iii) because we do not know the velocity distribution of the QSS, we approximate the relative velocity of the particles with the average velocity over all the particles of the system. The mean change in velocity is zero because the perturbations are randomly oriented, whereas the mean square velocity is non-zero (it is a random walk in velocity space). We will then calculate the average of the change of the square velocity. In order to perform the integration over all the impact parameters we divide the system in disks of thickness dz, sketched in Fig. [START_REF] Binney | Galactic Dynamics[END_REF]. We perform the integration over all the impact parameters in each disk, and then the integration over the variable z. We can estimate that crossing a disk of thickness dz the particle suffers

δn = B d N R d b d-2 db dz (22)
encounters with impact parameter between b and b + db, where B d is a factor which depends on the dimension d (e.g. B2 = 2/π, B3 = 3/2). Therefore, the average change in square velocity is, in d = 2 or d = 3:

|∆v 2 | |v 2 | ≃ N A 2 γ B d g mv 2 R γ 2 1 -1 dy √ 1-y b min /R dx x 2γ-d+2 . ( 23
)
The behavior of the integral depends on the value of γ and d, giving for d > 1

|∆v 2 | |v 2 | ≃ N A 2 γ B d g mv 2 R γ 2 C γ,d R bmin 2γ-d+1 + D γ,d (24)
where C γ,d and D γ,d are two constants of order unity (which depends on γ and d), which can be calculated analytically. We see therefore that if γ < (d -1)/2, the integral ( 23) is dominated by the size of the system, whereas if γ > (d -1)/2, it is dominated by the minimum impact parameter. We can simplify Eq. ( 24) making use of the virial theorem, which states that, for a stationary distribution

2K + γU = 1, ( 25
)
where K is the total kinetic energy and U the total potential energy. Hence, by dimensional analysis:

g mv 2 R γ ∼ 1 N gN 2 (mN v 2 )R γ ∼ 1 N U K ∼ 1 N . ( 26
)

Estimation of the relaxation rate

We can simply estimate the relaxation rate Γ by computing the normalized change in square velocity due to collisions, in units of τ mf :

Γτ mf ≃ |∆v ⊥ | 2 v 2 , ( 27
)
which gives, using Eq. ( 24) and ( 26) the following scaling:

Γ τ mf ∼      N -1 if γ < (d -1)/2 N -1 R b min 2γ-d+1 if γ > (d -1)/2, ( 28
)
where we have dropped all the factors of order unity. This is the first main result we present in this proceedings: for γ < (d -1)/2, the relaxation is dominated by the maximum impact parameter (which is of the order of the size of the system), whereas for γ > (d -1)/2 it is dominated by the minimum impact parameter. We can control the relaxation rate in the latter case by putting a softening in the potential, obtaining in this case:

Γτ mf ∼ N -1 R ǫ 2γ-d+1 . ( 29
)
In this case, and for any γ < d, we obtain lim

N→∞ Γ τ mf = 0, (30)
which signifies that, for any value γ, the QSS may last an infinite amount of time in this limit, provided that a sufficiently large softening ǫ > bmin is used for γ > d -1. However, considering unsoftened potentials, we can see from Eq. ( 21) and the virial relation (25) that the minimum impact parameter depends indeed on the number of particles N . We obtain therefore:

Γ τ mf ∼      N -1 if γ < (d -1)/2 N -(d-1-γ)/γ if γ > (d -1)/2. ( 31
)
This is the second main result presented in this proceedings: studying the zero of the exponent of the relaxation rate for γ > (d-1)/2, another threshold appears at γ = d-1. The relaxation rate becomes divergent for γ > d-1, which corresponds to an integrable force, and not an integrable potential.

We can therefore give the following dynamical classification of interactions, as a function of the existence of QSS in the infinite N limit: 1. Dynamically long range systems, in which the pair force is non integrable, i.e., γ < d -1, for which limN→∞ Γτ mf = 0 for unsoftened potentials, i.e., the QSS becomes stable in this limit. For finite N systems, the relaxation rate decreases increasing N . Furthermore, we have that

• If γ < (d -1)
/2 (i.e. more long range than gravity in d = 3), the relaxation is dominated by the maximum impact parameter (i.e. the size of the system), and, for unsoftened potential, Γτ mf ∼ N -1 .

• If (d -1)/2 < γ < d -1, (i.e. less long range than gravity in d = 3), the relaxation is dominated by the minimum impact parameter bmin, and, for unsoftened potential, Γτ mf ∼ N -(d-1-γ)/γ .

2. Dynamically short range systems, in which the pair force is integrable, i.e., γ > d -1, for which limN→∞ Γτ mf = ∞ for unsoftened potentials, i.e., the QSS is immediately destroyed, the dynamics being dominated by collisions. For finite N systems, the relaxation rate increases increasing N .

Comparison with numerical simulations

We carefully compare the theoretical scalings with molecular dynamics simulations in d = 3. To do so, we use a modification of the publicly available code GADGET2 [9], performing the appropriate modifications to integrate any power-law force. The potential was softened at the scale ǫ using a repulsive soft core, which does not modify the potential for r > ǫ and goes smoothly to v(0) = 0 for r < ǫ. We use soft reflecting boundary conditions in cubic box of size L, i.e., when the i th spatial coordinate of a particle lies outside the simulation box, we invert the i th component of the velocity. The initial condition is a uniform spherical distribution of particles with random velocities normalized in order to satisfy the virial relation (25). This choice of normalization implies that the initial condition is close to a QSS, as it can be seen in the simulations. We show an example of the evolution of the total kinetic energy K(t) for a set of simulations with N = 8000 particles, γ = 5/4 and different values of the softening parameter ǫ, in the left panel of Fig. 3. For the first few τ dyn , the evolution of K(t) is independent of ǫ, which corresponds to the mean-field evolution (violent relaxation). Then, K(t) exhibits a "plateau", whose slope depends on the value of ǫ. This is a manifestation of the collisional relaxation, which depends on ǫ, as predicted in Eq. (28).

A particle moving in a mean-field potential (e.g. the one correspondent to the mean-field force (4)) conserves its total energy. A common way to estimate the collisional relaxation consists then in measuring the change in energy of the individuals particles with time. We use the following estimator R(t) (see e.g. [10]),

R(t) = (e(t) -e(t0)) 2 4K(t0) 2 (32)
where e(t) is the total energy of a single particle at time t, . . . and average over all the particles, K(t) the total kinetic energy and t0 a reference time for which the system had time to form the QSS. In the right panel of Fig. 3 we show the evolution of R(t) for the same set of simulations as the one in the left panel. We estimate the relaxation rate Γ computing the slope of the linear fit of R(t), for the range in which it is linear. In Fig. 4 we plot the scaling measured in a set of simulations. In the upper panel the relaxation rate Γ is plotted for simulations with different softening ǫ and constant number of particles N . There is a very good agreement with the theoretical scaling (28) for a wide range of ǫ. For the smallest value of ǫ, the relaxation rate is smaller than the one predicted by the scaling: it corresponds to values of ǫ < bmin. For the largest values of ǫ, the mean field dynamics is altered by the softening, giving a different relaxation rate than the one predicted by the theory. In the lower panel of Fig. 4 we see the scalings obtained from a set of simulations taking ǫ/L = 0.01 and varying the number of particles, for γ = 5/4 and γ = 3/2. We see again a very good agreement with the theoretical scaling (28).

Conclusion

In this proceedings, we have generalized the Chandrasekhar estimate for the collisional relaxation rate for a system of particles with power-law pair interaction v(r → ∞) = 1/r γ in d dimensions. The main result we have found is that the relaxation rate expressed in units of the mean field dynamical time τ mf converges only if the pair force is integrable, i.e., γ < d -1. This leads to the following dynamical classification of interactions:

1. The interactions is dynamically long range if τ mf ≪ τ coll for a sufficiently large number of particles, and in particular limN→∞ Γτ mf = 0, which occurs for γ < d -1. In addition, we have identified that for γ < (d -1)/2, the relaxation is dominated by collisions with the maximum allowed impact parameter by the system (in our case the size of the system R), and if γ > (d -1)/2, the relaxation is dominated by collisions with minimum impact parameter bmin, in the absence of softening.

2. The interaction is dynamically short range if τ mf ≫ τ coll for a sufficiently large number of particles, and in particular limN→∞ Γτ mf = ∞, which occurs for γ < d -1.

As anticipated in the introduction, this classification differs from the one according to the thermal equilibrium of the system, in which the important quantity is the integrability of the potential. There is therefore a range of γ, d -1 < γ < d, in which the interaction is dynamically short range, but long range according to its thermal equilibrium properties. In this case, if the system has a large enough number of particles, the QSS would not form (as in short range systems), but however the thermal equilibrium state will presents the features of a long range system.

In the near future, we will present elsewhere a more detailed report of numerical simulations, including simulations with different cores (such as attractive ones) and the study of systems which are more long range than gravity in d = 3, such that the systems with γ < 1 in d = 3 or gravity in d = 2.

Figure 1 .

 1 Figure 1. Numerical computation of |∆v ⊥ | after a collision, for γ = 1/2 (plain curve), γ = 1 (dashed curve) and γ = 3/2(dashed-dotted curve). The weak collision approximation for each case is represented with dotted lines, which coincides perfectly with the exact calculations for b ≫ bmin.

Figure 3 .

 3 Figure 3. Left: evolution of the total kinetic energy K for simulations with N = 8000 particles and different softening length ǫ in the potential v(r) with γ = 5/4. Right: evolution of the estimator R(t) for the simulations.

Figure 4 .

 4 Figure 4. Top left: Relaxation rate estimated using the estimator (32) for N = 8000, γ = 5/4 and different values of the softening ǫ. Top right: the same plot but for γ = 3/2. Bottom left: relaxation rate for ǫ/L = 0.01, γ = 5/4 and different number of particles N . Bottom right: the same plot but for γ = 3/2.

In the case of an infinite system, the problem is more subtle. One has to subtract the contribution to the force and to the potential of the average distribution (the so-called Jeans swindle). For a detailed analysis of the properties of the convergence of the force, see[5].

Note that this is not the case for systems of spins on a lattice, such as the so-called α -HM F and related models[1], in which the potential and the force decay with the same power of the distance, by construction of the model.

Acknowledgments

We acknowledge many useful discussions with F. Sicard. This work was partly supported by the ANR 09-JCJC-009401 INTERLOP project. Numerical simulations have been performed at the SIGAMM cluster hosted at "Observatoire de Côte d'Azur", Université de Nice -Sophia Antipolis.


Tin Valéry Wolff

Tran Dinh

Stephane Raynaud
email: stephane.raynaud@insa-lyon.fr

Wolff Valery
email: valery.wolff@univ-lyon1.fr

Tran Dinh-Tin
email: dinh-tin.tran@insa-lyon.fr

Raynaud Stephane

Using virtual parts to optimize the metrology process

Keywords: metrology, control, CMM, measuring system, method of calculation

published or not. The documents may come

Introduction

The control of technical parts is very important in many industries, for example: the plastic industry, aviation, automotive or electronics. Currently, measured parts of mechanical systems are increasingly demanding higher accuracy, which is why the instruments are continuously improved (CMM, optical measuring systems without contact, ...). The measurement methods for a same part to control can be various. You can choose classical (calliper, ...) or hightechnology material (CMM, Vision, ...). The best result is not always given by the most expensive and the most accurate machine. It is also linked to the way of calculation proposed by the measurement system software.

In our study, we want to give a help to define the best way to control a part. This work is a first step to reach this goal. We want to apply different methods of calculation to a same measurement. In this way, we hope to find a significant effect of the method of calculation on the result.

Problematic

In this paper, we are working with a simple part (see fig. 1): a drilled hole on a face, and a geometrical specification of location with a datum coordinate system. In a perfect world, the all faces of the part are perfectly orthogonal, the drilled hole is a perfect perpendicular cylinder and all plane surfaces are without any default of form. In this case, a lot of calculation methods will give the same result: barycentric method, least square optimization, Tchebychev method [START_REF] Abdi | Least Squares[END_REF] But a real part as some defaults: flatness, cylindricity, perpendicularity of the faces, and perpendicularity of the axis. The software we use with the CMM (coordinate measuring machine) gives different options (see fig. 2 and fig. 3). We can distinguish the nominal element (a), the skin model element (b) and the associated element. The association of a theoretical element to a surface can be made by different ways. The operator can choose to use the option "tangent" or not. It gives different results: theoretical plane associated to a surface by the least square method (c) or the tangent plane associated with the same method (d) [START_REF] Valery | Comparison of a machine of measurement without contact and a CMM : optimization of the process of metrology[END_REF]. The possibilities of the software are also giving different ways to calculate the datum coordinate system. It is possible to use a constraint when we calculate an associated plane. For example, to be perpendicular to a first plane or to pass through a specific point... The Fig. 3 presents two ways for the construction of a tangent plane in a datum plane system. The difference is by adding a constraint to the plane before to calculate it.

The study

The study is limited to a simple part. The reason is that we use a method to construct parts. In this way we are able to observe the effects of some parameters on the result of the measurement. In a classical method, we would have machined a lot of different parts. The difficulty to machine an "exact" part with the default we want is erased by our methodology. We construct virtual parts on CAD system (CATIA), and we can have exactly the defaults we want for each part of the study.

The design of experiment (DOE)

The design of experiment is applying the method of Taguchi Design of Experiment [6,9,10,[START_REF] Valery | Comparison of a machine of measurement without contact and a CMM : optimization of the process of metrology[END_REF]. This is a way to reduce the number of experiments to find the effect of a parameter on a result. Documentation [1,[START_REF] Pillet | Les plans d'expériences par la méthode Taguchi[END_REF] gives an array with different tables of Taguchi. If we look in the "array selector" (Table 1), we can obtain different tables able to be used , if you have defined the number of parameters and the different levels that the parameters can take [4,11].

2 3 4 5 6 7 8 9 10 2 L4 L4 L8 L8 L8 L8 L12 L12 L12 3 L9 L9 L9 L9 L18 L18 L18 L27 L27 4 L16 L16 L16 L16 L32 L32 L32 L32 L32 5 L25 L25 L25 L25 L25 L50 L50 L50 L50

Number of levels

Numbers of parameters

The parameters of the DOE

We choose to make the experiments with 3 parameters, with each 3 levels. The first parameter is the quality of the top plane. The second is the quality of the side plane. The third parameter is the angle between the two planes. For this first study, we didn't consider the defaults of the measured cylinder (see fig. 4).

The parameter of flatness for the top and the side plane of the part are defined by the machining process used to obtain the surface. The 3 levels we use are: rough milling, finishing milling, and grinding. The values are given in the same order: 0,03 mm, 0,006 mm, and 0,0015 mm flatness default.

According to the document (table 1), we select the table of the Taguchi L9 experiment [START_REF] Besseris | Profiling effects in industrial data mining by non -parametric DOE methods: An application on screening checkweighing systems in packaging operations[END_REF]. That means that we will perform 9 experiments to examine the influence of all parameters to the result of measuring the position of a cylinder.

Taguchi table

The taguchi table we use (table 2), gives the order of the experiments and the levels we have to use for each one. According to the values of the Taguchi table, we have to construct 9 virtual parts.

The building of a virtual part

The part we use needs to define 6 faces and a cylinder. To build a model for a virtual part [START_REF] Sładek | Evaluation of coordinate measurement uncertainty use of virtual machine model based on Monte Carlo method, Measurement[END_REF], we use a CMM to measure a real surface. We obtain the coordinates of 25 points for the plane. We also measured a real cylinder to have a set of points for calculation.

The second step of the preparation of the virtual part is to use an Excel sheet to generate a theoretical set of points. We have done 3 quality for the planes, so we have 3 sets of 25 points. We do not use directly the XYZ measured coordinates. We have to apply the least square method [START_REF] Abdi | Least Squares[END_REF] to obtain an optimized plane with a theoretical normal direction (0,0,1) with a Z=0 position. In the reality, the two planes (top and side) are perpendicular to each other with an "error" due to manufacturing. Because it is difficult to machine an exact default, we use virtual part. To obtain a perpendicularity default between top and side plane, we use CATIA to generate a set of point with the right position. CATIA software helps us do this easily by a simple rotation of the plane and an additional translation if needed [4]. Within the limits of this paper, we created three virtual perpendicularity defaults with details of plane angles: 90.002, 90.1, and 91 degree. We have 0.02, 0.1, and 1° for the angle parameter. The process is shown in fig 6. At the end of the virtual parts building process, we have 9 sets of points. Each set is in conformity with an experiment of the Taguchi table. For this first paper on the subject, the parameters are limited to 3 levels. Later, we can imagine increasing the number of experiments.

The calculation method

The part we use for the experiment permit to define a specification of position of a hole. It is a question of determining which limits of the defects of form involve a variation on the measure of location. The main feature of the specification of position is to imply the construction of a reference coordinate system. Various datum systems can exist: 3 planes and plane-line-point are the most used. In our case, we use a Plane/Line/Point system of coordinate.

The options included in the Metrolog software allow defining four variations for the coordinate system. We can mix the options to obtain different systems: tangent association between skin model and theoretical plane or least square method; simple intersection or plane with perpendicularity constraint.

The results of the four possibilities are shown on the figure 7 above. We decide to limit the calculation to only one direction: the Y axis. The Rep 2 is the more simple to obtain. It is defined by two least square associations and an intersection to calculate the origin of the datum system. This is the "without-option" construction, and often, a non specialist user will take this one. We choose to take this datum system as the zero point for each part of the experiment. The value we can study is so the distance between Rep2 -Rep i with i in (1, 3 and 4).

It is important to notice that the best construction to be conforming to the norms is the Rep 3, with two tangent planes and a constraint of perpendicularity between these two planes. In the GPS (Geometrical Product Specification) norms, the theoretical planes associated to the surfaces A and B need to be tangent to the surfaces. In add, for the position specification , the norm define the construction of the datum coordinate system with a perpendicularity constraint between B and A (planes are defined on fig. 1).

Results and analysis

The dispersion on the distance between the datum system Rep2 and each Rep (i) possible to construct, gives some results. The figure 8 shows that, if we used REP2 or REP4, the results in the 9 locations of the cylinder during experiments we perform involves quite the same results (small variations). This means that REP4 and REP2 are very similar but not totally identical.

The Rep3 and the Rep1 gives exactly the same dispersion. Because Rep3 is more conform to the definition of the norm, we will forgot Rep1 and only study the Rep3 and the Rep4.

For the Rep3, we can observe (see fig. 8) that 3 values have very important level: experiments 3, 5 and 7. These are the 3 experiments with the maximum value for the perpendicularity default: 1°. The 0,25 mm difference between Rep2 (simplest) and Rep3 (norm) is almost due to the angle. The length of the part with an angle of 1° gives 0,5 mm error even with perfects planes (theoretical planes). It is obtained by the calculation: lengh x tan(angle) = 30 x tan(1°) ~ 0,5 mm.

The figure 9 indicates that the angle is the main parameter to have an effect on the result of the position of the datum system. The figure 10 indicates that there is no influent parameter when we use the Rep4. In order to refine the result, we also check the dispersions with a view angle/angle. The table 3 gives some information about the form parameters without taking into account the angle.

Figure 1 :

 1 Figure 1: Simple part for experiment: theoretical and skin model

Figure 2 :

 2 Figure 2: Different models for the association

Figure 3 :

 3 Figure 3: Different constructions of a plane

Figure 4 :

 4 Figure 4 : Parameters of the study: flatness and perpendicularity (angle)

Figure 5 :

 5 Figure 5: Least square method application Before to import the set of points (coordinates of the model) in CATIA, we have to save files in text format, with an adequate format. For each quality for the plane surface,

Figure 6 :

 6 Figure 6: Import/export from CATIA to METROLOG

Figure 7 :

 7 Figure 7: Different models for the association

Figure 8 :

 8 Figure 8: The 9 experiments results

Figure 9 :-

 9 Figure 9: Effects of the parameters on the Rep3

Figure 10 :

 10 Figure 10: Effects of the parameters on the Rep4

Table 1 :

 1 Choosing a Taguchi L(i) table

	Nominal element (a) Associated model (Tangent) (d)
	Associated model (Least Square) (c)	Skin model

Table 2 :

 2 L9 design of experiment parameters

EXP2 EXP4 EXP9 EXP1 EXP6 EXP8 EXP3 EXP5 EXP7 0,02 0 0,01 0,09 0,03 0,03 0,25 0,26 0,26 0,02 ° angle 0,1 ° angle 1 ° angle va ri a ti on of p os i ti on va ri a ti on of pos i ti on va ri a ti on of p os i ti on 0,015 0,061 0,012 The values with the maximum angle are higher than with the other angles, but if we look only the 3 experiments with the maximum angle, the effect of the flatness of top and side planes is very low.

In the case of the medium value of the angle, the effect of the angle is almost 0,05 mm, and the variation of the result is more than this value. The flatness of the planes has an effect on the result of the position of a cylinder. We can do the same observation for the minimum angle.

When the perpendicularity specification is given between the planes A and B on a draft, the operator is able to be careful with this problem. But even if the effect is small, it must be taking into account by any operator who is making a measurement operation. The perpendicularity default always has an effect on the result of a position specification.

Conclusion

This article is a first step for a more global study. It turns out that the local coordinates of the parts when we build in the process of measurement is affected by the perpendicularity of the plane and when the angle is low, also affected by the flatness of the planes. These defaults in the construction method of the coordinate datum system are always present and any operator who is making the measurement of the position of a hole with a CMM must be aware of that.

We have used CATIA to construct the virtual parts for the experiment. Because it was a first study, we have limited the number of values for each parameter. With the first results, we can now define another study with more values. We hope that another design of experiment will confirm what we have find: the position of a cylinder in a 3D measurement is affected by the perpendicularity when this is the main default; it is affected also by the quality of the part surfaces (flatness of the top and side plane) when the angle is lower.


Pierre Coucheney
email: pierre.coucheney@uvsq.fr

Patrick Maillé
email: patrick.maille@telecom-bretagne.eu

Maurizio Naldi
email: naldi@disp.uniroma2.it

A Influence of search neutrality on the economics of advertisement-financed content

Keywords: K.6.0 [Management of computing and information systems]: Economics Management, Performance Search neutrality, Economics, Game theory

The recently raised search neutrality debate questions the ranking methods implemented by search engines: when a search is performed, do they (or should they) display the web pages ordered according to the quality-of-experience (relevance) of the content? In this paper, we analyze that question in a setting when content is offered for free, content providers making revenue through advertising. For content providers, determining the amount of advertising to add to their content is a crucial strategic decision. Modeling the trade-off between the revenue per visit and the attractiveness, we investigate the interactions among competing content providers as a non-cooperative game, and consider the equilibrium situations to compare the different ranking policies. Our results indicate that when the search engine is not involved with any high-quality content provider, then it is in its best interest to implement a neutral ranking, which also maximizes user perceived quality-of-experience and favors innovation. On the other hand, if the search engine controls some high-quality content, then favoring it in its ranking and adding more advertisement yields a larger revenue. This is not necessarily at the expense of user perceived quality, but drastically reduces the advertising revenues of the other content providers, hence reducing their chances to innovate.

INTRODUCTION

Search engines represent nowadays the dominant way to access content on the web. Their role allows them to exert a remarkable influence on what people see and read on the Internet. Early on, the possibility that, either by accident or by deliberate choice, such influence turns into bias has been noted and whistleblowed against [START_REF] Introna | Shaping the Web: Why the Politics of Search Engines Matters[END_REF].

Actually, the structure of the market of search engines was such to raise the issue of a strong concentration as early as in 2001, when the Hirschman-Herfindahl concentration index (HHI), measuring the degree of competition and defined as the sum of the squares of the market shares -the smaller it is the higher the competition-was 0.116 [START_REF] Sheu | Monopoly Power on the Web -A Preliminary Investigation of Search Engines[END_REF]. The low barriers for new entrants observed in [START_REF]The dynamics of competition in the Internet search engine market[END_REF]] have turned into the present extremely strong dominance of Google [START_REF] Telang | The Market Structure for Internet Search Engines[END_REF], with an HHI well in excess of 0.6. The present near-monopoly structure of that market further strengthens concerns about the capability to influence operators located elsewhere in the value chain.

Search engines base their business model on advertising [START_REF] Levene | An introduction to search engines and web navigation[END_REF]], providing both organic links and sponsored links. They mark the latters as such and assign them some slots through auctions [START_REF] Maillé | Sponsored search auctions: an overview of research with emphasis on game theoretic aspects[END_REF]. Organic links are instead assigned slots through a proprietary ranking mechanism, based on the relevance of the linked webpage for the user's query. However, when ranking organic links, the search engine may include metrics related to its own interest, inducing an unfair result for some links -ranking them below where they should be, and therefore making them rarely reached by users.

Ranking criteria are crucial for the business model of all the stakeholders: search engines, content providers, and advertisers. Content providers wish to improve their ranking among organic links, e.g. through search engine optimization techniques without affecting the quality of the displayed content [START_REF] Berman | The Role of Search Engine Optimization in Search Marketing[END_REF]. Quality is however a main driver for users' choices, entering the competition between organic and sponsored links [START_REF] White | Search engines: Left side quality versus right side profits[END_REF]]. The relevance of the webpage's quality for users has been recognized in the case of sponsored links as well [START_REF] Chen | Paid Placement: Advertising and Search on the Internet*[END_REF][START_REF] Athey | Position Auctions with Consumer Search[END_REF], but is in turn influenced by the ranking strategy of the search engine. Search engines may use that influence to their own advantage, distorting both users' choices and the market structure. Acting as intermediaries between buyers and sellers, they can divert their users from their preferred websites to websites for which the search engine has a vested interest [START_REF] Hagiu | Why do intermediaries divert search?[END_REF]. Such a behavior may be labelled as non-neutral, which raises the issue of search neutrality.

A parallel can be made with what currently takes place over the internet, where network providers may unduly discriminate among the service/content providers that use their network (hence the issue of net neutrality [START_REF] D'acquisto | Impact on retail prices of non-neutral wholesale prices for content providers[END_REF]). Search neutrality is considered as the next frontier even if net neutrality should prevail [START_REF] Odlyzko | Network Neutrality, Search Neutrality, and the Never-ending Conflict between Efficiency and Fairness in Markets[END_REF]]. In the debate over search neutrality, doubts have been cast about the capability of measures to lead to neutral search results and really protect users against the abuse perpetrated by websites [START_REF] Grimmelmann | The next digital decade: Essays on the future of the Internet[END_REF]]. Critics of the search neutrality approach have even promoted search bias as the product of the competitive process, and the presence of vertical integration (the search engine favouring its own content) as a generally efficient and pro-competitive practice [START_REF] Manne | If search neutrality is the answer, what's the question?[END_REF]. But the search engine's ranking strategy may adversely affect the market position of content providers, and the debate on search neutrality should consider the impact of a non neutral behavior on the content providers' revenues.

In this paper, we define a model to analyze the influence of search neutrality with regard to the distribution of free content (i.e., content funded by advertising revenues). A typical example is the case of video content. A neutral search engine should rank the results of a search according to the relevance for users of the content, embodied by their quality of experience (QoE), which can be negatively affected by advertising. On the other hand, a non-neutral behavior could allow the search engine (SE) to display results based on the potential revenue it will get from the user consulting them (such a model can encompass the situation where the search engine favors its own content, and the one where it receives payment from CPs to favor their content when a search is performed by a user).

Our objective is to investigate the consequences (in terms of user QoE, content provider and search engine revenue) of the presence or not of a regulation imposing search neutrality. For that purpose, we define a noncooperative game setting among the content providers, which use their level of advertising as a strategic leverage to maximize their revenues. They do so in a framework where the SE (possibly constrained by regulation) decides its ranking policy. We consider both the case of a monopolistic search engine (the rate of requests to the SE being assumed independent of the QoE) and that where that rate depends on the quality of the content providers it addresses users to. The ranking policies we examine are based on either quality alone (the neutral approach) or the revenues the content provider transfers to the search engine, possibly weighted through the quality of experience perceived by the user -representing two different non-neutral approaches.

To the best of our knowledge, this paper is one of the very first to try to model mathematically the impact of a non-neutral search engine behavior on the Internet actors, and to analyze it thanks to game theory. The other noticeable reference is [START_REF] Coucheney | Comparison of search engines non-neutral and neutral behaviors[END_REF]], but it is not focusing on the impact of advertisement as we are doing here.

The paper is organized as follows. Section 2 introduces the mathematical models considered in the paper for the quality-of-experience resulting from content with advertising, the influence of ranking on the visit rate of content providers, and the strategies of content providers. In Section 3, we analyze the case where content providers neglect their individual influence on the success of the search engine (the number of requests per time unit), with the advertising strategies of content providers studied as a non-cooperative game. We prove the existence of a Nash equilibrium for that game, whatever the ranking policy. Under a neutral policy, we find that content providers with the same intrinsic quality (the perceived quality in the absence of advertising) are led to reduce their advertising level as the number of competitors grows. Content providers with higher intrinsic quality are instead led to advertise more, getting larger revenues. If the search engine adopts a revenue-based ranking policy, we prove that content providers are led to set their advertising level to the maximum possible value, zeroing the quality perceived by users, regardless of their relationship to the search engine. If the revenue-based policy is mitigated by considering the quality of experience as well, vertically integrated content providers are favored, yielding more advertising and larger revenues. Section 4 treats the case of content providers including their effect on the request arrival rate in their strategic decision, and compares the performance of neutral and non-neutral rankings. In that case, we prove that the Nash equilibrium can be found as the solution of a system of polynomial equations. Under the neutral policy, content providers with the same intrinsic quality set their advertising level so as to halve their quality of experience. Under a non-neutral policy, content providers are instead led to increase their advertising as the number of competitors grows, though their revenues decline until being lower than in the neutral case. The conclusions are given in Section 5.

MODELS FOR THE BEHAVIOR OF THE STAKEHOLDERS

We consider a single search engine that has to rank different webpages hosting content when a user performs a search. Though we focus on a single search engine, we do account for the possibility that the user selects an alternative search engine, abandoning the strictly monopolistic market structure for search engines. Contents are controlled by different CPs, which can play with the amount of advertisement included in their webpage. Throughout this paper, we consider a given piece of content (e.g., a video sequence, a movie, a TV show) that is searched for by a user and proposed by a set I of CPs. In this section, we provide models for the behavior of all the stakeholders: users, the search engine, and content providers. A discussion on general challenges, modeling issues and interactions between stakeholders in the field of network economics can be found in [START_REF] Maillé | Telecommunication Network Economics: From Theory to Practice[END_REF].

User's quality of experience with content providers

In addition to the sheer quality of the content, the quality of CPs as perceived by users is influenced by several factors: the graphical design of the user interface, the number of clicks needed to reach the content, and the time elapsed before accessing the content (for example, some CPs add an advertising sequence of a few seconds before a video can be watched). In all those cases, advertisements included by a CP are perceived as a nuisance by users, lowering their overall quality of experience. Advertisements have therefore a two-fold effect: they positively affect the content providers' advertising revenues, but negatively affect the QoE perceived by users. We denote by A i the total amount of advertising introduced by CP i, and interpret it in two ways, depending on the considered point of view.

-For the CP: A i is proportional to the advertising revenue that the CP gets each time a user clicks on the link. -For users: A i corresponds to a nuisance, and advertisement is supposed to yield a loss of QoE proportional to A i .

Through some inessential changes of unit, we consider that CP i earns A i each time its content is accessed, and that the quality of experience V i for the user with CP i ∈ I is

V i = Q i -A i ,
where Q i > 0 is the intrinsic quality of the content of CP i (that experienced by the user if there were no advertisement). We assume that V i is an intrinsic characteristic of the content and advertisement bundle provided by the content provider, depending neither on the decisions taken by the search engine (e.g., its ranking criterion), nor on the user's tastes.

For convenience, we will also use the notation a i := A i /Q i , the relative amount of advertisement introduced by CP i. Note also that we limit the advertising level to values that give a non-negative QoE, therefore we have

A i ∈ [0, Q i ], or equivalently a i ∈ [0, 1].

User's choice of a search engine

We focus only on one SE in this paper, but the user may not choose that SE, e.g., if the quality of the results provided by the SE is bad. We summarize that effect through the average request arrival rate β (for the considered content) that the SE receives per time unit. We assume that it depends on the expected QoE of the user with that SE. We use β as a proxy for the probability that the user chooses that SE among all the possible choices.

SE ranking policies and click-through-rates

While the user's QoE is determined by both the webpage's intrinsic quality and the amount of advertisement, the ranking criterion has a considerable influence on the behavior of users, and may reduce the visibility of some CPs with good QoE. In general, most users click on one of the links in the highest slots allocated by the SE. We assume in this paper that the link clicked after a search depends only on the ranking determined by the SE based on the scores s = (s i ) i∈I attributed by the SE to each CP. The SE can adopt one of several score functions, depending on its aim. In this section, we examine the most relevant, subdivided into the two general categories of neutral and non neutral behavior of the search engine.

We do not address separately ranking and the subsequent user clicking behavior here (in terms of click-through rate for each position in the ranking), but rather aggregate those two phenomena by considering that the SE allocates the slots (possibly introducing randomness) based on the set of scores s, so that the proportion of clicks on CP i is

C i = s i j∈I s j . (1)
Note that the average total number of clicks per search can be different from 1, since some users may decide not to click any link while other may try several ones. That constant factor can however be considered equal to 1 without loss of generality, since it can be included in the value of β (that would then be interpreted as the number of links visited via the SE per time unit). In other words, C i is the probability (conditional on a link being clicked) that CP i is accessed. That probability describes the overall behavior of the user. score considered by the SE in the neutral case thus equals the QoE, i.e.

s i = V i , ∀i ∈ I. (2)
According to (1), the proportion C i of clicks on CP i is then

C i = V i j∈I V j = Q i (1 -a i ) j∈I Q j (1 -a j )
.

2.3.2. Non-neutral ranking strategies. We will say that the SE adopts a non-neutral stance when the scores considered to rank content providers are not the QoE values (V i ) i∈I . In particular, we investigate the case when the ranking criterion adopted by the SE takes into account that the SE obtains a share b i of the advertising revenue of each CP i ∈ I. This should then constitute an incentive for the SE to favor CPs with a large b i and large amounts of advertising. More specifically, we consider two possible non-neutral ranking strategies:

-Revenue-based ranking, where the SE ranks content providers on the basis of the revenue it can collect from them rather than the quality experienced by the users. If the search engine receives money by content providers, it has a real interest in favoring those that may generate more revenues, hence to set the ranking scores

s i = b i A i = b i Q i a i , ∀i ∈ I, (3)
which lead to a click-through rate

C i = b i Q i a i j∈I b j Q j a j . (4)
-Weighted-QoE ranking where the SE modifies the neutral ranking rule (based on the user's QoE alone), introducing a bias to favor the CPs for which it has a greater economic interest. The bias is modelled by introducing the corrective factor b i in the neutral rule (2), which can also be interpreted as the share of the CP controlled by the SE: this is directly connected to the search neutrality debate, where search engines can be accused of favoring the contents they (partially) own. The scores considered in that case are then

s i = b i V i = b i (Q i -A i ) = b i Q i (1 -a i ), ∀i ∈ I, (5)
so that the click-through rate is

C i = b i Q i (1 -a i ) j∈I b j Q j (1 -a j )
.

Content providers: revenues and strategies

The expected revenues (per time unit) of a content provider i ∈ I are denoted by R i . Since we are considering free content in this work, CPs' revenues only come from advertising and are proportional to the amount of advertisem ent added to their content, but also to the number of clicks they receive per time unit (that depends on the SE ranking through (1)).

After deducting the fee paid to the SE, the average revenues per time unit of any CP are

R i = βC i A i (1 -b i ) = βC i Q i a i (1 -b i ). ( 6
)
We remark that the revenue of a CP i depends on its strategic choice a i , but also on the amount of advertising (a j ) j∈I =i set by the other CPs, through the proportion of clicks C i to that CP defined in ( 4). Here we model those interactions among CPs as a noncooperative game [START_REF] Osborne | A Course in Game Theory[END_REF], where each CP chooses its advertising load a i to maximize its revenues. When studying that noncooperative game, we will distinguish two types of models, where content providers act as either price takers or price setters.

2.4.1. Price-taking content providers. The search engine market is currently dominated by Google. According to the statistics concerning the period October 2011 through March 2012 the share of Google was 80.39% (see the data at http://www.statowl.com/search engine market share.php), with a normalized Hirschmann-Herfindahl index of 0.66, which is by any means an indicator of strong dominance. Reasoning on a short-term basis, we can expect that this quasi-monopoly situation would remain even if the quality of the results displayed were affected by a change in the ranking policy (from neutral to non-neutral). In our model, this can be interpreted as the rate β of requests not being affected by the quality of the results. More precisely, that rate may still vary with the average QoE experienced by users, but CPs do not consider that effect when deciding their advertising policy. That bias can for example stem from a large number of CPs (hence the individual effect of each CP on β is small, and neglected). In that sense, content providers are price takers: they do not consider the effect of their own actions on the global "price" (here, the search rate β).

2.4.2.

Price-setting content providers. In this model, content providers do anticipate the effect that their advertising strategies have on the global success of the search engine, embodied by β. We highlight that dependence by writing β = β(a), where a = (a i ) i∈I is the advertising profile of CPs.

As a result, each CP i will choose its advertising level a i so as to maximize

R i = β(a i , a -i )C i (a i , a -i )a i (1 -b i ), (7)
where a -i is the profile of advertising strategies of all CPs but i, i.e., a = (a i , a -i ).

In such a case, CPs are said to be price setters, since they are aware of their contribution to the search rate β, which may decrease as the amount of advertisement increases. Acting as price setters corresponds to making strategic moves with an eye on the long term.

EQUILIBRIUM ADVERTISING STRATEGIES OF PRICE-TAKING CONTENT PROVIDERS

In this section, we investigate the case when CPs are price takers, i.e., they treat the total request rate β as a constant when determining their advertising strategy. For each ranking policy, we will provide results for the general case, before treating two specific situations:

-the symmetric case, where all CPs are identical, -the duopoly case where only two CPs compete.

We study the behavior of content providers in response to the ranking strategy of search engines as a non cooperative game. Content providers act as the players using the level of advertising as their strategic leverage to maximize their revenues. The game is solved by searching for a Nash equiibrium, after identifying the best response function of each player.

Neutral ranking

Since the multiplicative factor (1-b i ) is constant, and β is considered as constant by CPs in this section, the quantity that the i-th content provider intends to maximize, under neutral ranking with the scoring function defined in (2), is the utility proportional to

U i := R i β(1 -b i ) = a i Q i C i = a i Q i V i j∈I V j = a i Q i Q i (1 -a i ) j∈I Q j (1 -a j ) . ( 8
)
We can establish here the existence of a (non-trivial) Nash equilibrium for the noncooperative game played among CPs. Proposition 3.1. When the search engine performs a neutral ranking (i.e., based on relevance), the noncooperative game played by CPs fixing their advertising level has at least one Nash equilibrium a NE ∈ (0, 1) |I| . More precisely, there exists a Nash equilibrium, and any Nash equilibrium is such that

1/2 < 1 + φ i -φ 2 i + φ i ≤ a NE i < 1, (9)
with φ i := j∈I\{i} Qj Qi . Proof. When all the other CPs set their advertising quantities, the i-th content provider seeks the quantity a i maximizing U i , that is, its best-response to the others' strategic choices.

The case when all competitors of CP i set their advertising level to the maximum value a j = 1 is degenerate and is treated first. In that case, C i = 1 as soon as a i < 1, and U i = a i Q i is then strictly increasing in a i . But C i is not defined for a i = 1, hence no exact best-response exists. However, that case is not a problem, since the strategy a i = 1 is dominated for each CP i, and strictly dominated when at least one opponent j sets a j < 1. It is therefore an unlikely situation.

We now consider the case when at least one CP j = i sets a j < 1. In that case, U i is a continuous function of a i , as can be easily seen in ( 8).

We remark that U i = 0 when a i = 0 and when a i = 1, and that ∂ 2 Ui ∂a 2 i has the same sign as

a i Q i -(Q i + j∈I\{i} Q j (1 -a j ))
, that is strictly negative. As a result, U i is a strictly concave function of a i on the interval [0, 1], and has a unique maximum that is in (0, 1).

Therefore, the best response of CP i is the only solution in (0, 1) of the equation

∂U i ∂a i = ∂ ∂a i a i Q i Q i (1 -a i ) j∈I Q j (1 -a j ) = 0, (10)
which brings a quadratic equation in the advertising quantity

a 2 i -2   1 + j∈I\{i} Q j Q i (1 -a j )   a i + 1 + j∈I\{i} Q j Q i (1 -a j ) = 0. ( 11
)
Of the two solutions of that quadratic equation, the larger has to be discarded, since it would lead to a i > 1. The other solution is therefore in (0, 1), and gives us the best response function for content provider i:

a BR i = 1 + ψ i -(1 + ψ i ) 2 -(1 + ψ i ) = 1 + ψ i -ψ i (1 + ψ i ), (12)
with

ψ i := j∈I\{i} Q j Q i (1 -a j ). ( 13
)
For convenience we define f (x

) := 1 + x -x(1 + x), so that a BR i = f (ψ i ). Differentiating f , we get for x > 0 df (x) dx = 1 - 2x + 1 2 x(1 + x) = 1 - x + 1/2 (x + 1/2) 2 -1/4 < 0, ( 14
)
therefore f is strictly decreasing on R + , and thus

lim x→∞ f (x) = 1/2 < f (φ i ) < a BR i = f (ψ i ) < f (0) = 1, (15)
with φ i := j∈I\{i} Qj Qi . Now let us consider a small ǫ ∈ (0, 1), and consider any strategy vector a in the compact set [0, 1 -ǫ] |I| . From (13), ψ i ≥ (n -1) Qmin Qmax ǫ, where Q min := min j∈I Q j and Q max := max j∈I Q j . From ( 12), the best-response of each CP i to that strategy vector equals

a BR i = f (ψ i ) ≤ f (n -1) Q min Q max ǫ .
Remark from ( 14) that the derivative of f is continuous on (0, +∞) and tends to -∞ at 0, therefore we can find ǫ small enough so that f (n -1) Qmin Qmax ǫ ≤ f (0) -ǫ, using the continuity of f . Since f (0) = 1, we obtain that the best-response correspondence

G : [0, 1 -ǫ] |I| → [0, 1] |I| a → (a BR i ) i∈I is such that f [0, 1 -ǫ] |I| ⊂ [0, 1 -ǫ] |I| . Since G is continuous and [0, 1 -ǫ] |I| is a com- pact convex subset of R |I| ,
from Brouwer's fixed point theorem, it has a fixed point that constitutes a Nash equilibrium with strategies a i ∈ [0, 1).

The lower bound on the equilibrium strategies directly comes from the lower bound of the best-reply (see Equation ( 15)).

Though not amenable to an analytical solution, the collection of best response functions (12) for all the content providers builds a system of nonlinear equations in the a i 's, which can be solved numerically to obtain the Nash equilibria points.

3.1.1. Symmetric case. We can consider the special case where all content providers have the same intrinsic quality (symmetric case). By setting 11), the utility for the i-th provider assumes the simple form

Q i = Q in Equation (
U i = a i 1 -a i j∈I (1 -a j )
.

In that case, the game can be entirely solved:

Proposition 3.2. When the search engine performs a neutral ranking, the noncooperative game played by CPs fixing their advertising level has the unique Nash equilibrium

a NE i = n 2n -1 ∀i ∈ I, n := |I|. ( 16
)
Proof. The revenue optimization procedure leads to the equation

(1 -2a i ) j∈I (1 -a j ) + a i (1 -a i ) = 0. ( 17
)
This implies that for any i, k ∈ I, we have

(1 -2a i ) j∈I (1 -a j ) + a i (1 -a i ) = (1 -2a k ) j∈I (1 -a j ) + a k (1 -a k ), which yields (a k -a i )   a k + a i -1 + 2 j∈I (1 -a j )   = 0.
But from Proposition 3.1, we know that at a Nash equilibrium a j > 1/2 for all j ∈ I, hence the right factor is strictly positive, and a i = a k : Nash equilibria are necessarily symmetric, of the form a i = a for all i ∈ I. Plugging that condition into (17), we obtain a unique equilibrium, where the optimal advertising quantity a for any provider is as in ( 16).

The Nash equilibrium advertising level of ( 16) is a decreasing function of the number of content providers: each content provider is led to stuff less advertisements as the competition level (number of content providers) grows. In the limit, when the number of competitors becomes very large, we have the optimal advertising quantity that cuts by half the QoE with respect to the upper bound represented by intrinsic quality

a lim = lim n→∞ a = 1 2 .
In the symmetric case, the utility for each content provider is

U i = a 1 -a n(1 -a) = 1 2n -1 ,
while the cumulated utility of the bunch of content providers (recall that the revenue of each provider is its utility multiplied by

β(1 -b)) is U = i∈I U i = n 2n -1 .
Since utilities are proportional to revenues (recall that R i = β(1 -b)U i ) and can be taken as a proxy for them, that last expression shows that the aggregated revenue shrinks as the number of players grows: the overall utility reduces by 1/3 when there are just two providers, but by 1/2 when the number of players gets very large.

3.1.2. Duopoly case. Another special case of interest is duopoly, where just two content providers (with different quality) are present. In fact, the presence of high fixed costs reducing profit margins may raise barriers to the entrance of new players and favour a monopoly or duopoly situation (a case of high fixed costs and low marginal costs is presented in [START_REF] Naldi | Performance of the Vickrey auction for digital goods under various bid distributions[END_REF]). In this duopoly case, the best response functions (12) become

a 1 = 1 - Q 2 Q 1 (1 -a 2 ) 1 + Q 1 Q 2 1 1 -a 2 -1 a 2 = 1 - Q 1 Q 2 (1 -a 1 ) 1 + Q 2 Q 1 1 1 -a 1 -1 .
Again, we can solve that system of nonlinear equations numerically, finding the Nash equilibrium as the intersection (if any) between the best responses being drawn on the same figure, as in Figure 1 (left). The best-response functions for the duopoly case are shown when the providers have equal intrinsic quality. The same shape is observed in all the other cases we have examined. Though the curves cross in two points, the solution that leads to a 1 = a 2 = 1 is to be discarded, since as explained in the proof of Proposition 3.1 there is no real best-response for CP i when the opponent j = i sets a j = 1, and moreover the strategy a i = 1 is dominated, and strictly dominated as soon as a j < 1.

In Figure 1 (right), we see how the Nash equilibrium point moves as the differences in quality between the two providers change. A content provider with higher intrinsic quality can increase its advertising load. In the symmetric case (Q 1 = Q 2 ), we obtain the Nash equilibrium point a 1 = a 2 = 2/3 from Equation ( 16) with n = 2.

3.1.3. Numerical study. We now go back to the general asymmetric case of n content providers and assess the presence and characteristics of Nash equilibrium in typical scenarios. For that purpose, we consider two types of repartition of the intrinsic quality among CPs: linear and geometric. Without loss of generality, we sort the CPs in decreasing order of quality: CP 1 exhibits the largest intrinsic quality, and CP n has the lowest one. We can define the quality of the generic i-th content provider as a function of the two bounds Q 1 0 0.5 1 0 0.5 1 Advertising factor a 2 of CP 2 Advertising factor a 1 of CP 1 a BR 1 (a 2 ) a BR 2 (a 1 ) (a) Best response functions 0.5 0.6 0.7 0.8 0.5 0.6 0.7 0.8

Q 1 /Q 2 = 10 Q 1 /Q 2 = 0
Advertising factor a 2 of CP 2 Advertising factor a 1 of CP 1 (b) Nash equilibrium points Fig. 1. Best response functions in the symmetric duopoly case (left) and locus of Nash equilibrium points in a duopoly, both under neutral behavior and Q n . In the linear model, the intrinsic quality of the i-th content provider is

Q i = Q 1 - i -1 n -1 (Q 1 -Q n ). ( 18
)
In the geometric model, we have instead

Q i = Q 1 exp - i -1 n -1 ln(Q 1 /Q n ) .
Note that we consider here that the share of benefits taken by the search engine is the same for all CPs, i.e. b i = b for all i ∈ I.

We report here the case of 5 content providers, with the extreme intrinsic quality values Q 1 = 0.9 and Q 5 = 0.1. We want to see how the intrinsic quality influences the amount of advertisement that is optimal for the content provider (as resulting from the Nash equilibrium). We use the solution (12). Both in the linear and the geometric case, we find a single Nash equilibrium. The relation between the intrinsic quality and the relative amount of advertising (the advertising factor a i ) is shown in Figure 2. Content providers with larger intrinsic quality are led to increase the weight of advertising, though the sensitivity is quite small: a ninefold increase in the intrinsic quality corresponds to an advertising factor increasing by just 17.58% in the linear model and by 21.94% in the geometric one.

Utility (and therefore, the revenue of the CP) is also affected by the intrinsic quality, as shown in Figure 2 (right). Though both trends are approximately linear, the more uneven repartition of qualities in the geometric case leads to wider imbalances in the repartition of utilities. While the ratio Q max /Q min of extreme intrinsic qualities is 9 in both cases, the range of utility U max -U min is larger for the geometric repartition (though the high-to-low ratio for utility is 8.63 for the linear case and just 8.41 for the geometric one)

After examining the impact of the intrinsic quality on the individual strategic decisions about the level of advertising, we now turn our attention to the impact on the quality perceived by users. For the i-th content provider, the introduction of advertisement brings its quality down from the intrinsic value Q i to the QoE V i = Q i (1-a i ). In the above example, we have considered a wide range for intrinsic quality values. That would be the range of quality values experienced by users in the absence of advertisement. We can examine if the introduction of advertisement (which is the leverage through which content providers seek their maximal profits) magnifies those differences in quality or levels them out.

In order to assess that impact, we employ the Herfindahl-Hirschman Index, which measures the concentration of a market among a number of competitors (i.e., the level of com- Fig. 2. Impact of the intrinsic quality on the game outcome (left) and utility (right), for price-taking CPs and a neutral ranking petition) and is the most sensitive among such indicators [START_REF] Naldi | Concentration indices and Zipf's law[END_REF]]. Given a set of market shares {m 1 , m 2 , . . . , m n }, which satisfy the constraint i∈I m i = 1, the HHI is

HHI = i∈I m 2 i , (19)
and lies in the interval [0, 1]. Higher values of the HHI indicate a larger degree of concentration (hence a lower level of competition). Here we do not have the market shares (expressed as fractions of the overall revenues), but we consider utility values as their proxy. In fact, utilities are proportional to revenues, the proportionality constant being equal for all competitors. After normalizing the utility values to their sum, we get figures equal to the market shares. In order to distinguish the HHI computed by using utilities to that computed using the market shares (though they lead to the same numerical result), we use the definition

HHI U = i∈I U i j∈I U j 2 = i∈I U 2 i i∈I U i 2 .
In addition to measuring the concentration of the market, we can use the HHI to measure the attraction power through quality values. In fact, quality works as a magnet for users: contents of higher quality attract more users, and differences in quality correspond to different capabilities to attract users. In this context, the HHI can be used to measure the degree of concentration of quality among the content providers. If we replace the market shares in the definition ( 19) with quality values, we obtain the two quality-based HHI

HHI Q = i∈I Q i j∈I Q j 2 = i∈I Q 2 i i∈I Q i 2 , HHI V = i∈I V i j∈I V j 2 = i∈I V 2 i i∈I V i 2 ,
employing respectively the intrinsic quality and the perceived quality. Larger values of HHI Q mean higher imbalances in quality. By comparing HHI Q (prior to including advertising) with HHI V (including advertisements), we can assess the effect of advertising choices of all content providers on the structure of the quality offer. We report the results in Table I. Under both the linear and the geometric model, the HHI index is larger (though not by much) for the intrinsic quality than for the QoE: the introduction of advertisement brings along a slight levelling of the quality perceived by the user. In Table I, we also report the HHI (denoted by HHI U ) pertaining to market concentration. We see that the concentration is somewhat intermediate between that of the intrinsic quality and that of the perceived quality: the repartition of utility is less affected by the introduction of advertisement than the quality perceived by users.

Non-neutral behavior: revenue-based ranking

When the ranking is only based on the potential revenue for the SE, and scores are taken from ( 3), with the position X i := b i Q i , the utility of the content provider is given by:

U i = βA i C i (1 -b i ) = β 1 -b i b i a 2 i (b i Q i ) 2 j∈I a j Q j b j = 1 -b i b i a 2 i X 2 i j∈I a j X j .
The following proposition shows that the non-neutral behavior incentivizes CPs to increase their advertising level with respect to the neutral case. That incentive is indeed twofold, since a larger a i yields more revenue per click, but also attracts more clicks because of the non-neutral ranking (where s i increases with a i ).

Proposition 3.3. When the search engine performs a revenue-based ranking, the noncooperative game played by price-taking CPs fixing their advertising level has a unique Nash equilibrium where each CP sets its advertising level to the maximum possible value, a i = 1 for all i ∈ I.

Proof. We simply see that the revenue R i of a CP i ∈ I is strictly increasing in a i : it is indeed null for a i = 0, and for a i > 0 it is strictly positive with

∂U i ∂a i = β 1 -b i b i X 2 i 2a i j =i a j X j + a 2 i X i ( j∈I a j X j ) 2 > 0.
We immediately remark that, in that case, the resulting QoE is V i = 0 for each CP i.

The revenue of each CP

i ∈ I becomes R i = β 1 -b i b i X 2 i j∈I X j .
If all CPs transfer to the search engine the same share of their revenue, i.e. b i = b for all i, then we obtain

R i = β(1 -b) Q 2 i j∈I Q j
. Additionally, if as in Section 2.3.1 we consider the symmetric case, where the n content providers have the same intrinsic quality, i.e.

Q i = Q, then each CP gets a revenue R i = β(1 -b) Q n .
Note that when β varies (increases) with the average QoE for users, that revenue can be much smaller than initially expected by CPs, that as price takers made their strategic choices considering β to be a constant. For example, if as in Section 4 we take β proportional to the expected user QoE, then the final outcome is a situation where users prefer not to use the search engine (since β = 0), and the CPs make no revenue.

Non-neutral behavior: weighted-QoE ranking

We investigate here the situation where the ranking scores are taken from (5), i.e., the search engine considers the QoE as in the neutral case, but introduces some weights among them so as to favor the CPs it has most interest in.

The resulting proportion of clicks per search on CP i is then

C i = Q i (1 -a i )b i n j=1 Q j (1 -a j )b j .
Accordingly, the utility of the content provider is given by the difference between what it receives through advertising and what it passes to the search engine:

U i = a i C i (1 -b i ) = Q i a i b i (1 -a i )(1 -b i ) n j=1 Q j (1 -a j )b j . (20)
Again, each content provider seeks to maximize its revenue by setting the quantity of advertising. The analysis follows that carried out in Section 3.1, where for each CP i the parameter Q i is replaced by b i Q i . In particular, the best response function of CP i is then

a i = 1 + n j=1 j =i Q j b j Q i b i (1 -a j ) -     1 + n j=1 j =i Q j b j Q i b i (1 -a j )     n j=1 j =i Q j b j Q i b i (1 -a j ).
We then have the counterpart of Proposition 3.1.

Proposition 3.4. When the search engine performs a weighted-QoE ranking with weights (b i ) i∈I , the noncooperative game played by price-taking CPs fixing their advertising level has at least one Nash equilibrium a NE ∈ (0, 1) |I| . More precisely, there exists a Nash equilibrium, and any Nash equilibrium is such that

1/2 < 1 + φi -φ2 i + φi ≤ a NE i < 1,
with φi := j∈I\{i} bj Qj biQi . Remark that the symmetric case, where the n content providers have the same intrinsic quality and transfer to the search engine the same share of their utility (i.e.,

Q i = Q, b i = b)
gives the exact same case as the one analyzed in Section 3.1.1 for the neutral ranking.

3.3.1. Numerical study. We examine now the asymmetric case, solving the game by numerical means. Again, we use the scenario of Section 3.1.3, with 5 content providers whose intrinsic quality follows either a linear or a geometric trend. We consider the case where one content provider is owned by the search engine (it transfers all its utility to it) and all the others pay the same share b i = 0.1, with two scenarios: the content provider owned by the search engine is that exhibiting either the highest intrinsic quality (Scenario A) or the lowest one (Scenario B), as reported in Table II. We examine the advertising choices made by the content providers and their impact on utility.

We report the results of the game, namely the resulting advertising factor a i determined by each provider, in Figure 3 for the two scenarios. In both cases we see that the content providers not owned by the search engine use an advertising factor that is slightly increasing with the intrinsic quality. Instead, the content provider owned by the search engine is led to substantially increase its advertising load, especially when its intrinsic quality is large: the boost is much higher in Scenario A (where the vertically integrated content provider has an intrinsic quality of 0.9) than in Scenario B (where that intrinsic quality is just 0.1). If we consider the net utility (that remaining after transferring a share to the search engine), the vertically integrated content provider has of course zero utility. But we get a better view of the competition between content providers by considering the gross utility (that obtained prior to paying the tax to the search engine), defined after Equation (20) as

Ûi = Q i a i b i (1 -a i ) n j=1 Q j (1 -a j )b j . ( 21
)
In Figure 3 (right), we see that for all providers but that owned by the search engine the utility grows roughly linearly with the intrinsic quality, though at a faster rate in the geometric case. The utility of the content provider owned by the search engine is instead boosted by the larger cash flow it transfers to the search engine, which in turn raises its score in the non-neutral case. The boost is again larger in Scenario A, i.e., when the vertically integrated content provider has the largest intrinsic quality. However, even in Scenario B the boost is enough to bring the vertically integrated content provider to include as much advertisement as the content provider with the highest intrinsic quality.

We can now perform the same concentration analysis as in the neutral case. For the gross utility defined in (21), we can similarly define the HHI

HHI Û = i∈I Û 2 i i∈I Ûi 2 .
The values obtained for HHIs are shown in Table III. By comparing the values of HHI before and after introducing advertisements (i.e., HHI Q AND HHI V ), We observe that the introduction of advertisement somewhat levels the quality perceived by users, since the HHI for the QoE is lower than that for the intrinsic quality. Instead, the market concentration is significantly altered, in a way that depends on which content provider is owned by the search engine. If the search engine owns the content provider with the highest intrinsic quality (Scenario A), that further boosts its score and its utility, leading to a quite stronger concentration: HHI Û is more than twice as large as HHI Q . When the search engine owns the content provider with the lowest intrinsic quality (Scenario B), the utility of the latter is likewise pushed up, but this leads to a more balanced repartition and a diminishing HHI.

EQUILIBRIUM ADVERTISING STRATEGIES OF PRICE-SETTING CONTENT PROVIDERS

Though the present situation of the search engine market is rather close to the monopoly analysed in Section 3, this is neither the general case nor a sure prediction for the future.

In this section, we consider that users may select a different search engine. For this general case, we define a game model and find the best response functions. We apply the model to some scenarios and examine the resulting advertising strategies. As in Section 3, we consider separately the case of neutral and non neutral behavior by the search engine.

The propensity of a user to use the search engine under consideration is still represented by β, assumed here to be proportional to the average QoE of content providers accessed through that search engine (the expected user's QoE when clicking on a link, C i being the probability that the user ends up visiting CP i):

β = i C i V i .
We recall the general expression (7) for CP i's revenues

R i = β(1 -b i )C i a i , (22)
where C i = s i / j∈I s j , and s i is the score credited to CP i by the SE.

Neutral behavior

As in Section 3.1, the neutral ranking is based on V i , hence the proportion of clicks on CP i

C i = V i j∈I V j .
By neglecting the revenue transfer to the search engine in the general expression ( 22) for the revenues, we can use the utility U i = βC i a i .

Under that ranking behavior, the revenue of the i-th content providers is proportional to

U i = j∈I V 2 j j∈I V j V i j∈I V j a i , (23)
which, by setting X = j∈I V j and Y = j∈I V 2 j , can be simplified to U i = V i Y X 2 a i . The i-th content provider optimizes its advertising behavior by maximizing its utility through the appropriate amount of advertising. Remark that U i = 0 if a i = 0 or a i = 1, and U i > 0 when a i ∈ (0, 1), therefore if the equation ∂U i /∂a i = 0 has a unique solution, that solution would give the best response function a * i = f (a 1 , a 2 , . . . , a i-1 , a i+1 , . . . , a n ). However, since ∂U i /∂a i = U i /a i + ∂U i /∂V i • ∂V i /∂a i , and ∂V i /∂a i = -Q i , the optimization equation becomes simply U i /(Q i -V i ) -∂U i /∂V i = 0. By expanding this equation, we obtain the following simplified form of the optimization equation for CP i

2V i (V i X -Y ) 1 - V i Q i + XY 1 -2 V i Q i = 0. ( 24
)
If we now replace the full expression for X and Y , and rearrange terms, we obtain a fourth-degree polynomial equation in the QoE

V 4 i +   2 j∈I\{i} V j - Q i 2   V 3 i -   3 2 Q i j∈I\{i} V j   V 2 i + j∈I\{i} V 2 j   j∈I\{i} V j + Q i 2   V i - Q i 2 j∈I\{i} V j j∈I\{i} V 2 j = 0.
By collecting the n similar expressions for the best response functions of all the content providers, we end up with a system of n polynomial equations, which has to be solved to find Nash equilibria. The system of equations can be solved numerically.

We can consider the special symmetric case by setting Q i = Q, b i = b, and a i = a in the general Equation ( 23), since nothing else depends on the specific content provider:

U = nV 2 nV V nV a = Q n a(1 -a).
The first order optimality condition is then

∂U ∂a = Q n (1 -2a) = 0, whose solution is a = 1 2 .

Non-neutral behavior: revenue-based ranking

In that case, the utility function of the search engine becomes

U i = C i a i j∈I C j V j = b i a 2 i j∈I b j Q j a j (1 -a j ) k∈I b k a k 2 . ( 25
)
From the utility maximization condition, we get

∂U i ∂a i = 2b i a i j∈I b j Q j a j (1 -a j ) ( n k=1 b k a k ) 2 +b 2 i a 2 i Q i (1 -2a i ) ( n k=1 b k a k ) -2 j∈I b j Q j a j (1 -a j ) ( n k=1 b k a k ) 3 = 0,
which leads to the following optimization equation whose solution should provide the best response function for the i-th content provider

2 j∈I b j Q j a j (1 -a j ) 1 - b i a i n k=1 b k a k + b i a i Q i (1 -2a i ) = 0,
giving the following third degree polynomial equation in a i :

-2b i a 3 i +   b i -4 k =i b k a k   a 2 i -3 k =i b k a k a i + 2 k =i b k a k j =i b j Q j a j (1 -a j ) b i Q i = 0.
Instead of the numerical approach required in the general case, we can find a simple form of the best response function in the symmetric case. If all the content providers transfer the same percentage of their utility to the search engine and exhibit the same intrinsic quality, revenue (the aggregated revenue of all CPs but the owned one prior to paying the SE, the revenue of the SE hence including the integrated CP revenue), and the global revenue, i.e. the sum of both. Notice that, even in the neutral scenario, the equilibrium depends on the CP vertically integrated with the SE, since their revenue is shared between both entities.

When the smallest CP is integrated with the SE, we observe on Figure 6 that all revenues decrease with the number of CPs. In addition, when there are more than three CPs, the ranking policies are Pareto ordered: the revenue-based ranking is worst for every stakeholder, and the neutral one is always preferred. This suggests that there is no need to enforce search neutrality: even for the search engine it is preferable to implement a neutral ranking.

In the case of the biggest CP integrated, we see on Figure 5 that the comparison is not as clear. The revenues are decreasing w.r.t. the number of players for every stakeholder, except the gross revenue, which increase at first: as the number of CPs grows, they get a bigger and bigger proportion of the global revenue at the expense of the SE. The weighted-QoE based ranking provides larger revenues both for the SE and on the overall, probably because owning the biggest quality CP (rather than the smallest quality one) gives the SE a stronger position in the game so as to adopt a non-neutral ranking. Also, users get a larger welfare for any ranking policy compared to Figure 6 and prefer weighted-QoE based ranking. Since the user's welfare corresponds to the propensity of using the SE, the average relevance is better with the non-neutral ranking. This observation, although not intuitive, shows that the use of non-neutral ranking may result in a Nash equilibrium where less advertisement is set compared to the neutral equilibrium. But this holds here because the SE owns the most relevant CP, and therefore should not be taken as a valid argument against neutrality. Indeed, one of the objectives of search neutrality is to enable innovation, by making (relevant) new entrants reachable through the SE: in our case a weighted-QoE based ranking goes against that objective, since the average perceived relevance is lower than in the neutral case in Figure 6 (when the best CPs are not owned by the SE).

Finally, note that in both scenarios the revenue of the non-integrated CPs is larger with a neutral ranking, which suggests enforcing neutrality. Indeed, even if a non-neutral stance increases the user's QoE when the SE integrates quality content, it harms the other CPs revenue, possibly preventing them from innovating and improving their quality.

CONCLUSIONS

This paper provides a mathematical model for the analysis of different ranking policies by search engines, in a context when content providers have to compete for users, and make revenue through advertising. Depending on the ranking adopted, content providers can choose their advertising level, balancing larger advertising revenues against lower qualityof-experience and less users. We have analyzed the noncooperative game played among content providers in different settings, and studied the corresponding equilibria.

Our results indicate that the neutral ranking provides users with the largest perceived quality-of-experience, which is not surprising. But we also observe that such a ranking policy can be preferred as well by a search engine willing to maximize revenue, a less intuitive outcome: this is true if the search engine does not control the best-performing content providers. However, if the search engine integrates quality content, then it can increase its revenue by switching to a non-neutral ranking; this may even benefit to users who will perceive a better quality-of-experience, but would be at the expense of the other content providers, and can then be seen as an impediment to innovation for new entrants.

Fig. 3 .

 3 Fig.3. Impact of the intrinsic quality on the advertising factor (left) and gross utility (right), with pricetaking CPs, weighted-QoE ranking.

Fig. 4 .

 4 Fig. 4. Nash equilibrium advertising factors (left) and CP utility (right) in the neutral and two non-neutral scenarios, for the symmetric case and price-setting CPs, with b = 0.1 and Q = 1

Fig. 5 .

 5 Fig. 5. Utility indices when the highest quality CP is vertically integrated with the SE.

Fig. 6 .

 6 Fig. 6. Utility indices when the smallest quality CP is vertically integrated with the SE.

Table I .

 I Attraction power concentration (price-taking CPs)

		Linear repartition	Geometric repartition
	HHI Q	0.264	0.305
	HHI V	0.253	0.279
	HHI U	0.261	0.298

Table II .

 II Intrinsic quality and revenue transfer to the search engine in the non-neutral case study

				Intrinsic quality Q i	Revenue transfer b i
				Linear	Geometric	Scenario A	Scenario B
				0.1	0.1	0.1	1
				0.3	0.17	0.1	0.1
				0.5	0.3	0.1	0.1
				0.7	0.52	0.1	0.1
				0.9	0.9	1	0.1
	Advertising factor a i	0.5 0.6 0.7 0.8	Integrated CP
			0.2	0.4	0.6	0.8
			Intrinsic quality Q i

Table III .

 III Concentration of attraction power with price-taking CPs and weighted-QoE based ranking

	Scenarios	A linear	B linear	A geometric	B geometric
	HHI Q	0.264	0.264	0.305	0.305
	HHI V	0.247	0.259	0.249	0.292
	HHI Û	0.644	0.227	0.708	0.261

ACM Journal Name, Vol. V, No. N, Article A, Publication date: January YYYY.

we expect their best response function to be the same. After setting b i = b, Q i = Q, and a i = a, and some manipulation, we obtain the symmetric equilibrium advertising level

When the number of providers grows, the relative amount of advertising tends towards the saturating value 1. If we insert the solution (26) in the general expression of utility (25), we get the utility for the symmetric case

Non-neutral behavior: weighted-QoE ranking

With the scores taken from (5), the utility function of CP i becomes

.

If we set, for sake of simplicity, X = j∈I b j Q 2 j (1 -a j ) 2 and Y = j∈I b j Q j (1 -a j ), the optimization equation can be written as a fourth-degree polynomial equation in a

If we consider the symmetric case, we have X = nbQ 2 (1-a) 2 and Y = nbQ(1-a), which, when replaced in ( 27), give the symmetric equilibrium advertising factor

which tends to the limit a = 1/2 when the number of providers grows.

In the symmetric case, the utility of each CP is therefore

= bQ 2 n(n + 1) 2 (2n + 1) 3 .

Neutral vs Non-neutral Ranking

We now compare the ranking strategies for the search engine, when the CPs have identical intrinsic qualities. We plot in Figure 4 the equilibrium advertising levels in the symmetric case vs the number of content providers. We refer to the equilibria in ( 26) and ( 28) respectively as revenue-based and weighted-QoE scoring. Both functions grow with the number of providers, but achieve different values. When the behavior of the search engine is purely greedy, the advertising factor starts at 0.75 with two CPs and tends to 1 when the number of CPs grows (under tough CP competition the QoE gets very close to zero). Instead, if the scoring function includes the QoE, the optimal advertising factor starts at 0.4 in the duopoly case and, though growing, is upper bounded by the value 0.5: users will get a QoE never lower than what they get in the neutral case (half the intrinsic quality value).

In Figure 4 we also plot the gross utility of each CP. A neutral ranking favors CPs, unless the number of competing CPs becomes large (above 20 when b = 0.1). In that case, the weighted-QoE based ranking would yield a larger utility to CPs.

We now assess the impact of the ranking policy in a non-symmetric setting, with a linear repartition of quality (18), when the number of CPs changes (the geometric distribution yields similar results). We consider two scenarios: the CP owned by the SE is that with the highest (Figure 5) or the lowest intrinsic quality (Figure 6). We solve the game iteratively. In order to evaluate the impact on users, we define user welfare (or, with a slight abuse of vocabulary, the revenue of users) as being equal to β, i.e. the propensity of users to use the search engine. We examine the revenue of the SE (which includes that of its CP), the gross