Member, IEEE Luca Rose
email: luca.rose@huawei.com

Member, IEEE E Veronica Belmega
email: belmega@ensea.fr

Member, IEEE Walid Saad
email: walids@vt.edu

Senior Member, IEEE Mérouane Debbah
email: merouane.debbah@supelec.fr

Pricing in Heterogeneous Wireless Networks: Hierarchical Games and Dynamics

Keywords: Small cell networks, game theory, Stackelberg game, Nonatomic game, Wardrop equilibrium

In this paper, a novel game-theoretic model of the complex interactions between network service providers (NSPs) and users in heterogeneous small cell networks is investigated. In this game, the NSPs selfishly aim at maximizing their profit while, simultaneously, the users seek to optimize their chosen service's quality-price tradeoff. A Stackelberg formulation in which the NSPs act as leaders and the users as followers, is proposed. The users' interactions are modeled as a general non-atomic game. The existence of a Wardrop equilibrium in the users' game is proven and its expression as a solution of a fixed point equation is provided (irrespective of the number of NSPs, services offered, pricing policies and QoS functions). Moreover, a set of sufficient conditions that ensure the uniqueness of the Wardrop equilibrium is provided. Notably, the uniqueness of the equilibrium for the particular case of congestion games is shown. An algorithm approximating these equilibria is provided and its convergence to an ε-Wardrop equilibrium is proven. The existence of Nash equilibria for the leaders' game is shown and illustrated via numerical simulations.

I. INTRODUCTION

The demand for wireless capacity has significantly increased in the past decade due to the proliferation of bandwidth-intensive applications [START_REF] Index | Global mobile data traffic forecast update[END_REF]. One promising solution towards satisfying the growing demand for higher wireless QoS is given by the deployment of heterogeneous networks (HetNets) [START_REF] Hu | Hetnets-a new paradigm for increasing cellular capacity and coverage[END_REF], [3]. The HetNets paradigm is based on the concept of deploying low-cost, low-power, small cells (SCs) such as femtocells (FCs), picocells, or WiFi access points to boost the performance of existing cellular networks [START_REF] Hoydis | Green small-cell networks[END_REF]- [START_REF] Hasan | Green cellular networks: A survey, some research issues and challenges[END_REF]. HetNets can then be utilized by network service providers (NSPs) that can group them into services to be offered to the users at specific prices. Thus, at the users' level, the variety of available services intrinsically creates a choice dilemma between the incentive of higher QoS and the disincentive of higher price, when chosing a service The individual users' choices with regards to wireless services are based on the tradeoff between the pricing levels, set by the NSPs, and the services' QoS levels that depend on both the wireless infrastructure and the subscribers' distribution over the available services. Given a set of prices, if no user can improve this tradeoff by unilaterally switching its service we say that the users are at the so called Wardrop equilibrium (WE). At the NSPs' end, revenues depend on the distribution of the users at the WE, which, in turn, are determined by the prices and the QoS levels of the offered services. Under these assumptions, NSPs must be able to predict the users' behavior in order to optimize their pricing policies and maximize their revenues.

This issue has already attracted some attention in the literature. In [START_REF] Shetty | Economics of femtocells[END_REF], an optimal pricing scheme is evaluated for a monopolistic market, while in [START_REF] Ren | Data demand dynamics in wireless communications markets[END_REF], the authors also study the dynamics of the users' demand in a monopolistic scenario. An extension to oligopolistic markets is introduced in [START_REF] Ren | User subscription dynamics and revenue maximization in communications markets[END_REF], [START_REF]Entry and spectrum sharing scheme selection in femtocell communications markets[END_REF] in which authors prove the existence and uniqueness of the users' game equilibrium under some assumptions on the offered QoS. These works further assume that the QoS offered by any service in the network depends only on the fraction of users that subscribe to the service. This reduces the users' game to a popular class of games known as congestion games [START_REF] Nisan | Algorithmic Game Theory[END_REF]. Such a QoS model is not always realistic, for example in cases in which single technologies are shared among different services, or in the case in which several services compete for the same spectral resources, as highlighted in [START_REF] Gussen | Pricing and bandwidth allocation problems in wireless multi-tier networks[END_REF]. In [START_REF] Rose | Dynamic service selection games in heterogeneous small cell networks with multiple providers[END_REF], the authors study the general non-atomic game under the assumption of fixed strictly different prices of the services. A non-atomic game is essentially a game with infinitely many players each of which cannot, individually, determine the utility of the others.

In contrast to these works, we propose a hierarchical or Stackelberg [START_REF] Stackelberg | The theory of the market economy[END_REF] game model to study these interactions. In a Stackelberg game, some players, namely the followers, myopically aim at maximizing their utilities while the other players, namely the leaders, can anticipate the outcome of the followers' game. In contrast with vast majority of the literature, a multi leader hierarchical game is here considered. Within the context of the studied service selection problem, we propose a model in which the NSPs assume the role of leaders while the users act as followers. Here, the NSPs are selfish entities that choose an optimal pricing strategy to maximize their revenues. To achieve this goal, the NSPs have to be able to predict the users' reactions to their pricing choice, i.e., the users distribution at the equilibrium. Hence, in this work, we study the complex interactions among the NSPs and the users, aiming at investigating the existence of the Stackelberg equilibrium arising from these interactions. This equilibrium is characterized by a NE for the leaders' game and a WE for the users' game. We show that, in order to evaluate the NE, the NSPs must be allowed to set any pricing policies, and that there always exists at least one Stackelbeg equilibrium.

Given the complexity of the Stackelberg formulation, first, we focus on the interactions of the users and, once their behavior is well understood, we investigate the optimal pricing strategies at the NSPs level. At the users' level, in order to study the WE, we define an appropriate best-response function and we show that the set of its fixed points coincides with the set of equilibria. This best-response function is defined in the case in which the users select one of the services which offer the highest utility, given the current distribution of users. We show that, starting from an arbitrary users' distribution, iterating this best-response may not lead to an equilibrium. Thus, we propose a modified algorithm that is shown to converge to a neighborhood of the WE. Moreover, this improved algorithm allows to more realistically capture the users' behavior.

At the NSPs' level, we assume that the leaders use this algorithm to anticipate the users' behavior, to be able to evaluate their pricing strategies. We analyze the leaders' game and , under the conjecture of continuous NSPs' best-response functions, we prove the existence of at least one equilibrium point, thus, the existence of an equilibrium for the overall hierarchical game.

In conclusion, the main contributions of this work may be summarized as follows: (i) We prove the existence of at least one Wardrop equilibrium (WE) for the general non-atomic users' game; (ii) We define a best-response function to describe the evolution of users' distribution when they select their individual optimal service; (iii) We show that the fixed points of this function correspond to the WE set of the users' game; (iv) We prove that the result of any best-response is characterized by a unique set of thresholds which divide the users having a different set of utility maximizing services; (v) We provide sufficient conditions that ensure the uniqueness of the WE. In particular, we show the uniqueness of the equilibrium when the game takes the form of a congestion game, whereas, to the best of our knowledge, only essential1 uniqueness was proven (for a detailed discussion see [START_REF] Roughgarden | How bad is selfish routing?[END_REF], [START_REF] Milchtaich | Generic uniqueness of equilibrium in large crowding games[END_REF]); (vi) We provide an iterative algorithm that allows the leaders to anticipate the users' choices by approximating the WE; (vii) We study the multi-level interactions between NSPs and users under a condition that implies the existence of at least one pure NE in the leaders' game; (viii) Extensive numerical simulations are used to validate all our theoretical results and to analyze the economical advantages of deploying a new technology.

The rest of the paper is organized as follows. Section II presents the problem formulation, while Section III provides detailed theoretical analysis on the properties of the Stackelberg game under study. In Section IV, we detail the analysis of the NSPs' game, these results are then validated via numerical simulations in Section V and conclusions are drawn in Section VI.

II. SYSTEM MODEL AND GAME FORMULATION

A. Network Model Consider a wireless system in which a continuum of users can choose to connect to a finite set of services that are being offered by a finite number of NSPs denoted by the set K {1, 2, . . . K}. The users are organized into a continuous and infinite number of classes. Each class groups all the users which a certain interest in the QoS. In detail, the users are distributed into the real segment [0, γ] where, γ represents the maximum interest in the QoS. We refer to users with interest γ ∈ [0, γ] as the users of type γ. Here, users having a higher interest in obtaining a higher QoS correspond to higher values of γ. In this model, the users are utility maximizing rational entities distributed on the domain of interest according to a certain distribution function ρ : [0, γ] → R+. We let

Γ(γ) = γ 0 ρ(x)dx denote the cumulative function with Γ(γ) = 1. Each NSP k ∈ K offers M k services within the set M k {1, 2, . . . , M k }.
Here, service 0 and provider 0 denote the absence of service.

Each offered service can be represented by a pair (k, s), with k ∈ K and s ∈ M k . For notational simplicity, we define the largest set of services being offered by the NSPs as Y = 1, . . . , max k M k and then we define a one-to-one mapping Φ : {K × Y ∪ {(0, 0)} → N as:

Φ(k, s) =      0, , if k = 0, s = 0, s + k-1 =1 M , otherwise. (1)
Thus, we use a single letter notation to describe the pair (k, s) via an integer label c = Φ(k, s) that represents a particular service-NSP pair. Thus, c ∈ C {0, 1, . . . , C}, with C = K k=1 M k . We let αc be the fraction of users connecting to service c (the service load) and α = (α0, α1, . . . αC ), α ∈ C , be the network's load profile 2 , or the user distribution.

In order to subscribe to a service c, a user must pay a price pc > 0, and we denote by p = (p0, p1, p2, . . . , pC ) the network pricing vector. Without loss of generality, these prices are assumed to be increasingly ordered, such that c > r implies pc ≥ pr. When selecting a service, a user perceives a QoS equal to gc(α), which is a function of the whole load profile. We denote the network QoS vector by g(α) = (g0, g1, g2, . . . , gC ) (α). Each gc(α) is assumed to be a continuous, differentiable function w.r.t. α and a monotonous nonincreasing function of αc [START_REF] Shetty | Economics of femtocells[END_REF]- [START_REF]Entry and spectrum sharing scheme selection in femtocell communications markets[END_REF], [START_REF] Gussen | Pricing and bandwidth allocation problems in wireless multi-tier networks[END_REF], such that gc(α) ≥ 0, ∀α. Furthermore, since it represents the absence of services, we set p0 = 0 and ∀ α ∈ C , g0(α) = 0.

B. Hierarchical Game Formulation

The users consider the service prices as fixed and select the service which maximizes the tradeoff between the QoS and the price. The NSPs consider that each user is selecting a service that maximizes its tradeoff, and, thus, choose the pricing policies that maximize their revenues. Here, we describe these interactions between NSPs and users via a two level, hierarchical (Stackelberg) game [START_REF] Stackelberg | The theory of the market economy[END_REF]. This framework has two interdependent games. The high-level game, or leaders' game, which is played by the NSPs, and the low-level game, or followers' game, which is played by the users. The NSPs must select the best pricing scheme while anticipating the users' possible reactions. In contrast, the users, ignore the leaders strategies and treat the pricing policies as fixed parameters independent from their choices.

1) Low-level game: The users consider the network price vector p as a fixed parameter, while aiming at choosing a service that maximizes their satisfaction. Since we consider a continuum of users, this competition is modeled as a non-atomic game defined by the tuple GF =

[0, γ], C, {U γ c } c∈C,γ∈[0,γ] .
The players are the nonatomic users ordered in an infinite number of classes over the real segment [0, γ]. The set of services C denotes the action set and

U (γ) c c∈C,γ∈[0,γ]
is the family of utility functions defined as:

U (γ) c (α) = γgc(α) -pc, (2)
where

U (γ)
c (α) is the utility that users of type γ obtain by subscribing to service c, when the load profile is α. We consider gc(α) to be function of the whole load profile α and not only on the service load αc. The latter is generally assumed in the literature [START_REF] Shetty | Economics of femtocells[END_REF]- [START_REF]Entry and spectrum sharing scheme selection in femtocell communications markets[END_REF] (i.e., gc(α) = gc(αc)), which implies a congestion non-atomic game.

One suitable solution for non-atomic game is through the concept of a Wardrop equilibrium (WE), [START_REF] Haurie | On the relationship between Nash-Cournot and wardrop equilibria[END_REF], [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF]. However, unlike classical WE games [START_REF] Smith | The existence, uniqueness and stability of traffic equilibria[END_REF], in our game, we assume users to evaluate each service also based on their type γ, therefore it is not straightforward to apply this equilibrium concept. Thus, we define a new concept of equilibrium used in the general non-atomic game investigated through this paper. We begin by introducing some useful definitions.

Definition 1 (Set of used services (SUS)) For any arbitrary γ ∈ [0, γ], we define the correspondence S (γ) ⊆ C as the set of services chosen by users of type γ. Further, we define the set of used service (SUS) as S γ∈[0,γ] S (γ) .

Here, it is important to note the analogy between users of the same type selecting different strategies in a non atomic game, and the use of mixed strategy in an atomic game [START_REF] Roughgarden | How bad is selfish routing?[END_REF], [START_REF] Schmeidler | Equilibrium points of nonatomic games[END_REF]. However, since all users of each type carry an infinitesimal amount of load, practically, it is more meaningful to study only the cases in which all the users of each type select only one service, i.e., ∀ γ ∈ [0, γ] , |S (γ) | = 1. Next, this is referred to as users of type γ employing a pure strategy, and as a SUS in pure strategies. We remark that, given an arbitrary load profile α ∈ C , in general it is not possible to infer the exact services that are employed by users of an arbitrary type γ ∈ [0, γ]. With this assumption, it is possible to compute the load profile α from the set S by using the service to load function defined next.

Definition 2 (Service to load function) Let S be the set of the correspondences between type of users and selected services. Assume that the users of almost 3 all types employ a pure strategy, that is for almost all γ ∈ [0, γ] we have that |S (γ) | = 1. Then, the fraction of users connecting to a service c ∈ C is given by αc = Rc(S). For each service c, the service to load function Rc : C → [0, 1] is defined as:

Rc(S) γ 0 1 {c∈S (x) } ρ(x)dx, (3)
where 1 {•} is the standard indicator function and ρ(•) is the users density function introduced in Section II. By defining R(S) (R1(S), . . . , RC (S)) it is possible to write α = R(S).

We can now define rigorously the WE in the non-atomic game GF :

Definition 3 (Non atomic game (Wardrop) equilibrium) A load α * ∈ C is a (Wardrop) equilibrium in pure strategies of the game GF , if there exists a set of used services S * = γ∈[0,γ] S * (γ) , such that all the users of almost all type employ a pure strategy, such that α * = R(S * ) and ∀ γ ∈ [0, γ] the following condition is met:

U (γ) c (α * ) ≥ U (γ) c (α * ) , c ∈ S * (γ) and c ∈ S * (γ) .
Here, we used the symbol S * (γ) to denote the particular set of actually used services at the WE. Hereinafter, we denote the set of the WE as W {α * 1 , . . . , α * W }. There exist several equivalent ways of expressing the WE, such as:

W = α * ∈ C : ∃ S * : α * R(S * ), ∀ γ ∈ [0, γ] , S * (γ) ⊆ arg max r∈C U (γ) c (α * ) (4)
This equilibrium is Wardrop-type equilibrium because all the users of a single type γ is at the equilibrium according to Wardrop second principle [START_REF] Wardrop | Some theoretical aspects of road traffic research[END_REF]. That is, focusing on a single type of users γ, all the users of this type select a service that provides a utility which is greater or equal that those of the unselected services. This concept is also related to the NE since no user can improve its utility by unilaterally changing the selected service [START_REF] Roughgarden | How bad is selfish routing?[END_REF]. Any arbitrary load profile α induces certain value of U

C (α). Thus, for all γ ∈ [0, γ] we define a correspondence between the set of the services which maximize the utility, for a certain α. We define this set as follows:

Definition 4 (Set of utility maximizing services) For any arbitrary load α ∈ C , the set of utility maximizing services for users of type γ is given by:

Ŝ(γ) (α) = arg max r∈C U (γ) r (α). (5)
From (4), it is clear that α * is a WE if, and only if, for all γ ∈ [0, γ] it results that: S (γ) ⊆ Ŝ(γ) (α * ). In other words, at the WE no user of any type can improve its utility by unilaterally switching service.

2) Leaders' game: Each NSP k ∈ K, can autonomously select its price vector, p k = (p1, p2, . . . pM k ) ∈ R M k + , so as to maximize its own revenue. The main difference between leaders and followers, in a hierarchical game, is that the leaders can predict the reaction of the followers to their strategies, while the followers are myopic. As opposed to the users' non-atomic game, the leaders' competition is a noncooperative Nash game, which can be expressed in normal-form 3 With the expression almost is intended that only users of a finite amount types are allowed to chose a plurality of services.

by the tuple GL = K, {P k } k∈K , {u k } k∈K where u k (•) denotes the utility of NSP k defined as:

u k (p k , p -k ) = c∈M k α * c (p)pc. (6)
When analyzing the leaders' game, we refer the WE of the users' game by α * (p) to highlight the dependence of such a state on the price vector of the leaders. Hence, α * c (p) represents the fraction of users employing service c when the underlying system is at a WE given the fixed pricing vector p.

With this formulation, a suitable solution is the NE [START_REF] Fudenberg | Game Theory[END_REF], that is a set of price policies such that no NSP can gain by unilaterally modifying its own strategy. In the studied hierarchical game, this represents the state in which no user can achieve a higher utility by switching service, and no leader can obtain higher revenue by changing its pricing strategy.

III. ANALYSIS OF THE USERS' GAME

In order to study the Stackelberg equilibrium of the studied hierarchical game, we first need to analyze the equilibrium of the users' game. Therefore, our first result pertains the existence of at least one WE in pure strategies 4 for the game GF for any arbitrary pricing profile as stated below:

Theorem 1 In the game GF defined in Section II-B1, if the following conditions are met:

[C1] The utility functions depend only on the traffic load and not on the users' identities;

[C2] The QoS functions, i.e., gc(α) are continuous functions of α, for all c ∈ C; then, for any price profile p ∈ R C + , there exists at least one WE in pure strategies.

Both conditions [C1] and [C2] follow from the assumptions of our model (Section II) and the proof follow easily from Theorems 1 and 2 in [START_REF] Schmeidler | Equilibrium points of nonatomic games[END_REF]. This result is particularly relevant since it guarantees that the users' game has a WE for any arbitrary pricing vector resulting from the leaders' game. Moreover, since this equilibrium is in pure strategies, we can calculate the load profile by means of the service to load function in Definition 2, i.e., ∀ α * ∈ W, α * = R(S * ).

While the existence of at least one WE in pure strategies is necessary for the analysis of the hierarchical game it is clearly not sufficient. In order to evaluate the optimal pricing policies each leader needs to be able to evaluate the value of the load of each service at the WE. To achieve this goal, we first define a type-wise best-response (TBR) correspondence, i.e., a function between any given load profile, and the services which maximize the utility function of a given type of user. This concept is similar to the standard best-response used in atomic games.

Definition 5 Let α ∈ C be an arbitrary load profile of the network and let Ŝ(α) be the corresponding set of utility maximizing services. We define the type-wise best-response (TBR) correspondence, for users of type γ ∈ [0, γ], a function BR (γ) : C → C such that

BR (γ) (α) = s, with s ∈ Ŝ(γ) (α), (7)
that is, each type of user selects an element of each SUS. We also define the set of the TBR as

BR(α) = γ∈[0,γ] BR (γ) (α), .
Basically, each type of user selects an unknown service, among the services that maximize the utility function.

A. Characterization of the best-response

The defined TBR is a behavioral rule that, for any arbitrary load profile, links each type of user to one of its utility maximizing services. However, this rule is insufficient for the NSPs to estimate the load profile. Thus, here, we introduce the load-wise best-response (LBR) function F : C → C . Given an arbitrary load α, this function evaluates the load profile which result when all users select one of the services which maximize their utility. In order to specify this function, we begin by defining the following: Definition 6 (Same-priced services set (SPS)) The set of samepriced services (SPS) is a subset P ⊆ C that contains all the services with identical price p. That is ∀ c ∈ P, pc = p, and ∀ c ∈ C \ P, pc = p.

Using Definition 6, we can organize all the provided services in a sequence of non-overlapping SPSs, characterized by strictly increasing prices. Thus, when p0 < p1 = p2 = p3 < p4 we have P0, P1, P2 such that p0 P 0 , p1, p2, p3

P 1 , p4 P 2
. The indices of these non-overlapping SPSs are then grouped in the set E = {0, . . . , E}, E ≤ C (with equality iff all the services have strictly different prices), and each SPS e ∈ E is associated its unique price pe. Without loss of generality, we can assume that the SPSs are listed in a strictly increasing order, i.e., ∀ c, r ∈ E, c < r ⇔ pc < pr.

For each one of these SPS, for any given load profile α, it is possible to define a best service (BS), that is a service that offers a utility greater or equal than any service in the SPS, as follows:

Definition 7 (Best service (BS)) Let P ⊆ C be an SPS where all services are assigned price p. Consider an arbitrary load profile α ∈ C and define ĝ(α) = maxr∈P gr(α). A best service (BS) is a service that is characterized by a price p and a QoS equal to ĝ(α).

By definition, within each SPS, there exists at least one service which has the characteristic of the BS. Moreover, the utility offered by the BS for all type of users is greater or equal than the one offered by any other service belonging to the same SPS. Hereinafter, we refer to the set E as the set of BSs and to its generic element as the BS e ∈ E, which is characterized by a QoS of ĝe(α) and price pe. Also, we say that users of type γ select a BS e, or that e ∈ Ŝ(γ) (α) meaning that all the users of type γ select one of the services belonging to the SPS Pe5 . Unlike in [START_REF] Rose | Dynamic service selection games in heterogeneous small cell networks with multiple providers[END_REF], where the non-atomic users select a service among a set of services with strictly different prices, here the users make their service choices out of a set of BS with strictly different prices.

For any given load profile, in each SPS there might be several services which share the same QoS. Then, for each SPS, we define the best service set (BSS), as a set (whose elements depend on the load profile) which contains all services offering the same QoS and asking the same price.

Definition 8 (Best services set (BSS)) Let P ⊆ C be an SPS where all services are assigned price p. Consider an arbitrary load profile α ∈

C and let ĝ(α) be the QoS of the corresponding BS. We define as the best services set (BSS) the subset P(α) ⊆ P, that is the set of services characterized by the same QoS of the BS:

P(α) = {c ∈ P : gc(α) = ĝ(α)}.
From [START_REF] Rose | Dynamic service selection games in heterogeneous small cell networks with multiple providers[END_REF], we know that, if all the prices are different, there exist some thresholds which isolate all the users of any type that select a certain service. This results holds since on the γ -U (γ) (α) plane, the utility (2) offered by each service is a line, and thresholds are the intersection points of these lines. Intersection points that are unique iff the slopes and the y-intercepts are all different.

Subsequently, we show that: (i) Among the services offering the same price, only those who offers the highest QoS may be chosen; (ii) It is possible to define some subsets of services or BSs which are never selected when the all the users best-respond. (iii) For any given load profile, there exists a unique set of thresholds that isolate all the users of any type that connect to services belonging to the same SPS; (vi) It is possible to define a function that computes the load profile resulting when all type of users select one of their utility maximizing services; (v) A load profile α * is a WE iff it is a fixed point of this function. First, we show a result pertaining to the behavior of users that desire to connect to some services that are member of an SPS.

Theorem 2 Consider an arbitrary load profile α (0) ∈ C , an arbitrary SPS P, and denote the QoS of the BS by ĝ(α (0) ) = maxr∈P gr(α (0) ), and by P(α (0) ) its corresponding BSS. Let all users of each type γ ∈ [0, γ] best-respond according to Definition 5, and denote by α (1) ∈ C the resulting load profile. Then, the utility of all services within the SPS that do not belong to the BSS is inferior to the one of the BS, thus, they are never selected by any rational user. That is, for any service c ∈ P \ P(α (0) ), α

(1) c = 0.
Proof: From (2) we can see that if c ∈ P and gc(α (0) ) < ĝ(α (0) ) then there exists at least one service r ∈ P(α

(0) ) such that ∀γ ∈ [0, γ] , U (γ) r α (0) > U (γ) c α (0)
. Hence, since users of each type select a service which maximize its utility, no type of user selects any service c ∈ P \ P(α (0) ), thus α

(1) c = 0. Theorem 2 states that, among a set of services all characterized by the same price, only the ones that are providing the users with the highest QoS have a chance of being selected. This is reasonable, since rational users always discard a service which demands the same price of another while providing lower QoS. In the next Lemma we show that any service that is characterized by a lower QoS and an higher price than another service is not chosen by any rational user.

Lemma 1 Let α (0) ∈ C be an arbitrary load profile and let c, r ∈ C be two arbitrary services such that either gc(α (0) ) ≥ gr(α (0) ) and pc < pr or gc(α (0) ) > gr(α (0) ) and pc ≤ pr. Let each type of user γ ∈ [0, γ] best-respond according to Definition 5, and denote by α (1) = α (0) , . . . , α

(1) C the resulting load profile. Then, ∀ γ ∈ ]0, γ] , U (γ) c (α (0) ) > U (γ) r (α (0) ), thus it results ∀ γ ∈ [0, γ] , r ∈ Ŝ(γ) (α (0) ) and then α (1) r = 0.
Note that the same results holds with r, c being two BSs. Given Lemma 1, we can define, without loss of generality, a set of eligible BS as follows: E0 = {e ∈ E : r = e ∈ E : (gr(α) ≥ ge(α)) ∧ (pr < pe)}, where E0 represents, for a given load profile, subset of BS that are not chosen by any user which best-respond according to Definition 5.

Lemma 2 Let α (0) ∈ C be an arbitrary load profile, let each type of user γ ∈ [0, γ] best respond according to Definition 5 and denote by α (1) = α (0) , . . . , α

(1) C the resulting load profile. For a given γ ∈ [0, γ], denote by c one of the utility maximizing services, i.e., c ∈ Ŝ(γ) (α (0) ). Let r ∈ C be such that gr(α (0) ) < gc(α (0) ). Then, ∀ γ ∈ ]γ, γ], the utility offered by service c is greater than the one offered by service r, hence r is never selected by any rational user of type γ ∈ ]γ, γ].

Note that the results of Lemma 2 apply to any BS. Thus, Lemma 2 allows us to extend the concept of eligible BS. If a BS e is an element of the set of utility maximizing services Ŝ(γ) (α) 6 for the users of type γ and it offers a QoS equal to ĝe(α), then all BSs offering a lower QoS are not chosen by any type of user with γ > γ. These lemmas' proofs are given in the appendix. Next, we show the existence of a unique set of thresholds that isolate all the users of any type that connect to the same BS, that is that select one of the service of the same SPS.

Theorem 3 Consider a network in which a set C = {0, . . . , C} of services, organized in a price-wise increasing order, are grouped into a set E = {0, . . . , E} of BSs organized price-wise in a strictly increasing order. Consider an arbitrary load profile α (0) ∈ C and let all users of type γ ∈ [0, γ] best-respond according to Definition 5. Then, there exists a unique set of thresholds, 0 ≤ γ c * 1 ≤ . . . ≤ γ e * N ≤ γ that isolate all the users of any type that connect to the same BS: e * 1 , e * 2 , . . . e * N . The elements of this unique set of thresholds can be evaluated, from the smallest to the greatest, using the following recursive system of equations:

                 En = E0 \ r ∈ E0 : ĝr(α (0) ) ≤ ĝe * n (α (0) ) e * n = arg min e∈E n-1 pe -p e * n-1 ĝe(α (0) ) -ĝe * n-1 (α (0) ) γe * n = min e∈E n-1 pe -p e * n-1 ĝe(α (0) ) -ĝe * n-1 (α (0) ) , (8)
with the initial conditions:

E0 = E \ e : ∃r ∈ E : ĝe(α (0) ) ≤ ĝr(α (0)
) and pe > pr

ĝe * 0 (α (0) ) = 0, p e * 0 = 0, γ0 = 0 . (9)
The evaluation stops when En = ∅.

Theorem 3 proves the following: (i) Any initial load α (0) induces a set of QoS value, which, together with the services' prices, set the utilities that each service offers to each user of the same type. Services which share the same price, can be selected only if they offer the highest QoS among their SPS. (ii) For any load α (0) , there exist a unique set of thresholds, uniquely determined by the QoS functions and the pricing vector, and evaluated via recursion [START_REF] Shetty | Economics of femtocells[END_REF], which determines the load corresponding to each BS, i.e., the fraction of users that select one of the services that belong to the SPS. (iii) For any initial load α (0) , the set of utility maximizing services Ŝ(α) has a particular structure, that is:

Ŝ(γ) (α) = Pen (α), ∀ γ ∈ γe n , γe n+1 , (10)
where Pen (α) ⊆ Pe n (α) represents the best services set of SPS Pe n , that is, all users of type γ ∈ γe n , γe n+1 , and no other user, select one of the service belonging to Pen (α). This Theorem, whose proof is reported in Appendix C, is a generalization of Theorem 4 in [START_REF] Rose | Dynamic service selection games in heterogeneous small cell networks with multiple providers[END_REF],

where services were all characterized by strictly different prices. Given this unique set of thresholds, it is possible to exploit the definition of Γ(•) in Section II to evaluate the fraction of users that select each BS. Consider two consecutive thresholds γe and γ f , we know that all the users of all the types between the thresholds, and no other user, select a service belonging to the same SPS, say Pe. Therefore, if we calculate the load of the BS e, that is the sum of the loads of the services of the SPS Pe, the service to load function in Definition 2, becomes simply the integral of the user density function ρ(•) from γe to γ f . That is: αe = γ f γe ρ(γ)sγ, which, by means of the cumulative function Γ(•), can be written as: αe = Γ(γ f ) -Γ(γe). Next, we show a theorem that proves the link between the thresholds evaluated in Theorem 3 and the load of each BS, that is the sum of the loads of the services belonging to each SPS.

Theorem 4 Consider a network in which a set C = {0, 1, . . . , C} of services, organized in a price-wise increasing order, are grouped into a set E = {0, 1, . . . , E} of BS organized price-wise in a strictly increasing order. Consider an arbitrary feasible load profile α (0) ∈ C . All the users of each type γ ∈ [0, γ] choose one of the services which maximize their utility, and denote by α (1) the resulting load profile. Let E * = {0, e * 1 , . . . , e * N } be the consequent set of selected BS, and γ = γ e * 0 , . . . , γ e * N the thresholds evaluated in Theorem 3 . Denote, by α

e ∈ [0, 1] the fraction of user which selects the BS e. Thus, we have α(1)

e * r∈Pe α (1)
r . Then, for any BS e ∈ E, the fraction of users that selects one of its services is given by: α(1)

e * n = Γ(γe n+1 ) -Γ(γe n ) ∀en ∈ E * α(1) e = 0 ∀en ∈ E * . (11)
Proof: From Theorem

Further, if en ∈ E * , then no type of user connects to any service that belong to Pe n . In this case, the load of each of these services is 0, i.e. ∀ r ∈ Pe n , α

(1) r = 0. Since α (1)
e * r∈Pe α

(1) r

we have that α [START_REF] Index | Global mobile data traffic forecast update[END_REF] e * = 0. To fully determine the load profile after that all users have bestresponded, we must evaluate the repartition of load of one BS into the services which compose the corresponding SPS. Thus, we define a loadwise best response function (LBR) that determines the load resulting from all user selecting one of the utility maximizing service as follows:

Definition 9 (Load-wise best response (LBR)) Let α (0) ∈ C be an arbitrary load profile, let all type of users select one of the service that maximize its utility function and denote by α (1) ∈ C the resulting (unknown) load profile. Denote by α = ( α0, . . . , αE) the vector of the loads of all BS calculated using Theorem 4. For each SPS e ∈ E, let Pe(α (0) ) ⊆ Pe be the corresponding best services set. We define as the load-wise best response a function F : C → C such that ∀ c ∈ C:

Fc(α (0) ) = =          α (0) c +     αe- r∈ Pe(α (0) ) α (0) r     | Pe(α (0) )| if ∃ e ∈ E : c ∈ Pe(α (0) ) 0 otherwise . ( 13
)
To understand [START_REF] Gussen | Pricing and bandwidth allocation problems in wireless multi-tier networks[END_REF], we note that, if each SPS is a singleton, then we obtain Fc(α (0) ) = αc. Thus, the load of the BS coincides with the load of the unique service of the SPS. Conversely, when the SPSs are not singleton, the load of the BS, say e, is uniformly divided among the services in the set of best services, defined in Definition 8. The term r∈ Pe(α (0) ) α (0) r represents the load of the BS e before the best-response. Hence, the term αe -r∈ Pe(α (0) ) α (0) r represents the variation of the load of the BS e caused by the best-response. This variation is then divided equally among these services, as if the users were selecting randomly, with equal probability, one of the service in the same BSS, labeled by e. Notice that, under the assumption that each type of player employs pure strategies, ∀ α ∈ C , F (α) can be calculated with no information on the exact structure of S.

Next, we show that the set of the fixed points of the equation F (•) corresponds to the set of WE in pure strategies.

Theorem 5 In the game GF , denote by W the set of WE in pure strategies, and let F (•) be the LBR function defined in Definition 9. Then,

α * ∈ W iff α * = F (α * ).
The proof of this Theorem is given in Appendix D. Since the set of WE coincides with the fixed points of the LBR, the threshold structure holds also at each WE. This means that, at the WE, the type of users which select their service from a given SPS are all isolated by two thresholds, which can be uniquely determined for each equilibrium.

B. Conditions for uniqueness of WE of the users' game

Here, we show some conditions ensuring the uniqueness of the WE. In particular, we show that the equilibrium point is unique when the game is a congestion one, i.e., when the QoS functions depend only on the load of the corresponding service. Thus, the following theorem states our most general condition for uniqueness (proof is in Appendix E):

Theorem 6 In the non atomic game GF , let α A = α A 0 , α A 1 , . . . , α A C and α B = α B 0 , α B 1 , . . . , α B C be two arbitrary feasible load profiles such that α A 0 ≥ α B 0 . Let the prices be order in strictly increasing order, i.e., ∀ r, c ∈ C, r > c implies pr > pc and let {gc(•)} be a family of positive functions such that ∀ c ∈ C \ {0} :

• [H1] if α A c ≤ α B c , then gc(α A ) ≥ gc(α B ), • [H2] if gc(α A ) ≤ gc(α B ), then α A c ≥ α B c .
Then, the game GF admits only a single equilibrium α * .

Notice that [H2] is actually a consequence of [H1]. Assumption [H1]

implies that, if the aggregate load of the NSPs' services (i.e., all the services aside service 0) decreases, then the QoS of each service losing subscribers must increase. Consequently, using Theorem 6, we show a set of theorems that provide some simpler QoS models in which the equilibrium is unique. The first of these theorems states that if the QoS offered by any service is more sensible to its own load than to the loads of the other services then the equilibrium is unique. This model can approximate homogeneous systems (e.g., a multi-provider network of Wi-Fi hotspots or small-cells) or system where a service's QoS depends only on the service's own load.

Theorem 7 Let the game GF be the non-atomic users' game, and let each service's QoS function meet the following conditions: ∀α ∈ W E ∀c, ∈ C \ {0} , c = , (i) gc (α) ≥ 0, (ii) ∂gc ∂αc (α) < 0, (iii) ∂gc ∂α (α) = mc, and (iv) ∂gc ∂αc (α) < ∂gc ∂α (α), where mc ≤ 0 is some negative constant, and let the prices be all different and ordered in a strictly increasing order (i.e., r > s implies pr > ps), then the game admits a unique WE.

The proof of this theorem is given in Appendix F. Below, we briefly explain conditions (i) -(iv). (i) implies that the QoS are always positive, which well models a wide range of practical cases, for instance a throughput-based QoS. (ii) implies that the QoS of each service decreases with the service's own load, which is true for most communication services (Wi-Fi, 3G, small cells,...). (iii) means that the QoS offered by any service does not increase with the load associated to the other service, irrespective from the service. (iv) means that each service's QoS is more sensible to the services' own load than on other services' ones. Indeed, notice that this formulation includes congestion games (i.e., the case where each service's QoS function depends only on the service own load). As a special case, we can obtain a congestion game by setting mc = 0. Thus, we can state the following:

Corollary 1 In the game GF , let each service's QoS function gc(•) depend only on the load of that service αc, that is gc(α) = gc(αc). Moreover, let each of this function be positive and monotonically decreasing, i.e, ∀c ∈ C : c = 0: gc (αc) ≥ 0 dgc dαc (αc) < 0, and let the prices be all different and ordered in increasing order (i.e., r > s implies pr > ps) then the game admits only one WE.

Most existing works on HetNets' markets (e.g., [START_REF] Shetty | Economics of femtocells[END_REF]- [START_REF]Entry and spectrum sharing scheme selection in femtocell communications markets[END_REF]) assume a non-atomic game with QoS which depends only on the load of the service. The equilibrium uniqueness problem in congestion games was already tackled in [START_REF] Roughgarden | How bad is selfish routing?[END_REF], [START_REF] Milchtaich | Generic uniqueness of equilibrium in large crowding games[END_REF]. In these works, the authors prove that the equilibrium is essentially unique, that is, the utility offered by each service is the same at any WE. In accordance, for our scenario, we have shown the existence of a unique load profile (i.e., W = α * ) which implies the uniqueness of the utilities.

C. Users' game WE learning

Having discussed the existence and uniqueness of equilibria in the studied game, here, we discuss the possible dynamics that can enable the users to reach a WE of the game. Little work has been done on this topic and it is generally assumed that a free market would naturally converge to a WE system state. However we observed that this is not true as long as all users change simultaneously their strategies.

The LBR defines a way to calculate the load profile which result from all the user best responding according to the TBR. Iterating this process, it is possible to define a dynamics in which, starting from any load profile, one can evaluate a new load profile as the result of the users' best-response dynamics (BRD):

α (t+1) = F (α (t) ), (14)
where we used α (t) to denote the load profile at time instant t. Such an algorithm is known in the technical literature under several different names: the best-response dynamics [START_REF] Fudenberg | Game Theory[END_REF] or the Picard algorithm [START_REF] Berinde | Iterative approximation of fixed points[END_REF]. It is known that these dynamics converge to a fixed point if the iterating function is a contraction mapping. However, in our scenario, we have observed via numerical simulations that the function F (•) is generally not a contraction. Hence, the Picard algorithm does not converge, and leads to a ping-pong effect, in which the users switch between the services in a cyclic manner as shown in Fig. 2. Nonetheless, assuming that all the users change simultaneously their strategies is not a realistic representation of the market, as users may obtain side-information and make their decisions at different time instants. Thus, as a behavioral rule for the studied non-atomic game, we propose the Krasnosielkij algorithm [START_REF] Berinde | Iterative approximation of fixed points[END_REF]:

α (t+1) = (1 -λ)α (t) + λF (α (t) ), (15)
α * α F (α ) F (α ) Fig. 1. Geometrical interpretation of condition [START_REF] Milchtaich | Generic uniqueness of equilibrium in large crowding games[END_REF]. The distance between F (α) and α * might be bigger than the distance between α and α * . However, the angle between the vectors F (α) -α and α * -α is minor than π 2 .

where λ ∈ [0, 1] is a constant parameter which tunes the fraction of users that change their strategies at each iteration of the algorithm. It is easy to see that this transformation has the same set of fixed-points as F (•), i.e., the WE set. The convergence conditions of the Krasnosielkij algorithm are less stringent than the Picard algorithm. For instance, the Krasnoselskij algorithm converges if F (•) is a pseudo-contraction mapping [START_REF] Berinde | Iterative approximation of fixed points[END_REF].

To simplify the notations, we define a pseudo-operator G : C → C as:

G(α (t) ) = (1 -λ)α (t) + λF (α (t) ). (16)
The dynamics in ( 15) can be re-written as follows:

α (t+1) = G(α (t) ).
However, even if we do not observe an asymptotic convergence of the Krasnoselskij algorithm we can state the following.

Theorem 8 Let α (0) ∈ C be the an arbitrary starting load profile, W the set of the fixed points of

F (•), K max α∈ C ||F (α) -α|| and ζ a real such that ζ ∈ [0, 1]. Let also gc : C → [0, 1] be a family of QoS functions such that: F (α) is continuous on C ; There exists an α * ∈ W such that ∀ α ∈ C ||F (α) -α * || 2 < ||F (α) -α|| 2 + ||α -α * || 2 . ( 17
)
Then, ∃ t ∈ N : ∀t > t

||α (t) -α * || < λK( 1 2ζ + 1) (18)
The proof of this theorem is given in Appendix G. Geometrical Interpretation and explanation of Theorem 8. Condition (17) can be geometrically described as follows. Consider the hyperplane orthogonal to the vector αα * which divides the simplex C in two half-space. Then, F (α) stays in the half-space that contains α * . More formally, let us denote by X the half space such that X = {x : x, αα * < ||α - * ||}. Then, ∀α ∈ C we have that F (α) ∈ X . Another simple interpretation, is that the angle between the vectors αα * and F (α) -α * is less than π 2 . The theorem guarantees that for any α that lies far enough from the fixed point (i.e., ||α -α * || ≥ λ K 2ζ ), then the result of one iteration of the Krasnosielkij algorithm is closer to the fixed point than α. With far enough being a distance which is λ-parametrized. Since the utility functions are continuous functions, we can then state the following corollary:

Corollary 2 Given any family of QoS functions gc :

C → [0, 1], such that [C1] and [C2] are satisfied the algorithm α (t+1) = G(α (t) ), converge to a ε-WE with ε ∝ λ.

An ε-WE essentially implies that the distance between the convergence point of the Krasnoselskij algorithm and a WE is less than or equal to ε [START_REF] Fudenberg | Game Theory[END_REF]. In order to prove Theorem 8, we first need the following Theorem.

* ∈ W such that ∀ α ∈ C ||F (α) -α * || 2 < ||F (α) -α|| 2 + ||α -α * || 2 , ( 19
)
and that ||α -

α * || ≥ λ K 2ζ , (20)
(where ζ is a fixed positive scalar such that 0

< ζ ≤ 1) then, ||G(α) -α * || < ||α -α * ||.
The proof of this Theorem is given in appendix H.

IV. LEADERS' GAME

In Section III, we have provided an algorithm that is able to evaluating the WE of the users' game, and we have provided some condition for the uniqueness of this equilibrium. In this section, we show the main results of the analysis of the leaders' game. In a hierarchical game, the leaders (the NSPs) must select their actions by considering that their outcome depends on the reaction of the users. In particular, the price induces a WE in the users' game, and this WE, together with the pricing policy, determines the leaders' revenues. Our first result pertains the definition of some maximum prices for the services. This results permits to the leaders to reduce their search-space for the price, and its fundamental in order to numerically simulate their behavior. From the expressions in Theorem 3, we can see that there exist some limits in the prices of the services such that, if the price of a service is set above this limit, then no user selects the service. These limits depend both on the maximum interest that the users can have in the QoS, i.e., γ, and on the services characteristics. In this respect, we can state the following results: Theorem 10 Let pc ∈ R be the price associated to service c ∈ C and denote by gc(0) the maximum QoS that c can offer. Also, let pc > γgc(0), then the utility of service c is always minor than 0, thus, no rational user selects this service. In particular, the load of c at any WE is 0.

Proof: If pc ≥ γgc(0), then ∀ α ∈ C , ∀ γ ∈ [0, γ] , U (γ) c (α) < 0, hence U (γ) c (α) < U (γ) 0 (α), i.e.
, the price asked is so high that even users of type γ receive an higher utility for selecting service 0, the absence of service. Then, from Definition 4, ∀ α ∈ C , c ∈ Ŝ(α), thus ∀ α * ∈ W, α * c = 0. Since each service has a finite maximum price, we can define the greatest of these prices as the maximum price for all the services: pM = γ maxc∈C gc(0). Hence it is possible to reduce with no loss of generality, the domain of the price vector, i.e., p ∈ [0, pM ] C .

Since the leaders' game is a Nash game [START_REF] Fudenberg | Game Theory[END_REF], the solution concept is the NE, which is defined as follows:

Definition 10 (Nash equilibrium) A price vector p ∈ [0, pM ] C is a NE of the game GL if ∀k ∈ K, ∀p k ∈ [0, pMAX ] M k u k (pk, p-k) ≥ u k (p k , p-k), (21)
where p-k represents the vector p without the k-th element and the notation p = p k , p-k serves to underline the role of the k-th element. Therefore, at the NE no NSP can improve its outcome by unilaterally changing its pricing strategy.

In order to show the existence of at least one NE, we begin by defining the leaders' best-response as follows:

pk ∈ BR k (α * (p)) = arg max p k ∈[0,p M ] M k c∈S k α * c (pk, p-k)pc. ( 22
)
Equation ( 22) states that the best pricing scheme for the player k is the one which maximized its utility given as fixed the prices of its competitors, and considering the overall effect of the prices on the users' choices. Notice that, the eventual multiplicity of the equilibria at the low-level game implies a multiplicity of the optimal prices. However, it is reasonable to assume that the NSPs know the initial load profile, i.e. how many users subscribe to a certain service at a given time. Therefore, if the NSPs assume that the users are actually following the Krasnosielkij algorithm (i.e., at each time a fraction of the users rationally updates its choices), also in case of multiple equilibria, it is possible for the leaders to predict the users' stable loads.

For each player, the BR correspondence defines a curve which denotes the optimal price given the prices chosen by the competitors. The intersection points of theses lines correspond with the NE of the game GL [START_REF] Weibull | Evolutionary Game Theory[END_REF]. Hence, we can express the NE as the fixed points of the following fixed-point equation:

p N E = BR(α * (p N E )) = BR * (p N E ), (23)
where we denote by BR * the composition of the best responses of the users' game and of the leaders' game, i.e, BR * = BR • α * . Hence, BR * : [0, pM ] C → [0, pM ] C is a convex and compact set (is the Cartesian product of real segments), we can state the following: Conjecture 1 Let p ∈ [0, pM ] C be the price vector chosen by leaders, gc(•) : C → R be a family of continuous non-increasing functions, α * (p) be the equilibrium reached in the users' game through the Krasnosielkij algorithm [START_REF] Roughgarden | How bad is selfish routing?[END_REF], expressed as a function of the price vector p. Then, α * (•) is a continuous function of p.

A sketch of the proof of this conjecture is given in Appendix I. This proposition basically states that to very small variations in the pricing scheme correspond very small variation in the loads. This result allow us to state the following: Theorem 11 Let gc(•) be a family of functions such that BR * (•) [START_REF] Berinde | Iterative approximation of fixed points[END_REF] is continuous with respect to p on the set [0, pM ] C , then the game GL has at least one NE.

The proof of this Theorem follows directly from Brower fixed-point theorem [START_REF] Brouwer | Über abbildung von mannigfaltigkeiten[END_REF]. In Fig. 4, we report an example of a system with two NSP each offering one service. The two lines represent the best-response lines associated to each operator. In this case, the equilibrium exists and is unique.

V. SIMULATION RESULTS

Here, we first show that, under certain conditions, the Picard algorithm [START_REF] Rose | Dynamic service selection games in heterogeneous small cell networks with multiple providers[END_REF] does not allow the NSP to predict the equilibrium while the Krasnosielkij ( 16) is smoothly converging; Second, we illustrate the uniqueness of the WE in the users' game equilibrium under the conditions derived in Section III; Finally, we analyze the interactions between the leaders and the users and we evaluate the outcome of the leaders under different assumptions regarding the performance of the considered HetNet.

A. Users' Game

The convergence to a WE of the Picard and Krasnoselskij algorithms is analyzed here. Consider a scenario where the leaders have already fixed their prices and the users select the respective services. The utilities associated to each service are:

U (γ) 0 (α) = 0; U (γ) 1 (α) = γ (7 -6.4 (α1 + α3)) -1.2; U (γ) 2 (α) = γ (6 -4.8 (α2 + α4)) -1.5; U (γ) 3 (α) = γ (9 -3.2α3) -3; U (γ) 4 (α) = γ (8 -4α4) -4.5, with γ = 1.
First, we let all the users freely select the services Fig. 2. Thresholds as functions of iteration steps. The dashed line marked with circles represents the evolution of the thresholds when all the users best-respond and are allowed to change their strategy, whereas the continuous line marked with crosses represents the evolution of the thresholds when a fraction equal to λ = 0.1 of users is allowed to switch their strategy. Note that, in the fourth plot, the two lines are superposed.

which best suits their QoS-price tradeoff (Picard algorithm), then we let only a fraction λ = 0.1 of the users change their strategies. The results are reported in Fig. 2. The four plots represent the evolution of the thresholds given in Theorem 3 over time, following ( 14) (Picard algorithm) and ( 15) (Krasnoselskij algorithm). These results are obtained starting from an initial load profile α (0) = (1, 0, 0, 0, 0) (i.e., no user is connected to any offered service). The load profile obtained via the Picard algorithm after 30 iterations is α (30) = (0.2869, 0.2411, 0, 0.4720, 0), while via the Krasnoselskij, the load profile is α (30) = (0.3008, 0.0287, 0.2290, 0.4415, 0). Moreover, it is possible to observe that, whereas the Krasnosielskij algorithm tends toward a stable point, the Picard algorithm loops continuously between the same loads. From these results, we see that if all users are allowed to change their strategies at every time instant, it is possible to enter in an unstable infinite loop. Here, NSPs are unable to anticipate the users' behavior which results in suboptimal pricing policies. Whether [START_REF] Rose | Dynamic service selection games in heterogeneous small cell networks with multiple providers[END_REF] converges or not strongly depends on the QoS variation with the system loads. When employing a logarithmic model similarly to the one used in [START_REF] Gussen | Pricing and bandwidth allocation problems in wireless multi-tier networks[END_REF], since the gc(•) QoS functions vary weakly with the system loads, then it is possible to observe the convergence of the Picard algorithm towards a WE.

To illustrate the uniqueness of the equilibrium, and the ability of the Krasnosielskij algorithm to predict it, we consider a system with C = 4 services. We set the users' utility functions to:

U (γ) 0 = 0; U (γ) 1 = γ(3 -2α1 -α2 -α3) -1.5; U (γ) 2 = γ(3.5 -1.5α2 - 0.75α1 -0.75α3) -2; U (γ) 3 = γ(4.5 -2α3 -α1 -α2) -3.
Note that the performances offered by the different services depend on the whole load profile, i.e., the game does not belong to the class of congestion games. However, since the conditions of Theorem 7 are met the game admits a unique equilibrium. In Fig. 3, we initialize the Krasnoselskij algorithm with six different values: The four vertices of the simplex 4 ; A point on a face of the simplex (i.e., α (0) = (0, 0.5, 0.5, 0)); A randomly chosen starting point α (0) = (0.41, 0.06, 0.18, 0.35)). Irrespective of the starting point, the algorithm always converges to the unique equilibrium: α * = (0.61, 0.17, 0.18, 0.02).

B. Leaders' Game

Each leader independently makes use of the Krasnosielkij algorithm [START_REF] Roughgarden | How bad is selfish routing?[END_REF] to estimate the equilibrium reached by the users thus setting the services' prices. In our system, the leaders select their optimal prices one after the other, in a sequential best-response dynamic [START_REF] Fudenberg | The Theory of Learning in Games, ser[END_REF] fashion. Tra jectory 4, α (0) = (0 0 0 1) Tra jectory 5, α (0) = (0 0.5 0.5 0)

Tra jectory 6, α (0) = (0.41 0.06 0.18 0.35) Fig. 3. Trajectories of the Krasonsielkij algorithm with different starting points all converging to the same WE α * = (0.61, 0.17, 0.18, 0.02). The settings for this simulation is:

U γ 0 = 0; U γ 1 = γ(3 -2α 1 -α 2 -α 3 ) -1.5; U γ 2 = γ(3.5-1.5α 2 -0.75α 1 -0.75α 3 )-2; U γ 3 = γ(4.5-2α 3 -α 1 -α 2 )-3.
Notice that the value of α 0 is not reported in axes of the figure since c∈C αc = 1. We consider a system with two NSPs, each offering one service. Each NSP assumes the competitors prices as fixed, and tests all its possible pricing strategies, evaluating the corresponding the WE trough the iteration of ( 16), thus evaluating its own payoff [START_REF] Webb | Wireless communications: The future[END_REF]. Therefore, for each NSP, and for all possible pricing policies of the competitor, we evaluate the optimal pricing. The resulting curve is an instance of best response curve [START_REF] Fudenberg | Game Theory[END_REF]. The intersection points of these curves provide the NEs of the game GL. In Fig. 4, the best response curves of the NSPs are plotted. The continuity of these curves ensures existence of at least one intersection point, which here happens in p * = (1.87, 0.65).

Next, we study the interaction among the leaders and the users. We analyze a duopoly market in which an NSP 1 offers one service (a macro-cell service) and an NSP 2 offers two services (a macrocell service and a small-cell service). NSP 2 is evaluating how much it should invest in the small-cell infrastructure, by evaluating the economical benefit resulting from its deployment. In this scenario, service 0 represents, as usual, the absence of service, service 1 and 2 the macro-cell services of NSPs 1 and 2 respectively and service 3 is the small-cell service. Each service is associated with a unique portion of the spectrum, hence the utilities depend exclusively on the services' own loads. Therefore, the QoS functions are designed as follows: g0(α) = 0, g1(α) = 3-α1, g2(α) = 3-α2, g3(α) = G0 -1.5α3. The parameter G0 represents the maximum QoS offered by the small-cell service (i.e., the QoS it offers when no user is selecting it). We assume that this value depends on the amount of infrastructure, and thus of economical effort, deployed by the NSP. The NSP is then interested in understanding how much should G0 be. The analysis is then performed as follows: we let G0 vary from 0 (i.e., no small-cell service deployed) to 5, thus evaluating the optimal pricing scheme (Fig. 5), the equilibrium loads (Fig. 6) and the NSPs' utilities (Fig. 7).

(α) = 0, g 1 (α) = 3 -α 1 , g 2 (α) = 3 -α 2 , g 3 (α) = G0 -1.
From Fig. 5 and Fig. 7, we can see that the income of NSP 1 is boosted by the new technology only when G0 > 3. When G0 < 3, NSP 2 can approximately limit the loss of users by decreasing the price asked for the service. In this case, the effect of the implementation of the new service by NSP 1 is to slightly decrease the profits of NSP 2 (therefore improving the utilities of the users), instead of increasing the revenues of NSP 1. In Fig. 5 and Fig. 6, it is possible to notice that an NSP with one service selects a price that leads to a load level similar in value to the price. In contrast, the NSP offering two services adopts a pricing scheme that maximizes the income correspondent to the service which offers the highest QoS.

Figs. 5-7 also show that the result of a small investment (small G0) is to decrease the market appeal of the competitor's offer. As long as G0 < 3, which is the maximum QoS offered by the macro-cell services, the second NSP can decrease the price to contain the effect of the new technology, thus avoiding a incisive increment in the outcome of the first NSP. However, when G0 > 3, decreasing the price stop being a viable tactic, and the first NSP income grows linearly with the performance of the HetNet.

VI. CONCLUSIONS

In this paper, the interactions between an arbitrary number of service providers offering a variety of services based on a set of heterogeneous technologies and an infinite population of users have been analyzed. To study this system, a hierarchical game-theoretic model has been formulated. This model is composed of a standard Nash game: the leaders, or network service providers' game, and a general non-atomic game as the followers, or the users' game. In the users' game, the assumption of congestion payoffs has been relaxed to allow the users' utility functions to comply with systems where the QoS of each service depends on the loads of all the services in the network. The existence of a Wardrop equilibrium was proven for any pricing policies and sufficient conditions for its uniqueness were provided. At the service providers' level, an algorithm, namely the Krasnosielkij algorithm, has been provided allow the leaders to anticipate the users' behavior at the equilibrium, which let the leaders effectively estimate the market behavior. Thus, this estimation is used by the NSPs to evaluate their optimal pricing strategies. Furthermore, by assuming the continuity of the NSPs' best-response, the existence of at least one Nash equilibrium has been shown, which represents the equilibrium of the overall hierarchical game. Thorough numerical simulations were performed to validate our theoretical results. Also, we provide a specific practical scenario to illustrate the possible uses of the mathematical tools developed in this work. In this framework, the providers can anticipate the benefit, if any, of deploying a new service.

f α (0) e * n ,r (γe * n ) = f α (0) e * n ,e * n-1 (γe * n ) + f α (0) e * n-1 ,r (γe * n ) = f α (0) e * n-1 ,r (γe * n ), (25)
since, by substituting the definition of γe * n in [START_REF] Weibull | Evolutionary Game Theory[END_REF], it results

f α (0) e * n ,e * n-1 (γe * n ) = 0. Reasoning ad absurdum, if we assume that f α (0) e * n-1 ,r (γ e * n-1 ) < 0 then γe * n > pr -p e * n-1 gr(α (0) ) -g e * n-1 (α (0) ) , (26)
which contradicts the definition of γe * n , since we would have found an eligible service r with a lower γr, therefore ∀r ∈ En-1 f α (0) e * n ,r (γe * n ) > 0. Now, we show that ∀r ∈ En f α (0) e * n ,r (γ e * n+1 ) ≥ 0. Reasoning ad absurdum, we assume that there exists a service r ∈ En such that f α (0) e * n ,r (γ e * n+1 ) < 0. Then, since fe * n ,r (γe * n ) > 0 and fe * n ,r (•) is a continuous function, there must exist a certain γr < γe n+1 such that fe * n ,r (γr) = 0. Using ( 24)

γr = pr -pe * n ĝr(α (0) ) -ĝe * n (α (0) ) , (27)
which contradicts the definition of γ e * n+1 in [START_REF] Shetty | Economics of femtocells[END_REF]. This concludes our proof.

APPENDIX D PROOF OF THEOREM 5

Proof: We begin by showing that if α * ∈ W then α * = F (α * ). We focus on an arbitrary service c ∈ C. Either this service does not belong to any best service set, i.e., ∀ e ∈ E, c ∈ Pe(α), or it belongs to one best service set, i.e., ∃! e : c ∈ Pe(α * ). We recall that a best service set is a subset of a certain same price service set, in which all services offer the highest QoS. In the first case, since c is not into any best service set, it is never selected by any rational user, thus, α * c = 0. Also, following [START_REF] Gussen | Pricing and bandwidth allocation problems in wireless multi-tier networks[END_REF], Fc(α * ) = 0. Hence, for all services that do not belong to any best service set it holds that Fc(α * ) = α * c . Let us consider now the case in which c is part of a best service set, say Pe(α * ). Let us evaluate the total load of the BS e. Knowing that, at the WE, by Definition 3 rational users chose only to connect to a utility maximizing services, then the load equals to the sum of the loads of all the services belonging to the SPS Pe, α * e = r∈Pe α * r . Since α * ∈ W, from (4) we have that S (γ) ⊆ Ŝ(γ) (α * ), that is all the selected services are utility maximizing services. However, from Theorem 3 and (10) we know that there exist two threshold, which we denote as γe and γ f , such that Ŝ

(γ) (α * ) = Pe(α * ) ⇔ γ ∈ [γe, γ f ].
This means that all the types of user that select one of the services inside the SPS are in the real segment [γe, γ f ], thus, the load of the BS can be calculated integrating the density function ρ(•) between these two thresholds. Hence, by using the cumulative density function,

α * e = Γ(γ f ) -Γ(γe). (28)
Furthermore, let all users of each type best-respond according to Definition 5, and denote by α (1) the resulting load profile. From Theorem 4, it results αe = Γ(γ f ) -Γ(γe). Which, by using (28), allows us to say that αe = α * e , thus αe = r∈Pe α * r . Substituting this in [START_REF] Gussen | Pricing and bandwidth allocation problems in wireless multi-tier networks[END_REF], we obtain Fc(α * ) = α * c . This concludes the first part of the proof.

Next, we show the reverse implication, that is if α * = F (α * ) then α * ∈ W. From the definition of WE in (4), we must show that there exists a set of used services S satisfying two conditions: (i) ∀ γ ∈ [0, γ] , S (γ) ⊆ Ŝ(γ) (α * and (ii) α * = R(S). Let all the users bestrespond to the load α * according to Definition 5 and let S be one of possible the resulting SUS. Recall that all best-responding users of each type γ may select indifferently any of the services in their set of best services Ŝ(γ) (α * ). We want to show that S is a set of used service which satisfies (i) and (ii).

Condition (i) is respected, in fact, from Definition 5, it results that ∀ γ ∈ [0, γ] , S (γ) ⊆ Ŝ(γ) (α * ). That is, all the users of each type select a service which maximizes their utility function when the initial load profile is α * .

To prove condition (ii), we focus on an arbitrary service c ∈ C, and we distinguish two cases: the case in which c does not belong to any best service set, and the case in which it belongs to a best service set denoted by Pe(α * ). In the first case, from [START_REF] Gussen | Pricing and bandwidth allocation problems in wireless multi-tier networks[END_REF] we have that α * c = 0. On the other hand, from Definition 8, when all user best-respond no user select such a service, hence Rc(S) = 0, thus α * c = Rc(S). In the case in which c belongs to some best service set Pe(α * ), from Theorem 3, we have that there exist two unique thresholds, which we denote as γe and γ f , that isolate all the users that connect to the BS e, i.e. that select one of the services belonging to the corresponding SPS Pe. The load of the BS e, is defined as the sum of the loads of all the services belonging to Pe. Hence, after the best-response, it is αe r∈Pe Rr(S). On the other hand, the assumption α * = F (α * ) implies, from [START_REF] Gussen | Pricing and bandwidth allocation problems in wireless multi-tier networks[END_REF], that αe = r∈ Pe α * r , thus, r∈Pe Rr(S) = r∈Pe α * r . This means that, if α * = F (α * ), then, after a type wise best-response from all the users, irrespective from the actual service chosen from all the users of any type, the sum of loads of all the services belonging to the same SPS must not change.

However, according to Definition 5, when best-responding, any user can arbitrarily select any service belonging to the best service set. Therefore, we can select each S (γ) ∀γ ∈ [0, γ] such that Rc(S) = α * c , we obtain that Rc(S) = α * c and, thus, α * = R(S). This concludes the proof.

APPENDIX E PROOF OF THEOREM 6

Proof: From Theorem 1, the game GF has at least one WE, that we denote by α A = α A 0 , . . .

where r, s ∈ C w are two arbitrary services and the superscript w ∈ {A, B} labels the WE load profile used as the argument of the QoS functions. The name intersection is justified by the fact that the value represents the unique value of γ for which it results that U γ r (α w ) = U γ s (α w ), where these utility functions are defined as in [START_REF] Hu | Hetnets-a new paradigm for increasing cellular capacity and coverage[END_REF]. We underline that from Theorem 3, each threshold γ A c * n is the minimum intersection among the available services, i.e., we can write

In order to prove the body of the theorem, we need to introduce some preliminary results. As a first step, we show that in any WE the first service to be used is service 0. By definition all prices are strictly positive values, therefore ∀α ∈ W, ∀c ∈ C it results that U 0 0 (α) > U 0 c (α), moreover following the results of Theorem 3, α0 = Γ(γc 1 ), and γc 1 = pc 1 gc 1 . Since both pc 1 and gc 1 ∈ R + , we have that γc 1 > 0. Since Γ(•) is a strictly increasing function and Γ(0) = 0, we obtain that Γ(γc 1 ) > 0. As a second step, we show that if

∀ < n α A c A ≥ α B c B then ∀ ≤ n γ A c A ≥ γ B c B .
We proceed by induction on n defining the following proposition

O : α A c A ≥ α B c B ⇒ γ A c A +1 ≥ γ B c B +1 . (31)
We show that for = 1 O is true. Considering that Γ(0) = 0, from [START_REF]Entry and spectrum sharing scheme selection in femtocell communications markets[END_REF] we have that

α A 0 ≥ α B 0 implies Γ γ A c A 1 ≥ Γ γ B c B 1
. By definition, Γ(•) is a monotonically increasing function, hence γ A

r1 1

 1 , by means of the service to load function (3), we have, ∀ e * ∈ E * : {r∈S (γ) } ρ(γ)dγ = γ 0 r∈P e * 1 {r∈S (γ) } ρ(γ)dγ. Since for each type of user γ, S (γ) contains only one service, we can write r∈P e * 1 {r=S (γ) } = 1 {S (γ) ∈P e * } , thus {S (γ) ⊆P e * } ρ(γ)dγ = γ e * n+1 γ e * n ρ(γ)dγ = Γ(γ e * n+1 ) -Γ(γe * n ).

Theorem 9

 9 Denote by W the set of the fixed points of F (•) and by K = max α∈ C ||F (α) -α||. Assume that there exists an α

Fig. 4 .

 4 Fig.4. Best-responses lines for a network where 2 NSPs offering one service each. Each leader estimates the WE of the users' game and evaluates its own optimal price for each of the possible price taken by the other leader. The meeting point of the two lines is the (unique) NE.

Fig. 5 .

 5 Fig. 5. Optimal prices for the leaders as a function of the maximum QoS offered by service 2 of NSP 1 (G 0 ). The QoS of the other services are:g 0 (α) = 0, g 1 (α) = 3 -α 1 , g 2 (α) = 3 -α 2 , g 3 (α) = G0 -1.5α 3 where service 0 represents the absence of service, service 1 and 2 represent respectively service 1 of NSP 1 and service 1 of NSP 2, and service 3 represents the small-cell service of NSP 2.

  Fig. 5. Optimal prices for the leaders as a function of the maximum QoS offered by service 2 of NSP 1 (G 0 ). The QoS of the other services are:g 0 (α) = 0, g 1 (α) = 3 -α 1 , g 2 (α) = 3 -α 2 , g 3 (α) = G0 -1.5α 3 where service 0 represents the absence of service, service 1 and 2 represent respectively service 1 of NSP 1 and service 1 of NSP 2, and service 3 represents the small-cell service of NSP 2.

2 Fig. 6 .

 26 Fig. 6. Load of each service at the Stackelberg equilibrium as a function of the maximum QoS offered from service 2 of NSP 1 (G 0 ).

Fig. 7 .

 7 Fig. 7. Revenues of each NSP at the Stackelberg equilibrium as a function of the maximum QoS offered from service 2 of NSP 1 (G 0 ). Notice that the revenues of NSP 1 increase strongly when G 0 ≥ 3.

  e * n ,r (γ e * n+1 ) ≥ 0 and thus ∀γ ∈ γe * n , γ e * n+1 , f α (0) e * n ,r (γ) > 0. In fact, if ∀ r ∈ E, ∀ γ ∈ γe * n , γ e * n+1 , f α (0) e * n (γ) > 0, then from Lemma 2 all, and only, the users of type γ ∈ γe * n , γ e * n+1 select th BS e * n . Let r ∈ En-1 be an arbitrary BS, it results that

  α A C and ad absurdum let α B = α B 0 , . . . α B C be a different WE, with γ A = γ A 0 , . . . γ A C and γ B = γ B 0 , . . . γ B C being the correspondent thresholds vectors. Moreover, ∀ c ∈ C, let us denote by g A c = gc(α A ) and g B c = gc(α B ) and letC A = 0, c A 1 , c A 2 , . . . c A N A and C B = 0, c B 1 , c B 2 , . . . c B N Bbe the respective strictly ordered sets of used services at the WE, this means that:α A c > 0 if and only if c ∈ C A and α B c > 0 if and only if c ∈ C B ; 0 < c A 1 < . . . < c A N A and 0 < c B 1 < . . . < c B N Bwith NA and NB representing the number of services used at the WE α A and α B respectively. Let us define the intersection function I w : C 2 → R as follows:I w (r, s) = pr -ps g w r -g w s ,

1 I

 1 A ( , c * n-1 ) .

1 .Lemma 5

 15 To complete the proof, let us assume O to be true ∀ < n and prove that On is also true. From[START_REF]Entry and spectrum sharing scheme selection in femtocell communications markets[END_REF] Γ(•) is monotonically increasing. Therefore, we can write thatΓ γ A c A n+1 -Γ γ B c B n+1 ≥ 0, thus, γ A c A n+1 ≥ γ B c B n+1which proves On.In the following we prove the main body of the theorem. With no loss of generality, let us assume α A 0 ≥ α B 0 . We aim at proving that ifα A 0 ≥ α B 0 then ∀ ∈ C α A ≥ α B which, since α A , α B ∈ C and α A = α B is absurd.Let us recall that the services are organized For Lemma 3 and the inner product definition (left multiplication by a scalar), we have that(F (α) -α) , (α -α * ) = 1 λ (G(α) -α) , (α -α * ) . (54) Thus, we have that (G(α) -α) , (α -α * ) < 0. Writing ||G(α)α * || 2 as ||G(α) -α * || 2 = ||(G(α) -α) + (α -α * )|| 2we apply the polarization identity and, using the previous result, we obtain||(G(α) -α * )|| 2 = ||G(α) -α|| 2 + ||α -α * || 2 + (55) 2 (G(α) -α) , (α -α * ) (56) < ||G(α) -α|| 2 + ||α -α * || 2 . (57)This ends our proof. For all α ∈ C we have that||G(α) -α * || ≤ ||α -α * || + λK. (58)Proof: We can write ||G(α) -α * || = ||G(α) -α + αα * ||, then for the triangular inequality, we have that||G(α) -α + αα * || ≤ ||G(α) -α|| + ||α -α * ||. (59)Since ||G(α) -α|| = λ||F (α) -α|| from Lemma 3, and from the definition of K we have that||G(α) -α|| + ||α -α * || ≤ λK + ||α -α * ||.(60)Hereunder, we show the proof of the Theorem. Proof: We begin by rewriting the distance between a single iteration of the Krasnosielkij algorithm and a fixed point α * as follows: ||G(α)α * || 2 = ||(G(α)-α)+(α-α * )|| 2 . Thus, by means of the polarization identity and the properties of the inner product, we can write||G(α) -α * || 2 = ||G(α) -α|| 2 + ||α -α * || 2 + +2 cos(θ)||G(α) -α||||α -α * ||. (61)Here, θ is the angle between the two vectors G(α) -α and αα * .The assumption that||F (α)-α * || 2 < ||F (α)-α|| 2 +||α-α * || 2 and Lemma 4 guarantee that ||G(α)-α * || 2 < ||G(α)-α|| 2 +||α-α * || 2 , which implies 2 cos(θ)||G(α) -α||||α -α * || < 0.Since the norms cannot obtain negative values, it means that cos(θ) < 0. For simplicity, we introduce a positive constant C = -cos(θ), thus 0 < C ≤ 1. Therefore, using Lemma 3, we can write (61) as||G(α) -α * || 2 = ||F (α) -α|| 2 λ 2 + ||α -α * || 2 + (62) -2Cλ||F (α) -α||||α -α * ||With some algebra, and by using the assumption that ||α-α * || ≥ λ K2Cwe can write:||G(α) -α * || 2 = = ||α -α * || 2 + λ||F (α) -α|| (λ||F (α) -α|| -2C||α -α * ||) ≤ ||α -α * || 2 + λ||F (α) -α|| (λK -2C||α -α * ||) ≤ ||α -α * || 2 + λ||F (α) -α|| (λK -λK) = ||α -α * || 2 . (63) Notice that the passage is justified from the fact that ||F (α)-α||λ ≥ 0 ∀α. Moreover, since by definition both ||G(α)-α * || and ||α-α * || are non-negative, ||G(α) -α * || 2 ≤ ||α -α * || 2 implies ||G(α) -α * || ≤ ||α -α * ||.

  3, the set γ = γ e * 1 , . . . , γ e * N defines the thresholds such that all the users of type γ ∈ γe * n , γ e * n+1 , and no other user, select the BS e * n . This means that, if we denote by S (γ) the set of services used by users of type γ, which results from all the users best-responding according to Definition 5, then S (γ) ⊆ Pe * n iff γ ∈ γe * n , γ e * n+1 . That is, all the users of types γ ∈ γe * n , γ e * n+1 select one of the services that belong to Pe * n , while all the users of different types select a service which does not belong to Pe * n . Since α(1)

Essential uniqueness refers to the fact that the utilities offered by each service at different WE points is the same.

We indicate with C the C-simplex,i.e., C = v ∈ [0, 1] C : ||v|| 1 = 1 .

We recall that, in this context, the expression pure strategy refers to the fact that all users of each type select only one service.

More formally, e ∈ Ŝ(γ) (α) means that ∃ c ∈ Pe : c ∈ Ŝ(γ) (α).

More formally, if ∃ c ∈ Pe : c ∈ Ŝ(γe) (α).

Let x,y be ∈ V two vector on a vectorial space V on which it has been defined a scalar product •, • , then we have that ||x+y|| 2 = ||x|| 2 +||y|| 2 +2 ( x, y ). Since in our case α, F (α) ∈ S ⊂ R S , 2 ( x, y ) = 2 x, y .

ACKNOWLEDGEMENTS

This research was supported by the ERC Starting Grant 305123 MORE (Advanced Mathematical Tools for Complex Network Engineering), and by the U.S. National Science Foundation under Grants CNS-1253731 and CNS-1406947.

APPENDIX A PROOF OF LEMMA 1

Proof: For any couple of services c, r ∈ C and any load profile α ∈ C let us define a utility difference function f α c,r : [0, γ] → R as follows:

Basically, f α c,r (•) measures the difference between the utilities that a user of type γ obtain for connecting to service c with respect to r. Notice that ∀ c, r ∈ C, α ∈ C f α c,r (•) is a monotonic function of γ, and f α c,r (γc,r) = 0 implies γc,r = pc-pr gc(α)-gr (α) . Proving the lemma is equivalent to proving that ∀γ ∈ [0, γ] , f α c,r (γ) > 0. In the case in which gc(α) ≥ gr(α) and pc < pr, f α c,r (γ) is a non-decreasing function of γ, which f α c,r (0) > 0, hence ∀ γ ∈ [0, γ] , f α c,r (γ) > 0. In the case in which gc(α) > gr(α) and pc ≤ pr, f α c,r (γ) is an increasing function of γ, which f α c,r (0) ≥ 0, hence ∀ γ ∈ ]0, γ] , f α c,r (γ) > 0. Therefore ∀ γ ∈ ]0, γ] , U (γ) c (α) > U (γ) r (α), from the definition of BR in Definition 5, ∀ γ ∈ ]0, γ] , BR (γ) = r, hence Rr(BR) = 0, i.e., α

(1) r = 0.

APPENDIX B PROOF OF LEMMA 2

Proof: By using f α c,r (γ) as defined in [START_REF] Weibull | Evolutionary Game Theory[END_REF], proving the statement is equivalent to proving that ∀γ > γc, f α c,r (γ) > 0. From the assumption that c ∈ Ŝ(γc) (α), we have f α c,r (γc) ≥ 0. From the assumption that gc(α) > gr(α), we obtain that f α c,r (γ) is a monotonically increasing function in γ. Therefore, γ > γc implies that f α c,r (γ) > 0.

APPENDIX C PROOF OF THEOREM 3

Proof: Let γe * n , e * n , En be defined as in [START_REF] Shetty | Economics of femtocells[END_REF]. From Lemma 1, restricting the set of eligible BS as in [START_REF] Ren | Data demand dynamics in wireless communications markets[END_REF] does not affect the generality of the formulation. From Lemma 2, ∀n ∈ N restricting the set of eligible BS from En-1 to En when evaluating γn and e * n does not affect the generality of the theorem.

Making use of the function f α e,r defined in [START_REF] Weibull | Evolutionary Game Theory[END_REF], proving the theorem is equivalent to prove that

price wise in an increasing order and that prices do not change from

As a consequence we focus only on the services which belong to C B . We proceed by induction. Let us define the proposition P :

It is easy to show that P0 is true, since we assumed that α A 0 ≥ α B 0 , and from the definition of service 0 we have that g A 0 = g B 0 = 0. To complete the proof, let us assume P to be true ∀ ∈ C, < n, and let us show that Pn is true.

If

is sufficient to prove the thesis, since from H1 (33 The first case is absurd.

Reconstructing the chain of inequalities, we obtain g B n ≤ g B b , that, from Lemma 2 implies n ∈ C B , which is absurd.

In the second case, we have that g A n > g A b and I A (n, b) > I A (r, b). As we have already stated, (31) implies that

where both parts of the first inequality are positive since from n ∈ C B we have that g

APPENDIX F PROOF OF THEOREM 7 Proof: Let us consider two different load profiles α A = α A 0 , . . . , α A C and α B = α B 0 , . . . , α B C and let us assume α A 0 ≥ α B 0 . Any QoS function respecting conditions (i) -(iv) can be written as

where fc : [0, 1] → R is a function such that ∂gc ∂αc = dfc dαc . Then, for any arbitrary service c ∈ C \ {0} it results that:

From (36) we can write:

where the passage between (39) and ( 40) is justified by the fact that ∀α ∈ C it results ∈C\{0} α = 1 -α0, and the passage between (40) and ( 41) is justified from the assumptions that α A 0 ≥ α B 0 and mc ≤ 0.

If gc α A ≤ gc α B then from (36) we have

From the assumptions that mc ≤ 0 and

, hence from Theorem 6 the game GF admits only one equilibrium.

APPENDIX G PROOF OF THEOREM 8

Proof: Let us begin by distinguishing two cases: (i) ∃ limn→∞ α (n) ; (ii) limn→∞ α (n) . In the first case, Banach fixed-point theorem, and the continuity of F (•) guarantee that limn→∞ α (n) = α * . Indeed, if F (•) is continuous then also G(•) is continuous, since is a composition of continuous functions. Let us denote as e the converging point, that is: limn→∞ α (n) = e, therefore, we have:

The passage from (43) and ( 44) is giustfied by the continuity of G(•). Since, by definition, limn→∞ α (n) = e we have e = G(e) which means that e is a fixed-point of G(•) and, thus, of F (•). Therefore, if there exists a limit, (i.e., if the algorithm converges) it converges to a fixed point. Notice that, the existence of the limit can also be expressed as: ∃α * ∈ W : limn→∞||α -α * || = 0. In the second case, let us define a distance sequence as

The thesis, thus, amounts to prove that ∃N : ∀n > N, dn ≤ λK 2C . We divide the proof in two steps: first, we prove that ∃N : dN ≤ λK( 1 2ζ ), second, by using Lemma 5, we show that ∀n > N dn ≤ λK( 1 2ζ + 1). Notice that:

• with no loss of generality, we assume α (0) to be any α ∈ A such that d0 > λK( 1 2ζ ), since otherwise the thesis results immediately proven,

• dn > λK 2ζ implies, from Theorem 9, dn+1 < dn, i.e., ∀n : dn > λK 2ζ , the sequence {dn} is monotonically decreasing. We shall prove that ∃N : dN ≤ λK 2ζ reasoning ad absurdum. Let us, thus, assume that N : dN ≤ λK 2ζ , then {dn} ∞ 0 is a monotonically decreasing sequence, hence it has a limit. That is limn→∞dn = d, which we assume to be d > λK 2ζ . We recall that for (63) and Lemma 3, we have that

thus, by using α (n) = G(α (n-1) ), dn = ||α (n) -α * || and defining an = ||G(α (n-1) ) -α (n-1) || we can write

The sequence an is bounded, since 0 < an ≤ λK. Thus, from the Bolzano-Weierstrass theorem there exists a subsequence of an which converges inside the boundaries. That is

12 in [START_REF] Prakash | [END_REF] insures that all the subsequences of a convergent sequence converge to the same limit, which means lim k→∞ d b k = d. We can then write (47) as:

and passing at the limit, we get d 2 = d 2 + a (a -2ζd) . This implies that, either a -2ζd = 0 or a = 0. In the first case, we would have d = a 2ζ , and since a ≤ λK then we have d ≤ λK 2ζ which contradicts the assumption that d > λK 2ζ . If a = 0, this means lim k→∞ ||G(α (b k ) )α (b k ) || = 0. This means lim k→∞ α (b k ) ∈ W, thus the algorithm has converged to a fixed point which contradicts the assumptions.

APPENDIX H PROOF OF THEOREM 9

In order to prove this Theorem, we first show some useful Lemmas.

Proof: By substituting [START_REF] Roughgarden | How bad is selfish routing?[END_REF] in G(α) -α, we have :

then, it results that 2 and, from the polarization identity 7

APPENDIX I SKETCH OF THE PROOF OF CONJECTURE 1

Proof: It is possible express the equilibrium as the result of a sufficient number of iterations of [START_REF] Roughgarden | How bad is selfish routing?[END_REF], that is α * (p) = α (T ) , where T is a large enough number of iterations.

Let us define γ (t) as the thresholds vector underlying the t-th iteration of the Krasnosielkij algorithm α (t) .

For any arbitrary α (t-1) , Theorem 3 implies that any arbitrary nth element of γ (1) is expressed from (8), more precisely γ

which is a continuous function of any price vector. Furthermore, the function Γ(•) is continuous, being an integral function. Hence, ∀ e ∈ E, α(t) e = Γ(γ f ) -Γ(γe) is continuous w.r.t. the pricing vector. Hence, ∀ t ∈ N