Veeraruna Kavitha

Eitan Altman

R El-Azouzi

Rajesh Sundaresan

Fair scheduling in cellular systems in the presence of noncooperative mobiles

We consider the problem of 'fair' scheduling the resources to one of the many mobile stations by a centrally controlled base station (BS). The BS is the only entity taking decisions in this framework based on truthful information from the mobiles on their radio channel. We study the well-known family of parametric α-fair scheduling problems from a gametheoretic perspective in which some of the mobiles may be noncooperative. We first show that if the BS is unaware of the noncooperative behavior from the mobiles, the noncooperative mobiles become successful in snatching the resources from the other cooperative mobiles, resulting in unfair allocations. If the BS is aware of the noncooperative mobiles, a new game arises with BS as an additional player. It can then do better by neglecting the signals from the noncooperative mobiles. The BS, however, becomes successful in eliciting the truthful signals from the mobiles only when it uses additional information (signal statistics). This new policy along with the truthful signals from mobiles forms a Nash Equilibrium (NE) which we call a Truth Revealing Equilibrium. Finally, we propose new iterative algorithms to implement fair scheduling policies that robustify the otherwise non-robust (in presence of noncooperation) α fair scheduling algorithms.

I. INTRODUCTION

Short-term fading arises in a mobile wireless radio communication system in the presence of scatterers, resulting in time-varying channel gains. Various cellular networks have downlink shared data channels that use scheduling mechanisms to exploit the fluctuations of the radio conditions (e.g. 3GPP HSDPA [START_REF]Technical Specification 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; High Speed Downlink Packet Access (HSDPA); Overall description; Stage 2[END_REF] and CDMA/HDR [START_REF] Bender | CDMA/HDR: A bandwidth-efficient high-speed wireless data service for nomadic mobiles[END_REF] or 1xEV-DO [START_REF]1xEV:1x Evolution IS-856 TIA/EIA Standard Airlink Overview[END_REF]). A central scheduling problem in wireless communications is that of allocating resources to one of many mobile stations that share a common radio channel. A lot of attention has been given to the design of efficient and fair scheduling schemes that are centrally controlled by a base station (BS) whose decisions depend on the channel conditions of each mobile. These networks use various fairness criteria ( [9], [START_REF] Altman | Generalized Nash Bargaining Solution for bandwidth allocation[END_REF]) called generalized α-fair criteria to design a class of parametric scheduling algorithms (which we henceforth call as α-fair scheduling algorithms or α-FSA). One special case, proportional fair sharing (PFS), has been intensely analyzed as applied to the CDMA/HDR system. See [START_REF] Chaponniere | Transmitter Directed code division multiple access system using path diversity to equitably maximize throughput[END_REF], [START_REF] Bender | CDMA/HDR: A bandwidth-efficient high-speed wireless data service for nomadic mobiles[END_REF], [START_REF] Andrews | Scheduling in a queueing system with asynchronously varying service rates[END_REF], [START_REF] Shakkottai | Scheduling algorithms for a mixture of real-time and non-real-time data in HDR[END_REF], [START_REF] Agrawal | Class and channel condition based weighted proportional fair scheduler[END_REF], [START_REF] Borst | Dynamic rate control algorithms for HDR throughput optimization[END_REF], [START_REF] Liu | A framework for opportunistic scheduling in wireless networks[END_REF]. These results are applicable to the 3GPP This project was supported by the Indo-French Center for the Promotion of Advanced Research (IFCPAR), project 4000-IT-1 and by the INRIA association program DAWN. The French co-authors have also been supported by the Bionets European project and the RNRT-ANR WiNEM project.

HSDPA system as well. Kushner & Whiting [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF] analyzed the PFS algorithm using stochastic approximation techniques and showed that the asymptotic averaged throughput can be driven to optimize a certain system utility function (sum of logarithms of offset-rates). See also Stolyar [25].

The BS is the only entity taking decisions in all the above methods, and the BS depends crucially on truthful reporting of their channel states by the mobiles. For example, in the frequency-division duplex system, the BS has no direct information on the channel gains, but transmits downlink pilots, and relies on the mobiles' reported values of gains on these pilots for scheduling. A cooperative mobile will truthfully report this information to the BS. A noncooperative mobile will however send a signal that is likely to induce the scheduler to behave in a manner beneficial to the mobile.

Examples of nonstandard, noncooperative, and aggressive transmission behavior is reported in WLANs. For example, Mare et al. ( [START_REF] Mare | Experimental validation of analytical performance models for IEEE 802.11 networks[END_REF]) report that certain implementations attempt more frequently than the specifications in the IEEE 802.11 standard. Bianchi et al. ( [START_REF] Bianchi | Experimental Assessment of the Backoff Behavior of Commercial IEEE 802.11b Network Cards[END_REF]) also report noncooperative behavior. This is presumably because the particular equipment provider wants to make its devices more competitive. Such behavior may occur in any system that uses an opportunistic scheduler in the downlink to profit from multi-user diversity (e.g., HSDPA, EV-DO). For instance, a noncooperative mobile can modify their 3G mobile devices or laptops 3G PC cards, either by using Software Development Kit (SDK) (see [START_REF]Novatel Merlin u870 PC Card[END_REF]) or the device firmware [START_REF] Tuna | Hacking EVDO[END_REF], in order to usurp time slots at the expense of cooperative mobiles, hence denying them network access. Users of future devices and software hackers may have the ability to reprogram their mobile devices to gain scheduling advantage.

In [START_REF] Kavitha | Opportunistic scheduling in cellular systems in the presence of non-cooperative mobiles[END_REF], [START_REF] Kavitha | Opportunistic scheduling in cellular systems in the presence of non-cooperative mobiles[END_REF] we analyzed efficient scheduling (the special case with α = 0, wherein the scheduler maximizes the sum throughput at the BS) in presence of noncooperation by modeling the interaction as a signaling game ( [START_REF] Sobel | Signaling Games, To appear in Encyclopedia of Complexity and System Science[END_REF]). In this paper, we consider the α-fair schedulers with α > 0, where fairness is also an important concern. The signaling game cannot be used here because, the utilities of the BS are not expected utilities but are concave combinations of the users' expected utilities. Further, α-fair scheduler (with α > 0) has an inherent feedback feature (more details in section II) that makes the study difficult and different from the efficient scheduling ( [START_REF] Kavitha | Opportunistic scheduling in cellular systems in the presence of non-cooperative mobiles[END_REF], [START_REF] Kavitha | Opportunistic scheduling in cellular systems in the presence of non-cooperative mobiles[END_REF]) case. This paper has contributions to three main areas:

Networking Aspects: (1) When the base station is unaware of the noncooperative behavior, we identify cases where noncooperation results in an unfair bias in the channel assignments in favor of noncooperative mobiles. [START_REF] Mare | Experimental validation of analytical performance models for IEEE 802.11 networks[END_REF] We characterize the limitation of the base station (BS), and obtain the conditions under which fair sharing is not possible even when the BS is aware of noncooperation. [START_REF]Novatel Merlin u870 PC Card[END_REF] We show that the ability to achieve fair sharing, in the presence of noncooperation, depends on the parameter α. (4) We design robust iterative algorithms that, under suitable conditions, fairly share the resources even in the presence of noncooperative signaling.

Game theoretical modeling: [START_REF] Bianchi | Experimental Assessment of the Backoff Behavior of Commercial IEEE 802.11b Network Cards[END_REF] We model a noncooperative mobile as a rational player that wishes to maximize its throughput. Since the α-fair assignment is related to the maximization of a related utility function, one can view the BS as yet another player. We thus have a game model even if there is a single noncooperative mobile. (2) We formulate three games of which one is a concave game. The formulation of the games turn out to be surprisingly complex. Except for the special case of α = 0 (where the game can be shown to be equivalent to a matrix game), the games are defined over an infinite set of actions. Despite the complexities we prove the existence of equilibria and characterize them for two games. [START_REF]Novatel Merlin u870 PC Card[END_REF] The third game arises when the BS is unaware of noncooperation. BS only responds to the mobiles, but in an optimal way. We model this as a noncooperative game with noncooperative mobiles as the only players. The BS optimizes the same utility being unaware of the strategic behavior of the mobiles, however the utility also depends upon mobiles signals. The mobiles are aware of BS optimization procedure and play to maximize their own utilities. [START_REF]1xEV:1x Evolution IS-856 TIA/EIA Standard Airlink Overview[END_REF] To analyze iterative algorithms, we consider a noncooperative game with asymptotic time limits (which equal average values of certain quantities) of the iterative algorithm as cost criteria.

Design of networking protocols based on stochastic approximation techniques: (1) We show that the existing α-fair scheduling algorithms ( [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF]) fail in the presence of noncooperation. [START_REF] Mare | Experimental validation of analytical performance models for IEEE 802.11 networks[END_REF] Using the extra knowledge of type statistics, we provide a modification that is robust to noncooperation. (3) While our focus is on the downlink of a wireless network, the same techniques are applicable in any allocation setting where fairness is of concern.

The robust policies require the additional knowledge of channel statistics. Estimating the channel statistics is well studied in many papers. For example, in FDD systems, average channel state is available if we assume that the BS is aware of the location of the mobile, and if we assume that the state distribution is a function of the location only. In TDD systems, the BS may be able to make uplink measurements and apply it to downlink, thanks to uplink-downlink duality. These do not depend on whether the mobile is cooperative or not. The channel distribution can then be deduced from the measured attenuation of a beacon whose power is known.

We finally end this section by motivating the problem using a simple example.

A Motivating example

We consider two users sharing a common channel. User 1 has two channel states with utilities 7 and 3 occurring with probabilities 0.33 and 0.67 respectively. User 2 has constant channel with utility 4. The BS has to assign the channel to one of the two users for every realization of the channel state and every such assignment rule results in a pair of users' average utilities. The BS uses an α-fair scheduler (described in the next section) to allocate the channel resources. First we assume that both users cooperate and report their individual channel states correctly. In Figures 1 and2 (see the curves with δ = 0, δ is a noncooperation parameter and will be introduced in the next paragraph) we plot the average utilities obtained by users under α-fair scheduler as a function of the fairness parameter α. We make the following observations: (1) For every α, the BS always allocates the channel to user 1 if he is in good state. (2) For α = 0, the expected share of user 1 (7 × 0.33) is less than that of the user 2 ((1 -0.33) × 4). This corresponds to efficient scheduling point. ( 3) For small values of α, BS allocates the channel to user 1 only when he is in good state. [START_REF]1xEV:1x Evolution IS-856 TIA/EIA Standard Airlink Overview[END_REF] The expected share of user 1 increases while that of user 2 decreases as α increases, and eventually the shares become equal. To achieve this, the BS starts allocating the channel to the user 1, even when that user is in the bad state with increasing probability.

The above scenario depends crucially upon the truthful reporting of channel by the user 1. Now, suppose that user 1 is noncooperative, wishes to increase his utility, and declares to be in good state 7 with probability δ when actually in bad state 3. BS now observes the "good channel" signal from user 1 with higher probability 0.33 + δ × 0.67 and will schedule as before but based on reported channel conditions. In Figures 1,2 we plot the resulting expected utilities of both the users as a function of fairness α for δ = 0.1, δ = 0.5 respectively. We observe that the utility of user 1 for small values of α is improved in comparison with its cooperative utility. This also reduces the utility of the user 2 below its cooperative share, resulting in unfair allocations. In game theoretic terms, reporting the truth is not an equilibrium. This holds for all values of α ≤ 1.75, α ≤ 6.85, respectively, for δ = 0.5, δ = 0.1. However, for α greater than the above values, user 1 loses; in fact its utility gets below its cooperative share, while that of the user 2 is much above its cooperative share. The above example indicates that the α-fair scheduler: (1) might be robust against noncooperation for large values of α; (2) fails for smaller values of α; (3) the larger the δ the larger the amount of gain at α = 0; (4) the larger the δ the smaller the α till which the mobile gains; [START_REF]Technical Specification 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; High Speed Downlink Packet Access (HSDPA); Overall description; Stage 2[END_REF] The above observations suggest also that the only scheduler robust to all kinds of noncooperation (here δ > 0) is max-min fair scheduler (α = ∞.) The study of this noncooperation and design of robust policies is the focus of our paper.

II. THE PROBLEM SETTING AND α-FAIR SCHEDULER

We consider the downlink of a wireless network with one base station (BS). There are M mobiles competing for the downlink data channel. Time is divided into small intervals or slots. In each slot, one of the M mobiles is allocated the channel. Each mobile m can be in one of the states h m ∈ H m , where H m is a finite valued set. We assume fading characteristics to be independent across the mobiles. Let h := [h 1 , h 2 , • • • , h M ] T be the vector of channel gains in a particular slot. The channel gains are distributed according to: p h (h) = M i=1 p hi (h i ), where {p hm ; m ≤ M } represent the statistics of the mobile channels. When the mobile's channel state is h m , it can achieve a maximum utility given by f (h m ). An example of utility is the rate

f (h m ) = r(m) = log(1 + h 2 m SNR)
where SNR captures the nominal received signal-to-noise ratio under no channel variation.

In every slot, the BS has to make scheduling decisions, i.e., allocate the downlink slot to one of the M users, based on the current realization of the channel state vector h. For any set C, let P(C) be the set of probability measures on C. A BS's decision is a function β that assigns to any given h an element in P({1, 2, • • • , M }), the probability distribution over the set of users. Thus β(m|h) is the probability that the BS schedules current slot to mobile m given channel state vector h. One can view β, the scheduling policy, as a vector in R B space 1 , with B := M |H|, where |H| is the cardinality of the product space H = Π M m=1 H m and it takes values in the set:

D = β ∈ R B : M m=1 β(m|h) = 1, β(m|h) ≥ 0 for all h, m .
We introduce the well known generalized α-fair criterion ( [START_REF] Altman | Generalized Nash Bargaining Solution for bandwidth allocation[END_REF]) where the quantity that we wish to share fairly is the expectation of the random (instantaneous) utilities corresponding to the assignment by the scheduler to the mobiles. Required level of fairness (dictated by parameter α) is achieved (see [START_REF] Altman | Generalized Nash Bargaining Solution for bandwidth allocation[END_REF]) by an assignment that maximizes the following function:

G α (β) := M m=1 Γ α (θ m (β)) (1)
where

θ m (β) := E h [f (h m )β(m|h)]
is the expected share of mobile m under policy β, and the α-fair system utility function is

Γ α (u) := log(u), for α = 1 u 1-α 1-α , for α ≥ 0, α = 1.
The objective function G α given by ( 1) is concave and continuous in β for each α, while the domain D is compact and convex. Hence there always exists a cooperative α-fair scheduling BS strategy β * :

β * ∈ arg max β∈D G α (β).
(

) 2
Remarks II-1: We may view the BS's schedule as a static optimization problem that corresponds to a single choice of β. Notice that the optimal schedule β * maximizes some function of the expected shares of utilities. This expected share depends on assignments at all channel states, and is therefore a joint optimization problem. This feature arises when α > 0. When α = 0 the problem is separable, and the solution β * (• | h) for a given h depends only on that h. Indeed, for α > 0, the implicit equation (3) below highlights a certain 'feedback' that is absent in case when α = 0. This makes the present study significantly different from our previous work on efficient scheduling with strategic mobiles ( [START_REF] Kavitha | Opportunistic scheduling in cellular systems in the presence of non-cooperative mobiles[END_REF], [START_REF] Kavitha | Opportunistic scheduling in cellular systems in the presence of non-cooperative mobiles[END_REF]).

Below we show a key (feedback) property of α fair schedulers. Define β * as the vector (fixed point) that satisfies (if it exists) the following:

β * (m|h) = 1 {m∈arg maxj dΓ α (θj (β * ))f (hj )} |arg max j dΓ α (θ j (β * ))f (h j )| (3)
where dΓ α (θ j (β)) := dΓ α du u=θj (β) is the derivative of Γ α with respect to (w.r.t.) u evaluated at θ j (β) and arg max is the set of indices that attain the maximum. We now have Lemma 1: If there is a β * satisfying (3), then β * is a global maximizer of the objective function in (2) over domain D and hence is an α-fair scheduler.

Let Θ := [θ 1 • • • θ M ] T , Θ(β) := [θ 1 (β) • • • θ M (β)] T and Θ(D) := {Θ(β) : β ∈ D} . The map Θ → m Γ α (θ m )
is strictly concave. Hence, there exists an unique maximizer (of the expected assigned shares) over the convex set Θ(D):

Θ * = max Θ∈Θ(D) m Γ α (θ m ). (4)
Hence, if there is a β * satisfying (3) then Θ * = Θ(β * ). Further, any β * which is a global maximum of the objective function (2) satisfies the 'efficiency' property: whenever

f (h m ) > f (h ′ m ) either β * (m|h m , h -m ) > β * (m|h ′ m , h -m ) (5)
or

β * (m|h m , h -m ) = β * (m|h ′ m , h -m ) ∈ {0, 1}
for all h -m ∈ Π j =m H j and for all m.

Proof : Please refer to Appendix B.

⋄

Remarks II-2: The assignment for particular state (h m ) for any mobile m increases with the increase in the utility (f (h m )) of the state. This efficiency property is used in the analysis under noncooperation.

Remarks II-3: The solution (3) explicitly shows the feedback we mentioned in Remark II-1. This solution has already been used in practical scenarios ( [START_REF] Lau | Proportional Fair SpaceTime Scheduling for Wireless Communications[END_REF]) to achieve 'fair' scheduling: The α-fair solution for the dynamic setting with ergodic channel states is the optimal β that shares fairly the time average utilities over a single realization of a whole sample path 2 . In fact, the solution (3) under ergodicity can be implemented by the following procedure: 1) At any time slot k, obtain the scheduling decision using the current channel vector h k and using the time averaged assigned utilities obtained till the last step {θ m,k-1 } in place of {θ m (β * )} of (3); 2) Update (in the obvious way) the time averaged assigned utilities up to step k, {θ m,k }, using the current scheduling decision.

A part of Lemma 1, regarding the possible solution (3), when restricted to proportional fairness, is already stated in [START_REF] Lau | Proportional Fair SpaceTime Scheduling for Wireless Communications[END_REF].

Remarks II-4: By observing the α-fair scheduler (3), one can understand the possible ways by which the required level of fairness is achieved: a) efficient scheduler (α = 0) for any given channel state vector realization (h) schedules with equal probability all the users with the highest instantaneous rate, but ignores fairness; b) the scheduler in (3) with α > 0 gives weightage to the deprived users via the gradient of the fair function Γ α before making the scheduling decision; c) the weightage depends upon the fairness index α and the expected utility θ m that the particular user would have obtained; d) the larger the fairness index α, the larger the emphasis on fairness and hence a larger weightage to the users with lesser expected utility. 2 For ergodic channels under appropriate conditions on the function g,

lim K→∞ 1 K K k=1 g(h k ) = E h [g(h)]
We are interested in a particular function g(h) = f (hm)β(m|h) whose average is exactly θm(β).

III. PROBLEM FORMULATION UNDER NONCOOPERATION

In every slot, the BS needs the knowledge of h for scheduling purposes. In practice, mobile m estimates channel h m using the pilot signals sent by BS. We assume perfect channel estimation. The mobiles send signals {s m } to BS, as indications of the channel gains. The BS therefore does not have direct access to channel state h, but instead has to rely on the mobile's signals for the information. If the mobiles are strategic, knowing the allocation policy, they can signal a better channel condition to grab the channel even when their channel condition is bad.

We assume that signals are chosen from the channel space itself, i.e., s m ∈ H m for all mobiles. We shall consider two settings, (1) unaware BS and (2) rational BS.

Unaware BS, Game G1: The BS is unaware of the possible noncooperative behavior from the mobiles and applies the αfair scheduler (2) to the signals s

= [s 1 , • • • , s M ] T (
as if they were the true channel values). The mobiles are aware of BS's scheduling policy and signal to optimize their own goals. We model this as a noncooperative game with noncooperative mobiles as the players.

Rational BS: The BS is modeled as an additional player in a one-shot game. When the BS becomes aware of the possible noncooperation, it could implement better policies. We first consider a M + 1 player game G2, where the BS schedules using only the signals from the mobiles as before. Because of its awareness, however, it could do better than the situation of game G1, but will not be successful in compelling the mobiles to reveal their channel condition truthfully (Section V-A). In Section V-B we construct more intelligent (policies that require more information) BS policies which would be robust against noncooperation: the new robust BS policies and the truthful signals from the mobiles form a Nash Equilibrium. We refer this game as game G3.

We now introduce the important concepts and definitions that are used in the paper. These are more specific to the first two game scenarios. The corresponding definitions and concepts may vary slightly for the game G3 and the differences are explained directly in Section V-B.

Common Knowledge : Channel statistics {p hm ; m ≤ M } of all mobiles is a common knowledge to all the mobiles and the BS. We assume that all the M mobiles are noncooperative and this is a common knowledge to all the agents (see our Infocom paper ( [START_REF] Kavitha | Fair scheduling in cellular systems in the presence of noncooperative mobiles[END_REF]) for a case when only a few of them are strategic). Utilizing our robust scheduling policies (proposed towards the end of the paper), the BS can actually detect the mobiles that are noncooperative and then this knowledge will not be required.

Mobile Policies : A policy of mobile m is a function {µ m ( |h m )} that maps a state h m to an element µ m ( |h m ) in P(H m ), where µ(s m |h m ) represents the probability with which the mobile signals s m when the actual channel state is h m .

BS Policies : A policy of the BS is a function which maps every signal vector s to a scheduler

β ∈ P({1, 2, • • • , M }).
More complicated policies are considered in section V-B and later.

Utilities for a given set of strategies : The instantaneous/sample utility of the mobile m depends only upon the true channel h m and the BS decision β and is given by (see Appendix A):

U m (s m , h m , β) = 1 {β=m} min{f (h m ), f (s m )}. (6)
Define the following to exclude mobile m:

h -m := [h 1 , • • • , h m-1 , h m+1 , • • • , h M ] , p h-m (h -m ) := Π j =m p hj (h j ), µ -m (s -m |h -m ) := Π j =m µ j (s j | h j ).
Also define, µ = {µ m ; m ≤ M } to represent strategy profile:

µ(s|h) := Π 1≤j≤M µ j (s j | h j ).
With the above definitions, each noncooperative user chooses its strategy µ m to maximize its own utility:

U α m (µ, β) = E h s U m (s m , h m , m)β(m | s)µ(s | h) (7)
Under α-fair criterion (1), the natural choice of BS utility is:

U α BS (µ, β) = m Γ α (U α m (µ, β)). (8)
Throughout when arg max S has more than one element, by i = arg max S we mean i ∈ arg max S. By j := arg max S we mean that j is a chosen element of arg max S.

ASA and ATA Utilities : When mobile signals do not match the true channel values, the game under consideration will have two important average utilities for any given pair of strategy profiles (µ, β) : (1) average signaled utilities under assignment β (ASA) utility, which a (more intelligent) BS can observe, and (2) average true and assigned (ATA) utility, which is the true average utility gained by the mobile and whose value cannot be estimated (so long as the mobile is noncooperative) by the BS. These are defined by

U ASA m (µ, β) := E h s f (s m )β(m|s)µ(s|h) (9)
U AT A m (µ, β) := E h s min{f (h m ), f (s m )}β(m|s)µ(s|h) . ( 10
)
From ( 6), [START_REF] Altman | Generalized Nash Bargaining Solution for bandwidth allocation[END_REF] we see that the utility of mobile m is its ATA utility, i.e., U α m (µ, β) = U AT A m (µ, β). Truth Revealing Strategy and the TRE : In the following, by truth revealing strategy at mobile m we mean the strategy

µ T m (s m |h m ) = 1 {sm=hm} for all h m , s m ∈ H m that signals the true channel state. Let µ T := (µ T 1 , • • • , µ T M ).
Under truthful strategies µ T , ATA and ASA utilities coincide. For any BS policy β, if strategy profile (µ T , β) forms a Nash Equilibrium (NE), then we call the NE as a Truth Revealing Equilibrium (TRE).

Cooperative Shares : Best response of BS to truthful signals µ T is any maximizer β * of G α given by (1). By Lemma 1, the best response results in unique maximum average ATA utilities,

θ αc m := θ m (β * ) = U α m (µ T , β * ), (11)
which we will Cooperative Shares.

Contrast between unaware BS and the rational BS: Recall that computing a fair assignment by BS involves maximization of [START_REF] Bianchi | Experimental Assessment of the Backoff Behavior of Commercial IEEE 802.11b Network Cards[END_REF]. Thus in the first scenario, when mobiles choose profile µ, the unaware BS attempts to share ASA utilities in a fair fashion under µ by maximizing [START_REF] Borst | Dynamic rate control algorithms for HDR throughput optimization[END_REF] (see next section). However, what needs to be shared fairly are the ATA utilities. This is achieved via the game perspective, wherein the rational BS tries to share the ATA utilities gained by the mobiles in a fair fashion.

IV. SCHEDULING UNDER NONCOOPERATION : UNAWARE BS, GAME PROBLEM G1

We consider the scenario in which the BS is unaware of the presence of noncooperative mobiles. As in the cooperative setting, the BS allocates the channel (using optimal scheduler (2)) to one of the mobiles. The mobile signals are assumed to reflect the channel state perfectly. Each mobile is aware of BS's scheduling policy and strategies to maximize its utility.

Utilities of G1: For any given mobile strategy profile µ, let the induced signal probabilities be represented by p s , i.e., p s (s) = h p h (h)µ(s|h). Since the BS observes p s (instead of p h ), it assumes the expected shares of mobile m to be θ m (µ, β) := E ps [f (s m )β(m|s)] and hence for the purpose of scheduling, it blindly maximizes,

m Γ α (θ m (µ, β))). ( 12
)
We note that the expected shares θ m (µ, β) are exactly the mobile ASA utilities U ASA m and that the utility (12) maximized by BS can be referred as the ASA utility of the BS U ASA BS (µ, β). We model this as a M -player noncooperative game and study its Nash Equilibrium. Nash Equilibrium for G1: This is a profile µ * which satisfies the following for all m:

µ * m = arg max µm U AT A m µ m , µ * -m , β * (µm,µ * -m ) .( 13
)
where β * µ is the scheduler utilized by the unaware BS, which gets affected by mobiles strategies µ in the following way:

β * µ = arg max β U ASA BS (µ, β). (14)
We now present some examples in which a user m deviates unilaterally from µ T and increases its utility above its cooperative share, resulting in unfair allocations. These examples do not have TRE for G1, i.e., truthful strategy profile µ T is not a Nash Equilibrium of G1. In particular for [START_REF] Borst | Dynamic rate control algorithms for HDR throughput optimization[END_REF], we consider α-fair scheduler given by ( 3). This scheduler is widely used in practice (see Remark II-3).

A. Asymmetric Examples 1) Proportional fair scheduler (α = 1) :

We continue with the motivating example of Section I. User 1 has two states with respective utilities given by rb, b and with r > 1.

The respective probabilities to be in one of these states are p, (1 -p) with p ∈ (1/(1 + r), 1/2). User 2 has a single state with utility a.

Using (3), one can easily estimate β * and {θ m (β * )} to be:

β * (1|a, rb) = 1, β * (2|a, b) = 1, θ 1 (β * ) = rbp and θ 2 (β * ) = a(1 -p). (15)
Note that θ 1 (β * ), θ 2 (β * ) are the mobile's cooperative shares.

It is important to note here that β * satisfying (3) exist only if p ∈ (1/(1 + r), 1/2) because in this case :

dΓ α (θ 1 (β * ))rb = rb rbp > a a(1-p) = dΓ α (θ 2 (β * ))a dΓ α (θ 1 (β * ))b = b rbp < a a(1-p) = dΓ α (θ 2 (β * ))a.
Suppose user 1 signals rb (when actually in state b) with probability q, i.e., µ 1 (rb|b) = q. Then users' maximum ASA rates (note that β * q = β * defined in ( 15)) are:

U ASA 1 (q, β * q ) = rb(p + q), U ASA 2 (q, β * q ) = a(1 -p -q) respectively whenever rb (p + q)rb > a a(1 -p -q) > b rb(p + q) .
With this, the mobile 1 obtains an improved ATA utility

U AT A 1 (q, β * q ) = rbp + bq > θ 1 (β * ), i.e.
, mobile 1 is successful in improving its utility (above its cooperative share) by signaling noncooperatively. The maximum possible value of q is q = (0.5 -p) . ⋄

2) Extension to general α: Computing as before, one can show that an α-fair scheduler satisfying (3) exists, i.e., the fixed point exists, if

(rb) α-1 p α < a α-1 (1 -p) α < r(rb) α-1 p α .
As α increases, the maximum p for which the solution in (3) exists, reduces. Thus given (a, r, b, p), there exists a maximum α max , beyond which there does not exist α-fair scheduler of the type (3). When α-fair scheduler in (3) exists, the noncooperative mobile benefits. Given α, the maximum q(α) with which the mobile can benefit from noncooperation is:

(p + q(α)) α (rb) α-1 = a α-1 (1 -p -q(α)) α .
For example with a = 4, r = 3, b = 3, p = 0.33 the maximum α for which α-fair scheduler in (3) exists is 7.9 and user 1 can benefit by signaling with q = .05 for all α ≤ 4.

3) Generalization to more states and general α: Consider two asymmetric users under the following assumptions: N.1 The cooperative α-fair solution β * in (3) exists and without loss of generality let arg max m θ αc m = 1. N.2 There exists an i > 1 such that,

η := inf h2∈H2 dΓ α (θ αc 1 )f (h 1,i-1 ) -dΓ α (θ αc 2 )f (h 2 ) > 0,
where

H 1 = {h 1,1 , • • • , h 1,N1 } are arranged such that f (h 1,1 ) > f (h 1,2 ) > • • • > f (h 1,N1 ).
Lemma 2: Under N.1-N.2, there exists a signaling policy µ δ 1 for mobile 1 that is not a TRE, i.e., its ATA utility

U AT A 1 (µ δ 1 , (f, β * µ δ 1
)) is larger than its cooperative share θ αc 1 . Proof : The proof is available in Appendix C.

⋄

Remarks IV-A4: Assumptions N.1-N.2 represent an example set of conditions under which the α-fair scheduler fails. The first condition ensures that a scheduler exists. The second condition ensures that there is a channel condition for mobile 1 with an advantage with respect to all the channel conditions of mobile 2. When this happens, mobile 1 can deviate by a positive amount that depends upon the gap η and obtain better utility than its cooperative share.

B. Symmetric Case

We consider a simple symmetric two mobile example. The mobiles have two states with utilities a 1 , a 2 occurring respectively with probabilities p 1 , p 2 . Let a 1 = ra 2 , p 1 = pp 2 with r > 1, p > 0. Under truthful signaling, by Lemma 1, an α-fair optimal BS policy (for any α) is given by:

β * (1|a 1 , a 1 ) = 1/2 = β * (1|a 2 , a 2 ), β * (1|a 1 , a 2 ) = 1, β * (1|a 2 , a 1 ) = 0, with equal cooperative shares θ 1 (β * ) = θ 2 (β * ) = p 2 1 2 + p 1 p 2 a 1 + p 2 2 a 2 2 = p 2 2 a 2 p 2 r + 1 2 + pr .
Without loss of generality say mobile 1 deviates unilaterally from its truthful revelation strategy with µ 1 (a 1 |a 2 ) = t. If mobile 1 was successful, its reported rate would be greater than θ 1 (β * ) which is obtained only when its declared state is a 1 with mobile 2's being a 2 . Thus, mobile 1 will be successful with maximum ASA utilities with α = 1 (user 1 gets allocated always and only when he signals his state as a 1 ):

U ASA 1 = (p 1 a 1 + p 2 ta 1 )p 2 = (p + t)p 2 2 a 1 and U ASA 2 = 1p 1 a 1 + p 2 (1 -t)p 2 a 2 = (pr + (1 -t)p 2 )p 2 a 2
and the corresponding ATA utility,

U AT A 1 = (p 1 a 1 + p 2 ta 2 )p 2 = (pr + t)p 2
2 a 2 if the following conditions are met:

a 1 U ASA 1 > a 2 U ASA 2 and θ 1 (β * ) < U AT A 1 , i.e., if 1 (p + t)p 2 > 1 (pr + (1 -t)p 2 )
and p 2 r + 1 2 < t. ⋄

C. Robustness at large α

For small values of α, α-fair scheduler fails. However we see a different phenomenon at higher α. As α increases to infinity, the 'fairness' increases and the expected shares, i.e., ATA utilities, of all the mobiles tend to become equal ( [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF]) provided all the mobiles signal truthfully. However, in presence of noncooperation, it will be the ASA utilities that tend to become equal for higher values of α. This results in all the cooperative (ATA equal ASA utilities) mobiles getting equal ATA shares which will be bigger than that for the noncooperative (ATA are strictly less than ASA utilities) mobiles. Thus the α-fair scheduler (2) itself becomes more robust towards noncooperation as fairness factor α increases, though not fully unless α = ∞, despite the BS's unawareness of the noncooperation. This effect is seen in the motivating example as well as in Figure 3 given in the later sections. In Figure 3, the noncooperative mobile's ATA utility diminishes as α increases and goes below its cooperative share beyond α = 0.65. Further, the cooperative mobile gets more than its cooperative share for these large values of α.

V. SCHEDULING UNDER NONCOOPERATION : GAME

THEORETIC STUDY In this section the BS knows about noncooperative behavior of mobiles and is considered as an additional player. We thus have an M + 1 player game.

A. BS Scheduling policies of section IV : Game G2

In contrast to section IV, the BS knows that the mobiles are noncooperative. The resulting game is a one-shot concave game: the utility (7) of mobile m is linear in its policy µ m while that of the BS ( 8) is continuous and concave in its policy β. From results in [START_REF] Rosen | Existence and Uniqueness of Equilibrium Points for Concave N-Person Games[END_REF], this game always has a NE 3 As discussed next game G2 has a "Babbling" equilibrium, but does not have a TRE.

1) G2 has Babbling NE : We will now show that this game has a Nash equilibrium where the BS neglects the signals from the noncooperative users. Define a scheduling policy that decides only based on the averaged utilities, i.e.,

β * := arg max [β1,••• ,β M ] m Γ α (β m E[f m ]). (16)
U AT A m (µ * , β) = E[f (h m )]β(m | h),
and hence from ( 16), β * is the best response of U AT A BS under µ * . One can easily see that the utilities U AT A m does not depend upon µ and we have the following lemma: Lemma 3: The pair (µ * , β * ) forms a NE for game G2. ⋄

The NE ((µ * , β * )) is one where BS ignores the signals from the noncooperative mobiles and is similar in sense to the Babbling equilibrium defined in the context of signaling games ( [START_REF] Sobel | Signaling Games, To appear in Encyclopedia of Complexity and System Science[END_REF]). This equilibrium is better than the equilibrium of game G1, because the noncooperative mobiles cannot grab the channel via strategic signaling. However, the BS completely neglects the signals from noncooperative mobiles and the multiuser diversity is lost.

2) G2 has No TRE : We now examine the existence of the desired TRE. The case α = 0 of efficient scheduling was studied in [START_REF] Kavitha | Opportunistic scheduling in cellular systems in the presence of non-cooperative mobiles[END_REF], where, G2 was modeled by a signaling game. It was shown that the game G2 has only Babbling equilibria as NE and hence does not have a TRE. We will now consider the case α > 0 and obtain the following:

Lemma 4: The game G2 has no TRE. Proof: Please refer to Appendix C.

⋄

Thus the BS, even when aware of the noncooperation, is not successful in eliciting truthful signals. In the following we construct more intelligent policies which induce a TRE.

B. Robust BS Policies : Game G3 has TRE

The BS can estimate signal statistics p s after sufficient observation of the mobile signals. We use p s to build robust policies for BS which give us the desired TRE. The BS now makes two decisions: 1) a scheduling decision β as before, which identifies the mobile that would be scheduled in the current time slot; 2) an allocation decision, that identifies the portion φ m of f (s m ) that will be allocated. Via this allocation decision φ m , the BS further controls the average utility assigned to a mobile m so as to ensure that this average does not exceed its cooperative share, θ αc m . The policy of BS now is a mapping that takes every ordered pair of signal and signal statistics (s, p s ) to an ordered pair (Φ, β) = {(φ m (s, p s ), β(•|s))}. All the utilities will change appropriately to include Φ. For example,

U α m (µ, (Φ, β)) = E h s min{φ m (s, p s ), f (h m )}µ(s|h)β(m|s) . A profile (µ * , (Φ * , β * )) is a NE for the game G3 if µ * m = arg max µm U α m ((µ m , µ * -m ), (Φ * , β * )), for all m (Φ * , β * ) = arg max (Φ,β) U α BS (µ * , (Φ, β)). (17)
When the BS knows the signal statistics, {p s }, it can estimate the ASA utilities for any scheduling policy and for any mobile profile µ because:

U ASA m (µ, (Φ, β)) = U ASA m (p s , (Φ, β)):=E s [φ(s, p s )β(m|s)] ,
where we have abused notation to show that U ASA m depends on µ only through p s . The expectation in E s is with respect to p s . The BS can also estimate the mobiles' cooperative shares {θ αc m } of (11) using its prior knowledge of the channel statistics. We now propose a robust policy at the BS which uses both these average utilities. The key idea is to design a policy at the BS which does not allow the (average) utility of any mobile m to be greater than θ αc m . When a noncooperative mobile uses a signaling strategy to improve its ATA utility U AT A m , even its ASA utility U ASA m improves. For each mobile m, the BS can estimate ASA utility U ASA m and sense the increase in it with respect to the cooperative share, θ αc m . The BS can ensure none of the mobiles is allocated more than its corresponding cooperative share, by allocating only a fraction and not the total signaled utility at every sample. The fraction to be allocated, is set based on the present excess over the cooperative share:

φ m (s m , p s ) := f (s m ) -U ASA m -θ αc m ∆ (18)
for some large value of ∆. Hence, to ensure that none of the mobiles get more ASA utility than its cooperative share, BS chooses Φ = {φ m } to satisfy the following:

U ASA m (p s , (Φ, β)) = E s φ m (s m , p s )β(m|s)1 {φm(sm,ps)>0} . (19)
Equation ( 19) is satisfied by every fixed point of the mapping

Θ → Υ(Θ), where Υ(Θ) := [γ 1 (Θ) • • • , γ M (Θ)] with γ m (Θ) := E s fm (s m , θ m )β(m|s)1 { fm>0} fm (s m , θ m ) := f (s m ) -∆(θ m -θ αc m
) for all m, and one is interested in the fixed points of the positive orthant.

Lemma 5: (i) The function Θ → Υ(Θ) has a fixed point in the positive orthant for every β, ∆ and µ.

(ii) For any α-fair scheduler β * given by ( 2) and for truthful signaling µ = µ T , Θ αc is the unique fixed point of Υ.

(iii) At any fixed point Θ * of Υ, and for any profiles µ, β:

θ * m ≤ θ αc m + O(1/∆) for all m. Proof: Please see Appendix C.

⋄

By the above lemma, the function Υ has at least one fixed point in positive orthant for every (µ, β). Consider one such fixed point Θ * and define allocation control using equation [START_REF] Kavitha | Fair scheduling in cellular systems in the presence of noncooperative mobiles[END_REF] wherein U ASA m is replaced by θ * m . With this allocation, the ASA utility of mobile m would indeed be θ * m and its ATA utility equals:

U AT A m (µ, (Φ, β)) = (20) E h,s f gain m (h m , s m , p s , β)β(m|s)1 {φm>0} f gain m (h m , s m , p s , β) := min{f (h m ), φ m (s m , p s )}.
Note that f gain m ≤ φ m and hence by [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF] and Lemma 5.(iii),

U AT A m (µ, (Φ, β)) ≤ U ASA m (µ, (Φ, β)) ≤ θ αc m + O(1/∆).
In other words, with the allocation [START_REF] Kavitha | Fair scheduling in cellular systems in the presence of noncooperative mobiles[END_REF] at BS, no mobile can gain O(1/∆) more than its cooperative share for any pair (µ, β).

Further, if BS uses any α-fair scheduler β * of (2), then by Lemma 5.(ii), Θ αc is the unique fixed point under truthful strategies (µ T ) and then it is easy to check using [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF] and [START_REF] Lau | Proportional Fair SpaceTime Scheduling for Wireless Communications[END_REF] and p s = p h that:

U ASA m (µ T , β * 1 ) = U AT A m (µ T , β * 1 ) = θ αc
m for all m. We have thus proved the following result:

Theorem 1: If BS knows cooperative shares Θ αc and the signal statistics {p s }, the M + 1 player strategic game has

µ T , ({φ m (s m , p s )} , β * (m|s))
as an ǫ-NE 4 , i.e., G3 has a TRE.

⋄

Till now, we looked at policies that were defined via some fixed points. One needs a method to calculate these fixed points and thereby practically implement the policies. In the coming sections, we will turn our attention to practical and iterative α-fair scheduling algorithms, which achieve precisely this computational goal. We begin by first studying α-FSA proposed and analyzed in [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF]. It is already known that this algorithm converges to cooperative shares when all the mobiles are cooperative (see [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF] and the same is also summarized in the next section). We will analyze under noncooperation, utilizing the results already derived in this paper and show that α-FSA fails under cooperation (in section VI) and then propose a robust modification of it (in section VII).

VI. FAIR SCHEDULER ALGORITHM (α-FSA)

From this section onwards the channel states h as well as the signaled states s (the states reported by the mobiles) are continuous random variables with stationary rates across time,

{r m,k } k≥1 = {f (h m,k )} k≥1 , {r s m,k } k≥1 = {f (s m,k
)} k≥1 for all m, satisfying the assumptions of Appendix D 5 .

This section and the coming section use various types of rates and hence the notations become complicated. Thus a table (in table III) of notations specific to these two sections is given in Appendix D, where all the rate notations are listed at one place.

By assumption A.3 of Appendix D, the rates are integrable and hence the mapping

Θ → [E h [f (h 1 )β(1|h, Θ), • • • , E h [f (h M )β(M |h, Θ)] , with β(m|h, Θ) = 1 {m=arg maxj dΓ α (θj )f (hj )} |{arg max j dΓ α (θ j )f (h j )}|
:= θ α 1,k , • • • , θ α M,k and r k := [r 1,k , • • • , r M,k ].
The algorithm is:

θ α m,k = θ α m,k-1 + ǫ k I α m (r k , Θ α k-1 )r m,k -θ α m,k-1 I α m (r, Θ) = 1 {m=arg maxj dΓ α (dj +θj )rj } (21) = 1 {m=arg maxj rj (θj +dj ) -α } 4 An ǫ-NE is a strategy profile that is within an additive ǫ of a NE, i.e., U α m ((µ * m , µ * -m ), β) > U α m ((µm, µ * -m ), β)
ǫ for all µm. 5 For understanding the asymptotic limits of the dynamic algorithms of this section we will need the results corresponding to the static settings of Section II. But, all the results of Section II correspond to discrete channel states and rates. We assume that for the more general case under study in this section, an α-fair solution of the form (3) exists and that the corresponding shares {θ αc m }are unique as in Lemma 1. Sufficient conditions for this to occur are under study. This result is required for showing that α-FSA asymptotically converges to the cooperative shares (i.e., limits maximize the α-fair criterion) for all α. In [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF] Theorem 2.3 does this job, at least approximately, for α ≤ 1: any other assignment rule results in a limit Θ with m Γ α (θm) less than that corresponding to scheduler {I α m } of α-FSA [START_REF] Liu | A framework for opportunistic scheduling in wireless networks[END_REF]. The simulations of this section further support our assumption.

where d m are small positive constants added for stability and ǫ k = ǫ/(k + 1) for some ǫ > 0. While making decisions {I α m }, if there are more than one users attaining maximum, one of the maximizers is chosen by the BS randomly. In [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF]Th. 2.2], the authors show that {θ α m,k } of ( 21), with α ≤ 1, converges weakly to the unique limit point Θ * that satisfies E [r m I α m (r, Θ * )] = θ * m for all m. A close look at this limit point (when we neglect {d m }) reveals that I α m (r, Θ * ) is the α-fair scheduler (3) and that Θ * are the unique cooperative shares, {θ m (β * )} = {θ cα m }. Thus, α-FSA weakly converges to the unique point (cooperative shares) that maximizes the α-fair criterion [START_REF] Bianchi | Experimental Assessment of the Backoff Behavior of Commercial IEEE 802.11b Network Cards[END_REF].

A. Convergence of α-FSA in the presence of noncooperation

The (unaware) α-FSA uses signaled rates r s m,k := f (s m,k ) and

r s k = [r s 1,k , • • • , r s M,k ]
T , in place of the corresponding true quantities r k , to make decisions as in Section IV. Here the algorithms take the form:

θ α m,k = θ α m,k-1 + ǫ k I α m (r s k , Θ α k-1 )r s m,k -θ α m,k-1 .
The signaled rates reflect the statistics p s (instead of p h ).

Weak convergence to an attractor can be shown (as in [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF]), however the limit is a different attractor, corresponding to p s . It is very easy to see as in Section IV that, when mobiles are noncooperative with profile µ, α-FSA converges weakly to unique maximum ASA rates U ASA m (µ, β * µ ) with β * µ , the best response to µ given by [START_REF] Borst | Dynamic rate control algorithms for HDR throughput optimization[END_REF].

B. Failure of α-FSA in presence of noncooperation

As noted above, the α-FSA (21) converges to the maximum ASA utility (under µ) which need not equal the ATA utility in the presence of noncooperation. However, to understand the behavior of ( 21) in presence of noncooperation, one needs to study the asymptotic true utilities gained by the mobiles under [START_REF] Liu | A framework for opportunistic scheduling in wireless networks[END_REF]. Towards this, we consider a second iteration running in parallel with [START_REF] Liu | A framework for opportunistic scheduling in wireless networks[END_REF], wherein the instantaneous signaled utility r s m,k is replaced by the true instantaneous utility gained by the mobile rm,k :

= min{r m,k , r s m,k }, i.e., θα m,k = θα m,k-1 + ǫ k I α m (r s k , Θ α k-1 )r m,k -θα m,k-1 . (22)
As in [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF], one can show that θm,k converges weakly to the ATA utility

U AT A m (µ, β * µ ), under (µ, β * µ )
. Thus, the asymptotic limits of α-FSA equal the maximum ASA utilities of section IV while the true utility adaptation [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF] converges to the corresponding ATA utilities. These time limits will thus have all the properties of section IV: the α-FSA will fail for small α and will be robust for large α as discussed in section IV. The only difference here is that the channel rates are continuous.

C. Numerical examples

In this section, via some numerical examples, we further illustrate that α-FSA fails under noncooperation. Two asymmetric users are considered in Figure 3. Let Z(σ 2 ) be a Rayleigh random variable with density f Z (z; σ 2 ) = ze -z 2 /2σ 2 . Channel state of User 1 is conditional Rayleigh distributed, i.e.,

h 1 ∼ f Z (z; 0.5)1 {z≤2} dz P (Z(0.5) ≤ 2) .
User 2 has a more diverse channel,

h 2 ∼ f Z (z; 1)1 {z≤2} dz P (Z(1) ≤ 2) .
The utilities are the achievable rates f (h) = log(1 + h 2 ). User 1 is noncooperative and utilizes a signaling strategy mapping h ! → s 1 (h 1 ). The utility indicated by the signals from User 1 equals: f (s 1 (h)) = f (h)(1-δ)+2δ with δ = 0.9. We plot the limit of the α-FSA, the limits of true utility adaptation ( 22) as a function 6 of α. For User 2, who is cooperative, we plot only one curve as the ATA and ASA utilities coincide. We also plot the cooperative shares obtained by the limits of α-FSA, i.e., the limits with δ = 07 . We observe that the cooperative shares tend towards equal values as α → ∞. User 1 is successful in gaining more (ATA) utility in comparison with its cooperative share for all α less than 0.65. Beyond 0.65, User 1 actually loses and the loss increases as α increases. The observations are similar to that in the motivating example and indicate that α-FSA is robust only for large α.

In table I, we consider a symmetric example. We consider the discrete channels of section IV. This example is considered in order to demonstrate that α-FSA works/fails as already explained in this section even for the examples with discrete channel states. We consider two users, both of them having two channel states with utilities a 1 = 4, a 2 = 2 occurring with probabilities p 1 = 0.3, p 2 = 0.7 respectively. In this example we work only with α = 1, i.e., the proportional fair scheduler. Both users have equal cooperative share, θ 1 (β * ) = θ 2 (β * ) = 1.51. Hence when both the mobiles report the channel states truthfully, under α-FSA scheduler, the asymptotic throughputs of both the mobiles converge to 1.51, i.e., lim k→∞ θ m,k = 1.51 for m = 1, 2. Hence maximum proportionally fair BS (asymptotic) utility is U * BS = 2 log(1.51) = 0.824. Suppose now that User 1 becomes noncooperative with µ 1 (a 1 |a 2 ) = t. We see that the User 1 is successful in grabbing the channel more often and increasing its utility in comparison to its cooperative share. The greater the inflationary signaling (the larger the value of t) the more he gains (look at the asymptotic throughput U AT A 1 in the second column in table I). He gains up to 12.5% more than its cooperative share. The cooperative user, User 2, looses due to the presence of the noncooperative mobile resulting in unfair allocations. , δ = 0 Mobile 1, ATA, δ = 0.9 Mobile 2, ATA = ASA, δ = 0.9 Mobile 1, ASA, δ = 0.9 Fig. 3. α-FSA: ASA and corresponding ATA shares versus α. Mobile 1 is noncooperative when δ > 0. We saw that α-FSA fails in the presence of noncooperative users. Hence, we propose a robustification of α-FSA against noncooperation using the policies of subsection V-B. In V-B, we proposed BS policies robust against noncooperation and in this section we propose stochastic approximation based algorithms to converge towards the ASA utilities of the policies given by [START_REF] Lau | Proportional Fair SpaceTime Scheduling for Wireless Communications[END_REF] . The policy of section V-B requires knowledge of signal statistics p s , which has to be estimated. The methods described in this section combine estimation and control using stochastic approximation based methods, as done by α-FSA. We will show robustness of these policies by using appropriate game theoretic tools as well as the results from the theory of stochastic approximation.

µ 1 (a 1 |a 2 ) (U AT A 1 , U AT A 2 ) m U AT A m m log(U AT A m ) 0 (Coop) (1.

A. Robust Policy 1

We now propose a robustification of ( 21) against noncooperation in the following update algorithm:

θ α m,k+1 = θ α m,k + ǫ k φ α m,k+1 I α m r s k+1 , Θ α k -θ α m,k , (23)
φ α m,k+1 = max 0, r s m,k+1 -θ α m,k -θ αc m ∆ , (24) θ α m,0 = θ αc m , (25)
where the decisions I α m (r, Θ) are same as those in α-FSA [START_REF] Liu | A framework for opportunistic scheduling in wireless networks[END_REF], but only the allocations

Φ α k := [φ α 1,k , • • • , φ α M,k ]
T are made robust. As in the case of α-FSA, to understand the behavior of this algorithm we need the following iteration which estimates the true utilities gained by the mobiles :

θα m,k+1 = θα m,k + ǫ k rα m,k+1 I α m r s k+1 , Θ α k -θα m,k , rα m,k+1 = min r m,k+1 , φ α m,k+1 . ( 26
)
1) Analysis : We analyze the robustness of the proposed algorithm using game theoretical tools. Fix any α. We consider a M + 1 player game with utilities defined by : U m := lim k→∞ θα m,k+1 for all m and

U BS := m Γ α (U m ).
We analyze the limits of (26) using ODE approximation methods (for e.g., [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF], [START_REF] Benveniste | Adaptive algorithms and stochastic approximation[END_REF]). As a first step, we obtain the following ODE approximation result .

Theorem 2: Assume that algorithms ( 23)-( 26) satisfy assumptions A.1, A.2 and A.3 of Appendix D . For any initial condition, (Θ α k , Θα k ) converges weakly to the set of limit points of the solution of the ODE (for all m ≤ M ):

θ m = m (Θ) -θ m , m (Θ) = E [φ α m I α m (r s , Θ)] , (27) θm = ˆ m (Θ) -θm , ˆ m (Θ) = E [r α m I α m (r s , Θ)] . ( 28
)
These conclusions hold whenever ǫ k → 0, k ǫ k = ∞ and for some ν k → ∞, lim k sup 0≤l≤ν k |ǫ k+l /ǫ k -1| = 0.

Remarks about the proof and the assumptions : This theorem can be proved exactly in the same way as is done for α-FSA by Theorem 2.1 of Kushner et al's [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF]. The required assumptions A.1-3 are also very similar to those in [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF]; the true channel rates {r k } and the signaled rates {r s k } should satisfy the conditions of [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF]. Also by Lemma 7 the right hand sides (RHS) of ODEs ( 27)-( 28

From ( 29), (30), the robust policy [START_REF] Shakkottai | Scheduling algorithms for a mixture of real-time and non-real-time data in HDR[END_REF] at BS together with the truth-revealing policy of users forms an ǫ-NE.

B. Robust Policy 2

The policies of previous subsection, Robust Policy 1, will not allow the ATA utility of any user to go above the cooperative share. Nevertheless, when a user is noncooperative, these policies may still result in a loss for the cooperative users: (i) because of the unchanged scheduling decision, the noncooperative user can still grab the channel from other users; (ii) however the noncooperative user does not gain because of the robust allocation policies [START_REF] Kavitha | Fair scheduling in cellular systems in the presence of noncooperative mobiles[END_REF]. To avoid this problem, we may robustify not only the allocations, but also the scheduling decision, by making decisions using the controlled allocations Φ α in place of the signaled utilities r s :

θ α m,k+1 = θ α m,k + ǫ k φ α m,k+1 I α m Φ α k+1 , Θ α k -θ α m,k . (31)
The analysis of this policy would be similar to Policy 1. We need to change the assumptions of the Appendix D appropriately to obtain the ODE approximation result (equivalent of Theorem 2). In particular, we need to replace the decisions I α m (r s , Θ) with I α m (Φ α , Θ) in all the places. The analysis of this policy, hence after, is considerably more difficult. While all the steps can be carried out as done for Policy 1 including Lemma 7, the uniqueness of the attractor under truthful strategies µ T remains an open question. However numerical evidence (next subsection) suggest that Policy 2 is also robust. The examples also show that these policies outperform Robust policy 1 in many ways, while Robust policy 1 is simpler to implement.

Numerical examples

We continue with the example of Figure 3 (for which α-FSA failed). We now use Robust Policy 1 in place of α-FSA in Figure 4. We set ∆ = 100. We plot only the ATA utilities for both values of δ = 0, δ = 0.9. We do not plot the ASA utilities in this figure to avoid clutter. But these utilities for all the cases studied are either close to, or less than the cooperative shares Θ αc , as proved by theory. We see that this policy is indeed robust : 1) the time limits of {θ m,k } (which correspond to ASA utilities) are either close to or less than the cooperative shares; 2) when all the mobiles are cooperative both the ASA as well as ATA utilities are close to the cooperative shares for all the mobiles (in Figure 4, we only plot the cooperative shares). 3) the time limit of the asymptotic true (ATA) utilities, unlike in the case of α-FSA (see the light curves in Figure 3), are less than the cooperative shares for the noncooperative mobile (light curves in Figure 4). This illustrates that the noncooperative mobiles does not gain, but actually loses because of noncooperation. However the cooperative mobile (mobile 2 in Figure 4, see the curves with circles) loses to a greater extent because of the other mobile's noncooperation. Robust policy 1 only ensures that the mobile 1 never gains because of noncooperation, but could not prevent the cooperative mobile 2 from losing. Robust Policy 2 solves exactly this issue.

In Figures 5,6 we compare the two robust policies. Here

h 1 ∼ f Z (z; 1)1 {z≤2} dz Pr(Z(1) ≤ 2) , h 2 -.45 ∼ f Z (z; 0.5)1 {z≤2} dz Pr(Z(0.5) ≤ 2) , f (h)
= log(1 + h 2 ) and ∆ = 1000. Mobile 1, can be noncooperative using the signaled utilities

f (s 1 (h)) = f (h) + (2 -f (h))δ
with δ = 0.9. In these figures we plot only the ATA utilities at δ = 0 and at δ = 0.9. The ATA utilities at δ = 0 are very close to the cooperative shares and hence cooperative shares are not shown separately. The ASA utilities are again omitted for improving clarity, they are either close to or less than the corresponding cooperative shares as is suggested by theory. We see from the figures that both the policies are robust. Even with high values of δ = 0.9 (which indicates large amount of noncooperation) both the policies do not allow the ATA utilities to go beyond the cooperative shares. However the Policy 2 is way better than the Policy 1: 1) the noncooperative mobile (mobile 1) is more severely punished in Policy 2, its ATA utility is significantly less than the cooperative share θ αc 1 (Figure 6, see curves without circles), but with Policy 1, it is slightly less than θ αc 1 (Figure 5); 2) the cooperative mobile 2 loses because of noncooperation from the mobile 1 to a much greater extent in Policy 1 (compare the curves with circles in Figures 56). This is in line with the extra robustification built into decision making by Policy 2. When BS uses Policy 1, the noncooperative mobile grabs the channel more often (almost always with large values of δ = 0.9). It, however does not gain much because of the robust allocation [START_REF] Kavitha | Fair scheduling in cellular systems in the presence of noncooperative mobiles[END_REF]. When the mobile is aware that he cannot gain from being noncooperative, he prefers to signal truthfully, unless the intention is to jam the other mobile (in which case the BS needs to use Policy 2). However Policy 1 is easier to implement than the Policy 2 because of simpler decisions, and may have faster convergence. In Table II we continue with the symmetric example of Table I wherein α-FSA fails. We see once again that (even with discrete and symmetric conditions) Policy 1 is robust against noncooperation; it does not allow the noncooperative user to improve his asymptotic throughput.

µ 1 (a 1 |a 2 ) = True Rates U BS = (U AT A 1 , U AT A 2 ) m U AT A m m log(U AT A m ) 0 (Coop) (1.

VIII. SUMMARY

We studied centralized downlink transmissions in a cellular network in the presence of noncooperative mobiles. Using α- fair scheduler, the BS has to assign the slot to one of the many mobiles based on truthful information from mobiles about their time-varying channel gains. A noncooperative mobile may misrepresent its signal to the BS so as to maximize his throughput. We modeled a noncooperative mobile as a rational player who wishes to maximize his throughput. For this game, we identified several scenarios related to the awareness of BS. When the BS is unaware of this noncooperative behavior, we modeled this game as noncooperative game with the mobiles alone as players. We identified that the presence of noncooperative users results in a bias in the channel assignment for small values of α. As α increases, an α-fair scheduler becomes more and more robust to noncooperation irrespective of the awareness of BS and a max-min fair scheduler is always robust. When the BS is aware of the noncooperative mobiles, we characterized a Babbling equilibrium which is obtained when both the BS and the noncooperative players make no use of the signaling opportunities. This game has no TRE (Truth Revealing Equilibrium). Using additional knowledge of the statistics of the signals observed at the BS, we built new robust policies to elicit truthful signals from mobiles, and, we achieved a Truth Revealing Equilibrium. We then studied the popular iterative and fair scheduling algorithm (which we called α-FSA) analyzed by Kushner and Whiting in [START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF]. We showed that α-FSA fails under noncooperation. Finally, we proposed iterative robust fair sharing to robustify the α-FSA in the presence of noncooperation.

APPENDIX A : REMARKS ON CHOICE OF UTILITY :

Even if a mobile signals more than its true value and the BS attempts to transmit at that higher transmitted rate, the actual rate at which the transmission takes place will still be f (h m ). This is reasonable given the following observations. The reported channel is usually subject to estimation errors and delays, an aspect that we do not consider explicitly in this paper. To address this issue, the BS employs a rate-less code, i.e., starts at an aggressive modulation and coding rate, gets feedback from the mobile after each transmission, and stops as soon as sufficient number of redundant bits are received to meet the decoding requirements. This incremental redundancy technique supported by hybrid ARQ is already implemented in the aforementioned standards (3GPP HSDPA and 1xEV-DO). Then a rate close to the true utility may be achieved. This along with (32) proves that β * is a global maximizer of the objective function in (2) over domain D and hence is a α-fair solution [START_REF] Mare | Experimental validation of analytical performance models for IEEE 802.11 networks[END_REF].

Most of the times there may not be a unique global optimizer for the α-fair objective function. However, uniqueness of Θ * follows from strict concavity of the mapping

Θ → m Γ α (θ m )
and the fact that D is compact and convex. From the uniqueness and Lemma 6 below, the last statement follows.

⋄

Lemma 6: Consider a BS policy β which is inefficient in the following sense. Without loss of generality consider the mobile indexed by 1. If there exists an h 1 , h ′ 1 ∈ H 1 and h-1 ∈ Π m>1 H m such that 0 < β(1|h 1 , h-1 ) ≤ β(1|h ′ 1 , h-1 ) < 1 when f (h 1 ) > f (h ′ 1 ) (33) then one can construct a better BS policy β that yields θ m ( β) = θ m (β) for all m > 1 and θ 1 ( β) > θ 1 (β). One can construct a better policy even if there exists an h 1 , h ′ 1 ∈ H 1 and h-1 ∈ Π m>1 H m such that

0 ≤ β(1|h 1 , h-1 ) < β(1|h ′ 1 , h-1 ) ≤ 1 when f (h 1 ) > f (h ′ 1 )
.

G α (β). Hence, the best response for truth revealing strategy profile µ T indeed equals one of the maximizers of Lemma 1, which satisfies the efficiency property [START_REF]Technical Specification 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; High Speed Downlink Packet Access (HSDPA); Overall description; Stage 2[END_REF]. Let β * be any maximizer of Lemma 1. The strategy profile (µ T , β * ) does not form a NE because: Let m be any mobile with non-zero cooperative share and let h be its channel value with largest utility, i.e., let h = arg max h∈H m f (h). The mobile by changing its policy from truthful signals µ T m to µ m(s m|h m) := 1 {s m = h} for all h m, s m increases its ATA utilities as by [START_REF]Technical Specification 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; High Speed Downlink Packet Access (HSDPA); Overall description; Stage 2[END_REF] for any h -m and for any h = h ∈ H m, β * ( m| h, h -m) ≥ β * ( m|h, h -m), and hence, (dj -δ) 1-α + δ 1 , j = m > 0, else.

A.3 True and signaled rates {(r l , r s l ) ; l ≥ 0} are defined on some compact set and have bounded joint density.

Remarks VIII-1:

The assumption A.1 can be ensured as in Lemma 7 given the assumption A.3.

Fig. 1 .

 1 Fig. 1. User utilities versus α for δ = 0.1. Mobile 1 is noncooperative when δ > 0.

Fig. 2 .

 2 Fig. 2. User utilities versus α for δ = 0.5 Mobile 1 is noncooperative when δ > 0.

  (µ * , β * ) µ m , µ * -m ), β * ), ∀m, and β * = arg max β U α BS (µ * , β).

Let

  hm := arg max hm f (h m ) for every m and let h = [ h1 , • • • , hM ]. Let µ * be the policy which always signals the state with highest utility, i.e., µ * m (s m |h m ) = 1 {sm= hm} for all h m and for all m. Then for any β and m:

  has a fixed point Θ (by Brouwer's fixed point theorem), β * (.|h) := β(.|h, Θ) satisfies (3), and hence is an α-fair solution. Thus, for continuous rates we always have fixed point α-fair solution (3). We outlined an algorithm to implement α-fair scheduler (3) in Remark II-3 following Lemma 1. The α-FSA ([START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF]), a stochastic approximation based fair scheduling algorithms, exactly follows this outline. Let Θ α k

Mobile 1 , 9 Fig. 4 .

 194 Fig. 4. Robust Policy 1: ATA utilities versus α. Mobile 1 is noncooperative with δ > 0.

  ) are Lipschitz and hence the ODEs have unique solution. ⋄ Hence, one can upper bound utilities {U m } by upper bounding all the attractors of the ODE (28). Any attractor Θ * of the ODE (27) is a zero of its right hand side and hence is a fixed point of the map Υ of Lemma 5 and thus by Lemma 5.(iii), θ * m ≤ θ αc m + O(1/∆). Further, any attractor of ODE (28) satisfies θ * m = ˆ m (Θ * ) leading to θ * m ≤ θ * m . Thus for any mobile strategy profile µ, U m w = θ * m ≤ θ * m ≤ θ αc m + O(1/∆), (29) where w = means the limit converges in distribution. So, none of the users, no matter what strategy they use or what strategies the others use, can gain more than θ αc m+ O(1/∆). Under µ T , Θ αc = [θ αc 1 , • • • , θ αc M ]T is the only zero of RHSs of the ODEs (27) and (28), as can be shown using fixed point analysis (see Lemma 5.(ii) and the logic just before Theorem 1 in section V-B). Note here that I α m (r s , Θ) is the α-fair scheduler β * (•|s) satisfying (3). Thus, Θ αc is the only possible attractor of both the ODEs under µ T . Thus U m w = θ αc m for all m under µ T .

Fig. 5 .

 5 Fig. 5. Robust Policy 1: ATA utilities of the mobiles versus α. Mobile 1 is noncooperative when δ > 0. The ATA utilities at δ = 0 and cooperative shares equal each other.

Fig. 6 .

 6 Fig. 6. Robust Policy 2: ATA utilities of the mobiles versus α. Mobile 1 is noncooperative when δ > 0. The ATA utilities at δ = 0 and cooperative shares equal each other.

  APPENDIX B : PROOF OF LEMMA 1Proof of Lemma 1: Since Γ α is a concave function,G α (β) -G α (β * )≤ m [θ m (β) -θ m (β * )] dΓ α (θ m (β * )). (32) From (3) β * maximizes the function β → m θ m (β)dΓ α (θ m (β * )) = E h m f (h m )dΓ α (θ m (β * ))β(m|h)over D and hence we have, m [θ m (β) -θ m (β * )] dΓ α (θ m (β * )) ≤ 0.

1 += 1 P

 11 m, µ T -m), β * ) -U AT A m (µ T , β * ) = h p h (h) β * ( m| h, h -m)f (h m) -β * ( m|h)f (h m) = h p h (h)f (h m) β * ( m| h, h -m) -β * ( m|h) > 0.Strict inequality results in the last line for all α > 0, as all the mobiles obtain non zero utility under an alpha fair scheduler. Thus, the mobile m can improve its utility by unilaterally moving away from µ T m , contradicting the definition of NE. ⋄ Proof of Lemma 5:With C f representing upper bound on f , f (s m , θ m )1 { f (sm,θm)>0} ≤ C f + θ αc m ∆ for all s m , θ m ≥ 0.Thus the map θ m → fm β(m|s)1 { fm>0} is bounded and continuous for almost all values of s and all m and hence by bounded convergence theorem the map Υ is continuous in the positive orthant. Thus by Brouwer fixed point theorem8 , there exists a fixed point for Υ.ii) At any α-fair scheduler β * of (2) and with µ = µ T , it is easy to check that Θ αc is a fixed point (notep s = p h ) of Υ. Also if Θ * is any other fixed point (note θ * m = γ m (Θ * )), θ * m -θ αc m = E h [f (h m )β * (m|h)1 { fm>0} ] -E[f (h m )β * (m|h)] -∆(θ m -θ αc )E h [β * (m|h)1 { fm>0} ]and hence for all m,θ * m -θ αc m = -E h [f (h m )β * (m|h)1 { fm≤0} ] 1 + ∆E h [β(m||h)1 { fm>0} ] ≤ 0. so that θ * m ≤ θ αc m . If θ * m < θ αc mfor some m, then the indicator 1 { fm≤0} = 0 for all h and then θ * m -θ αc m = 0 which is a contradiction. Hence with (µ T , β * ), Υ has unique fixed point, Θ αc .iii) If Θ * is any fixed point of Υ, irrespective of µ, β:θ * m -θ αc m = E s f (s m )β(m|s)1 { fm>0} -θ αc m ∆E s β(m|s)1 { fm>0} ≤ E s f (s m )β(m|s)1 { fm>0} ∆E s β(m|s)1 { fm>0} ≤ C f ∆ ≤ O(1/∆). ⋄In the above Θ is considered fixed. Also, I α m r s l+1 , Θ -ˆ m (Θ) = 0 in the sense of probability. There are small positive δ and δ 1 such that for every m ≤ M P dj -δ + δ 1 , j = m > 0, if α

TABLE I

 I

In major parts of our work (except for the stochastic approximation based algorithms) we deal with the situation in which the channel states can take one of the finitely many values, which in turn implies that the system has finite choices of transmission rates. It is in these cases that we can assume β ∈ R B . Indirectly we are assuming that each of the channel state represent an interval of the actual channel state realizations.

Note that when adding further concave constraints the game remains concave even if the constraints are coupled[START_REF] Rosen | Existence and Uniqueness of Equilibrium Points for Concave N-Person Games[END_REF]. We thus obtain equilibrium also for constrained versions of the game. Examples of such constraints are: the (possible weighted) sum of throughputs is bounded by a constant.

The authors in[START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF] analyze these algorithms only for α ≤ 1. However numerous examples suggest that they work for all values of α. That is, when all mobiles are cooperative the α-FSA (for any α) converges to the unique shares that maximize the objective function (4).

The cooperative shares can be estimated at the BS, apriori, using α-FSA (24), using the channel statistics and Monto Carlo simulations. A sequence of channel state realizations are produced by the BS according to the given channel statistics and the same is used as the signal from the mobiles (in other words, when δ = 0) and the iteration (24) is run for sufficient iterations so as to ensure convergence. From[START_REF] Kushner | Convergence of Proportional-Fair Sharing algorithms under general conditions[END_REF] when started from a far away point it needs around 10000 iterations, while lesser iterations would be required for a more accurate initial estimate of cooperative shares.

Brouwer fixed point theorem: Every continuous function f from a closed ball of a Euclidean space to itself has a fixed point, i.e., an x * which satisfies x * = f (x * ).

Proof : We first construct a better policy for the condition (33). Define a new policy β: for all m, let β(m|h) = β(m|h) when h = h 1 , h-1 or h = h ′ 1 , h-1 .

We will pickup constants {ǫ m,1 }, {ǫ m,2 } such that for all m β(m|h 1 , h-1 ) = β(m|h 1 , h-1 ) + ǫ m,1 and

and such that the constructed policy β satisfies the requirements of the lemma. First we note that, the sum m ǫ m,j need to be zero for both j = 1, 2, i.e., m ǫ m,j = 0. This is required because the newly constructed policy should satisfy

to make θ m (β) = θ( β) we need to set for all m > 1,

and hence,

.

Thus,

if we set ǫ 1,1 > 0 and because of the following :

• Because ǫ 1,1 > 0, we need m>1 ǫ m,1 < 0 and thus need at least one m > 1 such that β(m|h 1 , h-1 ) > 0. This is always possible under the hypothesis of the lemma as other wise,

and hence contradicts the hypothesis. • ǫ 1,2 < 0 and hence we need β(1|h ′ 1 , h-1 ) > 0, which is also true because of the hypothesis.

The above two reasons are required to ensure the basic necessary of the policy :

The maximum value of ǫ 1,1 is easily seen to be :

The last condition can also be taken care in a similar way. If for example, if there exists an

then for all m > 1 β(m|h ′ 1 , h-1 ) = 0, there exists at least one m > 1 for which β( m|h 1 , h-1 ) > 0. Then one can chose ǫ 1,1

and rest 0 with

.

⋄

APPENDIX C: PROOFS OF LEMMAS 2, 4 AND 5

Proof of Lemma 2: As in Lemma 1, for any µ if there exists a β * µ which satisfies:

then it maximizes [START_REF] Borst | Dynamic rate control algorithms for HDR throughput optimization[END_REF]. Define the following for mobile 1,

where i * is the maximum i satisfying N.2. Define,

Mobile 1 can deviate unilaterally from the truth revealing strategy using µ δ 1 and increase its truth revealing utility θ αc 1 to a higher utility

whenever the following conditions hold :

with η 1 + η 2 f (h 2 ) < η for all h 2 ∈ H 2 . This is because with the above choice of δ, the mobile 1, as in cooperative case, will grab the channel with signal s 1 = h 1,i * -1 because,

• the corresponding ASA utility

• for every α, the function dΓ α (.) is decreasing in its argument and hence

representing the new lower utility of the mobile 2, reduced because of the noncooperation of the mobile 1, by an amount not more than δu max 2 .

⋄

Proof of Lemma 4: If the M + 1 player game were to have a TRE, the corresponding (equilibrium) strategy of the BS, by definition of the NE, should be the best response to mobiles' truthful strategies µ T and hence will maximize

We first reintroduce some of the notations. This table lists and describes all the various rates used in sections VI and VII. The last column of this table provides the corresponding vector symbol for the vector of M components.

Variable

Description Vector

Here Θ is considered fixed. Let δ > 0 be arbitrary. The continuity is uniform in k and in ζ k in the set {Θ : θ i ≥ δ, i ≤ M }. A.2 The sequence {(r l , r s l ) : l ≥ 0} is stationary. Define the following stationary expectations: