Eitan Altman

Emergence of Equilibria from Individual Strategies in Online Content Diffusion

Keywords: User-generated content, Complex Systems, Video popularity, Game theory, Wardrop equilibria

Social scientists have observed that human behavior in society can often be modeled as corresponding to a threshold type policy. A new behavior would propagate by a procedure in which an individual adopts the new behavior if the fraction of his neighbors or friends having adopted such behavior exceeds some threshold. In this paper we study the question of whether the emergence of threshold policies may be modeled as a result of some rational process which would describe the behavior of non-cooperative rational members of some social network. We focus on situations in which individuals take the decision whether to access or not some content, based on the number of views that the content has. Our analysis aims at understanding not only the behavior of individuals, but also the way in which information about the quality of a given content can be deduced from view counts when only part of the viewers that access the content are informed about its quality. In this paper we present a game formulation for the behavior of individuals using a meanfield model: the number of individuals is approximated by a continuum of atomless players and for which the Wardrop equilibrium is the solution concept. We derive conditions on the problem's parameters that result indeed in the emergence of threshold equilibria policies. But we also identify some parameters inwhich other structures are obtained for the equilibrium behavior of individuals.

I. INTRODUCTION

Online media constitute currently the largest share of Internet traffic. A large part of such traffic is generated by platforms that deliver user-generated content (UGC). This includes, among the other ones, YouTube and Vimeo for videos, Flickr and Instagram for images and all social networking platforms.

Among such services, a prominent role is played by Yo u Tu b e , w i t h m o r e t h a n 3 billion hours of video watched every month and 72 hours of video uploaded every minute by YouTube's users 1 .O fc o u r s e ,n o ta l lv i d e o sp o s t e do n Yo u Tu b e a r e e q u a l . T h e k ey a s p e c t i s t h e i r " p o p u l a r i t y " , broadly defined as the number of views they score (also referred to as viewcount). This is relevant from a twofold perspective. On the one hand, more popular contents generate more traffic, so understanding popularity has a direct impacton ⋆ INRIA B.P.93, 2004 Route des Lucioles, 06902 Sophia-Antipolis, Cedex, FRANCE, email: eitan.altman@sophia.inria.fr CREATE-NET, via Alla Cascata 56 c, 38100 Trento, ITALY, email: {fdepellegrini,dmiorandi}@create-net.org † CERI/LIA, University of Avignon, 74 rue Louis Pasteur, 84029 AVIGNON Cedex 1, email: {rachid.elazouzi, tania.altman}@univ-avignon.fr This work has been partially supported by the European Commission within the framework of the CONGAS project FP7-ICT-2011-8-317672, see www.congas-project.eu.

1 http://www.youtube.com/t/press_statistics/ caching and replication strategy that the provider should adopt. On the other one, popularity has a direct economic impact. Indeed, popularity or viewcount are often directly related to click-through rates of linked advertisements, which constitute the basis of the YouTube's business model.

Recently, a number of researchers have analysed the evolution of the popularity of online media content [START_REF] Cha | I tube, you tube, everybody tubes: analyzing the world's largest user generated content video system[END_REF], [START_REF] Crane | Viral, quality, and junk videoso nY o u T u b e : Separating content from noise in an information-rich environment[END_REF], [START_REF] Gill | YouTube traffic characterization: A view from the edge[END_REF], [START_REF] Ratkiewicz | Traffic in Social Media II: Modeling Bursty popularity[END_REF], [START_REF] Chatzopoulou | A First StepT o w a r d s Understanding Popularity in YouTube[END_REF], [START_REF] Cha | Analyzing the video popularity characteristics of large-scale user generated content systems[END_REF], with the aim of developing models for early-stage prediction of future popularity [START_REF] Szabo | Predicting the Popularity ofO n l i n e Content[END_REF].

Such studies have highlighted a number of phenomena that are typical of UGC delivery. This includes the fact that a significant share of content gets basically no views [START_REF] Cha | Analyzing the video popularity characteristics of large-scale user generated content systems[END_REF], as well as the fact that popularity may see some bursts, when content "goes viral" [START_REF] Ratkiewicz | Traffic in Social Media II: Modeling Bursty popularity[END_REF]. Also, in [START_REF] Szabo | Predicting the Popularity ofO n l i n e Content[END_REF] the authors demonstrate that after an initial phase, in which contents gain popularity through advertisement and other marketing tools, the platform mechanisms to induce users to access contents (re-ranking mechanisms) are main drivers of popularity.

In this paper, we address such phenomena, by developing am o d e l ,b a s e do ng a m et h e o r e t i c a lc o n c e p t sa n dt o o l s ,f o r understanding how user's behaviour drives the evolution of popularity of a given content. The work is based on rational decision-making assumptions, whereby the users have to decide whether to see a given content or not. This configures as ag a m e ,w h e r eu s e r ss e e kt om a x i m i z es o m ee x p e c t e du t i l i t y based on their "perception" of the quality of the content2 and on viewcount. However, users suffer also a cost for accessing contents of bad quality, i.e., waste of time and possibly bandwidth, batteries, etc. In particular, in the decision process the viewcount is used as a noisy estimator of the quality of a content. Interestingly, this context resembles closelyt h e situation in the economic domain, where customers of a firm which are uninformed do infer the quality of products from the length of the queue they encounter upon requesting firm's goods to purchase [START_REF] Debo | Signaling quality via queues[END_REF].

Extensive advertising and marketing campaigns can be used to push the viewcount of a given content up. And in the decision making process users do not know whether the viewcount has been "pushed" by such means. Also, the decisions made by different users influence the viewcount and consequently the decisions made by other users, a process which suits well the usage of game theoretical machinery.

Specifically, we describe the conditions for the adoption of common behaviors in online content access. This is inspired by findings in social science [START_REF] Rolfe | Social networks and threshold models of collective behavior[END_REF], [START_REF] Granovetter | Threshold models of interpersonal effects in consumer demand[END_REF], [START_REF] Granovetter | Threshold models of collective behavior[END_REF]: results there show that emerging behaviours would propagate by a procedure in which an individual adopts a novel behavior if the fraction of neighbors or friends having adopted the same behavior exceeds some threshold. In our context, the threshold would be expressed in terms of viewcount or related metric.

In the sense of game theory, users of online media represent non-cooperative rational players connected through some social tie, e.g., being users of the same UGC platform. Since we consider systems composed by a very large number of users, the customary tool to study the user behaviour is that of Wardrop equilibria [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF]. In particular, we have found a number of conditions for which such equilibria exist and can be characterized analytically. Explicit conditions were found for content to stay at zero views or to become so popular that it is makes sense for all users to access it the sooner the better.

Furthermore, we identify, for the general case, conditions under which players tend to accrue around a common strategy depending on initial conditions. This is due to the existenceof ac o n t i n u u mo fe q u i l i b r i a :t h es y s t e mw i l ls e t t l ea ta n yp o i n t very much depending on initial conditions imposed, for instance, by a set of forerunners which cause significant changes of the content popularity. Such conditions were identified in early works such as [START_REF] Hassin | Equilibrium threshold strategies: The case of queues with priorities[END_REF] in other contexts: there, the authors applied threshold type Nash equilibrium strategies in which one purchases priority if and only if upon arrival the queue size is larger than some threshold value. Key motivation in [START_REF] Hassin | Equilibrium threshold strategies: The case of queues with priorities[END_REF] is predictability and control of purchase priority. What motivates this work is predictability and control of online content access.

Novel contribution: in this paper, we move away from the classical analysis of social networks in the spirit of [START_REF] Cha | I tube, you tube, everybody tubes: analyzing the world's largest user generated content video system[END_REF], [START_REF] Ratkiewicz | Traffic in Social Media II: Modeling Bursty popularity[END_REF], [START_REF] Chatzopoulou | A First StepT o w a r d s Understanding Popularity in YouTube[END_REF], [START_REF] Szabo | Predicting the Popularity ofO n l i n e Content[END_REF]: instead, we provide a first analysis based on games. The aim of this paper is to provide a novel perspective where contents compete to gain popularity and are subject to the effect of user's choice. For the sake of space, we omitted proofs and some model extensions that can be found in [START_REF] Altman | Emergence of equilibria from individual strategies in online content diffusion[END_REF] II. SYSTEM MODEL We consider contents made available to a user by means of Yo u Tu b e o r a s i m i l a r p l a t f o r m . We d e n o t e b y τ the lifetime of acontent,i.e.,thetimehorizonduringwhichthecontentbears some interest. In general, such horizon differs depending on the type of content: it can be typically of the order of weeks to months for YouTube videos or a few days for news [START_REF] Szabo | Predicting the Popularity ofO n l i n e Content[END_REF]. An extension to variable time horizon is addressed in [START_REF] Altman | Emergence of equilibria from individual strategies in online content diffusion[END_REF] We denote by X(t) the viewcount attained by a given content θ at time t seconds after it has been posted, for 0 ≤ t ≤ τ .

As in standard UGC platforms, there are two mechanisms that coexist and can jointly increase the viewcount: push:thecontentproviderexploitssomepreferentialchannels (including paid advertisement either directly on the UGC system or via social networking platforms) to make users aware of the content and to induce them to access it. We call push users the users that access the content as a reaction to the push mechanism. pull:u s e r sfi n da b o u tt h ec o n t e n tt h r o u g hs t a n d a r ds e a r c ha n d decide to access it based on the belief that the content is relevant for them. We call users accessing a content through the pull mechanism pull users.

In practice, many YouTube videos are subject to the push and the pull mechanisms described above such as the examples that we reported in Fig. 1. For instance, Fig. 1a, shows the dynamics of a popular video with viewcount X ≥ 675000. The YouTube statistics associated with the video describe explicitly a series of events happening in the first part of the dynamics of X.F ori ns t a nc e ,t hee v e ntBt ha ta ppe a rsa round 02/12/2012, is precisely the event ''First embedded on: plus.google.com'' which indeed configures as a push towards a social network platform. After the initial push, such events vanish, and the rest of the dynamics appears ascribed mostly to the pull mechanism defined above, with al i n e a ri n c r e a s ei nt h ev i e w c o u n t .

Also, some of the reported videos are representative of a specific class of online contents, which are those we will be dealing with in the rest of the paper. We can refer to those as the contents that comply to the exponential-linear model, for the sake of brevity. In particular, many such contents appear to obey to the following dynamics: after an initial exponential growth, the increase of the viewcount becomes linear. The way to interpret such behavior can be traced to the notion of push and pull mechanisms described above: the exponential growth corresponds to actions through which the source distributes the content within a basin of target push viewers. When such basin is finite and small with respect to the content diffusion dynamics, the viewcount dynamics experiences a saturation effect which takes over after an initial phase. However, at that stage, the access to the content is due to pull users that come across the content browsing online: they do so at random from a very large basin, so that the

X(t, θ) t β (θ) τ τ -t β (θ) β x Fig. 2:
The reward or the cost of content θ for a tagged user is represented by the time during which the content can be accessed, i.e., when viewcount is larger than threshold β.

access rate, i.e., the viewcount increase rate, is linear. These combined effects are visible in the case of the first two videos, i.e., Fig. 1a and Fig. 1b. In the case of the first video, the saturation effect is well visible, whereas in the case of the second one the linear increase following the saturation is dominating. The example in Fig 1c is a case where all the dynamics is linear: as it will be clear in the following, in the exponential-linear model this case is represented when either the basin of push users is large or when the rate at which contents are pushed is small. Not all videos will diffuse according to the proposed exponential-linear model. For instance, there exist cases when the initial viewcount dynamics displays a characteristic epidemic sigmoid shape [START_REF] Altman | Emergence of equilibria from individual strategies in online content diffusion[END_REF]: we can ascribe such similarity to the presence of a positive feedback in the push mechanism, e.g., feedback effect can happen between different channels on the same platform, e.g., YouTube channels, and across different platforms through the recommendation list that is presented to the platform users. This also qualifies the type of exponential-linear dynamics that we consider as those for which this type of feedback does not play a significant role.

In our model, we are interested in the uptake of the pull users. Pull users interested in the given content do not know in advance its quality. They may discover it during interval [0,τ] at random. Their estimation of the interest/potential quality is based on the viewcount X.Inthesimplestcase,contentswith higher viewcount are more likely to be accessed.

We define by X ps (t) the number of push users accessing the content up to time t as a reaction to the push mechanism and, analogously, by X pu (t) the number of those accessing it through the pull mechanism. Clearly, X(t)=X ps (t)+X pu (t).

Users have beliefs about the quality of the content. We denote by π G the belief that a given content is good (i.e., of interest or anyway worth accessing) and, conversely, by π B =1π G the belief that the content is bad. We denote by π =( π G ,π B ) the corresponding distribution. Stating π G =0 .75 means that a user believes that every 4 similar contents she would get 3 good ones and 1 bad one.

The content access configures as a game where we define players, strategies and utilities. Players: the players are pull users; based on their belief π, they may access the content θ or not.

Strategies: they access θ when the viewcount is above a certain threshold, i.e., X(t) ≥ β ≥ 0.H e n c e ,t h estrategy for ac e r t a i nu s e ri sthe viewcount threshold β ≥ 0.O fc o u r s e , all other players also adopt their own strategy with respect to θ and we denote α the vector of strategies, i.e., viewcount thresholds, for all other users.

Utilities: users face either a cost C or a reward R for playing strategy β:t h ec o s ta n dt h er e w a r di st h ef r a c t i o no fl i f e t i m e when the content is in the viewcount range, i.e, when they are willing to access it. The rationale to define this cost/rewardi s the following. Let a good content be worth one unit reward, and a bad content worth a unit cost. The user may hit several similar contents at random over time. If they are good, the fraction of those actually accessed will be proportional to 1 -

t β (θ)
τ ,w h e r ew ed e fi n et β (θ) = min{t | β = X(t),θ},i . e . , t β (θ) is the smallest instant when the threshold is achieved (the dependence of t β (θ) on α is dropped for notations' sake). That also is going to be the long term reward, or the cost, for accessing similar online contents. Formally,

R(α,β,G)=(τ -t β (G)) + ,C (α,β,B)=(τ -t β (B)) +
Finally, based on their belief π,p l a y e r se x p e c tau t i l i t yw h e n playing β that amounts to

U (α,β)=π G R(α,β,G) -π B C(α,β,B)
According to the above expression, the cost and the reward are a function of the interval when the content is above the threshold, i.e., when the users can benefit from it, and depends on the other players strategy. Furthermore, the action takenby players depends on their belief on the quality of the content.

In the following we will investigate symmetric equilibria, i.e., equilibria for which all users play α ≥ 0,i . e . ,α = α1; we then define t α = min{t|α = X(t)}.

Let a tagged user playing β when all the remaining users use α:wemaketheassumptionthatW ardropconditionsholds. Namely, for a large number of users any unilateral deviation of a single user does not affect the utilities of other users. I.e., deviations due to a single user action are negligible. Wardrop equilibria are much easier to compute than the Nash equilibrium; however, Wardrop is a good approximation for the latter, as in [START_REF] Haurie | On the relationship between Nash-Cournot and Wardrop equilibria[END_REF]. 3The tagged user expects to gain a certain reward R(α, β, G), for a good content and expects to suffer a cost C(α, β, B) when the content is bad: under which conditions α is the best response to itself, namely α = β * (α)?W ea n s w e rt ot h i s question in the next sections under different knowledge of the viewcount dynamics available to users.

Before we introduce our analysis, we recall that the utility function has the following expression for

β ≥ β τ,B U (α, β)= 0 if β ≥ β τ,G π G (τ -t β (G)) if β τ,B ≤ β ≤ β τ,G
where β τ,θ is solution of the following equation t βτ (θ)=τ .

We observe that the utility function U is nonincreasing for β ≥ β τ,B .Howeverthebestresponseβ * (α) can be found only in the interval [0,β τ,B ].A sar e s u l tw er e s t r i c to u ra n a l y s i s to case when β ≤ β τ,B in which the utility function can be expressed as

U (α, β)=π G (τ -t β (G)) -π B (τ -t β (B))

III. PLAIN VIEWCOUNT

The basic model that we introduce in this section is based on the assumption that pull users rely on the number of hits of the contents to judge if it is worth to access it or not, i.e., they judge based on how many users accessed it. Thus, they play based on the dynamics. We hence specialize our analysis to two cases.

A. Linear case

First, we examine the case when the process of diffusion of contents is linear. This is the case when the time scale of the content diffusion is very large compared to the pool of potential viewers. Amechanismthatthatisablegeneratesuch ad y n a m i c si st h ec o m b i n e de f f e c to fa na d v e r t i s e m e n tw h i c h is broadcasted to a very large pool of viewers, e.g., covering newspapers or other general audience media, and people so made aware of the existence of the content who decide to access the content with some random delay thereafter.

Thus, we let X ps (t, θ)=λ ps t• (t) where (t) is the unitary step function, and

X pu (t, θ)=λ pu (t -t α ) • (t -t α )
Observe that in this case λ ps = λ ps (θ),w h e r e a sλ pu is independent of θ.I nf a c t ,w ea s s u m ep u l lu s e r sj u d g eb a e d on viewcount only [START_REF] Debo | Signaling quality via queues[END_REF]. However, we assume that λ ps (G) ≥ λ ps (B).T h ea b o v er e s u l t sp r o v i d eac h a r a c t e r i z a t i o no ft h e possible symmetric Wardrop equilibria of the system. represents the time pace at which push users are believed to access a good content. Similarly πB λps(B) represents the time pace at which push users are believed to access a bad content. Thus, condition i. suggests that it is always convenient to anticipate the access to the content. In case ii., the situation is dictated by the uptake of pull users, because they increase the viewcount thus reinforcing the believed viewcount pace of a good content against that of a bad content. Finally, in case iii. there is no incentive in accessing the content.

B. Exponential case: fixed time horizon

Let us consider the content dissemination process operated by a content provider using a finite set of potential target users. After the content is posted by the provider directly to users, it will be transmitted to more and more users by using some preferential channels. In this case, we need to model the push dynamics accounting for the size N of the pool of push users, i.e., we assume that the content provider disseminates the content according to Ẋps (t, θ)=λ ps (θ)(N -X ps (t, θ)), so that

X ps (t, θ)=N (1 -e -λps(θ)t ) for t ≥ 0 (1)
We reported in Fig. 3 the shape of the utility function under the exponential case for a fixed time horizon. As it can be observed in case a), for smaller values of α,i . e ,α =4 0 0a low value of the belief π G causes the access to be delayed till time τ ,w h e r e a sf o ri n c r e a s i n gv a l u e so fπ G we observe first al o c a lm a x i m u ma tα (π g =0 .75), and finally the strategy β =0takes over corresponding to very large values of π G . Indeed, such behavior of the utility function resembles -fora fixed N -w h a tw eo b s e r v e di nt h el i n e a rc a s e .H o w e v e r ,a ta closer look, namely in Fig. 3c) we understand that the situation is more elaborate: in particular, we know that number of push users N impacts the speed at which the viewcount increases. As such, small values of N do not permit to pass the threshold α,w h e r e a sav e r yl a r g eo n eincentivizes early access: recall that β max := β τ,B means access at time t =0 .I nb e t w e e n , the presence of a maximum predicts, as in the linear case, the existence of best responses that lie in the interior of [0,β max ]. This intuitive numerical insight is confirmed by the theoretical results that we detail in the following.

As before, we need to distinguish two cases, namely α<β and β ≤ α,c o n s i d e rt h ed y n a m i c sa n dt h eu t i l i t ye x p e r i e n c e d for users adopting a strategy β above and below the threshold and compare the utility corresponding to the best response β * (α).W eo m i th e r et h ed e t a i l ,t h a tc a nb ef o u n di n[ 1 4 ] .

The resulting cases are summarized in the following theorem Theorem 2: Let λ ps (G) >λ ps (B) and λ ps (G)N ≤ λ pu , then in the exponential case

i) If π G ≤ π B then β τ,B is a symmetric Wardrop equilib- rium ii) If π G >π B then the following cases hold a) If πG πB < λps(G) λps(B) and 1+W (ζ(G)ξ(α,G)) W (ζ(B)ξ(α,B)) ≥ πG πB for all β ∈ [α, β τ,B ] then all 0 <β≤ β τ,B are symmetric Wardrop equilibrium b) If πG πB < λps(G) λps(B) and 1+W (ζ(G)ξ(βτ ,G)) 1+W (ζ(B)ξ(βτ ,B)) ≤ πG πB for all β ∈ [α, β τ,B ] then β τ,B is a symmetric Wardrop equilibrium c) If πG πB < λps(G)
λps(B) and there exists a β is the solution of the following equation

1+W (ζ(G)ξ( β,G)) 1+W (ζ(B)ξ( β,B)) = π G π B then β is a symmetric Wardrop equilibrium iii) If πG πB > λps(G)
β/β max N =5 0 0 0 0 N =1 0 0 0 N =7 0 0 (c) (b) (a)
) if 1+W (ζ(G)ξ(α,G)) 1+W (ζ(B)ξ(α,B)) ≤ πG πB for all β ∈ [α, β τ,B ],
t h e n there exists a symmetric Wardrop equilibrium which is given by

   0 if τπ B <π G t βτ,B (G) β τ,B if τπ B >π G t βτ,B (G) β * ∈{0,β τ,B } if τπ B = π G t βτ,B (G) (2)
Thm. 2 displays a structure of the best response that is similar to the result obtained for the linear case, but we should highlight some differences. First, the additional request λ ps (G)N ≤ λ pu is excluding the case when the effect of the pull mechanism is negligible compared to push mechanism. This means that we are restricting to the case when the aggregated maximum rate at which the viewcount can increase due to the push mechanism is smaller than the increase that is generated once the viewcount is above threshold for pull users. Indeed, this is the interesting case when the content provider's aim is to attract a large basin of pull users using a target limited audience of push users.

Second, we observe that the term π θ λps(θ)+λpu that was present in the linear case is now replaced by a term involving the Lambert function W (•) [START_REF] Corless | On the Lambert W Function[END_REF]: this is due to the combined effect of the exponential growth and the linear growth above the threshold, accounting for the saturation of the basin of push users. In the case when N is very large or λ ps is very small, the term collapses to the condition expressed in the linear case. The existence of symmetric Wardrop equilibria was deduced for all cases when α = β * (α).

IV. USERS WITH SIDE INFORMATION

In general, contents that are present online since a long time display different popularity than contents which last only as h o r tt i m e [START_REF] Szabo | Predicting the Popularity ofO n l i n e Content[END_REF] .A sw en o t i c e di nt h ep r e v i o u ss e c t i o n s , when popularity saturation occurs, Ẋ vanishes for large t. If users choose among contents with different trend and different viewcount, they would naturally choose a content with large viewcount and large increasing trend. To this respect y(t)= Ẋ(t)X(t) encodes the condition when the pull user still values the viewcount, but, she favors a large increasing trend given two contents with the same viewcount. Symmetric equilibria can be determined when in the system all users adopt a strategy α := y(t α ), 0 ≤ t α ≤ τ and again we determine the best response for a user deviating using β := y(t β ) as a reply, where 0 ≤ t β ≤ τ .

It is easy to see that in the linear case, the model developed in the previous section applies as long as one replaces the dynamics with the one below

X ps (t, θ)=λ 2 ps (θ)t + λ ps (θ),X pu = λ 2 pu (t -t α ) • (t -t α )
so that all the results can be specialized accordingly replacing λ ps and λ pu with λ 2 ps and λ 2 pu wherever they appear. The intuition is that when the regime of content diffusion is linear, i.e., when a large number of push users exists, the trend of popularity has the only effect to reinforce the inequality λ ps (B) = λ ps (G).W et h e nm o v et oam o r ei n t e r e s t i n gc a s e .

We are interested in the effect that information available to the viewers has onto the equilibria. In particular, potential viewers may be provided additional information on the upcoming popularity of a certain content, e.g., relying on some predictors or some apriori information they have. They judge whether to access or not a given content based on the product of the popularity X and the popularity trend Ẋ.But,theyonly know how such metric is going to accumulate over time, i.e., the metric for a user that approaches the content at time t is

y(t)= τ t X(u) Ẋ(u)du = 1 2 (X 2 (τ ) -X 2 (t))
This metric can be used as a simple benchmark case: it contains information on the future dynamics of X(θ),a n di t is defined by the current and the final values of the viewcount. However, the amount of such information is not sufficient at time t to state the type of the content in general. Of course, more sophisticated metrics are possible. Nevertheless, theone at hand will do for the purpose of showing that by making the potential viewers of a content aware of some side information, the system may experience a deep change in the structure of the equilibria. Let all users adopt strategy α := y(t α ), 0 ≤ t α ≤ τ and in the same way as done before we want to determine the best response for a user adopting β := y(t β ) as a reply, where 0 ≤ t β ≤ τ ;a sd o n eb e f o r e ,i ti ss u f fi c i e n tt oc o n s i d e r β ∈ [0,β τ,B ],w h e r eβ τ,B := 1 2 X(τ, B) In the case β ≥ α,w er e c a l lt h a tt h ed y n a m i c si s

X(t, θ)=α + λ(θ)(t -t α )
where λ(θ) := (λ pu + λ ps (θ)) for the sake of notation, so that

α + λ(θ)(t β -t α )= X 2 (τ, θ) -2β which solves for t β = 1 λ(θ) α λ pu λ ps (θ) + X 2 (τ, θ) -2β .
The corresponding expression for the utility is

U (α, β)= U 0 (α, β) - π G X 2 (τ, G) -2β λ(G) - π B (X 2 (τ, B) -2β) λ(B)
where the term

U 0 (α, β)=(π G -π B )τ -αλ pu πG λps(G)λ(G) - πB λps(B)λ(B) .
B yd e r i v i n gt h ec a l c u l a t i o nf o rt h et w oc a s e s , best responses turn out to depend on two real parameters (see [START_REF] Altman | Emergence of equilibria from individual strategies in online content diffusion[END_REF] for a detailed derivation): is the set of symmetric Wardrop equilibria for the system.

β1 = 1 2 -X 2 (τ, G) π B λ(B) 2 + X 2 (τ, B) π G λ(G) 2 π G λ(G) 2 -π B λ(B) 2 β2 = 1 2 -X 2 (τ, G) π B λps(B) 2 + X 2 (τ, B) π G λps(G)
ii. If λ pu <λ s pu then W s ⊆{0,β τ,B }. The result in Thm. 3 let us observe a neat phase transition effect on λ pu :w h e nt h ei n t e n s i t yo ft h ev i e w sd u et ot h ep u l l mechanism is below threshold λ s pu ,o n l ye x t r e m a lW a r d r o p equilibria are possible. Above that threshold, there can exist ac o n t i n u u mo fe q u i l i b r i aw h e r et h es y s t e mc a ns e t t l e .L e t µ(•) denote the standard real measure: a sufficient condition is provided in the following Corollary 1: µ(W s ) > 0 if λ pu >λ s pu and β 2 ≥ 0 >β 1 . We can observe that π G <π B implies β 2 ≥ 0 and λ pu > 0 > λ s pu ,s ot h a tas t r o n g e rs u f fi c i e n tc o n d i t i o nt h a nt h eo n ej u s t provided in turn becomes: π G <π B and β 1 ≤ β τ,B .

V. C ONCLUSIONS

In this paper we characterized the access to online contents by game theoretical means by leveraging on the concept of Wardrop equilibrium. We deduced the structure of equilibria in systems where users adopt threshold type policies to select online contents. The analysis presented here can cover several cases: the case when the plain viewcount is the metric, or the viewcount trend, or both are combined as a product metric (see [START_REF] Altman | Emergence of equilibria from individual strategies in online content diffusion[END_REF] for the full derivation). Finally, we explored the impact of side information available to content viewers.

In all such cases we deduced the presence of a continuum of equilibria, which has potential implications in the design and control of platforms for online content access. In future work, in particular, we are exploring the dynamics associated to such sets of interior restpoints, when they exist, and comparing those with typical dynamics of online contents. However, not only equilibria are relevant: as showed in [START_REF] Granovetter | Threshold models of interpersonal effects in consumer demand[END_REF], threshold strategies, under specific conditions, may well lead the system to be asymptotically unstable; system trajectories may in turn consist of cycles that can move into a chaotic dynamics, essentially indistinguishable from random noise.

Fig. 1 :

 1 Fig.1: Dynamics of the viewcount for three sample videos: the push dynamics can be identified with the first part of the dynamics, where labels identify some actions that are significant for the diffusion of the video; observe for cases a, b and c how a linear dynamics takes over in the last part of the dynamics.

Theorem 1 :

 1 i. If πG λps(G) ≥ πB λps(B) ,then0 is a symmetric Wardrop equilibrium ii. If πG λps(G) ≤ πB λps(B) but πG λps(G)+λpu ≥ πB λps(B)+λpu ,then all 0 ≤ β ≤ β τ,B are symmetric Wardrop equilibria iii. If πG λps(G) ≤ πB λps(B) but πG λps(G)+λpu < πB λps(B)+λpu , then β τ,B is a symmetric Wardrop equilibria It is possible to interpret the above result as follows: πG λps(G)

  λps(B) ,t h e nt h ef o l l o w i n gc a s e sh o l d a) if 1+W (ζ(G)ξ(α,G)) 1+W (ζ(B)ξ(α,B)) ≥ πG πB for all β ∈ [α, β τ,B ] then 0 is a symmetric Wardrop equilibrium : λ pu =1.5 N λ ps (G) β/β max U(α,β) πG =0 , 0.25, 0.5, 0.75: λ pu =1.5 N λ ps (G) β/β max πG =0 , 0.25, 0.5, 0.75: λ pu =1.5 N λ ps (G)

Fig. 3 :

 3 Fig. 3: The utility function for N =1000,forτ =10days, λps(G)=10 -1 views/day, λps(B)=λps(G)/10.a)α =400views, b) α =700 views. Increasing values of the belief πG determine different shapes for the utility function. c) Increasing values of N =700, 1000, 50000 for α =700.A l lg r a p h sf o rλpu =1.5Nλps(G).

  b

2 Finally

 2 , the above combines into the characterization of symmetric equilibria as it follows:Theorem 3: Denote thresholdλ s pu = π B π Gπ B (λ ps (G)λ ps (B))λ ps (B) i. If λ pu >λ s pu ,t h e n W s =[β 1 ,β 2 ] ∩ [0,β τ,B ]

This may come, e.g., from the name of user who posted the content.

At r a d i t i o n a la p p l i c a t i o no fW a r d r o pe q u i l i b r i ai sr o a dt r a ffic, where users tend to settle to routes minimizing their delay: the effect ofar o u t ec h a n g e of an individual driver belonging to a flow is negligible system-wide to the utilities of other users.


Richard Combes

Zwi Altman

Eitan Altman

Interference coordination in wireless networks: a flow-level perspective

Keywords: Wireless Networks, Queuing Theory, Traffic Engineering, Self-Organizing Networks, Stochastic Approximation, Stability, OFDMA, Load Balancing, Self configuration, Self Optimization

In dense wireless networks, inter-cell interference highly limits the capacity and quality of service perceived by users. Previous work has shown that approaches based on frequency reuse provide important capacity gains. We model a wireless network with Inter-Cell Interference Coordination (ICIC) at the flow level where users arrive and depart dynamically, in order to optimize quality of service indicators perceivable by users such as file transfer time for elastic traffic. We propose an algorithm to tune the parameters of ICIC schemes automatically based on measurements. The convergence of the algorithm to a local optimum is proven, and a heuristic to improve its convergence speed is given. Numerical experiments show that the distance between local optima and the global optimum is very small, and that the algorithm is fast enough to track changes in traffic on the time scale of hours. The proposed algorithm can be implemented in a distributed way with very small signaling load.

I. INTRODUCTION

As wireless networks become increasingly dense to accommodate the rising traffic demand, inter-cell interference becomes one of the limiting factor as far as performance is concerned. Interference can be managed at various layers and time-scales. At the physical layer, two promising approaches are multi-user detection ( [START_REF] Verdu | Multiuser Detection[END_REF]) and multi-antenna techniques such as beam-forming and network Multiple Input Multiple Output (MIMO). At the MAC layer, inter-cell scheduling is believed to provide large capacity gains ( [START_REF] Bonald | Inter-cell scheduling in wireless data networks[END_REF]). On a slower time scale, which we consider in this article, approaches based on frequency reuse other than reuse 1 can provide significant performance improvements ( [START_REF] Bonald | Capacity gains of some frequency reuse schemes in OFDMA networks[END_REF]). Soft reuse and fractional reuse are two such approaches.

In this article we propose self-optimizing algorithms to automatically tune the parameters of frequency reuse schemes based on measurements. The self-optimization allows to configure the network and adapt it to daily traffic patterns automatically. The proposed algorithms fall within the scope of Self-organizing networks (SON) ( [START_REF] Gpp | Evolved Universal Terrestrial Radio Access Network (E-UTRAN); Self-configuring and self-optimizing network (SON) use cases and solutions[END_REF]). The SON technology is expected to enable complex and costly network management tasks such as node deployment and configuration, parameter optimization and troubleshooting to be performed automatically.

Previous work on self-organizing ICIC in wireless networks ( [START_REF] Stolyar | Self-organizing dynamic fractional frequency reuse for best-effort traffic through distributed inter-cell coordination[END_REF], [START_REF] Combes | Self-optimizing strategies for interference coordination in OFDMA networks[END_REF]) does not take into account flow-level dynamics i.e users arrival and departures explicitly and adopts a static approach. Namely, it is assumed that the number of active users and their position remain constant for a sufficient amount of time, so that the transmit powers of the Base Stations (BSs) can be adjusted to maximize a utility function of the users throughput. The flow level performance is then assessed through simulation.

For N active users in the network, define D n as the throughput of the n-th user. A popular approach for ICIC is to adjust transmit powers to maximize the α-fair utility ( [START_REF] Mo | Fair end-to-end window based congestion control[END_REF]):

1≤n≤N D 1-α n -1 1 -α . (1)
There is a strong interaction between the chosen rate allocation (the value of α) and the congestion process, i.e the stochastic process describing the number and location of active users as a function of time. In the context of wired networks, [START_REF] Bonald | Impact of fairness on internet performance[END_REF] investigates the topic and suggests that α = 2 is appropriate for elastic traffic. Numerical studies in [START_REF] Combes | Self-optimizing strategies for interference coordination in OFDMA networks[END_REF] confirm that α = 2 is adequate for ICIC in wireless networks with elastic traffic. The problem with this utility-based approach is that the optimal value of α is not known a priori, making the design complex.

Our contribution : Our contribution is to propose a new approach: we model the system at the flow level taking into account users arrivals and departures, and optimize directly functions of the loads of stations. All flow-level performance indicators such as blocking rate and file transfer time can be expressed as function of the loads, so this approach allows to prove mathematically the convergence of the proposed mechanism to a configuration which is optimal at the flow level. This flow level approach to SON was used in [START_REF] Combes | Self-organization in wireless networks: A flow-level perspective[END_REF] to adjust cell sizes automatically based on network measurements.

We propose an algorithm to tune the parameters of ICIC schemes automatically based on measurements. The conver-gence of the algorithm to a local optimum is proven, and a heuristic to improve its convergence speed is given. Numerical experiments show that the distance between local optima and the global optimum is very small, and also that the algorithm is fast enough to track changes in traffic on the time scale of hours. The proposed algorithm can be implemented in a distributed way with very small signaling load.

The remainder of the paper is organized as follows: in section II we state the traffic model and the calculation of the network flow-level performance. In section III we expose the three main ICIC schemes that have received attention in the literature, and explain how to calculate user data rates with each of them. In section IV we present a general algorithm to tune the parameters of the ICIC schemes, we prove its convergence and demonstrate that it can be implemented in a distributed way with very little signaling load. In section V we illustrate the performance of the proposed scheme numerically. Section VI concludes the paper.

II. MODEL FOR ELASTIC TRAFFIC

We write A ⊂ R 2 the network area. There are N s BSs, and we define A s the area covered by BS s. Users arrive in the network according to a Poisson process on A × R of measure λ(dr × dt) = λ(dr) × dt. Namely the mean number of users who arrive in the network during time

[t 1 , t 2 ) in any (Borel) region A ′ ⊂ A is equal to (t 2 -t 1 )λ(A ′ ).
The data rate of a user located at r ∈ A who is attached to BS s and is the only user served by s is denoted by R s (r). Elastic traffic is appropriate for modeling File Transfer Protocol (FTP)-like services. Users want to download a file of size σ, with E [σ] < +∞ and E σ 2 < +∞. Round-Robin scheduling is used: when BS s has n s active users, the throughput of a user located at r is Rs(r) ns . Each station can be modeled by a M/G/1/PS(Processor sharing) queue ( [START_REF] Bonald | Wireless downlink data channels: user performance and cell dimensioning[END_REF]). The load of BS s is:

ρ s = E [σ] As λ(dr) R s (r) , (2)
and BS s is stable if ρ s < 1 i.e the distribution of the number of active users tends to a finite stationary distribution. The average number of active users in s in stationary state is:

E [n s ] = ρ s 1 -ρ s (3)
Using Little's law ( [START_REF] Little | A Proof for the Queuing Formula: L= λ W[END_REF]), the mean file transfer time in the network is given by the expected number of active users divided by the arrival rate:

E [F ] = 1 λ(A) Ns s=1 ρ s 1 -ρ s . (4)
With admission control the blocking rate is:

B s = ρ Nmax s Nmax i=1 ρ i s (5)
with N max -the maximal allowed number of active users in a BS.

III. INTERFERENCE COORDINATION SCHEMES

In order to perform ICIC, we must show the link between the powers transmitted by BSs and the data rates R s (r). The data rate calculation is done for several ICIC schemes that have received attention in the literature.

While this article is written with Orthogonal Frequency-Division Multiple Access (OFDMA) networks in mind, the results hold for any access scheme where the radio resources can be divided in a set of parallel orthogonal channels. The term "resources" stands for: time-frequency blocks for OFDMA, codes for Code Division Multiple Access (CDMA) (when inter-code interference can be ignored), and time slots for Time Division Multiple Access (TDMA). We denote by N r the number of resources, h s (r) -the signal attenuation comprising path loss and shadowing between BS s and location r, and φthe mapping between Signal to Interference plus Noise Ratio (SINR) and data rate on a resource, for an Additive White Gaussian Noise (AWGN) channel. In subsequent sections, we will choose φ as:

φ(S) = bW log 2 (1 + S a ), (6)
with W being the bandwidth for a resource, and a ≥ 1, b ≤ 1 two constants. For a = 1 and b = 1, (6) is simply the Shannon formula. a represents the loss of efficiency due to practical (finite length) coding schemes, and b the proportion of effectively usable bandwidth, since part of the bandwidth is used for signaling in practical systems. A very good fit between ( 6) and link-level simulations was shown by [START_REF] Mogensen | Lte capacity compared to the shannon bound[END_REF], and suggested that a = 1.25 and b = 0.75 were the correct values for Long Term Evolution (LTE) systems. We define Z s (r) the amplitude of the channel fading between BS s and location r on a resource, with E [Z s (r)] = 1. We assume independence of the fading processes on different resources. We further assume independence of the fading across BSs, i.e Z s (r) ⊥ ⊥ Z s ′ (r), s = s ′ . The coherence time of the channel is much smaller than the time scale on which users arrive and depart, so that the throughput of a user in a given user configuration can be considered equal to the expected data rate, when expectation is taken on the fading.

A. Fractional load 1) Data rate calculation:

The first scheme is denoted Fractional Load (FL), as introduced in [START_REF] Pokhariyal | Frequency domain packet scheduling under fractional load for the utran lte downlink[END_REF]. Instead of using all available resources, BS s uses each resource with probability 0 < p s ≤ 1. This enables reducing inter-cell interference since the average interference caused by BS s to its neighbours is proportional to p s . This scheme is completely decentralized, since each BS chooses the resources used for transmission independently of the decision taken by other BSs. If a BS uses a resource, it transmits at a fixed power P max . We define a random variable U s ∈ {0, 1}, with P [U s = 1] = p s , and U s ⊥ ⊥ U s ′ , s = s ′ , since BSs take their decisions independently. Let S s (r) denote the SINR between BS s and location r on a resource, when it is used:

S s (r) = P max h s (r)Z s (r) N 2 0 + s ′ =s P max h s ′ (r)U ′ s Z s ′ (r) , (7)
with N 2 0 the thermal noise power on a resource. The total data rate is proportional to the number of used resources:

R s (r) = N r E [U s φ(S s (r)] = N r p s E [φ(S s (r))] (8)
The expression in ( 8) can be calculated by BS s since:

• P max is known • Channel attenuations h s (r)
, ∀s, the distribution of the channel fading Z s (r), ∀s and the resource utilization p s , ∀s can be known through measurements done by the users. 2) Simplified calculation: Although the data rate in (8) can be calculated, it involves a fairly large amount of signaling between users and the BSs, in particular to know the channel statistics Z s (r), ∀s. In practical scenarios, the calculation can be made much simpler as long as we can assume that there are a large number of interfering BSs. In this case we can calculate the data rate (8) replacing the interference by the mean interference. [START_REF] Combes | Scheduling gain for frequencyselective rayleigh-fading channels with application to self-organizing packet scheduling[END_REF] shows that for hexagonal networks in a urban environment, the approximation is very accurate.

We write I s (r) the mean interference at location r when served by station s:

I s (r) = P max s ′ =s p s ′ h s ′ (r) (9)
Using Jensen's inequality we obtain a lower bound for the data rate:

R s (r) ≥ N r p s E φ( P max h s (r)Z s (r) N 2 0 + I s (r) ) , (10)
which is considerably simpler to calculate than (8) since it does not involve the distribution of the fading of interfering signals Z s ′ (r), s ′ = s.

B. Fractional frequency reuse

1) Data rate calculation: Another scheme is Fractional Frequency Reuse (FFR), which is based on frequency planning and is considered in [START_REF] Stolyar | Self-organizing dynamic fractional frequency reuse for best-effort traffic through distributed inter-cell coordination[END_REF] as a basis for self-organizing ICIC. Resources are divided into N b sub-bands of equal size. The BSs use all the resources, but they do not transmit the same power on all sub-bands. Namely, if a BS transmits at strong power on a given sub-band, then its neighbors should transmit at smaller power in order to avoid creating too much inter-cell interference. Reuse patterns appear in the network, which enables mitigating the inter-cell interference. Each user receives each resource of each sub-band an equal amount of time, i.e Round-Robin scheduling applies.

Let P s,b denote the power transmitted by BS s on a resource of sub-band b and S s,b (r) -SINR at location r, on a resource of sub-band b when served by BS s:

S s,b (r) = P s,b h s (r)Z s (r) N 2 0 + s ′ =s P s ′ ,b h s ′ (r)Z s ′ (r) (11)
The data rate is:

R s (r) = N r N b 1≤b≤N b E [φ(S s,b (r))] . (12)
2) Simplified calculation: As said in III-A2, the data rate calculation in ( 12) can be simplified. The mean interference at r when served by BS s on a resource of sub-band b is:

I s,b (r) = s ′ =s P s ′ ,b h s ′ (r). (13)
The simplified expression for the data rate is:

R s (r) ≥ N r N b 1≤b≤N b E φ( P s,b h s (r)Z s (r) N 2 0 + I s,b (r)
) .

C. Soft frequency reuse 1) Data rate calculation: The last scheme considered is called Soft Frequency Reuse (SFR), and performance studies in [START_REF] Bonald | Capacity gains of some frequency reuse schemes in OFDMA networks[END_REF] show that it enables a significant increase in capacity in dense networks. Region A s served by BS s is divided into two regions denoted "center" and "edge" A s,c and A s,e , based on a path-loss threshold, i.e users far from the BS are called edge users and the other are called center users. [START_REF] Bonald | Capacity gains of some frequency reuse schemes in OFDMA networks[END_REF] further shows that it is optimal to choose the path-loss threshold as the median path-loss in the cell. Resources are divided in 3 sub-bands of equal size. One sub-band is used to serve edge users on which BS s transmits at maximal power P max , and two sub-bands are used for center users on which it transmits at low power P max κ s . Typical values for κ s are around -10dB ( [START_REF] Bonald | Capacity gains of some frequency reuse schemes in OFDMA networks[END_REF]). We define B s,e the sub-band used by BS s to serve edge users, and B s,c the set of two sub-bands used by BS s to serve center users. Using the same notations as for FFR, we have that P s,b = P max if b ∈ B s,e and P s,b = P max κ s if b ∈ B s,c . The SINR S s,b (r) is calculated as for FFR by [START_REF] Little | A Proof for the Queuing Formula: L= λ W[END_REF].

The data rate for edge users R s,e (r) is:

R s,e (r) = N r N b b∈Bs,e E [φ(S s,b (r))] , (15)
and the data rate for center users R s,c (r) is:

R s,c (r) = N r N b b∈Bs,c E [φ(S s,b (r))] . (16)
The previous remark III-A2 on the simplified data rate calculation remains valid.

2) Queuing model: Each station can be modeled as 2 parallel M/G/1/PS queues ( [START_REF] Bonald | Capacity gains of some frequency reuse schemes in OFDMA networks[END_REF]) with loads:

ρ s,e = E [σ]
As,e λ(dr) R s,e (r) ,

ρ s,c = E [σ] As,c λ(dr) R s,c (r) . ( (17)
) 18
As previously, the mean number of active users in BS s is:

E [n s ] = ρ s,e 1 -ρ s,e + ρ s,c 1 -ρ s,c . (19)

IV. SELF-ORGANIZING INTERFERENCE COORDINATION

In order to compute ρ s , we need to know the data rates at every point of the cell R s (r) and the arrival intensity λ(dr). To compute the data rate R s (r), using the calculations of Section III, we need to know the signal attenuations from all the BSs h s (r) , 1 ≤ s ≤ N s . In practice, this information is not available. In this section, we show that the loads can be estimated by observing users arrivals and file sizes. This allows to optimize a function of the loads in an "online" fashion: the characteristics of the arrival process are not known and the system is optimized based on successive observations. The observations are by nature noisy, and we will show that an optimum can still be found using stochastic approximation theorems.

A. Load estimation

We denote by {T n , r n , σ n } n∈Z the marked point process of users arrivals, locations and file sizes. Namely T n is the instant at which the n-th user arrives, r n his location of arrival, and σ n its file size. Time is divided in time slots of size T , and the k-th time slot is [kT, (k + 1)T ). We assume that T is larger than a typical flow duration. We define ρ s [k] the load estimate for BS s during the k-th time slot:

ρ s [k] = 1 T n∈Z σ n R s (r n ) 1 [kT,(k+1)T ) (T n ). (20)
We further need to calculate the derivatives of the loads for our optimization algorithm. For the calculations not to depend on the considered ICIC scheme, we denote by θ the parameters of interest. Namely, θ stands for {p s } 1≤s≤Ns for FL, {P s,b } 1≤s≤Ns,1≤b≤N b for FFR and {κ s } 1≤s≤Ns for SFR. We define ∇ θ ρ s [k] the gradient with respect to θ of the load estimate for BS s during the k-th time slot:

∇ θ ρ s [k] = - 1 T n∈Z σ n ∇ θ R s (r n ) R s (r n ) 2 1 [kT,(k+1)T ) (T n ). (21)
The formulas for calculating ∇ θ R s (r) are given in Appendix A. Loads and their derivatives are estimated without bias, as stated by theorem 1. Furthermore, the standard deviation of those estimates is proportional to

1 √ T . Theorem 1. (i) E [ρ s [k]] = ρ s (θ[k]) , (ii) E [∇ θ ρ s [k]] = ∇ θ ρ s (θ[k]), (iii) varρ s [k] and var∇ θ ρ s [k]
are both finite and proportional to 1 T . Proof: see appendix B It is noted from the expressions of the data rates that ∇ θ ρ s [k] can be computed by BS s provided that it knows θ, the derivative of φ, the value of the path-loss at the locations of arrivals of users that arrived during the k-th time slot, and the fading distributions. Once again, from the remark in III-A2, when the number of interfering BSs is large, the interference can be replaced by the mean interference. Then only the distribution of the fading between the serving BS and the users is needed, and the computation is simpler.

B. Load optimization 1) Optimization objective:

We write ρ = (ρ 1 , • • • , ρ Ns ) the load vector. The objective is to minimize a given function of the loads U (ρ). A case of particular interest is to minimize the average file transfer time, and according to (4), this can be done by choosing

U (ρ) = Ns s=1 ρ s 1 -ρ s , (22)
where we have ignored the total arrival rate λ(A) since it does not depend on θ.

For our proof we will assume that U is differentiable with bounded derivatives. For the file transfer time, we will either assume that the loads are bounded away from 1, or we will replace f (ρ s ) = ρs 1-ρs by a smooth function g such that f = g on [0, 1-d) and g is linear on (1-d, +∞), with d an arbitrarily small constant. Another case of interest is when we try to minimize the load of the most loaded station, i.e U ≡ max. In this case we can use the smooth approximation:

U (ρ) = 1 τ log( Ns s=1 exp(τ ρ s )), (23)
with τ a smoothing parameter.

2) Constraint sets: For each ICIC scheme, parameter θ is constrained to a compact convex set P. For FL the constraint set is:

{p|p min ≤ p s ≤ 1}, (24)
where p min > 0 since ρ s → ps→0 + +∞. For FFR the constraint set is:

{P|P min ≤ 1≤b≤N b p s,b ≤ P max , 1 ≤ s ≤ N s }, (25)
with P max the maximal allowed total transmit power of a BS and P min > 0 since ρ s → b P s,b →0 + +∞. For SFR the constraint set is:

{κ|κ min ≤ κ s ≤ 1}, (26)
with κ min > 0 since ρ s,c → κs→0 + +∞. We define a constraint set for the loads C = [0, ρ max ] Ns for FFR and FL, and C = [0, ρ max ] 2Ns for SFR. We define π P [.] and π C [.] the projection on P and C respectively. We denote by ∂U ∂s the partial derivative of U with respect to its s-th parameter.

3) Algorithm: We define the filtered loads C[k] for the k-th time slot:

C[k + 1] = π C [(1 -δ)C[k] + δρ[k]], (27)
with 0 < δ a filtering parameter. We define the update vector for the k-th time slot:

Y [k] = 1≤s≤Ns ∇ θ ρ s [k] ∂U ∂s (C[k]). (28)
θ is updated at each time slot and projected back on the constraint set P:

θ[k + 1] = π P [θ[k] -ǫY [k]]. (29)
with ǫ > 0 a small step size. Theorem 2 demonstrates that when ǫ, δ → 0 with ǫ δ → 0, the sequence {θ[k]} k∈N converges in distribution to U, the set of local minima of U on the constraint set P. The proof is based on stochastic approximation. The performance gap between local optima and the global optimum will be discussed in Section V, and we will show that it is small. Theorem 2. For ρ max large enough, {θ[k]} k∈N converges in distribution to U when ǫ → 0, δ → 0 and ǫ δ → 0. Namely, for all β > 0:

lim sup k P [d U (θ[k]) > β] → ǫ,δ, ǫ δ →0 0, ( 30
)
with d U (θ) = inf u∈U θ -u the distance to set U.
Proof: See appendix C

C. Numerical considerations

While the algorithm (29) can be proven mathematically to converge to a local minimum, its performance can further be improved due to the specificity of the problem considered here. After extensive numerical experiments, we suggest a modification of (29) which makes it much more efficient in practice, especially when traffic is not stationary and the algorithm must be fast enough to "track" the traffic variations. The efficiency will be illustrated numerically in Section V.

When P s,b is small, ∂U ∂P s,b has a large absolute value and its sign varies quickly which forces us to use a small value of ǫ to avoid instability. However when P s,b is large, | ∂U ∂P s,b | is close to 0, which causes the algorithm to "get stuck" in regions where P s,b is large for a long time, unless ǫ is large. Hence we suggest to work with powers on a logarithmic scale (in dB) so that the steps at low power will be smaller than the steps taken at high power. Furthermore, instead of taking steps proportional ∇ θ U , we take steps of constant size. Our modified algorithm can be written:

θ[k + 1] = π P [exp (log(θ[k]) -ǫ sign(Y [k]))]. ( 31
)
where sign(x) is a vector whose components are the signs of the components of x, and sign(0) = 0. This modification enables very good tracking performance.

D. Distributed implementation and signaling load

Since our algorithm runs in real-time, we must show that it can be implemented in a distributed way, where each BS controls its own parameters, with a small signaling load. Namely, we write θ s the components of θ which are parameters of BS s. That is: θ s = p s for FFR, θ s = {P s,b } 1≤b≤N b for FFR and θ s = κ s for SFR. Assume that U is additive and can be written:

U (ρ) = Ns s=1 u(ρ s ), (32)
with u a scalar function. We define N s the set of neigbours of BS s, such that ∂ρ s ∂θ s ′ = 0 if s ′ / ∈ N s . This means that, in order to be able to calculate the gradient ∂U ∂θs , BS s only needs to know the derivative of the loads of its neigbours. Hence at each time slot, each neighbor of BS s, BS s ′ ∈ N s will communicate to BS s the value of ∇ s u(ρ s ′ ), and in this way the algorithm can be implemented in a distributed way, with the only assumption that there exists an interface between neighboring BSs. Such an interface exists in LTE (X2 interface).

The amount of signaling (exchanged every T seconds) per base station is proportional to the number of components of θ s multiplied by the number of neighbours. In practical cases, we will have 3 components for FFR, and 1 for FL and SFR, T = 60s and 6 neighbours (hexagonal network). Assuming that floating numbers are coded on 32 bits, the signaling per BS will be of 3×32×6 60 = 9.6 bits/s which is indeed very small for current networks. It is also noted that since information is exchanged every 60s or so, the interface delay will not be problematic, since the typical delay value for the X2 interface is 50ms.

V. NUMERICAL EXPERIMENTS

In this section we illustrate the performance of the proposed schemes numerically. We show two main features of our method: the algorithm is fast enough to track the changing traffic on the time scale of hours and that although the algorithm is proven to converge to a local optimum, the distance to the global optimum is small.

A. Simulation setting

We perform simulations for a hexagonal network with 12 BSs. In order to avoid introducing border effects, we use a wrap-around, which is equivalent to placing the stations on a torus. The measurement interval length is T = 60s. T should be reasonably larger than flow durations (a few seconds) in order to avoid sudden changes of the data rate for active flows. In our simulation, we assume that the arrival rate varies slowly. We want to show that the proposed algorithm is able to adapt to the changing traffic distribution. This is essential in practical settings since traffic intensity and distribution changes on the time scale of hours or so. For our numerical experiments we choose the traffic variation to be sinusoidal:

λ(dr × dt) = (λ 1 + λ 2 1 A1 (r) sin( 2πt 4 ))dr × dt, (33)
with t in hours. The arrival rate is the sum of a uniform traffic which does not vary with time, and a traffic in BS 1 which varies sinusoidally. Namely, there is a "hot spot" in BS 1 which appears and disappears periodically. We will compare the performance of the proposed algorithm to a reference scenario (denoted as "no SON") in which all BSs transmit at full power on all resources. Other simulation parameters are given in Table I.

B. Results

On Figure 1, we plot the file transfer time in the network as a function of time for different ICIC schemes. During high traffic periods, the network becomes critically overloaded, which results in a high file transfer time. All ICIC schemes bring some improvement and are indeed able to adapt to the changing traffic. The FFR scheme performs the best and greatly reduces the file transfer time, followed by the SFR and the FL comes in last.

For FFR, the transmitted powers by BS 1 and 2 as a function of time are represented on figures 2 and 3 respectively. BS 1 and BS 2 are neighbors. We first notice that BS 1 transmits most of its power on band 2, while BS 2 transmits most of its power on band 3. Since BSs are neighbors, they should indeed avoid transmitting at strong power on the same band, and this shows that the algorithm creates reuse patterns in the network in a autonomous, self-organizing manner. We also notice that during high traffic periods BS 1 increases its transmitted powers noticeably on bands 1 and 3 in order to serve its users faster and avoid congestion.

For FL, the proportion of used resources by BS 1 and 2 as a function of time is represented on figure 4. During the periods of low traffic, both BSs use their resources fully, while during the high traffic periods, BS 2 uses 80% of its resources in order to create less interference to BS 1 which is overloaded.

For SFR, the edge/center power ratio for BSs 1 and 2 as a function of time is represented on figure 5. At low traffic, both BSs use the same power ratio, and at high traffic, BS 1 transmits at stronger power to serve its users faster, while BS 2 transmits at a weaker power in order to create less interference to BS 1 and help reducing its congestion.

On figure 6, we compare the distance between the global optimum and the local minima found by the proposed algorithm. For each ICIC scheme, we first derive the global optimum of U through a global search heuristic (particle swarm was used here). Then we run the proposed algorithm for 1 hour (i.e 60 iterations if T = 60s) a hundred times, each time starting from a random point in the constraint set P. We then plot the cumulative distribution function (c.d.f) of the performance over those 100 trials (the first point of the c.d.f being the global optimum). We can see that for the three ICIC schemes, the performance of the proposed algorithm is very close to the global optimum. This is a very interesting result because it indicates that a simple local search achieves good performance without the need to spend possibly an extensive amount of computing power and signaling for a global search. optimum is proven, and a heuristic to improve its convergence speed is given. Numerical experiments show that the distance between local optima and the global optimum is small, and that the algorithm is fast enough to track changes in traffic on the time scale of hours. The proposed algorithm can be implemented in a distributed way with very small signaling load.

APPENDIX A CALCULATION

OF ∇ θ R s (r)
We calculate the derivatives of the data rates with respect to the parameters for the three ICIC schemes. We will always use the so-called simplified formulas since they apply in practical scenarios. We denote by φ ′ the derivative of φ. The most important message is that BS s can always calculate ∇ θ R s (r) as long as it knows:

• Path loss for both useful signal and interfering signals: BS s does not need to know the distribution of the fading of interfering signals Z s ′ (r) , s ′ = s, • φ ′ the derivative of the φ. All those quantities are either assumed to be known (e.g the function φ ′ ) or can be measured and transmitted to BS s by the users it serves.

h s ′ (r) , 1 ≤ s ′ ≤ N s , 0

A. FL

To ease notation we define: S s (r) = P max h s (r)Z s (r) N 0 + I s (r) .

We have that:

∇ ps R s (r) = R s (r) p s , (35)
and for s ′ = s:

∇ p s ′ R s (r) = N r p s E -P max h s ′ (r) S s (r) N 0 + I s (r) φ ′ (S s (r)) .

(36)

B. FFR

To ease notation we define:

We have that:

∇ P s,b R s (r) = N r N b E S s,b P s,b φ ′ (S s,b ) , (38)
and for s ′ = s:

∇ P s ′ ,b R s (r) = N r N b E -h s ′ (r) S s,b (r) N 2 0 + I s,b (r)
φ ′ (S s,b (r)) .

(39)

C. SFR

The formulas for SFR are deduced from the FFR case.

APPENDIX B PROOF OF THEOREM 1 Theorem 3. Consider {T k , r k } k∈Z a Poisson process on R 2 × R with measure λ(dr) × dt, and marks {σ k } k∈Z which are independent and identically distributed (i.i.d) and independent of {r k , T k } k . Consider f : R 2 → R positive and measurable, t 2 > t 1 , and define:

F (t 1 , t 2 ) = k∈Z σ k f (r k )1 [t1,t2) (T k ).
(40)

Then:

E [F (t 1 , t 2 )] = E [σ] (t 2 -t 1 ) R 2 f (r)λ(dr), (41)
and:

varF (t 1 , t 2 ) = E σ 2 (t 2 -t 1 ) R 2 f (r) 2 λ(dr). (42)
Proof: We recall the Campbell formula ( [START_REF] Dalay | An introduction to the theory of point processes[END_REF]):

E k∈Z g(r k , T k ) = R 2 ×R g(r, t)λ(dr)dt, (43)
with g : R 2 × R → R an arbitrary positive measurable function. The first statement is proven by applying the Campbell formula with g(r, t) = f (r)1 [t1,t2) (t).

Applying the Campbell formula at the second order we have that:

E F (t 1 , t 2 ) 2 =E σ 2 (t 2 -t 1 ) R 2 f (r) 2 λ(dr) + (t 2 -t 1 ) R 2 f (r)λ(dr) 2 , (44)
so that:

varF (t 1 , t 2 ) 2 = E σ 2 (t 2 -t 1 ) R 2 f (r) 2 λ(dr), (45)
proving the second result.

APPENDIX C PROOF OF THEOREM 2

We use a two-time scale stochastic approximation argument for proving convergence. The following conditions are true:

has a unique globally asymptotically stable point which is ρ(θ). Once again θ → ρ(θ) is continuous. The mean ODE for the "slow time scale"is:

θ = -∇ θ U (ρ(θ)), (47)
and U the set of local minima of U is a Lyapunov stable attractor for this ODE. Then applying [START_REF] Kushner | Stochastic Approximation and Recursive Algorithms and Applications 2nd edition[END_REF][Theorem 6.1, chap 8, page 287] guarantees that θ[k] converges to U in distribution. Namely:

lim sup k P [d U (θ[k]) > β] → ǫ,δ, ǫ δ →0 0, (48)
for all β > 0 which concludes the proof.

Fig. 1 .Fig. 2 .Fig. 3 .Fig. 4 .

 1234 Fig. 1. File transfer time as a function of time, comparison between ICIC schemes

Fig. 5 .Fig. 6 .

 56 Fig. 5. Edge/center power ratio for BS 1 and 2 as a function of time for SFR

S

  s,b (r) = P s,b h s (r)Z s (r) N 2 0 + I s,b(r).

•

  {Y [k]} k∈N , {ρ[k]} k∈N are both uniformly integrable since they are bounded in mean square • (θ, C) → 1≤s≤Ns ∇ θ ρ s (θ) ∂U ∂s (C) and θ → ρ(θ) are continuous • For a fixed value of θ, the Ordinary Differential Equation (ODE) Ċ = ρ(θ) -C,

This work has been partially carried out in the framework of the FP7 UniverSelf project under EC Grant agreement