Efficiency Loss in a Network Resource Allocation Game Ashish Khisti October 26 2004 1 Introduction In this report we summarize the paper by Ramesh Johari and John Tsitsiklis 1 This paper considers the problem of distributed resource allocation mechanisms for the Internet The current Internet is used widely by a heterogenous population of users Different users place different values on the perceived network performance Moreover there are some fundamental constraints on the maximum rate each link can support How can the bandwidth be efficiently allocated to different users in such a setting To make the problem more concrete consider the example shown in figure 1 taken from 2 User 1 Path 1 Src 1 Dest 1 Link A CA 2 Src 2 Link B CB 1 Dest 2 User 2 Path 2 Src 3 User 3 Path 3 Dest 3 Figure 1 Two link Network In the figure above there are three users 1 labelled 1 2 and 3 and two links A and B The path belonging to user 1 uses both links A and B Similarly user 2 uses link A while user 3 uses link B only Also suppose the capacities of the two links are CA 2 and CB 1 How should the rates be allocated to the three users One possible solution is to do a max min fair allocation This particular allocation has a desirable property that it gives the most poorly treated user i e the user with the lowest rate the maximum possible share without wasting network resources The max min allocation in this example is d1 d3 0 5 and d2 1 5 2 However max min fair allocation may not always be desirable Suppose user 1 only requires 0 25 units of bandwidth and does not care about the rest Then it is preferable to assign d1 0 25 d2 1 75 and d3 0 75 In general one should consider the utility function of users before doing bandwidth allocation Suppose each user r 1 2 R has a utility function Ur The network optimization problem is to allocate each user a data rate dr to solve the following problem R max Ur dr d1 d2 dR r 1 1 Each 2 We source destination pair refers to one user divide link B equally between user 1 and 3 On link A since user 1 uses only 0 5 units user 2 gets 1 5 units 1 The set of feasible rate vectors d1 d2 dR must satisfy capacity constraints on each link 3 We will impose the following constraint on the utility functions A SSUMPTION 1 For each r Ur dr is a continuously differentiable non decreasing strictly concave function The above assumption has been used throughout the paper An important implication of this assumption is that the demand of each user is elastic The utility keeps increasing as the user gets higher rate In particular utility functions shown in 2 b are not permissible a Permissible Utility Function b Not Permissible Utility Function Figure 2 Permissible Utility Functions To solve this optimization problem the network manager needs to know the utility function of each user In practice it may not be possible The idea behind distributed resource allocation is to introduce a pricing mechanism that solves the above optimization problem in a distributed manner Each user performs a local computation based on its own utility function and submits a bid to the network The network manager collects these bids and determines the price to charge the users In the remainder of this report we will explain this distributed pricing mechanism in more detail In Section 2 we will consider the case of a single link All users wish to use a single link with total capacity of C We will first describe the pricing mechanism that solves the global optimization problem This particular mechanism assumes that the users are price taking i e they do not anticipate the effect of their bids on the price Then we will consider the case when the users are price anticipating In this case there is a unique Nash equilibrium Moreover at the Nash equilibrium the aggregate utility is within 3 4 of the optimal value Section 3 generalizes these single link results to the case of an arbitrary network 2 Single Link Case Suppose R users wish to communicate over a single link with capacity C Each user is assigned a portion of this capacity say dr We wish to solve the following problem SYSTEM maximize Ur dr 1 dr C 2 dr 0 r 1 2 R 3 r subject to r 3 For the single link case this constraint is r dr C For the network case this constraint will be formalized in section 3 2 Under assumption 1 the above problem has a unique optimal solution We will now describe a specific pricing mechanism that solves this problem in a distributed manner Suppose user r gives a payment of wr to the link manager we assume that wr 0 Given the vector w w1 w2 wr of bids the link manager chooses a rate allocation d d1 dr such that dr wr where r wr C 4 In the subsequent sections we will consider two different ways in which the users will interact with this pricing mechanism First we will consider the case when the users are price taking and establish the existence of a competitive equilibrium Then we will consider the case when the users are price anticipating and establish the existence of a Nash equilibrium and study its properties 2 1 Price taking Users and Competitive Equilibrium In this section we consider a competitive equilibrium between the users and the link manager which was first observed in 3 A central assumption here is that the users are not price anticipating More specifically given a price 0 each user r acts to maximize the following payoff function over wr 0 Pr wr Ur wr wr 5 The first term represents the utility to user r of receiving a rate allocation equal to wr The second term is the payment wr made to the manager The users are price taking in a sense that they take the price as a given quantity and do not anticipate its dependence on wr We say that a pair w is in competitive equilibrium if each user maximizes his her payoff in 5 and the network sets the price according to 4 At the competitive equilibrium we have the following conditions Pr wr Pr w r r wr C for w r 0 r 1 R 6 7 We now present the main result for this pricing mechanism T HEOREM 1 Under assumption 1 there exists a unique competitive equilibrium i e a unique pair w that satisfies 6 7 Furthermore the corresponding rate vector d w satisfies the SYSTEM problem 1 3 Proof Outline The system problem can be formulated as a lagrangian optimization problem L d Ur dr dr C r r Differentiating with respect to dr we have Ur dr if dr 0 Ur dr if dr 0 3 Substituting dr wr we have wr wr Ur Ur if …