# A Game-Theoretic Analysis of Bandwidth Allocation under a User-Grouping Constraint

Authors: Shun-Pin Hsu; Shun-Liang Hsu; Alan Shenghan Tsai
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

A new bandwidth allocation model is studied in this paper. In this model, a system, such as a communication network, is composed of a finite number of users, and they compete for limited bandwidth resources. Each user adopts the decision that maximizes his or her own benefit characterized by the utility function. The decision space of each user is subject to constraints. In
addition, some users form a group, and their joint decision space is also subject to constraints. Under the assumption that each user’s utility function satisfies some continuity and concavity conditions, the existence, uniqueness, and fairness, in some appropriate sense, of the Nash equilibrium point in the allocation game are proved. An algorithm yielding a sequence converging to the equilibrium point is proposed. Finally, a numerical example with detailed analysis is provided to illustrate the effectiveness of our work.


---

## Body

## 1. Introduction

With the widespread use of internet and the increasing popularity of mobile devices, more and more people can get online at almost anytime and anywhere. An immediate challenge facing the significant increment of online users is the support of quality of service (QoS). Over the past decade considerable efforts have been made to ensure the smooth operation of the networking systems. For example, the load balancing problems were considered by Anselmi et al. [1] and Ayesta et al. [2]. The routing problems were studied by La and Anantharam [3], Richman and Shimkin [4], Boulogne et al. [5], and Korilis et al. [6–8]. Niyato and Hossain [9] studied the practical issue such as the admission control for the wireless broadband standard. Ganesh et al. [10] and Yaïche et al. [11] considered the pricing issues. In modeling the networking problems, quite often the bandwidth availability is the main concern and has its role in the associated performance measure. The network system quantifies the results caused by different operation scenarios and seeks the approach leading to the greatest benefits in some sense. Since the benefit of any network user inevitably involves that of other users, its evaluation is mostly carried out in the context of game theory. In the survey paper Altman et al. collected a long list of networking models based on game theoretic formulation. Interested readers are referred to [12] and the rich reference therein.As mentioned above, the bandwidth availability is the major concern in many networking problems. The bandwidth allocation is thus the core issue as far as the quality of service is concerned. While the bandwidth allocation problem was considered by many authors in different contexts of networking protocols or communication standards (see e.g., [9, 11, 13, 14]), at a high level of abstraction the problem can be regarded as the classical resources distribution problem studied in many professional fields such as economics, management science, and operations research. Given a finite number of units competing for the limited resources, how does each unit decide its share based on its own utility function? Lazar et al. [15] formulated this problem for the network composed of noncooperative users. Under certain monotonicity, differentiability, and convexity assumptions on the cost function the unique existence and certain fairness property of the Nash equilibrium point (NEP) were proved. An algorithm based on Gauss-Seidel and Jacobi schemes was proposed and proved to yield a sequence converging to the NEP. However, the framework in [15] assumes only the natural constraint for the bandwidth allocation. That is, the feasible bandwidth of any user falls within the interval lower bounded by zero and upper bounded by the bandwidth available for that user. In practice some techniques such as the bandwidth throttling and bandwidth/traffic shaping [16] are available to provide more adaptive bandwidth control. To address this issue, Rhee and Konstantopoulos [17, 18] relaxed the assumption and allowed some prespecified numbers for the upper and lower bounds of the bandwidth. This relaxation increases the flexibility of flow control and helps the QoS satisfaction by the networking system. On the other hand, in modern broadband communication systems some users might form a group and expect the group-wise QoS, in addition to the user-wise one. For example, the customers of an internet service provider (ISP) might include the individuals and a company with many employees. To maintain the QoS, parameters would be assigned to bound the bandwidth of each individual and each employee. Furthermore the ISP and the company would set the constraint for the employee-averaged, or equivalently, employee-totaled bandwidth, as shown in Figure 1. A similar concept of group constraint can be seen in the cost-effective broadband access network such as the Ethernet-based passive optical network (EPON) [19, 20]. This system is composed of an optical line terminal (OLT) and many optical network units (ONUs). The OLT is situated in the central office and ONUs are distributed over the remote areas for multimedia communication with the subscribers. In the upload process each ONU adopts the time division multiplexing access (TDMA) protocol to transmit data frames to the OLT, in the sense that each ONU only transmits the data during the time slots specifically scheduled for it [21]. The protocol avoids the frame collisions between different ONUs at the cost of imposing the upper bound for the time-average flow of each ONU and the upper bound for the total flow of all ONUs.Figure 1
The system bandwidth allocationr=(r1,r2,…,rn) subject to user-wise constraints: r_i≤ri≤r-i for i∈{1,2,…,n}, and a user-grouping constraint R_g≤∑i=1m‍ri≤R-g. The total allocation R=∑i=1n‍ri is less than T, the total bandwidth.In light of the bandwidth sharing mechanism in EPON and other similar systems, we extend the existing results to include the user-grouping constraint for better model fitting. Suppose each user has his or her own utility function that describes the relation between the allocated bandwidth and the resultant benefit to that user. Following the standard assumptions, (1) the function depends on the bandwidth of the user, and on the bandwidth of other users only through their total bandwidth, and (2) the function satisfies certain continuity and concavity properties; we show the unique existence and the fairness with some appropriate sense, of the NEP in the allocation game. The contributions of our work are twofold. First, a novel concept called user-grouping NEP is proposed. This concept is corresponding to the new introduction of the group constraint, under which the uniqueness of NEP proved in [15, 17] no longer holds. Based on this concept we give a new definition for the equilibrium point and prove its uniqueness under our assumptions. The fairness of the allocation based on the user-grouping NEP is also proved. Second, we show that the Gauss-Seidel type algorithm in [15, 18] can be modified to yield a sequence converging to the user-grouping NEP. Since the bandwidth allocation is of central concern in networking systems, our results might result in the reinvestigation and reformulation of other networking issues such that more practical approaches can be developed.


## 2. Preliminaries

Suppose a networking system hasn users and they compete for the system bandwidth. Each user is assigned with the bandwidth subject to predecided upper and lower bounds. In addition, m of the n users form a group and the total bandwidth of the m users is also subject to a predecided constraint. We would like to design the system bandwidth allocation policy that optimizes the performance index of each user in the game-theoretical sense. For convenience, we use the list of nomenclature shown at the end of the paper.Assume the utility function for each user depends on the bandwidth of that user and the total bandwidth of other users. That is, the utility function for useri in 𝒩 can be written as Ui(ri,R). Also, assume the utility function satisfies the following continuity and concavity properties [18]:Assumption 1.
For each utility functionUi(ri,R)(a)
Ui(ri,R) is continuously differentiable with respect to ri;(b)
(∂/∂ri)Ui(ri,R) is strictly decreasing with respect to ri and nonincreasing with respect to R.Now we define the allocation function. For useri in 𝒩∖ℳ with the available bandwidth Ti, the allocation function Ai is defined as
(1)Ai(Ti)=argmaxr_i≤r≤r-iUi(r,r+T-Ti).
For user i in ℳ with the available bandwidth Ti and inside-group information Tig, the allocation function 𝒜i is defined as
(2)𝒜i(Ti,Tig)=argmaxr_i≤r≤r-i,R_g≤Tig+r≤R-gUi(r,r+T-Ti).Assumption 2.
The bandwidth allocation with the constraint parameters has the following properties:(a)
Ti>𝒜i(Ti,Tig) for each feasible Ti and Tig where i∈ℳ, and Ti>Ai(Ti) for each feasible Ti where i∈𝒩∖ℳ;(b)
∑i=1m‍r-i>R-g>R_g>∑i=1m‍r_i.In our framework, the classical Nash equilibrium point (NEP) in the allocation game is defined as(3)r*:=(r1*,r2*,…,rn*),
where
(4)ri*∈argmaxr∈CiUi(r,r+∑j≠i‍rj*).
Note that Ci is {r∣r_i≤r≤r-i,R_g≤r+∑j∈ℳ∖{i}‍rj*≤R-g} if i∈ℳ and is {r∣r_i≤r≤r-i} otherwise. The user-grouping NEP is defined as
(5)rg*:=(Rg*m,rm+1*,rm+2*,…,rn*),
where
(6)Rg*:=∑i=1m‍ri*.Remark 3.
The definitions (3)-(4) reflect the central concept of the well-studied constrained NEP. That is, given the constrained strategy space Ci for each user i∈𝒩, ri* is defined as the maximizer of the utility function of user i provided that the strategy rj* is adopted by user j for each j∈𝒩∖{i}. Note that the bandwidth of users in the group ℳ should satisfy the extra group constraint and thus ri* might lose its uniqueness in Ci as the group constraint is active. The novel concept of user-grouping NEP in (5)-(6) is thus proposed to compensate the property of the equilibrium point. We will show in Section 3.1 that our setting ensures the uniqueness of the user-grouping NEP.Remark 4.
SupposeTi*:=T-∑j≠in‍rj*. Also, let Tig*:=R-g-∑j≠im‍rj*, then
(7)ri*:={𝒜i(Ti*,Tig*)ifi∈ℳAi(Ti*)ifi∈𝒩∖ℳ.
By part (a) in Assumption 2 we have
(8)ri*<Ti*=T-∑j≠in‍rj*.
Consequently,
(9)R*:=∑i=1n‍ri*<T.
This means that the NEP, or r*, satisfies the natural constraint R*≤T and the constraint is always inactive. Part (b) in Assumption 2 is a natural condition such that the constraint R_g≤∑i=1m‍ri≤R-g makes sense.The existence of the NEP in our setting is guaranteed by Rosen’s result in the following.Theorem 5 (see [22, Theorem 1]).
An equilibrium point exists for every concaven-person game.Theorem5 can be obtained using the classical Kakutani fixed point theorem and in some sense generalizes Nash’s setting on the strategy space of the users [23, 24]. In the next section we delve into other properties and propose an algorithm to locate the NEP.


## 3. Main Results

### 3.1. Uniqueness

Our first result is concerned with the uniqueness of the user-grouping NEP. This property as shown in [18, page 13] is not implied by the uniqueness theorem in [22]. For the NEP r*=(r1*,r2*,…,rn*) defined in (3)-(4), the Karash-Kuhn-Tucker (KKT) conditions must be satisfied. That is, for each i∈𝒩∖ℳ there exist KKT multipliers λ-i* and λ_i* (see e.g., [25, page 458]) such that
(10)-∂∂riUi(ri*,R*)+λ-i*-λ_i*=0,(11)λ-i*(ri*-r-i)=0,(12)λ_i*(r_i-ri*)=0,(13)r_i≤ri*≤r-i,(14)λ_i*≥0,λ-i*≥0.
In addition, for each i∈ℳ there exist KKT multipliers λ-i* and λ_i* satisfying (11)–(14), and γ-i* and γ_i* satisfying
(15)-∂∂riUi(ri*,R*)+λ-i*-λ_i*+γ-i*-γ_i*=0,(16)γ-i*(Rg*-R-g)=0,(17)γ_i*(R_g-Rg*)=0,(18)R_g≤Rg*≤R-g,(19)γ_i*≥0,γ-i*≥0,
where Rg* is defined in (6).Lemma 6.
For eachi∈𝒩∖ℳ, let ri(1):=Ai(Ti(1)) and ri(2):=Ai(Ti(2)) for some feasible Ti(1) and Ti(2), then
(20)ri(1)>ri(2)⇒λ-i(1)-λ_i(1)≥λ-i(2)-λ_i(2),
where the nonnegative KKT multipliers λ-i(1), λ_i(1),  λ-i(2) and λ_i(2) satisfy
(21)λ-i(1)(ri(1)-r-i)=0,λ_i(1)(r_i-ri(1))=0,(22)λ-i(2)(ri(2)-r-i)=0,λ_i(2)(r_i-ri(2))=0.Proof.
Sinceri(1) and ri(2) are both feasible, ri(1)>ri(2) implies λ_i(1)=0 and λ-i(2)=0 by (21) and (22), respectively. Consequently, the result follows since λ-i(1)≥0 and λ_i(2)≥0.Theorem 7.
The user-grouping NEP defined in (5) is unique.Proof.
Supposer(1)=(r1(1),r2(1),…,rn(1)) and r(2)=(r1(2),r2(2),…,rn(2)) are both the equilibrium points. Let R(1)=∑i=1n‍ri(1) and R(2)=∑i=1n‍ri(2). We can thus write for i∈𝒩∖ℳ that
(23)-∂∂riUi(ri(1),R(1))+λ-i(1)-λ_i(1)=0,-∂∂riUi(ri(2),R(2))+λ-i(2)-λ_i(2)=0,
where λ-i(1), λ_i(1),  λ-i(2), λ_i(2) are the associated KKT multipliers. Assume that R(1)>R(2). If there exists i∈𝒩∖ℳ such that ri(1)>ri(2), by Lemma 6 and Assumption 1 we have
(24)-∂∂riUi(ri(1),R(1))+λ-i(1)-λ_i(1)>-∂∂riUi(ri(2),R(2))+λ-i(2)-λ_i(2),
which is a contradiction. We thus have ri(1)≤ri(2) for i in 𝒩∖ℳ. This implies Rg(1):=∑i=1m‍ri(1)>∑i=2m‍ri(2)=Rg(2). Note that, for i∈ℳ,
(25)-∂∂riUi(ri(1),R(1))+λ-i(1)-λ_i(1)+γ-i(1)-γ_i(1)=0,-∂∂riUi(ri(2),R(2))+λ-i(2)-λ_i(2)+γ-i(2)-γ_i(2)=0.
With similar arguments in proving Lemma 6 we can show that
(26)Rg(1)>Rg(2)⇒γ-i(1)-γ_i(1)≥γ-i(2)-γ_i(2).
If ri(1)>ri(2) for some i∈ℳ, we have
(27)-∂∂riUi(ri(1),R(1))+λ-i(1)-λ_i(1)+γ-i(1)-γ_i(1)>-∂∂riUi(ri(2),R(2))+λ-i(2)-λ_i(2)+γ-i(2)-γ_i(2),
which is a contradiction. We thus have ri(i)≤ri(2) for each i∈ℳ and therefore Rg(1)≤Rg(2), also a contradiction. With analogous arguments we can show that assuming R(1)<R(2) also leads to a contradiction. Therefore R(1)=R(2) and by Lemma 6  ri(1)=ri(2) for i∈𝒩∖ℳ. This implies Rg(1)=Rg(2); therefore rg* is unique.


### 3.2. Fairness

A bandwidth allocationr=(r1,r2,…,rn) is said to be fair if for any feasible t1 and t2(28)𝒜i(t1,t2)≥𝒜j(t1,t2)⇒ri≥rj,
where i,j∈ℳ, and for any feasible t(29)Ai(t)≥Aj(t)⇒ri≥rj,
where i,j∈𝒩∖ℳ. This definition suggests that a fair allocation guarantees the user in greater need of bandwidth actually obtains more bandwidth.Theorem 8.
The bandwidth allocation based on the NEP defined in (3)-(4) is fair.Proof.
Supposei∈ℳ. Let ri(1)=𝒜i(Ti(1),t) and ri(2)=𝒜i(Ti(1)+ΔT,t+ΔT). We thus have
(30)-∂∂riUi(ri(1),R(1))+λ-i(1)-λ_i(1)+γ-i(1)-γ_i(1)=0,-∂∂riUi(ri(2),R(2))+λ-i(2)-λ_i(2)+γ-i(2)-γ_i(2)=0.
Assume ri(2)-ΔT>ri(1), which implies ri(2)>ri(1) and by Lemma 6  λ-i(2)-λ_i(2)≥λ-i(1)-λ_i(1). Also,
(31)R(2)≔ri(2)+R-i(2)>ri(1)+ΔT+R-i(2)=ri(1)+R-i(1):=R(1).
Similarly,
(32)Rg(2)≔ri(2)+∑j≠im‍rj(2)>ri(1)+ΔT+∑j≠im‍rj(2)=ri(1)+∑j≠im‍rj(1):=Rg(1).
Note that (32) implies γ-i(2)-γ_i(2)≥γ-i(1)-γ_i(1). We then have
(33)-∂∂riUi(ri(2),ri(2)+R-i(2))+λ-i(2)-λ_i(2)+γ-i(2)-γ_i(2)>-∂∂riUi(ri(1),ri(1)+R-i(1))+λ-i(1)-λ_i(1)+γ-i(1)-γ_i(1),
which is a contradiction. Therefore, ri(2)-ΔT≤ri(1), which implies
(34)Ti(1)+ΔT-ri(2)≥Ti(1)-ri(1),
namely,
(35)Ti(1)+ΔT-𝒜i(Ti(1)+ΔT,t+ΔT)≥Ti(1)-𝒜i(Ti(1),t).
To show the allocation based on r* is fair, consider first the case that i,j∈ℳ. By definition ri*=𝒜i(Ti*,Tig*), rj*:=𝒜j(Tj*,Tjg*) where Ti*, Tig*, Tj* and Tjg* are all feasible. With R* defined in (9) we have
(36)T-R*=Ti*-𝒜i(Ti*,Tig*)=Tj*-𝒜j(Tj*,Tig*),
which equals the remaining bandwidth of the system after allocation. Given 𝒜i(Ti*,Tig*)>𝒜j(Ti*,Tig*), we have
(37)Ti*-𝒜j(Ti*,Tig*)>Ti*-𝒜i(Ti*,Tig*)=Tj*-𝒜j(Tj*,Tjg*).
Note that
(38)Ti*-Tj*=Tig*-Tjg*=ri*-rj*:=ΔT*.
Equations (35) and (37) imply ΔT*>0; hence ri*>rj*. The case for i,j∈𝒩∖ℳ can be similarly proved and is thus ignored (see [18, Theorem 2.3] for details).


### 3.3. Algorithm

In this section we analyze the scheme to identify the user-grouping Nash equilibrium point. We say anindividual update is implemented on user i if the bandwidth of each user other than i is fixed and the bandwidth of user i is updated to maximize his or her utility function. In addition, we say a batch update occurs in the collection 𝒦 of users if the bandwidth of each user not in 𝒦 is fixed and the individual update is sequentially implemented on each user in 𝒦 repeatedly till an equilibrium is reached. Here 𝒦 is either ℳ or 𝒩∖ℳ. If 𝒦=ℳ the batch update is implemented assuming no group constraint, namely, R-g=∞ and R_g=0. Note that the batch update is guaranteed to reach an equilibrium (see [15] and [18, Section 2.4]). As a result, suppose rk=(r1k,r1k,…,rnk) is the system allocation at step k. If an individual update occurs at user i∈𝒩∖ℳ at step k+1, that means rjk+1=rjk for j∈𝒩∖{i}, and
(39)-∂∂riUi(rik+1,Rk+1)+λ-ik+1-λ_ik+1=0,
for some KKT multipliers λ-ik+1 and λ-ik+1 and Rk+1=∑i=1n‍rik+1. If a batch update occurs at the group of users at step k+1, that means rjk+1=rjk for each j∈𝒩∖ℳ, and we can write for each i∈ℳ(40)-∂∂riUi(rik+1,Rk+1)+λ-ik+1-λ_ik+1+γ-ik+1-γ_ik+1=0,
where λ-ik+1, λ-ik+1, γ-ik+1 and γ-ik+1 are the associated KKT multipliers. We now show that a repeated implementation of sequential batch updates on users in ℳ and users in 𝒩∖ℳ, as outline in Algorithm 1, yields a sequence converging to the user-grouping NEP rg* in (5). Define first the error measure e(rgk) between rgk and rg* as
(41)e(rgk)=∑i=m+1n‍|rik-ri*|+|Rgk-Rg*|+|Rk-R*|,
where Rgk:=∑i=1m‍rik. Rg* and R* are defined in (6) and (9), respectively.The scheme to locate the user-grouping NEP.
(P1) Initiate the algorithm with a feasiblerg and set s=0.
(P2) (if current step isk) Perform a batch update for users in ℳ at step k+1
by assigningrjk+1=rjk  for all j∈𝒩∖ℳ,
to reachrik+1=𝒜i(Tik+1,Tig,k+1)  for all i∈ℳ.
(P3) (if current step isk^) Perform an individual update at user i in 𝒩∖ℳ
by assigningrjk^+1=rjk^  for all j∈𝒩∖{i},
to reachrik^+1=Ai(Tik^), and let k^=k^+1.
Sequentially implement this whole procedure till each user in𝒩∖ℳ
is updated.
(P4) Repeat (P3) to complete a batch update at users in𝒩∖ℳ.
(P5) Sets=s+1 and record the current rg as ℛ(s).
If∥ℛ(s)-ℛ(s-1)∥<ε then stops, otherwise go to (P2).Lemma 9.
The error measuree(rgk) defined in (41) is nonincreasing, namely, e(rgk+1)≤e(rgk) for any positive integer k.Proof.
If at stepk+1 an individual update occurs at i∈𝒩∖ℳ, (39) is satisfied. Since (10) is also satisfied, we have by Lemma 6 and part (b) in Assumption 1 that
(42)Rk+1≥R*⇒rik+1≤ri*,Rk+1≤R*⇒rik+1≥ri*.
Under the assumption
(43)e(rgk+1)-e(rgk)=|rik+1-r*|-|rik-r*|+|Rk+1-R*|-|Rk-R*|.
Suppose Rk+1≥R*. If Rk≥Rk+1, then
(44)e(rgk+1)-e(rgk)=-(rik+1-r*)-|rik-r*|+Rk+1-Rk⇒{=0ifrik<ri*<0o.w.
Since Rk<Rk+1 implies rik<rik+1, we have
(45)e(rgk+1)-e(rgk)=-rik+1+rik+Rk+1-R*-|Rk-R*|⇒{=0ifRk>R*<0o.w.
Using similar arguments we can analyze the case for Rk+1<R* and obtain also that e(rgk+1)≤e(rgk). If at step k+1 a batch update occurs, (15) and (40) hold for each i∈ℳ. Suppose Rk+1≥R*. If there exists an i∈ℳ such that rik+1>ri* then part (b) in Assumption 1 implies
(46)γ-ik+1-γ_ik+1<γ-i*-γ_i*;
therefore by (26) Rg*≥Rgk+1. If no such i exists, namely, rik+1≤r* for each i∈ℳ, then naturally Rgk+1≤Rg*. A similar result can be derived for the case Rk+1≤R*. We then have
(47)Rk+1≥R*⇒Rgk+1≤Rg*,(48)Rk+1≤R*⇒Rk+1≥Rg*.
Now
(49)e(rgk+1)-e(rgk)=|Rgk+1-Rg*|-|Rgk-Rg*|+|Rk+1-R*|-|Rk-R*|.
Assume Rk+1≥R*. If Rk≥Rk+1 then
(50)e(rgk+1)-e(rgk)=-(Rgk+1-Rg*)-|Rgk-Rg*|+Rk+1-Rk⇒{=0ifRgk<Rg*<0o.w.
If Rk<Rk+1, which is equivalent to Rgk<Rgk+1, then
(51)e(rgk+1)-e(rgk)=-Rgk+1+Rgk+Rk+1-R*-|Rk-R*|⇒{=0ifRk>R*<0o.w.
Applying similar arguments again we can analyze the case for Rk+1<R* and obtain also that e(rgk+1)≤e(rgk).Theorem 10.
Algorithm1 yields a sequence {rgk}k=1∞ converging to rg*, the user-grouping NEP of the bandwidth allocation game.Proof.
In the light of Lemma9, we only need to show that for each positive integer k, rgk≠rg* implies the existence of a finite integer k1 such that e(rgk+k1)<e(rgk). Suppose it is not the case Then there exists some k such that e(rgk+k2)=e(rgk) for any positive integer k2, where rgk≠rg*. Consider the update scheme that, at step k+i-m for i∈𝒩∖ℳ, the individual update occurs at user i, and at step k+n+1-m the batch update takes place for users in ℳ. Without loss of generality we assume Rk+n+1-m≥R*, then Rg(k+n+1-m)≤Rg* by (47). Since e(rgk+n+1-m)=e(rgk+n-m), (50) together with (51) implies Rk+n-m≥R*; hence Rgk+n-m≤Rg*. That is, R·-R* and Rg·-Rg* do not change their signs as the step number is increased from k+n-m to k+n+1-m. Moreover, Rk+n-m≥R* implies rnk+n-m≤rn*. Since e(rgk+n+1-m)=e(rgk+i-m-1) for i∈𝒩∖ℳ, (44) and (45) together imply Rk+i-m≥R* and thus rik+i-m≤ri*, for i∈𝒩∖ℳ. As a result, rik+n-m≤ri* for i∈𝒩∖ℳ. Note that Rgk+n-m≤Rg* and
(52)Rk+n-m=Rgk+n-m+∑i=m+1n‍rik+n-m≥R*=Rg*+∑i=m+1n‍ri*.
We conclude that Rgk+n-m=Rg* and rik+n-m=ri* for i∈𝒩∖ℳ, namely, rgk=rg*, a contradiction.


## 3.1. Uniqueness

Our first result is concerned with the uniqueness of the user-grouping NEP. This property as shown in [18, page 13] is not implied by the uniqueness theorem in [22]. For the NEP r*=(r1*,r2*,…,rn*) defined in (3)-(4), the Karash-Kuhn-Tucker (KKT) conditions must be satisfied. That is, for each i∈𝒩∖ℳ there exist KKT multipliers λ-i* and λ_i* (see e.g., [25, page 458]) such that
(10)-∂∂riUi(ri*,R*)+λ-i*-λ_i*=0,(11)λ-i*(ri*-r-i)=0,(12)λ_i*(r_i-ri*)=0,(13)r_i≤ri*≤r-i,(14)λ_i*≥0,λ-i*≥0.
In addition, for each i∈ℳ there exist KKT multipliers λ-i* and λ_i* satisfying (11)–(14), and γ-i* and γ_i* satisfying
(15)-∂∂riUi(ri*,R*)+λ-i*-λ_i*+γ-i*-γ_i*=0,(16)γ-i*(Rg*-R-g)=0,(17)γ_i*(R_g-Rg*)=0,(18)R_g≤Rg*≤R-g,(19)γ_i*≥0,γ-i*≥0,
where Rg* is defined in (6).Lemma 6.
For eachi∈𝒩∖ℳ, let ri(1):=Ai(Ti(1)) and ri(2):=Ai(Ti(2)) for some feasible Ti(1) and Ti(2), then
(20)ri(1)>ri(2)⇒λ-i(1)-λ_i(1)≥λ-i(2)-λ_i(2),
where the nonnegative KKT multipliers λ-i(1), λ_i(1),  λ-i(2) and λ_i(2) satisfy
(21)λ-i(1)(ri(1)-r-i)=0,λ_i(1)(r_i-ri(1))=0,(22)λ-i(2)(ri(2)-r-i)=0,λ_i(2)(r_i-ri(2))=0.Proof.
Sinceri(1) and ri(2) are both feasible, ri(1)>ri(2) implies λ_i(1)=0 and λ-i(2)=0 by (21) and (22), respectively. Consequently, the result follows since λ-i(1)≥0 and λ_i(2)≥0.Theorem 7.
The user-grouping NEP defined in (5) is unique.Proof.
Supposer(1)=(r1(1),r2(1),…,rn(1)) and r(2)=(r1(2),r2(2),…,rn(2)) are both the equilibrium points. Let R(1)=∑i=1n‍ri(1) and R(2)=∑i=1n‍ri(2). We can thus write for i∈𝒩∖ℳ that
(23)-∂∂riUi(ri(1),R(1))+λ-i(1)-λ_i(1)=0,-∂∂riUi(ri(2),R(2))+λ-i(2)-λ_i(2)=0,
where λ-i(1), λ_i(1),  λ-i(2), λ_i(2) are the associated KKT multipliers. Assume that R(1)>R(2). If there exists i∈𝒩∖ℳ such that ri(1)>ri(2), by Lemma 6 and Assumption 1 we have
(24)-∂∂riUi(ri(1),R(1))+λ-i(1)-λ_i(1)>-∂∂riUi(ri(2),R(2))+λ-i(2)-λ_i(2),
which is a contradiction. We thus have ri(1)≤ri(2) for i in 𝒩∖ℳ. This implies Rg(1):=∑i=1m‍ri(1)>∑i=2m‍ri(2)=Rg(2). Note that, for i∈ℳ,
(25)-∂∂riUi(ri(1),R(1))+λ-i(1)-λ_i(1)+γ-i(1)-γ_i(1)=0,-∂∂riUi(ri(2),R(2))+λ-i(2)-λ_i(2)+γ-i(2)-γ_i(2)=0.
With similar arguments in proving Lemma 6 we can show that
(26)Rg(1)>Rg(2)⇒γ-i(1)-γ_i(1)≥γ-i(2)-γ_i(2).
If ri(1)>ri(2) for some i∈ℳ, we have
(27)-∂∂riUi(ri(1),R(1))+λ-i(1)-λ_i(1)+γ-i(1)-γ_i(1)>-∂∂riUi(ri(2),R(2))+λ-i(2)-λ_i(2)+γ-i(2)-γ_i(2),
which is a contradiction. We thus have ri(i)≤ri(2) for each i∈ℳ and therefore Rg(1)≤Rg(2), also a contradiction. With analogous arguments we can show that assuming R(1)<R(2) also leads to a contradiction. Therefore R(1)=R(2) and by Lemma 6  ri(1)=ri(2) for i∈𝒩∖ℳ. This implies Rg(1)=Rg(2); therefore rg* is unique.


## 3.2. Fairness

A bandwidth allocationr=(r1,r2,…,rn) is said to be fair if for any feasible t1 and t2(28)𝒜i(t1,t2)≥𝒜j(t1,t2)⇒ri≥rj,
where i,j∈ℳ, and for any feasible t(29)Ai(t)≥Aj(t)⇒ri≥rj,
where i,j∈𝒩∖ℳ. This definition suggests that a fair allocation guarantees the user in greater need of bandwidth actually obtains more bandwidth.Theorem 8.
The bandwidth allocation based on the NEP defined in (3)-(4) is fair.Proof.
Supposei∈ℳ. Let ri(1)=𝒜i(Ti(1),t) and ri(2)=𝒜i(Ti(1)+ΔT,t+ΔT). We thus have
(30)-∂∂riUi(ri(1),R(1))+λ-i(1)-λ_i(1)+γ-i(1)-γ_i(1)=0,-∂∂riUi(ri(2),R(2))+λ-i(2)-λ_i(2)+γ-i(2)-γ_i(2)=0.
Assume ri(2)-ΔT>ri(1), which implies ri(2)>ri(1) and by Lemma 6  λ-i(2)-λ_i(2)≥λ-i(1)-λ_i(1). Also,
(31)R(2)≔ri(2)+R-i(2)>ri(1)+ΔT+R-i(2)=ri(1)+R-i(1):=R(1).
Similarly,
(32)Rg(2)≔ri(2)+∑j≠im‍rj(2)>ri(1)+ΔT+∑j≠im‍rj(2)=ri(1)+∑j≠im‍rj(1):=Rg(1).
Note that (32) implies γ-i(2)-γ_i(2)≥γ-i(1)-γ_i(1). We then have
(33)-∂∂riUi(ri(2),ri(2)+R-i(2))+λ-i(2)-λ_i(2)+γ-i(2)-γ_i(2)>-∂∂riUi(ri(1),ri(1)+R-i(1))+λ-i(1)-λ_i(1)+γ-i(1)-γ_i(1),
which is a contradiction. Therefore, ri(2)-ΔT≤ri(1), which implies
(34)Ti(1)+ΔT-ri(2)≥Ti(1)-ri(1),
namely,
(35)Ti(1)+ΔT-𝒜i(Ti(1)+ΔT,t+ΔT)≥Ti(1)-𝒜i(Ti(1),t).
To show the allocation based on r* is fair, consider first the case that i,j∈ℳ. By definition ri*=𝒜i(Ti*,Tig*), rj*:=𝒜j(Tj*,Tjg*) where Ti*, Tig*, Tj* and Tjg* are all feasible. With R* defined in (9) we have
(36)T-R*=Ti*-𝒜i(Ti*,Tig*)=Tj*-𝒜j(Tj*,Tig*),
which equals the remaining bandwidth of the system after allocation. Given 𝒜i(Ti*,Tig*)>𝒜j(Ti*,Tig*), we have
(37)Ti*-𝒜j(Ti*,Tig*)>Ti*-𝒜i(Ti*,Tig*)=Tj*-𝒜j(Tj*,Tjg*).
Note that
(38)Ti*-Tj*=Tig*-Tjg*=ri*-rj*:=ΔT*.
Equations (35) and (37) imply ΔT*>0; hence ri*>rj*. The case for i,j∈𝒩∖ℳ can be similarly proved and is thus ignored (see [18, Theorem 2.3] for details).


## 3.3. Algorithm

In this section we analyze the scheme to identify the user-grouping Nash equilibrium point. We say anindividual update is implemented on user i if the bandwidth of each user other than i is fixed and the bandwidth of user i is updated to maximize his or her utility function. In addition, we say a batch update occurs in the collection 𝒦 of users if the bandwidth of each user not in 𝒦 is fixed and the individual update is sequentially implemented on each user in 𝒦 repeatedly till an equilibrium is reached. Here 𝒦 is either ℳ or 𝒩∖ℳ. If 𝒦=ℳ the batch update is implemented assuming no group constraint, namely, R-g=∞ and R_g=0. Note that the batch update is guaranteed to reach an equilibrium (see [15] and [18, Section 2.4]). As a result, suppose rk=(r1k,r1k,…,rnk) is the system allocation at step k. If an individual update occurs at user i∈𝒩∖ℳ at step k+1, that means rjk+1=rjk for j∈𝒩∖{i}, and
(39)-∂∂riUi(rik+1,Rk+1)+λ-ik+1-λ_ik+1=0,
for some KKT multipliers λ-ik+1 and λ-ik+1 and Rk+1=∑i=1n‍rik+1. If a batch update occurs at the group of users at step k+1, that means rjk+1=rjk for each j∈𝒩∖ℳ, and we can write for each i∈ℳ(40)-∂∂riUi(rik+1,Rk+1)+λ-ik+1-λ_ik+1+γ-ik+1-γ_ik+1=0,
where λ-ik+1, λ-ik+1, γ-ik+1 and γ-ik+1 are the associated KKT multipliers. We now show that a repeated implementation of sequential batch updates on users in ℳ and users in 𝒩∖ℳ, as outline in Algorithm 1, yields a sequence converging to the user-grouping NEP rg* in (5). Define first the error measure e(rgk) between rgk and rg* as
(41)e(rgk)=∑i=m+1n‍|rik-ri*|+|Rgk-Rg*|+|Rk-R*|,
where Rgk:=∑i=1m‍rik. Rg* and R* are defined in (6) and (9), respectively.The scheme to locate the user-grouping NEP.
(P1) Initiate the algorithm with a feasiblerg and set s=0.
(P2) (if current step isk) Perform a batch update for users in ℳ at step k+1
by assigningrjk+1=rjk  for all j∈𝒩∖ℳ,
to reachrik+1=𝒜i(Tik+1,Tig,k+1)  for all i∈ℳ.
(P3) (if current step isk^) Perform an individual update at user i in 𝒩∖ℳ
by assigningrjk^+1=rjk^  for all j∈𝒩∖{i},
to reachrik^+1=Ai(Tik^), and let k^=k^+1.
Sequentially implement this whole procedure till each user in𝒩∖ℳ
is updated.
(P4) Repeat (P3) to complete a batch update at users in𝒩∖ℳ.
(P5) Sets=s+1 and record the current rg as ℛ(s).
If∥ℛ(s)-ℛ(s-1)∥<ε then stops, otherwise go to (P2).Lemma 9.
The error measuree(rgk) defined in (41) is nonincreasing, namely, e(rgk+1)≤e(rgk) for any positive integer k.Proof.
If at stepk+1 an individual update occurs at i∈𝒩∖ℳ, (39) is satisfied. Since (10) is also satisfied, we have by Lemma 6 and part (b) in Assumption 1 that
(42)Rk+1≥R*⇒rik+1≤ri*,Rk+1≤R*⇒rik+1≥ri*.
Under the assumption
(43)e(rgk+1)-e(rgk)=|rik+1-r*|-|rik-r*|+|Rk+1-R*|-|Rk-R*|.
Suppose Rk+1≥R*. If Rk≥Rk+1, then
(44)e(rgk+1)-e(rgk)=-(rik+1-r*)-|rik-r*|+Rk+1-Rk⇒{=0ifrik<ri*<0o.w.
Since Rk<Rk+1 implies rik<rik+1, we have
(45)e(rgk+1)-e(rgk)=-rik+1+rik+Rk+1-R*-|Rk-R*|⇒{=0ifRk>R*<0o.w.
Using similar arguments we can analyze the case for Rk+1<R* and obtain also that e(rgk+1)≤e(rgk). If at step k+1 a batch update occurs, (15) and (40) hold for each i∈ℳ. Suppose Rk+1≥R*. If there exists an i∈ℳ such that rik+1>ri* then part (b) in Assumption 1 implies
(46)γ-ik+1-γ_ik+1<γ-i*-γ_i*;
therefore by (26) Rg*≥Rgk+1. If no such i exists, namely, rik+1≤r* for each i∈ℳ, then naturally Rgk+1≤Rg*. A similar result can be derived for the case Rk+1≤R*. We then have
(47)Rk+1≥R*⇒Rgk+1≤Rg*,(48)Rk+1≤R*⇒Rk+1≥Rg*.
Now
(49)e(rgk+1)-e(rgk)=|Rgk+1-Rg*|-|Rgk-Rg*|+|Rk+1-R*|-|Rk-R*|.
Assume Rk+1≥R*. If Rk≥Rk+1 then
(50)e(rgk+1)-e(rgk)=-(Rgk+1-Rg*)-|Rgk-Rg*|+Rk+1-Rk⇒{=0ifRgk<Rg*<0o.w.
If Rk<Rk+1, which is equivalent to Rgk<Rgk+1, then
(51)e(rgk+1)-e(rgk)=-Rgk+1+Rgk+Rk+1-R*-|Rk-R*|⇒{=0ifRk>R*<0o.w.
Applying similar arguments again we can analyze the case for Rk+1<R* and obtain also that e(rgk+1)≤e(rgk).Theorem 10.
Algorithm1 yields a sequence {rgk}k=1∞ converging to rg*, the user-grouping NEP of the bandwidth allocation game.Proof.
In the light of Lemma9, we only need to show that for each positive integer k, rgk≠rg* implies the existence of a finite integer k1 such that e(rgk+k1)<e(rgk). Suppose it is not the case Then there exists some k such that e(rgk+k2)=e(rgk) for any positive integer k2, where rgk≠rg*. Consider the update scheme that, at step k+i-m for i∈𝒩∖ℳ, the individual update occurs at user i, and at step k+n+1-m the batch update takes place for users in ℳ. Without loss of generality we assume Rk+n+1-m≥R*, then Rg(k+n+1-m)≤Rg* by (47). Since e(rgk+n+1-m)=e(rgk+n-m), (50) together with (51) implies Rk+n-m≥R*; hence Rgk+n-m≤Rg*. That is, R·-R* and Rg·-Rg* do not change their signs as the step number is increased from k+n-m to k+n+1-m. Moreover, Rk+n-m≥R* implies rnk+n-m≤rn*. Since e(rgk+n+1-m)=e(rgk+i-m-1) for i∈𝒩∖ℳ, (44) and (45) together imply Rk+i-m≥R* and thus rik+i-m≤ri*, for i∈𝒩∖ℳ. As a result, rik+n-m≤ri* for i∈𝒩∖ℳ. Note that Rgk+n-m≤Rg* and
(52)Rk+n-m=Rgk+n-m+∑i=m+1n‍rik+n-m≥R*=Rg*+∑i=m+1n‍ri*.
We conclude that Rgk+n-m=Rg* and rik+n-m=ri* for i∈𝒩∖ℳ, namely, rgk=rg*, a contradiction.


## 4. A Numerical Example

Consider a data communication network system with 100 users. Suppose 30 of them form a group. We then have𝒩={1,2,…,100} and ℳ={1,2,…,30}. The adopted utility function is
(53)Ui(ri,R)=riαi(T-R),
where the parameters αi’s are listed in Table 1. Note that the utility function, known as the generalized power function [26], has the continuity and concavity properties required by Assumption 1. In particular, it can be shown [18, page 11] easily that the maximizer
(54)argmaxrUi(r,R)=αi1+αiTi<Ti,
and thus part (a) in Assumption 2 is satisfied. Suppose the total available bandwidth T=6000, and the upper and lower bounds for total bandwidth allocated to the group is R-g=2000 and R_g=800, respectively. Assume that the individual bandwidth constraint for each user in Table 2 is used. Clearly these parameters satisfy the natural requirements of part (b) in Assumption 2. Applying Algorithm 1 yields a dynamic bandwidth allocation evolving with the implementation step, as shown in Figure 2. The left part of the figure shows the evolution of total bandwidth allocated to the group, which is composed of user 1, user 2, up to user 30. At the beginning of the algorithm, an initial feasible bandwidth allocation is allocated to each user of the system. Fix the total bandwidth allocated to the users not in the group and find the optimal total bandwidth Rg. In the example Rg is 3950.3. Since this value is greater than the upper bound R-g=2000. Rg is replaced with R-g. Fix this Rg we have the total available bandwidth T-Rg=6000-2000=4000 for users not in the group. Based on this availability of the bandwidth we can find the equilibrium point for users not in the group. In the example we have, for instance, the bandwidth r70=50, r90=57.554, and r100=38.0004. Now fix the total bandwidth of the users not in the group, and find the optimal bandwidth Rg again. In the example we obtain Rg=2115.8. Since this value is greater than the upper bound R-g=2000, Rg is replaced with R-g again. Note that the current optimal bandwidth allocation for each user outside the group is found based on the condition that the total bandwidth for the group is R-g. The current R-g and rm+1,…,rn is thus the R-g* and rm+1*,…,rn* for the user-grouping NEP in (5).Table 1
The parameters ofαi for i∈𝒩={1,2,…,100}.
i
α
i
1–10
.6111
.7052
.0283
.5209
.2591
.5082
.9732
.8182
.8588
.8966
11–20
.2995
.8800
.2552
.1921
.1866
.8611
.4446
.3866
.8320
.2065
21–30
.8978
.4595
.1634
.2687
.5207
.7724
.3874
.0444
.9868
.5230
31–40
.8437
.8919
.6856
.5178
.4420
.3801
.0318
.2159
.0853
.7969
41–50
.4018
.0498
.3165
.8712
.9314
.4257
.8662
.4806
.9083
.2505
51–60
.5266
.2448
.8384
.5257
.3498
.2571
.1688
.5992
.8110
.8489
61–70
.8448
.2350
.5083
.6694
.0907
.5430
.2980
.3818
.5339
.4265
71–80
.2320
.0284
.0260
.2743
.6945
.3300
.7505
.7957
.0537
.0092
81–90
.7281
.6644
.5853
.9190
.1673
.9720
.2196
.0382
.7078
.2290
91–100
.3526
.7095
.5887
.1088
.6468
.7311
.8634
.0226
.5252
.1512Table 2
The bandwidth constraint for each user.
User (i)
1–10
11–20
21–30
31–70
71–90
91–100
Upper bound (r-i)
100
200
290
50
78
100
Lower bound (r_i)
10
20
30
5
10
22The sequence generated by Algorithm1 for the example.
(a)
(b)


## 5. Conclusion

We have proposed a novel bandwidth allocation model based on game theory. The consideration of the user-grouping constraint distinguishes this model from the abundant ones concerning similar allocation issues. Suppose each user competes for the system bandwidth resources and is granted with a constrained decision space. In particular, some users are united in one group and the total bandwidth allocated to the group is constrained as well. Given the appropriate constraint parameters and the utility function satisfying mild continuity and concavity conditions for each user, we have shown the unique existence of the user-grouping Nash equilibrium point for the allocation game. In addition, we have shown the fairness, in a proper sense, of the allocation based on this equilibrium point. Finally, we have proposed an iterative algorithm and proved that a sequence converging to the point can be generated by the algorithm. A practical example illustrating a network satisfying our settings has been given to show how the equilibrium point can be located successfully.



---

*Source: 480962-2013-01-30.xml*