O Brun
email: brun@laas.fr

B J Prabhu
email: bjprabhu@laas.fr

Worst-case Analysis of Non-Cooperative Load Balancing

We investigate the impact of heterogeneity in the amount of incoming traffic routed by dispatchers in a non-cooperative load balancing game. For a fixed amount of total incoming traffic, we give sufficient conditions on the cost function under which the worst-case social cost occurs when each dispatcher routes the same amount of traffic, that is, the game is symmetric. We then analyze the symmetric game and derive an explicit expression for the equilibrium flows. We also obtain lower bounds on the Price of Anarchy for (i) cost functions that are polynomial on server loads; and (ii) cost functions representing the mean delay of the Shortest Remaining Processing Time (SRPT) service discipline.

Introduction

We consider a distributed load-balancing system comprising of multiple dispatchers and multiple servers. The task of a dispatchers is to receive requests and decide which server to route them to. The routing decisions are taken by the dispatchers so as to minimize the cost (for example, the mean waiting time) incurred by the requests it routes. We shall assume that the dispatchers do not exchange information on their strategies and take decisions independently of the others. Thus, the dispatchers are involved in a non-cooperative game. Since the number of players (dispatchers) is finite, we shall be interested in the performance of the system at the Nash Equilibrium (NE).

Although the distributed architecture described above is attractive due to its scalability and robustness, it can be inefficient from the system performance 1 point of view. Indeed, since each dispatcher minimizes its own cost function, the system performance is possibly worse than that in a centralized architecture. Thus, before going in for a distributed architecture, a system designer may be interested in knowing how worse its performance can be compared to that of a centralized architecture.

Our objective is to find out under what circumstances we can expect to find the worst-case scenario for the distributed load-balancing system, and then to characterize how worse this performance can be. We first show that, for a fixed total incoming traffic to the system, the worst-case performance at the NE occurs when all the dispatchers have the same amount of traffic to be routed, that is, they are involved in a symmetric game. We give sufficient conditions on the objective function under which the above statement is true. We then analyze the symmetric game and derive an explicit expression for the equilibrium flows. Using this result, we give a lower bound on the Price of Anarchy (PoA, [START_REF] Koutsoupias | Worst-case equilibria[END_REF]) for cost functions of type: (i) 1 + x m ; and (ii) 1/(1x) m .

Related work

The distributed load balancing game has been analysed previously by several authors. In [START_REF] Ayesta | Price of anarchy in non-cooperative load balancing games[END_REF], similar results were obtained for the M/M/1 type delay functions, and the present work is a generalization of that to a larger class of cost functions. In terms of methodology, our work is closely related to that of Orda et al [START_REF] Korilis | Capacity allocation under noncooperative routing[END_REF][START_REF] Orda | Competitive routing in multi-user communication networks[END_REF] and the arguments we use are inspired from their work. However, there are a couple of differences with their work. First, in [START_REF] Korilis | Capacity allocation under noncooperative routing[END_REF], the authors restrict themselves to the M/M/1 delay function, whereas we consider a larger class of cost functions. In particular, we allow for the association of a heterogeneous cost per unit time (holding cost) with each server. The introduction of heterogeneous holding costs can significantly change the PoA for certain cost functions. For example, for the M/M/1 delay function and equal holding costs, it was shown in [START_REF] Haviv | The price of anarchy in an exponential multi-server[END_REF] that the PoA is upper bounded by the number of servers whereas for the same model and unequal holding costs, it was shown in [START_REF] Ayesta | Price of anarchy in non-cooperative load balancing games[END_REF] that the PoA is of the order of the square root of the number of dispatchers as long as there is at least one server. Second, in [START_REF] Korilis | Capacity allocation under noncooperative routing[END_REF], it is shown that, for a fixed incoming traffic vector, transferring capacity from a server to another one that has a higher service rate improves the performance at the NE. We look at the complementary problem in which we fix the service capacities, and look at what happens when we transfer traffic from one dispatcher to another.

The computation of PoA for disciplines other than Processor Sharing (or the M/M/1 delay function) has also been previously investigated. In [START_REF] Anselmi | Optimal routing in parallel, non-observable queues and the price of anarchy revisited[END_REF], the authors compute the PoA of routing policies with memory in server farms with First-Come-First-Served or Processor Sharing service discipline using a lower bound on the cost of the centralized architecture. The computation of PoA for server farms with SRPT discipline but without memory was given in [START_REF] Chen | The effect of local scheduling in load balancing designs[END_REF]. The authors compute the PoA on assuming that the system is in heavy-traffic. Our approach and our model differ from these papers in that we give the worst-case scenario for any fixed total traffic vector whether the system is in heavy traffic or not. Using this scenario we construct a lower bound on the PoA. Moreover, in our model, we have a finite number of dispatchers whereas in the model of both these papers each request takes a decision by itself, thereby leading to an infinite number of dispatchers.

Organization of the paper

The rest of the paper is organized as follows. In Section 2, we describe the model and state the problem. In Section 3, we explore the structure of the underlying Nash equilibria and prove their existence and uniqueness. We also establish several properties of these equilibria that form the foundation of the subsequent analysis. In Section 4, we analyze the social cost at the Nash equilibria, and show that the maximum of this cost is achieved in the symmetric case. We then analyze the symmetric game and derive an explicit expression for the equilibrium flows in Section 5. With this result at hand, in Section 6, we derive lower bounds on the PoA for the two different cost functions mentioned previously. Finally, we draw some conclusions in Section 7.

Problem Formulation and Main Results

Denote C = {1, . . . , K} to be the set of dispatchers and S = {1, . . . , S} to be the set of servers. Jobs received by dispatcher i are said to be jobs of class i.

Server j ∈ S has capacity r j and a holding cost c j per unit time is incurred for each job sent to this server. We let u j = cj rj denote the ratio of the holding cost to the capacity for server j. By convention, u S+1 = ∞. It is assumed that servers are numbered in the order of increasing cost per unit capacity, i.e., if m ≤ n, then u m ≤ u n , so that the first servers are more attractive than the last ones. Let r = (r j ) j∈S and c = (c j ) j∈S denote the vectors of server capacities and server costs, respectively, and let r = n∈S r n denote the total capacity of the system. Jobs of class i ∈ C arrive to the system according to a Poisson process and have generally distributed service-times. Let λ i be the traffic intensity of class i. It is assumed that λ i ≤ λ j for i ≤ j. Moreover, it will also be assumed that the vector λ of traffic intensities belongs to the following set:

Λ = λ ∈ IR K : i∈C λ i = λ ,
where λ denotes the total incoming traffic intensity.

Let x i = (x i,j ) j∈S denote the routing strategy of dispatcher i, with x i,j being the amount of traffic it sends towards server j. Let

X i =    x i ∈ IR S : 0 ≤ x i,j ≤ r j , ∀j ∈ S; j∈S x i,j = λ i   
denote the set of feasible routing strategies for dispatcher i. The vector x = (x i ) i∈C will be called a multi-strategy. The multi-strategies belong to the product strategy space X = i∈C X i .

Dispatcher i seeks to minimize its cost function which is denoted by T i (x). This optimization problem can be formulated as follows:

minimize xi∈Xi T i (x)
The model is illustrated in the figure below.

1 j S K i 1

Dispatchers

Servers A Nash equilibrium of the routing game is a multi-strategy from which no class finds it beneficial to deviate unilaterally. Hence, x ∈ X is a Nash Equilibrium Point (NEP) if

λ 1 λ i λ K r 1 , c 1 r j , c j r S , c S x i,j
x i = arg min z∈Xi T i (x 1 , . . . , x i-1 , z, x i+1 , . . . , x K ), ∀i ∈ C.
Turning our attention to a server j ∈ S, we let y j be the total flow on that server, i.e., y j = i∈C x i,j . We let also ρ j = y j /r j denote the utilization rate of server j ∈ S. In the following, it will be assumed that the cost function of each user i ∈ C is the sum of server cost function, i.e.,

T i (x) = j∈S ψ j (x i,j , y j ),
where, ψ j (x i,j , y j ) = u j x i,j φ(ρ j ).

Note that the cost incurred by class i on server j depends both on its amount of flow on that server, which measures its "investment" on that server, and on the total amount of flow through the server, which determines the server performance.

We shall consider two different types of congestion functions φ. Cost functions of the first type operate over the domain D = [0, +∞) and satisfy the following assumptions:

I-1 φ : [0, ∞) → [1, ∞),
I-2 φ(0) = 1 and lim ρ→∞ φ(ρ) = +∞, I-3 φ is a continuous, strictly increasing and convex function on [0, ∞), I-4 φ is continuously differentiable and its second derivative φ ′′ exists.

Cost functions satisfying the above assumptions will be referred as type-I functions in the following. For type-I congestion function, it will be assumed throughout the paper that r j = 1, j ∈ S. In this case, ψ j (x i,j , y j ) = c j x i,j φ(y j ) for all j ∈ S. Examples of such functions include polynomial functions φ(ρ) = 1 + α k ρ k with α k > 0 and k ≥ 1, as well as functions of the type φ(ρ) = exp(ρ).

Congestion functions of the second type are defined over the domain D = [0, 1). They satisfy the following assumptions:

II-1 φ : [0, 1) → [1, ∞),
II-2 φ(0) = 1 and lim ρ→1 -φ(ρ) = +∞, II-3 φ is a continuous, strictly increasing and convex function on [0, 1), II-4 φ is continuously differentiable and its second derivative φ ′′ exists.

Typical type-II functions are those from queueing theory, e.g. the M/G/1/PS congestion function φ

(ρ) = 1 1-ρ or the M/G/1/FCFS congestion function φ(ρ) = 1+ρ 1+c 2 b 2 (1-ρ)
, where c 2 b denotes the squared coefficient of variation of the job sizes. This class of functions also contains the delay function of the M/P areto/1/SRP T in heavy-traffic, which is given by 1 (1-ρ) m , where m depends on the shape parameter of the Pareto distribution [START_REF] Chen | The effect of local scheduling in load balancing designs[END_REF]. For type-II functions, it will be assumed throughout the paper that λ < r, which is the necessary and sufficient condition to guarantee the stability of the system.

Cost functions ψ j that comply with type-I or type-II assumptions are a special case of type-B functions, as defined in [START_REF] Orda | Competitive routing in multi-user communication networks[END_REF]. As proved in Theorem 2.1 of this reference, these assumptions are sufficient to assert the existence of a unique NEP.

Let ψ ′ j be the partial derivative of ψ j with respect to its first argument. We therefore have

ψ ′ j (x i,j , y j ) = u j φ(ρ j ) + x i,j r j φ ′ (ρ j ) , (1)
for all j ∈ S. According to the Karush-Kuhn-Tucker (KKT) optimality conditions, x ∈ X is a NEP if and only if there exist multipliers µ i such that

ψ ′ j (x i,j , y j ) = µ i if x i,j > 0, (2)
ψ ′ j (x i,j , y j ) ≥ µ i if x i,j = 0. (3)
Let C j = {i ∈ C : x i,j > 0} be the set of classes which route traffic to server j. Similarly, let S i = {j ∈ S : x i,j > 0} be the set of servers to which class i routes traffic. Note that i ∈ C j ⇐⇒ j ∈ S i . Since φ is strictly increasing, we can now rewrite equations ( 2) and (3) as

ψ ′ j (0, y j ) < µ i ⇐⇒ i ∈ C j ⇐⇒ j ∈ S i . (4)
Let x be the NEP for the system with K dispatchers. The global performance of the system can be assessed using the global cost

D K (λ, r, c) = i∈C T i (x) = j∈S c j ρ j φ(ρ j )
where the utilization rates ρ j are those at the NEP. Note that when there is a single dispatcher, we have a single class whose traffic intensity is λ 1 = λ. The global cost can therefore be written as D 1 ( λ, r, c) in this case.

For our model, the PoA is defined as r,c) .

P oA(K) = sup λ,r,c D K (λ, r, c) D 1 ( λ,

Main Results

Our main result states that that the global cost D K (λ, r, c) achieves its maximum when λ is the symmetric vector λ = = λ K , . . . , λ K .

Theorem 1 sup

λ,r,c

D K (λ, r, c) = sup r,c D K (λ = , r, c).
This result implies that, for the calculation of the PoA, we can restrict ourselves to the symmetric game. This, coupled with the fact that in our setting the symmetric game is also a potential game, makes it more tractable for the analytic computation of the NEP and the global cost, thereby greatly simplifying the derivation of the lower and upper bounds on the PoA.

Properties of the Nash Equilibrium

In this section, we investigate properties of the traffic flow at the NEP. We first establish some properties of the cost function φ that will be useful in the sequel.

Properties of the cost function φ

We prove below some lemmata stating properties of the cost function φ. These properties are used in the sequel for the characterisation of the NEP.

= w + ǫ, it yields φ ′ (w) ≤ [φ(w + ǫ) -φ(w)] /ǫ < +∞. Lemma 2 ∀a, b ∈ D -{0}, b φ ′ (b) φ(b) ≥ a φ ′ (a) φ(a) ⇐⇒ b ≥ a Proof. It is sufficient to show that the function g : w → g(w) = w φ ′ (w) φ(w) is increasing on D -{0}. Let f (w) = φ ′ (w)
φ(w) . Then g(w) = w f (w). Note that since φ is twice differentiable on D, the derivatives f ′ (w) and g ′ (w) exist for all w ∈ D, and g ′ (w) = f (w) + w f ′ (w). Note also that f (w) > 0 since φ is strictly increasing on D.

Let us consider w ∈ D. If f is increasing at point w, then g ′ (w) > 0 and g is strictly increasing at point w. Assume now that f is strictly decreasing at point w, i.e. f ′ (w) < 0. From φ ′ (w) = f (w) φ(w), we obtain φ

′′ (w) = f ′ (w) φ(w) + f (w) φ ′ (w). Since φ is convex on D, we have φ ′′ (w) ≥ 0, i.e. f ′ (w) φ(w) + f (w) φ ′ (w) ≥ 0 (5)
The convexity of φ implies that φ(b) ≥ φ(a) + (ba) φ ′ (a) for all a, b ∈ D. With a = w and b = 0, it yields φ(w) ≤ φ(0) + w φ ′ (w). From 5, we thus get

f ′ (w) [φ(0) + w φ ′ (w)] + f (w) φ ′ (w) ≥ 0, (6)
and hence,

φ ′ (w) g ′ (w) = φ ′ (w) [f (w) + w f ′ (w)] ≥ -φ(0) f ′ (w) ≥ 0, (7)
from which we deduce that g ′ (w) ≥ 0, i.e. that g is increasing at point w.

Properties related to traffic intensities

We prove below that there is a monotonicity among classes in their use of servers: a class with a higher demand uses more of each and every server. We first prove a series of technical lemmata before stating our main results in Proposition 1 and Corollary 1.

Lemma 3 S i ∩ S k = ∅.
Proof. Assume the contrary, i.e., if m ∈ S i then m / ∈ S k , and if n ∈ S k then n / ∈ S i . For one such pair m and n, from (4), we can conclude that

µ i > ψ ′ m (0, y m ) ≥ µ k and µ k > ψ ′ n (0, y n ) ≥ µ i , which is a contradiction. Since S i ∩ S k = ∅, from (2)
, we have

µ i -µ k = ψ ′ j (x i,j , y j ) -ψ ′ j (x k,j , y j ), ∀j ∈ S i ∩ S k . ( 8
)
Lemma 4 µ i < µ k ⇐⇒ ∃j ∈ S k : x i,j < x k,j .

Proof. Straight part: From Lemma 3, S i ∩ S k = ∅. If µ i < µ k , then, from (8), ∃j ∈ S k : ψ ′ j (x i,j , y j ) < ψ ′ j (x k,j , y j ) which implies that ∃j ∈ S k : x i,j < x k,j . Converse part: ∃j ∈ S k : x i,j < x k,j . Either j ∈ S i or j / ∈ S i . If j ∈ S i then, from (8), ψ ′ j (x i,j , y j ) < ψ ′ j (x k,j , y j ) implies µ i < µ k . If j / ∈ S i , then, from (4),

µ i ≤ ψ ′ j (0, y j ) < ψ ′ j (x k,j , y j ) < µ k . Lemma 5 If µ i < µ k , then S i ⊂ S k .
Proof. If j ∈ S i , then, from (4), ψ ′ j (0, y j ) < µ i . If µ i < µ k then ψ ′ j (0, y j ) < µ k . Hence, from (4) we can conclude that j ∈ S k . Therefore, S i ⊂ S k .

Lemma 6 ∃m ∈ S k : x i,m < x k,m ⇐⇒ x i,j < x k,j , ∀j ∈ S k .
Proof. Straight part: If ∃m ∈ S k : x i,m < x k,m , then, from Lemmata 4 and 5, we have µ i < µ k and S i ⊂ S k . For j ∈ S i , from (8), we have ψ ′ j (x i,j , y j ) < ψ ′ j (x k,j , y j ), which implies x i,j < x k,j . For j ∈ S k \ S i , x i,j = 0 and 0 < x k,j . Hence, x i,j < x k,j , ∀j ∈ S k .

Converse part: It is true from the statement.

Proposition 1

The following statements are equivalent:

1. µ i < µ k . 2. ∃j ∈ S k : x i,j < x k,j . 3. x i,j < x k,j , ∀j ∈ S k . 4. λ i < λ k .
Proof. 1 ⇐⇒ 2 ⇐⇒ 3 follows from Lemmata 4 and 6. Now, we show 3 ⇐⇒ 4. Straight part: If x i,j < x k,j , ∀j ∈ S k , then, from the fact that 3 ⇐⇒ 1 and Lemma 5, we can conclude that

λ i = j∈Si x i,j = j∈S k x i,j < j∈S k x k,j = λ k . Converse part: Since λ k = j∈S k x k,j , if λ i < λ k , then ∃j ∈ S k : x i,j < x k,j . Since 2 ⇐⇒ 3, if λ i < λ k , then x i,j < x k,j , ∀j ∈ S k .
The above proposition shows that a class with a higher demand uses more of each and every server. The following corollary shows that if two classes have the same traffic intensity, then they send the same amount of flow on each server.

Corollary 1 From Proposition 1, it follows that 1. µ i = µ k ⇐⇒ ∃j ∈ S k : x i,j = x k,j ⇐⇒ x i,j = x k,j , ∀j ∈ S k ⇐⇒ λ i = λ k . 2. If λ i < λ k , then S i ⊂ S k . 3. If λ i = λ k , then S i = S k .
In particular, if all classes have the same demand, i.e. λ = λ = , then, for all server j ∈ S and for all i ∈ C, we have x i,j = y j /K.

Recall that we have assumed that λ i ≤ λ k for i ≤ k. Therefore, according to the above results, if we consider two classes i and k > i, then we have S i ⊆ S k , µ i ≤ µ k and x i,j ≤ x k,j for all servers j ∈ S k , with the equalities holding if and only if

λ i = λ k . Let N j = |C j |. Proposition 1 implies that if k ∈ C j , then i ∈ C j , ∀i > k.
As a consequence, the set C j has the following structure: C j = {K -N j + 1, . . . , K}.

Properties related to server cost functions

The above results tell how an order on λ i translates to an order on x i,j , µ i and S i , i.e., quantities of class i. We now give the analogous results for similar quantities of server j.

Lemma 7 C m ∩ C n = ∅.
Proof. Assume the contrary, i.e., if i ∈ C m , then i / ∈ C n , and if k ∈ C n , then k / ∈ C m . For one such pair i and k, from (4), we can conclude that ψ ′ m (0,

y m ) < µ i ≤ ψ ′ n (0, y n ) and ψ ′ n (0, y n ) < µ k ≤ ψ ′ m (0, y m ), which is a contradiction. Lemma 8 If ψ ′ n (0, y n ) ≤ ψ ′ m (0, y m ), then C m ⊆ C n . Proof. If i ∈ C m , then, from (4), µ i > ψ ′ m (0, y m ). If ψ ′ n (0, y n ) ≤ ψ ′ m (0, y m ), then µ i > ψ ′ n (0, y n ). Hence, from (4) we can conclude that i ∈ C n . Therefore, C m ⊆ C n . Since C m ∩ C n = ∅, from (2), we have µ i = ψ ′ m (x i,m , y m ) = ψ ′ n (x i,n , y n ), ∀i ∈ C m ∩ C n . (9)
Lemma 9

The following hold:

ψ ′ n (0, y n ) < ψ ′ m (0, y m ) ⇐⇒ ∃i ∈ C n : u m x i,m r m φ ′ (ρ m ) < u n x i,n r n φ ′ (ρ n ). Proof. Straight part: From Lemma 7, C m ∩ C n = ∅. If ψ ′ n (0, y n ) < ψ ′ m (0, y m ), then, from (9), ∃i ∈ C n : ψ ′ m (x i,m , y m ) -ψ ′ m (0, y m ) < ψ ′ n (x i,n , y n ) -ψ ′ n (0, y n ), i.e. um xi,m rm φ ′ (ρ m ) < un xi,n rn φ ′ (ρ n ). Converse part: Assume ∃i ∈ C n : um xi,m rm φ ′ (ρ m ) < un xi,n rn φ ′ (ρ n ). Then ψ ′ m (x i,m , y m ) -ψ ′ m (0, y m ) < ψ ′ n (x i,n , y n ) -ψ ′ n (0, y n ). Either i ∈ C m or i / ∈ C m . If i ∈ C m , then, from (9), ψ ′ n (0, y n ) < ψ ′ m (0, y m ). If i / ∈ C m , then, from (3), ψ ′ m (0, y m ) ≥ µ i = ψ ′ n (x i,n , y n ) > ψ ′ n (0, y n ). Hence, ψ ′ n (0, y n ) < ψ ′ m (0, y m ).

Lemma 10

The following hold:

ψ ′ n (0, y n ) < ψ ′ m (0, y m ) ⇐⇒ u m x i,m r m φ ′ (ρ m ) < u n x i,n r n φ ′ (ρ n ), ∀i ∈ C n . Proof. Straight part: If ψ ′ n (0, y n ) < ψ ′ m (0, y m ), then from Lemma 8, C m ⊂ C n . For i ∈ C m , from (9), ψ ′ m (x i,m , y m ) -ψ ′ m (0, y m ) < ψ ′ n (x i,n , y n ) -ψ ′ n (0, y n ), i.e., um xi,m rm φ ′ (ρ m ) < un xi,n rn φ ′ (ρ n ). For i ∈ C n \ C m , x i,m = 0 and 0 < x i,n . Hence, since φ is strictly increasing, um xi,m rm φ ′ (ρ m ) = 0 < un xi,n rn φ ′ (ρ n ).
Converse part: the proof is a direct consequence of Lemma 9.

The following proposition proves a monotonic property regarding the order of preference of servers as seen by each class.

Proposition 2

The following statements are equivalent:

1. ψ ′ n (0, y n ) < ψ ′ m (0, y m ). 2. ∃i ∈ C n : um xi,m rm φ ′ (ρ m ) < un xi,n rn φ ′ (ρ n ).

3.

um xi,m rm

φ ′ (ρ m ) < un xi,n rn φ ′ (ρ n ), ∀i ∈ C n .. 4. u n < u m .
Proof. 1 ⇐⇒ 2 ⇐⇒ 3 follows from Lemmata 9 and 10. Next, we show 3 ⇐⇒ 4.

Straight part:

If um xi,m rm φ ′ (ρ m ) < un xi,n rn φ ′ (ρ n ), ∀i ∈ C n ,
then from the fact that 3 ⇐⇒ 1 and Lemma 8, we can conclude that

u m ρ m φ ′ (ρ m ) = i∈Cm u m x i,m r m φ ′ (ρ m ) < i∈Cn u n x i,n r n φ ′ (ρ n ) = u n ρ n φ ′ (ρ n ) (10)
Observe that it implies ρ n > 0. Assume first that ρ m > 0. Note that ψ ′ n (0, y n ) < ψ ′ m (0, y m ) can also be written as

u n φ(ρ n ) < u m φ(ρ m ). Together with inequality 10, it implies that ρ n φ ′ (ρn) φ(ρn) > ρ m φ ′ (ρm) φ(ρm) , which according to Lemma 2 is equivalent to ρ n > ρ m . Clearly, ρ n > ρ m also holds if ρ m = 0. We thus get u n φ(ρ m ) < u n φ(ρ n ) < u m φ(ρ m ) in both cases, which implies that u n < u m , as claimed.
Converse part: To prove 4 =⇒ 1, we prove that ¬1 =⇒ ¬4. Assume that

u n φ(ρ n ) ≥ u m φ(ρ m ). Since ¬1 ⇐⇒ ¬2, we get um xi,m rm φ ′ (ρ m ) ≥ un xi,n rn φ ′ (ρ n ), ∀i ∈ C n . According to Lemma 8, u n φ(ρ n ) ≥ u m φ(ρ m ) implies C n ⊆ C m ,

and thus

u m ρ m φ ′ (ρ m ) ≥ i∈Cm u m x i,m r m φ ′ (ρ m ) ≥ i∈Cn u n x i,n r n φ ′ (ρ n ) = u n ρ n φ ′ (ρ n ).
Let us first assume that ρ n > 0 and ρ m > 0. Together with

u n φ(ρ n ) ≥ u m φ(ρ m ), it implies that ρ n φ ′ (ρn) φ(ρn) ≤ ρ m φ ′ (ρm) φ(ρm) , which is equivalent to ρ n ≤ ρ m according to Lemma 2. Clearly, ρ n ≤ ρ m still holds if ρ n = 0. The case ρ m = 0 < ρ n is impossible because C n ⊆ C m . We thus obtain that ρ n ≤ ρ m in all cases. But from u n φ(ρ n ) ≥ u m φ(ρ m ) and φ(ρ m ) ≥ φ(ρ n ), we deduce that u n ≥ u m . We thus conclude that if u n < u m , then u n φ(ρ n ) < u m φ(ρ m ), i.e., ψ ′ n (0, y n ) < ψ ′ m (0, y m ).
Corollary 2 From Proposition 2 it follows that

1. u n < u m ⇐⇒ um xi,m rm φ ′ (ρ m ) < un xi,n rn φ ′ (ρ n ), ∀i ∈ C n ⇐⇒ u n φ(ρ n ) < u m φ(ρ m ) 2. If u n < u m then C m ⊂ C n . 3. If u n = u m then C m = C n .
The above corollary shows that we get a partition of classes among servers at the NEP: starting with a server m of maximal cost per unit capacity u m and moving towards servers n with lower cost per unit capacity u n < u m , we observe more and more classes joining the servers, i.e. C m ⊂ C n .

Recall that it is assumed that the servers are numbered in the following order: c 1 /r 1 ≤ c 2 /r 2 ≤ . . . ≤ c S /r S . According to the above properties, it implies that if we consider two servers n and m > n, then we have

C m ⊆ C n , u n φ(ρ n ) < u m φ(ρ m ) and um xi,m rm φ ′ (ρ m ) < un xi,n rn φ ′ (ρ n ) for each class i ∈ C n , with the equalities holding if and only if c n /r n = c m /r m . Let S i = |S i |. Proposition 2 implies that if m ∈ S i , then n ∈ S i , ∀n < m.
As a consequence, the set S i has the following structure:

S i = {1, . . . , S i }.
The following lemma proves that the above order on the servers implies exactly the same order on their utilization rates at the NEP.

Lemma 11 ∀j ∈ S, ρ j ≥ ρ j+1
Proof. The assertion is obviously true if ρ j+1 = 0. Let us therefore assume that ρ j+1 > 0. This implies that ρ j > 0 because

C j+1 ⊆ C j . Since C j+1 ⊆ C j and uj+1 xi,j+1 rj+1 φ ′ (ρ j+1 ) < uj xi,j rj φ ′ (ρ j ) for all i ∈ C j , we have u j+1 ρ j+1 φ ′ (ρ j+1 ) = i∈Cj+1 u j+1 x i,j+1 r j+1 φ ′ (ρ j+1 ) < i∈Cj u j x i,j r j φ ′ (ρ j ) = u j ρ j φ ′ (ρ j ) Together with u j φ(ρ j ) ≤ u j+1 φ(ρ j+1 ), it implies that ρ j+1 φ ′ (ρj+1) φ(ρj+1) ≤ ρ j φ ′ (ρj )
φ(ρj ) , from which we deduce that ρ j ≥ ρ j+1 using Lemma 2.

Before moving to the analysis of the set of servers used by each class at the equilibrium, we conclude this section with a last property related to the server costs per unit capacity. This technical result will play a key role when comparing the costs of two different equilibria.

Lemma 12 ψ ′ j (y j , y j ) ≥ ψ ′ j+1 (y j+1 , y j+1 ), ∀j, with strict inequality if C j \ C j+1 = ∅.
Proof. From (2), if x i,j > 0, then

µ i = ψ ′ j (x i,j , y j ) = u j φ(ρ j ) + x i,j r j φ ′ (ρ j ) ,
from which we conclude that

i∈Cj µ i = u j [N j φ(ρ j ) + ρ j φ ′ (ρ j )] = (N j -1) u j φ(ρ j ) + ψ ′ j (y j , y j ).
Similarly, we have

i∈Cj+1 µ i = (N j+1 -1) u j+1 φ(ρ j+1 ) + ψ ′ j+1 (y j+1 , y j+1 ). Now, i∈Cj+1 µ i = i∈Cj µ i - i∈Cj \Cj+1 µ i = (N j -1) u j φ(ρ j ) + ψ ′ j (y j , y j ) - i∈Cj \Cj+1 u j φ(ρ j ) + x i,j r j φ ′ (ρ j ) = (N j -1) u j φ(ρ j ) + ψ ′ j (y j , y j ) -(N j -N j+1 ) u j φ(ρ j ) -u j φ ′ (ρ j ) i∈Cj \Cj+1 x i,j r j = (N j+1 -1)u j φ(ρ j ) + ψ ′ j (y j , y j ) -u j φ ′ (ρ j ) i∈Cj \Cj+1
x i,j r j .

Thus,

ψ ′ j (y j , y j ) -ψ ′ j+1 (y j+1 , y j+1 ) = (u j+1 φ(ρ j+1 ) -u j φ(ρ j )) (N j+1 -1) + u j φ ′ (ρ j ) i∈Cj \Cj+1
x i,j r j .

From Proposition 2, we have u j+1 φ(ρ j+1 ) ≥ u j φ(ρ j ). Moreover φ ′ (ρ j ) > 0 because φ is strictly increasing. Since the second term on the RHS is strictly positive if

C j \ C j+1 = ∅, we can conclude that ψ ′ j (y j , y j ) -ψ ′ j+1 (y j+1 , y j+1 ) ≥ 0, with strict inequality if C j \ C j+1 = ∅.

Characterization of the set of servers used

The following proposition shows that the set of servers used by each class has the so-called water-filling structure. Proposition 3 For each class i ∈ C, the threshold S i is such that

G Si < λ i ≤ G Si+1 , (11)
where

G s = s j=1 r j u j φ ′ (ρ j ) [u s φ(ρ s ) -u j φ(ρ j )] s = 1, . . . , S. (12)
Proof. Let A be a subset of S i . Equation ( 2) can be rewritten as

rj uj φ ′ (ρj ) µ i = rj φ ′ (ρj )
φ(ρ j ) + x i,j for all j ∈ S i . Summing over j ∈ A, we get

µ i = j∈A rj φ ′ (ρj ) φ(ρ j ) + x i,j j∈A rj uj φ ′ (ρj ) A ⊆ S i , (13)
which in the case A = S i can be written as

µ i = λ i + j∈Si rj φ ′ (ρj ) φ(ρ j ) j∈Si rj uj φ ′ (ρj ) . ( 14
)
Since S i+1 ∈ S i , we have from (3)

µ i = λ i + j∈Si rj φ ′ (ρj ) φ(ρ j ) j∈Si rj uj φ ′ (ρj ) ≤ u Si+1 φ(ρ Si+1 ),
which yields λ i ≤ G Si+1 after some algebra. For the lower bound, observe that, since S i ∈ S i , (2) holds for j = S i . Therefore, using (13) with A = {1, . . . , S i -1}, we can write

µ i = Si-1 j=1 rj φ ′ (ρj ) φ(ρ j ) + x i,j Si-1 j=1 rj uj φ ′ (ρj ) = u Si φ(ρ Si ) + x i,Si r Si φ ′ (ρ Si ) .
With λ i > Si-1 j=1 x i,j , it yields

λ i > u Si φ(ρ Si ) + x i,Si r Si φ ′ (ρ Si ) Si-1 j=1 r j u j φ ′ (ρ j ) - Si-1 j=1 r j φ ′ (ρ j ) φ(ρ j ) + x i,j , from which we get λ i > G Si since xi,S i rS i φ ′ (ρ Si ) > 0.
Remark 1 In the special case λ i = G i,Si+1 , inequality (3) holds tight for j = S i + 1. Therefore, in this case, we can define the set of servers used by class i as S i = {1, . . . , S i , S i + 1}, where server S i + 1 is "marginally" used, with x i,Si+1 = 0.

From Corollary 1, we can conclude that the thresholds S 1 , . . . , S K satisfy the order S 1 ≤ S 2 ≤ . . . ≤ S K .

Analysis of the Social Cost

In this section, it will be assumed that the cost functions vector ψ is fixed. Our goal is to prove that the social cost D K (λ, ψ) achieves its maximum in the symmetric case, i.e. when λ = λ = .

For each rate vector λ ∈ Λ, we already know that there exists a unique NEP x ∈ X . Let us define the function N : Λ → X such that for each vector λ ∈ Λ, N (λ) ∈ X is this unique NEP. In the sequel, the function N will be called the Nash mapping. We have the following result.

Theorem 2

The Nash mapping N is a continuous function from Λ into X .

Proof. Note that for each vector λ ∈ Λ, N (λ) ∈ X ⊂ i∈C j∈S [0, r j ] and the latter set is a compact set. As a consequence, in order to apply the closed graph theorem (see Appendix A), we only need to show that the graph G N of N is closed. Let us therefore consider a convergent sequence (λ n , x n ) n∈IN of points in G N , where x n = N (λ n ). Let (λ, x) denote the limit of this sequence. Note that λ ∈ Λ since Λ is closed as a topological space. We need to show that x = N (λ).

We first show that x ∈ X . For i ∈ C and j ∈ S fixed, the sequence (x n i,j ) n∈IN takes values in the closed set [0, r j ] and converges to x i,j , from which we deduce that 0 ≤ x i,j ≤ r j . Moreover, for each n ∈ IN and each i ∈ C, we have

j∈S x n i,j = λ n i . Since x n → x, we have for each class i ∈ C, λ i = lim n→∞ λ n i = lim n→∞ j∈S x n i,j = j∈S x i,j .
We therefore conclude that the limit point x is such that x ∈ X . Let us now show that x is the NEP associated to the rate vector λ. For each n ∈ IN, since x n is a NEP, there exist multipliers µ n i , i ∈ C, such that

µ n i = u j φ(ρ n j ) + x n i,j r j φ ′ (ρ n j ) if x n i,j > 0 (15) µ n i ≤ u j φ(ρ n j ) if x n i,j = 0. (16)
Now, let us show that there exist

µ i < +∞ such that µ n i → µ i , i ∈ C. Let y n j = i∈C x n i,j
, ρ n j = y n j /r j and y j and ρ j be the respective limits when n → ∞. The proof is an immediate consequence of (15) and ( 16) for type-I congestion functions since φ(ρ n j ) → φ(ρ j ) < +∞ and φ ′ (ρ n j ) → φ ′ (ρ j ) < +∞ as n → ∞ for all j ∈ S (Lemma 1).

Let us therefore assume that φ is a type-II congestion function and prove that µ n i → µ i < +∞ as n → ∞. To this end, we first prove that ρ n 1 → ρ 1 < 1. Assume on the contrary that ρ 1 = 1. In this case, the relation φ(ρ n j ) ≥ u1 uj φ(ρ n 1 ) implies that φ(ρ n j ) → ∞ for all j ∈ S, and hence that ρ n j → 1, ∀j ∈ S. We thus get y n j → r j , ∀j ∈ S, which implies that λ = j∈S y n j → r = j∈S r j . This is clearly a contradiction with our assumption λ < r.

As a consequence, we have ρ < 1, which implies that φ(ρ n 1 ) → φ(ρ 1 ) < +∞ and φ ′ (ρ n 1 ) → φ ′ (ρ 1 ) < +∞ (Lemma 1) as n → ∞. Since all classes use server 1, we have

µ n i = u 1 φ(ρ n 1 ) + x n i,1 r 1 φ ′ (ρ n 1 ) i ∈ C.
Taking the limit as n → ∞, we obtain that µ n i → µ i < +∞, where

µ i = u 1 φ(ρ 1 ) + x i,1 r 1 φ ′ (ρ 1 ) i ∈ C.
Observe that it implies that ρ j < 1, ∀j ∈ S. Indeed, if ρ j > 0, then there exists k ∈ IN such that ρ n j > 0, ∀n ≥ k. Therefore, there exists i ∈ C such that x n i,j > 0 for all n ≥ k. With (4), it yields φ(ρ n j ) < rj cj µ n i for all n ≥ k. As a consequence, we have lim n→∞ φ(ρ n j ) ≤ rj cj µ i , which proves that ρ n j → ρ j < 1 as n → ∞.

We have proved above that µ n i → µ i < +∞ as n → ∞ for both type-I and type-II congestion functions. Now, let us consider the complementary slackness conditions for each NEP x n , that is,

x n i,j u j φ(ρ n j ) + x n i,j r j φ ′ (ρ n j ) -µ n i = 0, j ∈ S, i ∈ C.
Taking the limit as n → ∞, we obtain

x i,j u j φ(ρ j ) + x i,j r j φ ′ (ρ j ) -µ i = 0, j ∈ S, i ∈ C.
Since the above are the necessary and sufficient optimality conditions for a point to be a NEP, we conclude that x = N (λ) and thus that the graph G N is closed. Applying the closed graph theorem yields the proof.

In order to prove that the global cost achieves its maximum in the symmetric case, we need to compare the equilibria N (λ) and N ( λ) that are induced by two different rate vectors λ and λ in Λ. If the resulting equilibria are such that the set of servers over which each class sends its flow do not coincide at both equilibria, then the comparisons become extremely complex, if possible at all.

To avoid this difficulty, we proceed as follows. In section 4.1, we first prove some preliminary results concerning the comparison of the equilibria induced by two different rate vectors λ and λ, assuming that these equilibria are such that each class sends its flow to the same servers under both equilibria. In Section 4.2, we compare the equilibria induced by two different rate vectors λ and λ, assuming that (i) these equilibria are such that each class sends its flow to the same servers under both equilibria, and (ii) λ is obtained from λ using a certain transformation. In Section 4.3 we exploit the continuity of the Nash mapping to show that the global cost increases under this transformation even when the set of servers is different at the two equilibria. Finally, in Section 4.4, we show that the symmetric rate vector λ = can be obtained from any rate vector λ with a finite number of such transformations.

Preliminary Results

In this section, we prove some lemmata that will be used in order to compare the Nash equilibria induced by two vectors λ ∈ Λ and λ ∈ Λ. In the sequel, if z is a certain quantity related to the Nash equilibrium induced by the vector λ then we shall denote the corresponding quantity for vector λ by ẑ.

Lemma 13 For i ∈ C j , 1. if ŷj < y j and xi,j ≤ x i,j , then μi < µ i .

2. if ŷj ≤ y j and xi,j ≤ x i,j , then μi ≤ µ i .

3. if ŷj ≤ y j and xi,j < x i,j , then μi < µ i . [START_REF] Chen | The effect of local scheduling in load balancing designs[END_REF]. if ŷj = y j and μi < µ i , then xi,j < x i,j .

Proof. Proof of part 1 : for i ∈ C j , we have µ i = ψ ′ j (x i,j , y j ) and μi ≤ ψ ′ j (x i,j , ŷj ). Since ψ ′ j (x, y) is strictly increasing in each of its two arguments, ŷj < y j and xi,j ≤ x i,j implies that μi ≤ ψ ′ j (x i,j , ŷj ) < ψ ′ j (x i,j , y j ) = µ i . The proofs of parts 2, 3, and 4 follow similarly.

Lemma 14 For m and n in S, and i ∈ C m ∩ C n , if ŷm > y m , xi,m ≥ x i,m , and ŷn ≤ y n , then xi,n > x i,n .

Proof. Assume the contrary, that is, ∃ n, m ∈ S and i ∈ C m ∩ C n such that ŷm > y m , xi,m ≥ x i,m , ŷn ≤ y n and xi,n ≤ x i,n . From Lemma 13.1, ŷm > y m and xi,m ≥ x i,m implies μi > µ i . However, from Lemma 13.2, ŷn ≤ y n and xi,n ≤ x i,n implies μi ≤ µ i , which is a contradiction.

In the rest of the section, we shall make the following assumption on the vectors λ and λ.

Assumption 1 The vectors λ and λ are such that C j = Ĉj , ∀j ∈ S.

From the above assumption, it follows that S i = Ŝi , ∀i ∈ C.

Lemma 15 For any j ∈ S:

1. ŷj ≥ y j ⇐⇒ i∈Cj μi ≥ i∈Cj µ i . 2. ŷj > y j ⇐⇒ i∈Cj μi > i∈Cj µ i .
Proof. Proof of part 1: from (2), if i ∈ C j , then

µ i = ψ ′ j (x i,j , y j ) = u j φ(ρ j ) + x i,j r j φ ′ (ρ j )
Thus,

i∈Cj µ i = (N j -1) u j φ(ρ j ) + ψ ′ j (y j , y j )
Since N j = Nj (from Assumption 1) and ψ ′ j (x, y) is strictly increasing in each of its two arguments, we can conclude that i∈Cj µ i is an increasing function of y j .

The proof of part 2 follows similarly.

Lemma 16 If C m = C n then : 1. ŷm ≥ y m ⇐⇒ ŷn ≥ y n . 2. ŷm > y m ⇐⇒ ŷn > y n .
Proof. Proof of part 1: from Lemma 15, ŷm ≥ y m is equivalent to i∈Cm μi ≥ i∈Cm µ i , which, since C m = C n , is equivalent to i∈Cn μi ≥ i∈Cn µ i . Again, from Lemma 15, we can conclude that ŷn ≥ y n .

The proof of part 2 follows similarly.

Corollary 3 For m, n ∈ S 1 , ŷm > y m ⇐⇒ ŷn > y n . Proof. Recall from corollary 1 that S 1 ⊆ S k for all k ∈ C. Since, for m, n ∈ S 1 , C m = C n = {1, 2
, ..., K}, the above statement follows from Lemma 16.2.

Basic Transformation of a Rate Vector

For each rate vector λ ∈ Λ, recall that by convention λ 1 = min i∈C λ i and λ K = max i∈C λ i . Define the sets C min and C max as follows: Definition 1 For each rate vector λ ∈ Λ, define the function h λ : [0, n max λ K ] → Λ as follows:

C min = {i ∈ C : λ i = λ 1 } , C max = {i ∈ C : λ i = λ K } ,
h λ (ǫ) = λ + ǫ 1 n min i∈Cmin e i - 1 n max i∈Cmax e i , (17)
where e i denotes the vector in IR K with the i-th component equals to 1 and all other components are equal to 0. A rate vector λ ∈ Λ is said to be obtained from λ under a basic transformation if and only if there exists ǫ ∈ [0, n max λ K ] such that λ = h λ (ǫ). In this case, ǫ is called the step of the transformation.

Note that the above transformation increases the traffic of classes i ∈ C min (the classes with the smallest amount of traffic) and decrease correspondingly the traffic of classes i ∈ C max (the classes with the largest amount of traffic), i.e., it preserves the total amount of traffic:

i∈C λ i = i∈C λi = λ. There are several other properties of the basic transformation which are worthwhile noticing. They are stated in the following lemma.

Lemma 17 Let λ be obtained from λ under a basic transformation, i.e., λ = h λ (ǫ). Then,

1. λi ≥ λ i , ∀i ∈ C min , λi ≤ λ i , ∀i ∈ C max , and λi = λ i , ∀i ∈ C min ∪ C max ,
where the inequalities are strict if and only if C min = C max and ǫ > 0.

2. λi = λ1 ∀i ∈ C min and λi = λK ∀i ∈ C max , 3. λi ≤ λ K ∀i ∈ C min and λi ≥ λ 1 ∀i ∈ C max for ǫ ≤ min(n min , n max )(λ Kλ 1 ).

4.

i∈Cmin λiλ i = -i∈Cmax λiλ i , 5.

j∈S y j = j∈S ŷj , Proof. In part 1, if either C min = C max or ǫ = 0, then λ = λ. Hence, the equalities are satisfied. So, we consider the case when C min = C max and ǫ > 0, and show that the inequalities are strict. From (17), it is immediate that λi = λ i for i ∈ C min ∪C max . Moreover λi = λ i + ǫ nmin for all i ∈ C min and λi = λ i -ǫ nmax for all i ∈ C max . Since ǫ > 0, we thus obtain λi > λ i for i ∈ C min and λi < λ i for i ∈ C max , and 1 is proved.

We note that if C min = C max , then λ = λ. Hence, the parts 2 to 5. So, for the rest of the proof, we assume that C min = C max . ¿From λ i = λ 1 for i ∈ C min and λ i = λ K for i ∈ C max , we obtain that λi = λ 1 + ǫ nmin = λ1 for i ∈ C min and λi = λ K + ǫ nmax = λK for i ∈ C max , which proves 2. To prove 3, let us consider i ∈ C min . We observe that ǫ ≤ min(n min , n max )(λ Kλ 1 ) implies that λi = λ i + ǫ nmin ≤ λ i + min(nmin,nmax)

nmin (λ K -λ 1 ) ≤ λ i +(λ K -λ 1 ) = λ K . The proof of λi ≥ λ 1 for i ∈ C max is symmetric.
To prove 4, we observe that,

i∈Cmin λi -λ i = i∈Cmin ǫ n min = ǫ = i∈Cmax ǫ n max = - i∈Cmax λi -λ i
Finally, the proof of property 5 is immediate since it is equivalent to i∈C λ i = i∈C λi .

In the following, we will compare two rate vectors λ and λ. If z is a certain quantity related to the Nash equilibrium induced by the vector λ then we shall denote the corresponding quantity for vector λ by ẑ. The comparison is done under the following assumption.

Assumption 2

The rate vectors λ ∈ Λ and λ ∈ Λ are such that:

1. λ is obtained from λ under a basic transformation, 2. C j = Ĉj , ∀j ∈ S.

In other words, we assume that the transformation λ into λ leaves unaffected the set of servers used by each class.

The key point here is that in order to determine the impact of a basic transformation of the rate vector λ on the global cost, we need to compare the server loads under the equilibria x = N (λ) and x = N ( λ). To this end, let us define the sets S + and S -as follows:

S + = {j ∈ S : ŷj > y j } and S -= S \ S + , i.e., S + is the set of servers whose load increases under the transformation while S -is the set of servers whose load is non-increasing under the transformation.

We first prove two lemmata concerning the sets S + and S -. The first one shows that S + is empty if and only if the load of each and every server is constant under the transformation.

Lemma 18 y j = ŷj , ∀j ∈ S ⇐⇒ S + = ∅.

Proof. If S + = ∅ then S -= S. That is, ŷj ≤ y j , ∀j ∈ S. We also have j∈S ŷj = j∈S y j . This is possible only if ŷj = y j , ∀j ∈ S. The converse is true by definition of S + .

The second lemma shows that S -cannot be empty, i.e. that there is at least one server whose load is non-increasing under the transformation.

Lemma 19 S -= ∅.

Proof. Assume S -= ∅, then y j < ŷj , ∀j ∈ S. Therefore, j∈S y j < j∈S ŷj . This is in contradiction with Assumption 2 which says j∈S y j = j∈S ŷj .

We now prove three fundamental propositions regarding the impact of the transformation on server loads. We first show in proposition 4 that if there exists at least one server whose load increases under the transformation, then the load of each and every server used by class 1 increases. We then prove in proposition 5 that the load of all servers is non-increasing under the transformation if and only if all traffic classes use the same set of servers. Finally, proposition 6 proves that the transformation induces a monotonic partition of servers: there exists a threshold J < S such that for all servers j > J the load is non-increasing under the transformation.

Proposition 4 If S + = ∅ then S 1 ⊂ S + .
Proof. Assume by contradiction that we can find a server s ∈ S 1 such that s ∈ S -. Then, according to Corollary 3, S 1 ⊂ S -. Since S + = ∅ and ŷj > y j for all j ∈ S + , we have j∈S + ŷj > j∈S + y j , i.e.,

i∈C   j∈S + xi,j   > i∈C   j∈S + x i,j   ,
from which we conclude that there exists i such that j∈S + xi,j > j∈S + x i,j . Since S k = S 1 ⊂ S -for all k ∈ C min , we necessarily have i ∈ C min and thus λi ≤ λ i . Therefore, λi =

j∈S - xi,j + j∈S + xi,j ≤ j∈S - x i,j + j∈S + x i,j = λ i . Thus, j∈S - xi,j ≤ j∈S - x i,j +   j∈S + x i,j - j∈S + xi,j   < j∈S - x i,j .
We therefore conclude that class i is such that j∈S + xi,j > j∈S + x i,j and j∈S -xi,j < j∈S -x i,j . Therefore, we can find a server m ∈ S + and a server n ∈ S -such that xi,m > x i,m and xi,n < x i,n . But according to Lemma 14, this is impossible. We therefore conclude that S 1 ⊂ S + .

Proposition 5 S + = ∅ ⇐⇒ S 1 = S K .
Proof. We first prove that if S + = ∅ then S 1 = S K . From Lemma 18, this is equivalent to proving that if y j = ŷj , ∀j ∈ S then S 1 = S K . Assume the contrary, that is S 1 S K . Then, ∃m : m ∈ S K , m / ∈ S 1 .

Since y m = ŷm , from Lemma 15, we get i∈Cm µ i = i∈Cm μi , which we can rewrite as

i∈Cmax µ i + i∈Cm\Cmax µ i = i∈Cmax μi + i∈Cm\Cmax μi . ( 18
)
We shall show that the above equality is not possible, which then proves the claim.

For i ∈ C max , since λ i > λi , j∈Si x i,j > j∈Si xi,j . Thus, there exists an n ∈ S i such that x i,n > xi,n . Since y n = ŷn , from Lemma 13.3, we can conclude that µ i > μi , and that i∈Cmax µ i > i∈Cmin μi , which, upon substitution in (18), leads to

i∈Cm\Cmax µ i < i∈Cm\Cmax μi .
If C m \C max = ∅, then the above inequality cannot be possible which then proves the claim. So, assume C m \ C max = ∅. Then the above inequality implies that ∃i / ∈ C min ∪ C max : µ i < μi . Since y j = ŷj , ∀j ∈ S i , application of Lemma 13.4 leads to x i,j < xi,j , ∀j ∈ S i , and consequently to λ i = j∈Si x i,j < j∈Si xi,j = λi . However, for i / ∈ C min ∪ C max , from Lemma 17.1, λ i = λi . Hence, there is a contradiction, and we can conclude that S 1 = S K .

As a direct consequence of the above proposition, we get the following corollary that tells us that if at equilibria x and x all classes use the same set of servers, then the server loads are constant under the transformation.

Corollary 4 y j = ŷj , ∀j ∈ S ⇐⇒ S 1 = S K .

We now turn our attention to the set S -and prove the following result.

Proposition 6 For all j ∈ S, if j ∈ S -then j + 1 ∈ S -.

Proof. If S + = ∅ then the proposition is true. So, assume S + = ∅. Then, from Proposition 4, S 1 ⊂ S + . In order to prove the proposition, assume by contradiction that there exists a server j ∈ {S 1 + 1, . . . , S K -1} such that j ∈ S -and j + 1 ∈ S + . Again, if S 1 + 1 = S K then the proposition is true. So, assume that S 1 + 1 < S K .

Since j ∈ S -and j + 1 ∈ S + , from Lemma 16,

i∈Cj μi ≤ i∈Cj µ i , (19)
and

i∈Cj+1 μi > i∈Cj+1 µ i , (20)
Moreover, from the contrapositive of Lemma 16, we can conclude that C j \C j+1 = ∅. Note that since j < S K , classes i ∈ C max do not belong to C j \C j+1 . Similarly, since j > S 1 , classes i ∈ C min do not belong to C j \ C j+1 .

Since C j+1 ⊂ C j , we have, for all i ∈ C j+1 ,

µ i = ψ ′ j (x i,j , y j ) = u j φ(ρ j ) + x i,j r j φ ′ (ρ j ) .
Therefore, i∈Cj+1 μi > i∈Cj+1 µ i is equivalent to

(N j+1 -1) φ(ρ j )+ψ ′ j   i∈Cj+1 xi,j , ŷj   > (N j+1 -1) φ(ρ j )+ψ ′ j   i∈Cj+1
x i,j , y j   and since ŷj ≤ y j , this implies that i∈Cj+1 xi,j > i∈Cj+1 x i,j . Since ŷj ≤ y j , necessarily i∈Cj \Cj+1 xi,j < i∈Cj \Cj+1 x i,j . However, since all classes k ∈ C min ∪ C max do not belong to C j \ C j+1 , we know that λi = λ i for all i ∈ C j \ C j+1 , and thus (21) Subtracting ( 20) from ( 19), we obtain

i∈Cj \Cj+1 μi < i∈Cj \Cj+1 µ i .
Hence, for each server l < j,

(N j -N j+1 ) φ(ρ l )+ψ ′ l   i∈Cj \Cj+1 xi,l , ŷl   < (N j -N j+1 ) φ(ρ l )+ψ ′ l   i∈Cj \Cj+1 x i,l , y l   .
But, for l < j and l ∈ S + , it implies that i∈Cj \Cj+1

xi,l < i∈Cj \Cj+1

x i,l , and thus x i,l .

l<j,l∈S + i∈Cj \Cj+1 xi,l < l<j,l∈S + i∈Cj \Cj+1 x i,l . (22
According to (20), for each server l < j,

(N j+1 -1) φ(ρ l )+ψ ′ l   i∈Cj+1 xi,l , ŷl   > (N j+1 -1) φ(ρ l )+ψ ′ l   i∈Cj+1 x i,l , y l   .
But, for l < j, l ∈ S -, it implies that

i∈Cj+1 xi,l > i∈Cj+1 x i,l ,
and thus

l<j,l∈S -i∈Cj+1 xi,l > l<j,l∈S -i∈Cj+1 x i,l (24)
Now, summing (24) and ( 23) gives

l<j,l∈S -i∈Cj xi,l > l<j,l∈S -i∈Cj x i,l . (25)
However, for each server l ∈ S -, we have ŷl ≤ y l and thus l<j,l∈S -ŷl ≤ l<j,l∈S -y l . Since, for l < j, y l can also be written as

y l = i∈Cj x i,l + i ∈Cj x i,l , it yields l<j,l∈S -i / ∈Cj xi,l ≤ l<j,l∈S -i / ∈Cj x i,l +   l<j,l∈S -i∈Cj x i,l - l<j,l∈S -i∈Cj xi,l   ,
and using (25),

l<j,l∈S -i / ∈Cj xi,l < l<j,l∈S -i / ∈Cj x i,l . (26)
Therefore, there exists a class i / ∈ C j such that

l<j,l∈S - xi,l < l<j,l∈S - x i,l . (27)
It implies that, for this class i, we can find a server ninS i and n ∈ S -such that xi,n < x i,n . Since C max C j , we know that i ∈ C max . Moreover, since S k = S 1 ⊂ S + for all k ∈ C min , i ∈ C min . We therefore have λi = λ i . Thus,

l∈S - xi,l + l∈S + xi,l = l∈S - x i,l + l∈S + x i,l , which implies l∈S + xi,l = l∈S + x i,l + l∈S - x i,l - l∈S - xi,l ,
and with (27), it yields

l∈S + xi,l > l∈S + x i,l .
This implies that there exists a server m < j, m ∈ S + such that xi,m > x i,m . But, according to Lemma 14, there cannot be two servers m, n ∈ S such that ŷm > y m , ŷn ≤ y n , xi,m > x i,m and xi,n < x i,n . This is a contradiction. Therefore, if j ∈ S -, then j + 1 ∈ S -for all servers j ∈ S.

Proposition 6 proves that the transformation induces a monotonic partition of servers: there exists a threshold J < S such that for all servers j > J the load is non-increasing under the transformation.

Using the above results regarding the impact of the transformation on the server loads, the following two theorems compare the costs D(λ) and D( λ). The first theorem uses the following lemma.

Lemma 20 If b i , i = 1, 2, ..., is such that 1. b 1 > 0, 2. b i ≤ 0 ⇒ b i+1 ≤ 0, and

3.

i b i = 0, and a i , i = 1, 2, ..., is such that 1. a i ≥ a i+1 , and

2. a I -a I+1 > 0,
where

I = max{i : b i > 0}, then i a i b i > 0.
Proof. We have

i a i b i = i≤I a i b i + i>I a i b i ≥ a I i≤I b i + i>I a i b i ≥ a I i≤I b i -a I+1 i>I |b i | ≥ (a I -a I+1 ) i≤I b i > 0.
We are now in position to state our main results.

Theorem 3 D(λ) < D( λ) ⇐⇒ S 1 S K .
Proof. We first show that if S 1 S K then D(λ) < D( λ). Let ∆y j = ŷj -y j for all j ∈ S. Since the global cost D is a convex function of the offered traffics y j , j ∈ S, we have D( λ) ≥ D(λ) + ∇D(λ).∆y.

We thus have

D( λ) -D(λ) ≥ j ∂D ∂y j ∆y j = j ψ ′ j (y j , y j ) ∆y j (28)
We now show that the RHS in the above inequality is strictly positive. Since S 1 S K , from Proposition 4 and Lemma 19, we can infer that S + = ∅ and S -= ∅. From Proposition 4, we can also infer that S 1 ⊂ S + . Hence, ∆y 1 > 0. From Proposition 6, if j ∈ S -then j + 1 ∈ S -. Therefore, the sequence ∆y j , j ∈ S is such that 1. ∆y 1 > 0, 2. ∆y j ≤ 0 ⇒ ∆y j+1 ≤ 0, and

3.

j∈S ∆y j = 0.

Let J = max{j : j ∈ S + }. Then, J + 1 = min{j : j ∈ S -}. Note that C J = C J+1 , otherwise from Lemma 16, either both J and J + 1 belong to S + or both belong to S -. From Lemma 12, we can conclude that 1. ψ ′ j (y j , y j ) ≥ ψ ′ j+1 (y j+1 , y j+1 ), ∀j, and 2. ψ ′ j (y J , y J ) ≥ ψ ′ J+1 (y J+1 , y J+1 ).

Since the sequences ψ ′ j (y j , y j ) and ∆y j satisfy the conditions of Lemma 20, we have j ψ ′ j (y j , y j )∆y j > 0, and hence, from (28), we can conclude that D(λ) < D( λ).

To show the converse, if D(λ) < D( λ) then necessarily there exists an m such that y m = ŷm . From Proposition 4, we obtain S 1 = S K . Since S 1 ⊂ S K , we can conclude that S 1 S K .

Theorem 3 shows that if all the classes do not use the same set of servers at the equilibrium x, then the transformation will strictly increase the cost. The following theorem proves that the cost is constant under the transformation if all classes use the same set of servers.

2. λ i (ǫ) ≥ max λ K , max k∈C\Cmax λ k for all i ∈ C max , and the inequality is strict if ǫ < n max ∆ max , whereas it holds as an equality if ǫ = ∆ = n max ∆ max .

Proof. For i ∈ C min , we have λ i (ǫ) = λ 1 + ǫ nmin . Since ǫ ≤ n min ∆ min , it yields λ i (ǫ) ≤ λ 1 + ∆ min , i.e. λ i (ǫ) ≤ min λ K , min k∈C\Cmin λ k , as claimed. Note that the inequality is strict if ǫ < n min ∆ min and that it holds as an equality if ǫ = n min ∆ min . The proof of property 2 is symmetric.

The following two lemmata detail how the sets C min and C max evolve under the transformation.

Lemma 22 For each ǫ ≤ ∆,

1. C min ⊆ C min (ǫ) and C max ⊆ C max (ǫ), 2. If ǫ < n min ∆ min , then C min = C min (ǫ), 3. If ǫ < n max ∆ max , then C max = C max (ǫ), 4. If ǫ = n min ∆ min and C min = C, then C min C min (ǫ), 5. If ǫ = n max ∆ max and C max = C, then C max C max (ǫ).
Proof. We just prove the relations between C min and C min (ǫ), since the proofs of the relations between C max and C max (ǫ) are symmetric. We first prove assertion 1. Let i ∈ C min . From Lemma 21.1, we have λ i (ǫ) ≤ λ k for all k ∈ C \ C min . For k ∈ C min ∪ C max , Lemma 17.1 states that λ k (ǫ) = λ k , which implies that λ i (ǫ) ≤ λ k (ǫ) for all k ∈ C min ∪ C max . From Lemma 21.1, we also have λ i (ǫ) ≤ λ K ≤ λ k (ǫ) for all k ∈ C max , where the last inequality comes from Lemma 21.2. We therefore conclude that λ i (ǫ) ≤ λ k (ǫ) for all k ∈ C \ C min . However, from Lemma 17.2, we have λ k (ǫ) = λ i (ǫ) = λ 1 (ǫ) for all k ∈ C min . We conclude that if i ∈ C min , then λ i (ǫ) ≤ λ k (ǫ) for all k ∈ C, and thus i ∈ C min (ǫ). This shows that C min ⊂ C min (ǫ).

Let us now prove assertion 2. Assume ǫ < n min ∆ min . Since C min ⊂ C min (ǫ), we just need to prove that

C min (ǫ) ⊂ C min . It is sufficient to show that if k ∈ C min , then k ∈ C min (ǫ). Let k ∈ C \ C min . If k ∈ C max , then, according to Lemma 21.1, λ 1 (ǫ) < λ k = λ k (ǫ), whereas if k ∈ C max , λ 1 (ǫ) < λ K ≤ λ k (ǫ)
, also from Lemma 21. Since λ 1 (ǫ) = min i∈C λ i (ǫ), we conclude that k ∈ C min (ǫ), and thus that C min = C min (ǫ).

We now prove assertion 4. From Lemma 21.1, we have either

λ 1 (ǫ) = λ K or λ 1 (ǫ) = min k∈C\Cmin λ k . • If λ 1 (ǫ) = λ
K , then it clearly implies that λ i (ǫ) = λ K for all i ∈ C. However, since C min = C, it implies that class K belongs to C min (ǫ) but not to C min .

• If λ 1 (ǫ) = min k∈C\Cmin λ k , we can find j ∈ C \ C min such that λ j ≤ λ K and λ j = min k∈C\Cmin λ k . From λ j ≤ λ K we deduce that j ∈ C max . Therefore from Lemma 17.1 we obtain λ j (ǫ) = λ j = λ 1 (ǫ). We conclude that class j belongs to C min (ǫ) but not to C min .

Since in both cases we can find a class i ∈ C min (ǫ) such that i ∈ C min , we conclude that C min C min (ǫ).

Lemma 23

The following statements hold.

1. If C min ∪ C max = C, then C min ∪ C max C min (∆) ∪ C max (∆). 2. If C min ∪ C max = C, then λ(∆) = λ = .
Proof. We first prove assertion 1. Assume that C min ∪ C max = C. We have either ∆ = n min ∆ min , or ∆ = n max ∆ max . According to Lemmata 22.4 and 22.5, if ∆ = n min ∆ min , then C min C min (ǫ), while if ∆ = n max ∆ max we have C max C max (ǫ). We therefore conclude that C min ∪C max C min (∆)∪C max (∆).

The following proposition states that if we consider two rate vectors obtained from λ under basic transformations of steps lower than the maximum step, then one can be obtained from the other by a basic transformation.

Proposition 7 Let ǫ 1 , ǫ 2 ∈ [0, ∆], ǫ 1 < ǫ 2 .
Then λ(ǫ 2 ) can be obtained from λ(ǫ 1 ) under a basic transformation.

Proof. Since ǫ 1 < ǫ 2 implies ǫ 1 < ∆, from Lemmata 22.2 and 22.3 we have C min (ǫ 1 ) = C min and C max (ǫ 1 ) = C max . Accordingly, λ(ǫ 2 ) can be written as

λ(ǫ 2 ) = λ + ǫ 1     i∈Cmin e i n min - i∈Cmax e i n max     +(ǫ 2 -ǫ 1 )      i∈Cmin(ǫ1) e i n min (ǫ 1 ) - i∈Cmax(ǫ1) e i n max (ǫ 1 )      , i.e., λ(ǫ 2 ) = h λ(ǫ1) (ǫ 2 -ǫ 1 ).
We now show that even if some classes change the set of servers they use, the global cost is non-decreasing under the transformation λ(ǫ) = h λ (ǫ) provided that ǫ ≤ ∆. The proof is based on the following theorem which is proved in [START_REF] Korilis | Capacity allocation under noncooperative routing[END_REF] (Theorem 5, page 321), and closely parallels the discussion in section III.B of the above reference.

Theorem 5 (Theorem 5 in [START_REF] Korilis | Capacity allocation under noncooperative routing[END_REF]) Let f : X → IR, where X ⊂ IR is a closed interval. Consider a family A = {A 1 , . . . , A n } of closed subsets of X, such that (i) ∪ n i=1 A i = X, and (ii) for every A i ∈ A, we have : x, y ∈ A i and x < y ⇒ f (x) < f (y). Then f is non-decreasing in X.

The following theorem extends Theorems 3 and 4 to the case when the transformation changes the set of servers used by some classes.

Theorem 6 For ǫ ≤ ∆, D(λ(ǫ)) ≥ D(λ).
Proof. Consider a rate vector λ and the transformation λ(ǫ) = h λ (ǫ) of this rate vector for ǫ ∈ [0, ∆]. We want to prove that D(λ(ǫ)) ≥ D(λ). Since all quantities of interest, and in particular the global cost, can be treated as functions of ǫ, it suffices to show that D is a non-decreasing function of ǫ on [0, ∆].

Let A i,j = {ǫ ∈ [0, ∆] : G i,j (ǫ) ≤ λ i (ǫ) ≤ G i,j+1 (
ǫ)}, denote the set of ǫ ∈ [0, ∆] for which class i sends flow to servers {1, . . . , j} under equilibrium N (ǫ). From (12), one can see that G i,j is a continuous function of the ρ j , which in turn are continuous function of the equilibrium strategies of all classes. The continuity of the Nash mapping then implies that G i,j is a continuous function of ǫ ∈ [0, ∆]. Continuity of the functions G i,j (ǫ) and λ i (ǫ) implies that A i,j is a closed set.

For each S ∈ S K , define

A S = ∩ i∈C A i,Si ,
which is also a closed set. If ǫ 1 , ǫ 2 ∈ A S , then each class sends its flow to the same set of servers under equilibria N (ǫ 1 ) and N (ǫ 2 ). Consider a vector S ∈ S K and assume that we can find ǫ 1 , ǫ 2 ∈ A S such that ǫ 1 < ǫ 2 , i.e. A S is neither empty nor reduced to an isolated point. According to Proposition 7, the vector λ(ǫ 2 ) can be obtained from λ(ǫ 1 ) under a basic transformation. Since ǫ 1 , ǫ 2 ∈ A S , this transformation satisfies Assumption 1, and according to Theorems 3 and 4 we have either D(ǫ 2 ) > D(ǫ 1 ) or D(ǫ 2 ) = D(ǫ 1 ). We therefore conclude that if we can find ǫ 1 , ǫ 2 ∈ A S such that ǫ 1 < ǫ 2 , then D(ǫ 2 ) ≥ D(ǫ 1 ). Since [0, ∆] = ∪ S∈S K A S , all conditions of Theorem 5 are fulfilled, and we can conclude that D is a non-decreasing function of ǫ on [0, ∆].

Maximum of the Global Cost

The purpose of this section is to prove that the global cost achieves its maximum in the symmetric case, i.e., when λ = λ = = λ K , . . . , λ K . To this end, starting from a fixed rate vector λ, we build a sequence λ k k∈IN of rate vectors such that:

• λ 0 = λ, and • λ k+1 is obtained from λ k under a basic transformation of maximum step, i.e., λ k+1 = h λ k (∆ k ).

The following proposition shows that the sequence λ k k∈IN converges to λ = in a finite number of steps.

Proposition 8

The sequence λ k k∈IN converges to λ = in at most K steps.

Proof. Let w k be the number of classes in C k min ∪ C k max . Note that w 0 ≥ 2. According to Lemma 23.2, if w k = K, then λ k+1 = λ = . Otherwise, according to Lemma 23.1, we have C k min ∪ C k max C k+1 min ∪ C k+1 max , and thus w k < w k+1 ≤ K. This structure implies that in at most K steps we have w k = K, and thus λ k+1 = λ = .

We now prove Theorem 1.

Proof of Theorem 1. For each λ ∈ Λ, the sequence λ k k∈IN converges to λ = in a finite number of steps. According to Theorem 6, we have D(λ k+1 ) ≥ D(λ k ). This implies that D(λ = ) ≥ D(λ).

Analysis of the Symmetric Game

In the sequel, we will need the following assumption:

Assumption 3 φ(0) = 1.
Note that the above assumption is satisfied by type-II functions. The results established below are therefore valid for all type-II functions. They also hold for all type-I functions that satisfy assumption 3.

According to Theorem 1, we have

P oA(K) = sup λ,r,c D K (λ, r, c) D 1 ( λ, r, c) = sup r,c D K (λ = , r, c) D 1 ( λ, r, c) . (30)
Therefore, in order to analyze the PoA, we can focus on the symmetric case. We first introduce some preliminary results in Section 5.1 and then analyze the symmetric game in Section 5.2 where we derive an explicit expression for the equilibrium flows.

Preliminary Results

We introduce below some results that will be used to derive the NEP of the symmetric game.

Let

• D be the interior of the interval D upon which the function φ is defined. For each server j ∈ S and for K ≥ 1, let the function f j (K, ρ) :

• D→ (u j , +∞) be defined as follows

f j (K, ρ) = u j φ(ρ) + ρ K φ ′ (ρ) ∀ρ ∈ • D . (31)
From our assumptions regarding the function φ, it is easy to see that f j (K, ρ) is a continuous, strictly increasing and differentiable function on

• D.
It follows that the inverse function of f j (K, ρ) exists and maps (u j , +∞) onto • D. In the following, it will be denoted as ρ j (K, z), i.e., for each z ∈ (u j , +∞), ρ j (K, z) is the unique value of ρ ∈

• D such that f j (K, ρ) = z.
The following lemma establish some properties of the function ρ j (K, z).

Lemma 24 The function ρ j (K, z) has the following properties: a) For a fixed K, the function ρ j (K, z) is continuous and strictly increasing in z on (u j , +∞).

b) For a fixed K, the function ρ j (K, z) is differentiable on (u j , +∞) and

ρ ′ j (K, z) = 1 f ′ j (K, ρ j (K, z)) (32) c) if f j (K, ρ) is convex, then ρ j (K, z) is concave.
d) For a fixed z, the function ρ j (K, z) is strictly increasing in K.

e) lim z→u + j ρ j (K, z) = 0 f ) For two strictly positive integers K 1 and K 2 , and for each z ∈ (u j , u j+1 ), the following statement holds:

∃i ≤ j , ρ i (K 1 , z) < ρ i (K 2 , z) ⇐⇒ ρ s (K 1 , z) < ρ s (K 2 , z
) , ∀s ≤ j g) For type-I functions, lim z→+∞ ρ j (K, z) = +∞, while for type-II function lim z→+∞ ρ j (K, z) = 1.

Proof. Properties (a), (b) and (c) are well known properties of the inverse function of a continuous, strictly increasing and differentiable function (with a strictly positive derivative everywhere). See e.g. [START_REF] Bourbaki | Fonctions d'une variable réelle[END_REF].

To prove (d), let us consider two strictly positive integers K 1 and K 2 such that K 1 < K 2 . For z > u j , assume that ρ j (K 1 , z) ≥ ρ j (K 2 , z). Since f j (K, ρ) is strictly decreasing in K and strictly increasing in ρ, it yields

f j (K 1 , ρ j (K 1 , z)) > f j (K 2 , ρ j (K 1 , z)) ≥ f j (K 2 , ρ j (K 2 , z)), which is clearly a contradiction with f j (K 1 , ρ j (K 1 , z)) = f j (K 2 , ρ j (K 2 , z)) = z.
As a consequence, ρ j (K 1 , z) < ρ j (K 2 , z), which shows that for a fixed z, ρ j (K, z) is increasing in K.

Property (e) follows from φ(0) = 1 and the fact that φ and φ ′ are continuous functions.

Let us now prove property (f). Straight part: if ∃i ≤ j such that ρ i (K 1 , z) < ρ i (K 2 , z) then K 1 < K 2 because ρ i (K, z) is strictly increasing in K. Since z ∈ (u s , +∞) and ρ s (K, z) is strictly increasing in K, it implies that ρ s (K 1 , z) < ρ s (K 2 , z) for all s ≤ j, as claimed. Converse part: it is true from the statement.

Finally, to prove property (g), assume that z = f j (K, ρ) → ∞. In view of (31), this is only possible if we have either φ(ρ) → ∞, or ρ φ ′ (ρ) → ∞, or both. Since φ(w) < +∞ and φ ′ (w) < +∞ for all w ∈ D, this implies that ρ j (K, z) → ∞ for type-I functions, while ρ j (K, z) → 1 for type-II functions.

Let us now define the function W (K, z) = j∈S W j (K, z), where

W j (K, z) = ½ {z∈[uj ,uj+1)} • j s=1 r s ρ s (K, z) -λ .
The following lemma states some properties of the function W (K, z).

Lemma 25 The function W (K, z) is such that:

1. for a fixed K, the function W : [u 1 , ∞) → R is continuous, strictly increasing and differentiable in z, 2. for a fixed z, W (K, z) is strictly increasing in K, 3. for a fixed K, W (K, z) = 0 has a unique solution in the interval (u 1 , ∞).

Proof. Let us first prove property 1. By definition W (k, x) = W j (K, x) in the interval [u j , u j+1 ). The functions ρ s (K, z) are continuous and strictly increasing in (u s , +∞), which implies that W is continuous and strictly increasing in (u j , u j+1 ). To conclude the proof, we need to verify that W is continuous at u j , j = 2, 3, . . . , S. We have

lim x→u + j W (K, x) -lim x→u - j W (K, x) = lim x→u + j W j (K, x) -lim x→u - j W j-1 (K, u j ) = j-1 i=1 r i ρ i (K, u j ) + r j lim x→u + j ρ j (K, x) -λ - j-1 i=1 r i ρ i (K, u j ) -λ = r j lim x→u + j ρ j (K, x) = 0,
where the last equality follows from Lemma 24.(e). This shows that the function W (K, x) is also continuous at the points u j , j = 2, 3, ..., S.

To prove property 2, let us considers two strictly positive integers K 1 and K 2 such that K 1 < K 2 . For z ∈ (u j , u j+1 ), we have using Lemma 24.(f)

W (K 1 , z) < W (K 2 , z) ⇐⇒ j s=1 r s ρ s (K 1 , z) -λ < j s=1 r s ρ s (K 2 , z) - λ ⇐⇒ ρ s (K 1 , z) < ρ s (K 2 , z) ⇐⇒ K 1 < K 2 ,
which shows that for a fixed z ∈ (u j , u j+1 ), W (K, z) is strictly increasing in K. Continuity of W (K, z) at points u j , j = 2, 3, . . . , S implies that this is true for all z ∈ [u 1 , +∞).

Finally, let us now prove property 3. First, we note that W (K, u 1 ) = r 1 ρ 1 (K, u 1 ) -λ = -λ. From Lemma 24.(g), we have W (K, ∞) = +∞ for type-I functions, while for type-II functions W (K, ∞) = r -λ. In both cases, W (K, ∞) is strictly positive. Also according to property 1, W (K, z) is continuous and increasing in the interval [u 1 , ∞). Hence, there is a unique value of z for which W (K, z) = 0.

In the following, we let γ(K) be the unique solution of W (K, z) = 0 in [u 1 , ∞).

Analysis of the Symmetric Game

It is well known that in this case the non-cooperative routing game is a potential game, i.e., the equilibrium flows are the global minima of a standard convex optimization problem (see e.g. Theorem 4.1 in [START_REF] Cominetti | The impact of oligopolistic competition in networks[END_REF]). This is formally stated in the following proposition.

c j ρ j φ(ρ j ) + (K -1) ρj 0 c j φ(z)dz s.t. j∈S r j ρ j = λ, 0 ≤ ρ j < 1, ∀j ∈ S, (33)
then the multi-strategy x such that x i,j = r j ρj K , ∀i ∈ C, ∀j ∈ S, is the NEP of the symmetric game.

Proof. The statement follows from Theorem 4.1 in [START_REF] Cominetti | The impact of oligopolistic competition in networks[END_REF] with c a (x a ) = u a φ( xa ra ).

Note that when K = 1, the above problem reduces to the global optimization problem solved by the centralized scheme. When K → ∞, the equivalent problem states the common function that is optimized jointly by an infinite number of players and is characteristic of the Wardrop equilibrium.

The following proposition gives the solution of the symmetric game.

Proposition 10 The set of servers used at the NEP of the symmetric game is S * (K) = {1, . . . , j * (K)}, where j * (K) is the unique server such that W (K, u j * (K) ) < 0 ≤ W (K, u j * (K)+1 ). Moreover, the offered traffic of server j ∈ S at the NEP is 0 if u j ≤ γ(K) and ρ j (K, γ(K)) otherwise.

Proof. Let ρ be an optimal solution of the equivalent problem stated in Proposition 9. According to the KKT conditions, there exists γ such that for each j ∈ S,

f j (K, ρ j ) = u j φ(ρ j ) + ρ j K φ ′ (ρ j ) ≥ γ, (34)
with equality if and only if ρ j > 0.

Let us now consider a server j ∈ S. Let us first assume that u j < γ. In this case, a necessary condition for (34) to hold is f j (K, ρ j ) > u j , which implies ρ j > 0. We therefore obtain that (34) holds as an equality, and thus that γ = f j (K, ρ j ), i.e. ρ j = ρ j (K, γ).

Let us now assume on the contrary that u j ≥ γ. If ρ j > 0, then f j (K, ρ j ) > u j ≥ γ, which implies that ρ j = 0, i.e. a contradiction. Therefore, if u j ≥ γ, then ρ j = 0. Let j * (K) be the unique value of j such that u j < γ ≤ u j+1 . Then j * (K) j=1 r j ρ j = λ can be written as j * (K) j=1 r j ρ j (K, γ) -λ = 0, i.e. W (K, γ) = 0, from which we deduce that γ = γ(K). From Lemma 25.1 and u j * (K) < γ(K) ≤ u j * (K)+1 , we then obtain that W (K, u j * (K) ) < 0 ≤ W (K, u j * (K)+1 ).

We now prove that the distributed scheme with K dispatchers uses only a subset of the servers used by the centralized scheme. The proof is based on the following proposition.

Proposition 11 The function γ(K) is decreasing in K.

Proof. For K 1 < K 2 , we have W (K 1 , z) < W (K 2 , z) for all z ∈ [u 1 , +∞). With z = γ(K 1 ), it yields 0 = W (K 1 , γ(K 1 )) < W (K 2 , γ(K 1 )). Since W (K 2 , z) is strictly increasing in z, we conclude that γ(K 2 ) < γ(K 1 ). Therefore, γ(K) is decreasing in K.

The fact that γ(K) is decreasing in K implies that j * (K) is non-increasing in K. We therefore have the following important corollary.

Corollary 5 For K ≥ 1, S * (K + 1) ⊂ S * (K).

As an immediate consequence, we can conclude that S * (K) ⊂ S * (1), i.e., the distributed scheme with K dispatchers uses only a subset of the servers used by the centralized scheme.

Lower bound on Price of Anarchy

In this section we give lower bounds on the PoA for the functions of type (i) φ(x) = 1 (1-x) m , and (ii) φ(x) = 1 + x m . According to Theorem 1, we can restrict the analysis to that of the symmetric game.

In order to prove the lower bounds, we shall construct an example with two servers and symmetric dispatchers. For this symmetric game, we use its analysis given in Section 5.2 to show that the ratio D K /D 1 attains the desired value, which will then give a lower bound on the PoA.

Proposition 12 For φ(x) = 1 (1-x) m , P oA(K) ≥ K K 1/(m+1) + mK 1/(m+1) -m . ( 35
)
Proof. We consider the symmetric game of section 5.2 instance in which all the classes use only server 1 in the distributed case whereas they use all the servers in the centralized case. Let λ < r 1 , and c j = r j = 1 for j ≥ 2. For simplicity, let us consider the case of two servers. The same result holds for any number of servers as well. From the KKT conditions, if c 1 r 1 φ( λ/r 1 ) + λ

c 1 r 1 r 1 r 1 -λ m + λ Kr 1 m r 1 r 1 -λ m+1 ≤ c 2 r 2 (37)
Let us assume that c 1 is such that the above two inequalities are satisfied, and that it is closer to the upper bound. We note that when λ ↑ r 1 , the first term within the square brackets of (37) can be neglected with respect to the second term so that As λ ↑ r 1 , we can approximate D K as

D K ≈ K m (r 1 -λ). (39)
In the centralized case, in order to compute the total cost, D 1 , we need to first find the traffic on each of the servers. From the KKT conditions, the loads y j satisfy c j r j r j r jy j m + y j r 1 m r 1 r 1y j m+1 = γ(1), (40)

j y j = λ. ( 41
)
From the optimality conditions we know that γ(1) > c 2 /r 2 = 1, and we also know that when λ ↑ r 1 , γ(1) → c 2 /r 2 = 1. From ( 40) and (38) as λ ↑ r 1 , r 1y 1 ≈ K 1/(m+1) (r 1 -λ).

(42)

Since y 1 + y 2 = λ,

y 2 = λ -y 1 ≈ λ -(r 1 -K 1/(m+1) (r 1 -λ)) = (r 1 -λ)(K 1/(m+1) -1),
that is, y 2 tends to zero in proportion to (r 1 -λ).

As λ ↑ r 1 , the centralized cost can now be computed as

D 1 = c 1 y 1 r 1 r 1 r 1 -y 1 m + c 2 y 2 r 2 r 2 r 2 -y 2 m ≈ r 1 m K r 1 r 1 -λ m+1 -1 y 1 r 1 r 1 r 1 -y 1 m + c 2 y 2 r 2 ≈ K m (r 1 -λ) r 1 - λ r 1 -y 1 m + (r 1 -λ)(K 1/(m+1) -1) ≈ (r 1 -λ) K m 1 K m/(m+1) + K 1/(m+1) -1 = (r 1 -λ) K 1/(m+1) m + K 1/(m+1) -1 . (43)
Using ( 43) and (39), we obtain the lower bound (35) on the PoA as was claimed. 2. As K → ∞, the lower bound of (44) tends to a constant, unlike the lower bound (35) which tends to infinity. Thus, for delay function of the type of M/P areto/1/SRP T queues, the PoA can be unbounded when each job minimizes its own mean delay.

3. Moreover, for K = ∞, the lower bound (44) is of the order of m/ log(m), which matches the PoA obtained by Roughgarden [START_REF] Roughgarden | The price of anarchy is independent of the network topology[END_REF] for polynomial functions for the Wardrop equilibrium.

4. For m = 1 the delay function of M/P areto/1/SRP T tends towards that of the M/G/1/P S. From the lower bound formula given above, we retrieve the lower bound in [START_REF] Ayesta | Price of anarchy in non-cooperative load balancing games[END_REF].

Although we do not have the upper bounds for PoA as in [START_REF] Ayesta | Price of anarchy in non-cooperative load balancing games[END_REF], we conjecture that the lower bounds constructed using the above method give the right order of the PoA, just as was proved in [START_REF] Ayesta | Price of anarchy in non-cooperative load balancing games[END_REF] for the case of M/M/1 delay functions.

Conclusion

We investigated the performance of non-cooperative load-balancing in processorsharing server-farms. We have first shown that the worst global performance is obtained when all K dispatchers route exactly the same amount of traffic. This result implies that the analysis of the PoA can be done by focusing on the symmetric case, and therefore using the potential function method.

Figure 1 :

 1 Figure 1: Distributed load balancing.

  , φ ′ (w) < +∞ Proof. If w ∈ D, then ∃ǫ > 0 such that w + ǫ ∈ D. Hence, φ(w + ǫ) < +∞. However, since φ is convex and continuously differentiable on D, it lies above all of its tangents: φ(b) ≥ φ(a) + (ba) φ ′ (a) for all a, b ∈ D. With a = w and b

  and let n min = |C min | and n max = |C max |.

  ) ¿From (21), we have l<j,l∈S -i∈Cj \Cj+1 xi,l > l<j,l∈S -i∈Cj \Cj+1 x i,l +   l<j,l∈S + i∈Cj \Cj+1 x i,l -l<j,l∈S + i∈Cj \Cj+1 xi,l   , and using (22) it leads to l<j,l∈S -i∈Cj \Cj+1 xi,l > l<j,l∈S -i∈Cj \Cj+1

Proposition 9

 9 If the vector ρ is global optimum of the following convex optimization problem minimize ρ j∈S

2 ,

 2 then in the distributed case all the classes use only the first server whereas in the centralized case all the servers are used. For φ(x)

  case, since all the classes use only server 1, D K = c 1 λ

Figure 3 :

 3 Figure 3: Comparison of D K /D 1 and its lower bound for m = 1, 2, ..., 100 and K = 20.

Figure 4 :

 4 Figure 4: Comparison of D K /D 1 and its lower bound for m = 1, 2, ..., 100 and K = 200.

Acknowledgments

The authors would like to thank U. Ayesta (Basque Center for Applied Mathematics, Bilbao, Spain) for useful discussions.

Theorem 4 D(λ) = D( λ) ⇐⇒ S 1 = S K .

Proof. From Lemma 19 and Proposition 4, if S 1 = S K then y j = ŷj , ∀j ∈ S and therefore, D(λ) = D( λ). To prove the inverse, if S 1 = S K then necessarily S 1 S K . From Theorem 3, we can conclude that D(λ) = D( λ).

Maximum Step of a Basic Transformation

Theorems 3 and 4 enable the comparison of the equilibria induced by two different rate vectors λ and λ, provided that λ can be obtained from λ under a basic transformation which leaves unaffected the set of servers used by each class. The main limitation of these results comes from the latter assumption. However, as will be shown below, the continuity of the Nash mapping can be exploited to prove that, under certain conditions, the global cost is non-decreasing under the transformation even if some classes change the set of servers they use.

Definition 2 For each rate vector λ ∈ Λ, the maximum step of the transformation h λ is

where

Intuitively, if the step ǫ of a basic transformation is lower than the maximum step ∆, then the sets C min and C max will be unaffected by the transformation. On the contrary, if ǫ = ∆, then, after the transformation, we will have either (i) one more class in the set C min or C max , or (ii) λ = λ = .

For each rate vector λ, let λ(ǫ) = h λ (ǫ) for ǫ ∈ [0, ∆]. All quantities of interest can be treated as functions of ǫ. Therefore, in the following, if z is a certain quantity related to the Nash equilibrium induced by the vector λ then we shall denote the corresponding quantity for vector λ(ǫ) by z(ǫ).

We first prove the following properties of the transformation when ǫ ≤ ∆.

Lemma 21 For each ǫ ≤ ∆, 1. λ i (ǫ) ≤ min λ K , min k∈C\Cmin λ k for all i ∈ C min , and the inequality is strict if ǫ < n min ∆ min whereas it holds as an equality if ǫ = ∆ = n min ∆ min , Conjecture 1 For φ(x) = 1 + x m and m ≥ 1,

We shall give numerical evidence to support our claim that (44) is a lower bound for the PoA. We first note that for the polynomial function, the stability condition is λ < ∞. We now construct an example in which the number of servers is λ and λ → ∞. Following the steps in the proof of Proposition 12, we can show that

where ρ 2 is the solution of

We now claim that the denominator of D K /D 1 is upper bounded by (1 + m/K) -1 1+m/K 1+m m+1 m +m -1 log 1+m 1+m/K , which then supports the conjecture. In support of the conjecture, in figures 2, 3 and 4, we plot the exact value of D K /D 1 , and the lower bound for various values of m and K.

Remark 2

1. The lower bounds obtained above are independent of r and c.


Gérard Régimbeau

About knowledge on History of Art on the internet : profane, specialized and documental writings

Keywords: History of Art, internet, mediation of knowledge, writing, enunciation, popular culture, blog, folksonomy, artistic culture, édition, art documentation, art journals, typology, taxinomy

To approach the present state of affairs concerning the mediation of knowledges on History of Art on the internet, this paper proposes to observe, by means of case analysis, the characteristics of three writings: profane, specialized and documental writings. This approach considers the characters and enunciative contexts of each one in a socio-semiotic perspective, which makes it possible to cross knowledge and informational and communicational practices, so as to study how the interdependence between support and medium is built.

issue is, first of all, to make sense of an informational reality with the assistance of descriptive criteria taken from the analysis of enunciation, from the analysis of content and sociosemiotics, to attempt to find the dominant and maybe even revealing traces of certain logics of publication and edition, in the external expression of certain digital qualities.

Among the writings we will deal with are 1) those whose status fluctuates from testimonial, reaction to the exchange with readers or public trust: The "profane writings"; 2) then, those that were developed in an old format and in permanent reconstruction of the periodic press through newspapers and magazines: The "special-ized writings"; 3) and, finally, those that intend to place, work out and communicate references: "documental writings". These three fields are far from indenting the changing and extensive matter of writings on art, but they offer boundaries where knowledge, informational and communicational practices cross each other so as to study how the interdependence of support and medium is built [START_REF] Souchier | Lorsque les écrits de réseaux cristallisent la mémoire des outils, des médias et des pratiques[END_REF]ORRIGI, 2004).

"Profane" writings on art

Along with the historical, scientific, critical and esthetic genders related to artists, university students and professional authors, other writings on art are ex-pressed and put into circulation on the internet. They feed blogs, forums, websites, personal webpages and other spaces ! $! devoted to them. The interest they arouse is indisputable for those wishing to interrogate certain forms of knowledge on art history and recover its con-tents. They could be called "common writings", "amateur writings" or "restricted writings" as well -not intending a connotation whatsoever -since their authors come from an amateur or non-specialized group (in several degrees). The term "profane", taken from the sociologi-cal vocabulary, attempts to translate the idea of a text from non-proficient individuals, idea that Hervé [START_REF] Moëlo | L'ordinaire et le littéraire[END_REF]1 promoted as "laical" in an article in which he clearly states the difficulty of referring to the so-called "common" writings without questioning the ideological basis of the notion itself.

"Blog" writings and forum words

Generally short and reactive shared comments and articles referring to exhibitions, they remind us of the reasons why a certain work should cause interest or they deal with interests related to movements and artists; these texts, previously part of personal diaries, letters or reader's mail, now consist accessible sources for the study of these writings (considering them "files" could be premature because of the ephemeral character of the personal websites). This kind of investigation is obviously the interest of a reception sociology which considers popular expressions of culture -popular culture itself -as well as a certain popular relation with other cultures, especially with the erudite culture -immediately defining that the matter, in these statements, refer to fragments mixed with the most varied cultural horizons, where curious beginners, versatile individuals, eager amateurs and also learned individuals wandering outside their specialty, gather together. However, this study cannot remain unknown for or independent from information and communication sciences, which, in this field, have a typical example of the textual and cultural confronta-tions on the enunciation modalities connected to the communication means and conditions.

In some cases, among others, these enunciations determine the tone of what could be the topic of a more systematic prospection.

•

For example, a web user who writes ironically about a certain car introduced by Citroën: "It's a shame its design is so clumsy... To be clear, using the name of a genius like Picasso for a machine that looks like a compact Caesar formation is amazing..."2 He humorously witnesses a certain familiarity with the "standards" of contemporary art. Certainly, these taking of stands, these opinions with no real editorial commitment, these glances, have existed for a long time, but with the internet they have surfaced to the public level and brought about a horizon of reception, opening up the "golden book" of arts, usually restricted to the place where the exhibition took place.

"Tagged" texts

Another expression of the profane writings on art is the phenomena, now generalized, of the folksonomy that consists -in a kind of spontaneous creation of an index -in any author or web user creating "tags" (labels or keywords) for texts and images without mentioning (or at least without any explicit reference) to the lists of topics and references or documental languages.

The Flickr5 photo sharing website invites us to use a tag with the following statement as an encouragement: "What are tags? You can give your photos and videos a "tag", which is like a keyword or category label. Tags help you find photos and videos which have something in common. It is pos-sible to label up to 75 tags for each photo or video." However, there is a distance between what is announced and what is feasible. For example, the tags attached to Brian Eno's6 work "Quiet Club" for the Lyon Biennial of 2005 are only five: "Lyon;

Contemporary Art Biennial, Dalbera (who took the photos); France; Eno". The same happens with other works exhibited on the site, which really limits the pos-sibilities to find images.

Maybe it can be inferred that folksonomy is incapable of deep or pertinent indexation because it is not possible to improvise as an index maker out of nowhere, especially when the motivation of the "publication" does not distinguish itself by the interest in spreading certain specialized information, rather it is interested in the transposition of personal picture albums.

It is possible, however, to bring together amateur practices and principles inherited from

! &!
museology, dedicated to the popularization and facilitated access to culture. This is what happens with the experiment called "Steve" in which some American museums collaborated: "We are a group of volunteers, primarily from art museums, who share a common interest in improving access to our collections. We are concerned about barriers to public access to online museum information [...] who believe that social tagging may provide profound new ways to describe and access museum collections and encourage visitor engagement with museum objects."7 ---This project started a few years ago is supposed to generate reports on the efficiency of the opening to active consultation by visitors from all fields: "[...]

Participation in steve is open to anyone with a contribution to make to developing our collective knowledge, whether they formally represent a museum or not"8. This kind of experience internet makes possible, more than any other communication system, is carefully followed by some professionals, who consider folksonomy a way to enrich the indexation of the works -"...since the tags added to the works are a lot richer, simply because of the multicultural-ity folksonomy engenders"9 -as well as a way get the visitor more involved by means of using one's own comments or simplifying access to the works through the use of a less specialized vocabulary: "This vocabulary understood by anyone evidently makes searches easier, since tags are also metadata."10 Seth Van Hooland insisted on the need to count on these new practices: "The comments from users may be greatly useful, for example, in databases of historical images to increase the quality of metadata available" ( VAN HOLLAND, 2006, p.46).

These aspects -only half-shown here according to spaces or places of expressions -concern this research and do hold a growing place in the study of mediatic (as medium and media) specificities of the internet (Cf. EUTIC, 2007)11. Soon comparative synthesis will become possible, both from a historical point of view (social, economic and cultural) of the personal and shared websites or typologies and from the concrete demonstration (themes, forms, contents...) of these expressions, "leading to analyses that avoid the banalization of the quotidian and resist the reflex of heroification through text", as Hervé Moëlo affirms.12

Specialized writings: art magazines and journals

With the internet we are facing an enunciation system that places or intertwines private and public registers, close and far, internal and external, native and exogenous -a fact which leads us to finding every level of publication. The journalistic world is certainly one of the most

! '!
represented, be it professionally or "amateur-ishly" (with blogs, websites for sharing purposes and forums), recovering certain semiotic and rhetoric aspects of the journalistic signatures and tone. The professional mode is characterized by print, among which we can find exclusively digital titles and "bi-media" titles (paper and digital) in the category of newspapers as well as magazines. What was observed in other studies (RÉGIMBEAU, 1999;[START_REF] Regimbeau | Les revues d'art contemporain entre imprimé et électronique : évolutions récentes[END_REF]COURBIÈRES et al., 2007)

From printed paper to computer media

An important title in the field, easily found in newsstands, bookstores and libraries, Connaissance des arts (http://www.connaissancedesarts.com/) is publicized and introduced as an information media: "Every month, Connaissance des Arts keeps its readers updated with international news." Thus the topics intend to cover all events in an encyclopedic fashion: "To better understand the art of all times, from archeology to contemporary creation, from garden art to design and architecture". However, this copy of the print version becomes an online media, associating information to contents closer to a collec-tion of works, such as "Chronicles of a life, Art and society, Analysis of style, Study of a work, Library" as well as to functionalities involving files and the dissemination of topics such as "Videos, Portfolio, Listen, Introduction to Art" through which one can have access to documental films and interviews. The total, in the periphery and in hypertextual links with expected titles in the editorial center mobilized by covers and summaries of the print edition. Emphasis is placed on the abundance of topics on a dense homepage -"home" (overloaded, which is quite common on sites meant for large screens) on which headlines, titles and subtitles, links and advertisements squeeze in, which relate this kind of online publication to a multimedia newspaper.

Among the art press sites, this kind sums up a ten-dency that aims at opening in the web, not only a website to go with the paper version, but also to develop a portal that may encourage the visitor to use all the areas of the website, reminding us, as a promise, of the remarkable information content of the newspaper. This reader, who is also a spectator and an auditor, may have permanent access to information stocked according to a dosage of proportions finely weighed compared to the print ver-sion. The portal performs the function of promotional ! (! argumentation for the newspaper, publicizing its quality by means of the simple reduction of topics: Quantitative, in this case is under signs, subject to the questioning of its meanings when the print media, especially everyday media, reduces at the same time its texts and surfaces.

From the digital magazine to the center of artistic initiatives

After the implementation phase, magazines had to find out how to survive. Generally, this was what happened to the online edition, whose first steps on the Internet were supported by public, private or association structures. Synesthésie is among the titles that survived due to several actions in the publishing, social and finan-cial fields. The formula used by the magazine in its initial phase is characteristic of its position in between an art magazine, a forum, an editor and an association. If on one hand it claims precocity and its significant experi-ence, suggesting that it "was the first art magazine on the in-ternet in France", on the other hand it also establishes that its activities are both publicizing and editing: "In 2002 we created, the CAV (Virtual Art Center) on the site, a space to access works especially created for the internet and for Synesthésie." This Virtual Art Center with the Synesthésie badge was possible thanks to several regular contributions from the cities, departments, regions and the Ministry of Culture and the Regional Culture Man-agement. This action was carried out, among others, in 2006, through the virtual participation -and also physi-cal -in a Biennial called "Urban Mutations" in Seine-Saint-Denis (Parisian region), which was extended by means of an informative presence of the Biennial on the Synesthésie website, continuing the publicization of the works by invited artists in this space accessed through the CAV13, also

showing expository texts by the curators14. The functions normally acquired in posterior phases and different supports, up to the most consequent, that is, naturally, the conservation of the works created for the event, are thus gathered and -for a certain amount of time, maybe, still to be observed -accessible.

The filing of old numbers, virtual works, studies, projects, which is a constant concern from the begin-ning of the magazine, created dense assets, which places it in a new enunciative configuration: As a portal or a platform to organize open files. In the subject of Art His-toryin which another vector is also active concurring and complementing the article published in a scientific magazine: The exhibition's catalog -the importance placed on the arguments of the exhibition, the historical texts and the comments on works is marked by this will to preserve characteristics.

!

)!

Documental writings

The grouping, as well as the crossing and "accumulation" of data on the internet, so diverse and numerous, favored studies that sought to understand and clarify the landscape of information.

Typology and organization of knowledge

Regarding art, the studies were carried out aiming at new possibilities created by computer techniques. During the 1990's, for example, several works came about strug-gling to circumscribe the characteristics of the websites and generating forms of typological categorization: An important example was the classification of digital works, performed by Annick Bureaud so as to "display the great categories of works online" [START_REF] Bureaud A | Pour une typologie de la création sur Internet[END_REF].

This category approach also came from the docu-menting services and libraries in the organization of topics and the architecture of its websites. Having the objective of selecting and relating, as well as creating a scope of understanding for the field, these tools have news.

The analysis of the inputs in complex information is not only of practical interest; it is an important clas-sifier which can be a complementary theoretic tool to analytically define a field of study. These documental text principles can be used, for example, in the methodic exploration of the web to define the theme of an aca-demic dissertation.

Taxonomy and indexation

Other documental tools come about on the net and may aid comprehension or, more ! *! specifically, add to the pedagogic instruments necessary to understand the works. Francis Parent16, art critic and historian, worked to define taxonomy for a database, articulated around a few main required criteria for the reception and critical appreciation of the works.

The four criteria chosen for the base called Artrinet17, which actually determine the indexation classification, are A) Formalism (most abstract, most figurative, most..., etc., from the most "immaterial" to the most "realistic"?); B) Materiality (pure concept, group of materials, transversal object, etc., classified as the most "immaterial" to the most "real"?); C) The body-mind investment (which is the Body/Mind ratio by which the artist expresses oneself in the work? Classified from the most "intellectual", for example, "Conceptual Art", ... to the most "physical", for example, "Body Art",...). D) Communication (The artist deliberately intends to communicate some kind of message through his/her work?

(classified from most "spiritualist" to most "mundane").

This principle of plastical and esthetical definition of an important corpus is interesting in more than one instance: Be it for a contextual observation that may consider it an additional moment of critical methodology, be it for an observation strictly guided by and for the art market, be it as a witness of the esthetic commitments of the Artension magazine which supports this project18. All these approaches are possible, but the one we support here is the formalization of documental criteria whose list and organization are worth a pre-figuration of a compen-dium which is applicable to contemporary works, usually hard to synthesize (condense) documentally by keywords or descriptions, such as thematic dimensions.

Conclusion

Our contribution proposed to deal with the specific field of internet writings, inferring that these examples, interesting in themselves, could also be used to approach other cases to study the mediation of knowledge and the information on art.

The new modes of writing or reading authorized by the Internet where the network, the sites, the exchanges and the hypertextuality are coordinated resort to three essential types of new:

The new signs at play, engendered by technique and esthetics; the one arising from the new conditions of text and image (both referring to innova-tion) enunciation; and the one referring to updating or original generation of contents (this type referring to, above all, innovation).

! "+!

Varying, the text receives differ-ent shapes as to linguistic and editorial unity, not only according to the context of its production, as well as its availability. These two moments can also be conceived as united or even mixed, when a concept of text updating is referred to only in its reception. The text is not what is read once by a receiver, cultivated or not. Turning our observation to the kind and the context of the enuncia-tion, we try to make sense of the dynamics that sow the communication intention.

As new writings, these enunciations created by different social actors who invest contents, motivations and several obligations, presuppose an observation and analysis of the modes of expression and inscription in a mediatic and informational window crossed by ideologi-cal and economical (paid websites, commercial, free, etc.) and cultural (art, science, education) challenges which cannot be dissociated from political and social chal-lenges. Since these writings result in the organization of a discourse, this would be one of the issues to resume in a socio-semiotic perspective that is concerned with the relation between the sign and the meaning.

Notes

  has continued, taking diverse new faces, of which we will portray a few aspects, using as examples, the website of an old print newspaper (Connaissance des arts [Art knowledge] created in 1952) and the typical model of a digital magazine that exceeds digital (Synesthésie [Synaesthesia] created in 1995).

  become themselves typological documents. Claiming the theorization of documental pragmatics, we established a first synthesis of the reference potential of the notions and points of view from the selection of meaningful web-sites in the delimitation of "classifications" or relation with the subject15: Artists; 2) subjects and techniques; 3) works (collection, exhibitions, conservation); 4) research on art; 5) geography; 6) cultural mediation of art; 7) edition, mediatization and criticism; 8) documental re-sources; 9) formation of artists; 10) markets and galleries; 11) law and professional and social statute; 12) cultural policy; institutions and support; 13) activities and actors associated, among which art education;[START_REF]Arte grandeza natureza 06[END_REF]