The Effects of Monopolistic Pricing in a Network Resource Allocation Game Danielle Hinton 6 454 Graduate Seminar in Area 1 November 3 2004 1 Introduction There is a recent body of literature that seeks to quantify the performance degradation of networks in the absence of centralized control via game theoretic techniques Users are considered as selfish agents participating in a noncooperative game who choose routes consistent with the notion of a Nash Equilibrium As we saw last week Khi04 results by Johari and Tsitsilikis have shown that equilibrium performance degrades to of the social optimum which could be achieved with centralized planning JoT03 Other results by Roughgarden and Tardos RoT00 show that if the latency of each edge is a linear function of its congestion the total latency of the routes chosen by selfish network users is at most 4 3 times the minimum possible total latency In the more general case where edge latency is assumed to be continuous and non decreasing in the edge congestion they also prove that latency is no more than the total latency incurred by optimally routing twice as much traffic While the former models captures the decentralized routing decisions of users and the effects of those decisions on performance the literature neglects that the networks are controlled by service providers whose objective isn t operating at an efficient social optimum but rather is to maximize profits The practically motivated nuance incorporated in the work of D Acemoglu and A Ozdaglar is the consideration of the effect of monopolistic pricing on congestion in unregulated networks In Flow Control Routing and Performance from Service Provider Viewpoint the authors consider a two staged game where the single profit maximizing service provider sets prices anticipating the subsequent behavior of users and then the users taking prices and latency as given game selfishly to optimize their own objectives The authors develop results on the equilibrium behavior of such a network characterize the equilibrium prices and develop insights into why monopoly pricing may improve the performance of the system They also compare the performance of the Monopoly Equilibrium to the social optimum full information and zero prices In the summary which follows we first outline the network model in section 2 In Section 3 we characterize the Network Equilibrium In Section 4 we show the derivation of the optimal monopoly pricing scheme and explain their effects on congestion In Section 5 we compare the performance of the network under monopolized pricing to the performance in the centrally controlled zero priced social optimum We conclude with a summary of the key contributions of this work 2 Network and Game Theoretic Model Danielle Hinton Nov 3 2004 6 454 The network is modeled as having I parallel links and J users where J 1 The following parameters are used to describe the network and users x ij the flow of user j on link i I j x ij the total flow rate of user j on all links i 1 J i x ij total flow on link i j 1 l i i l i x as x C i u j j pi flow dependent latency function which specifies the delays in transmission as a function of the link load Continuous and strictly increasing l i 0 0 Capacity constraint on the links utility function price of link i The utility function is assumed to be strictly concave that is that we are considering elastic traffic delay tolerant where increased data rates has diminishing returns for users We also assume that the utility function is nondecreasing and continuously differentiable which allows the authors to characterize the equilibrium and the equilibrium prices shown here in sections 3 and 4 For each user there is also an associated payoff function which depends not only on that user s own flows but also on the flows of all the other users via the latency they all create on a given link Each user acts as a price taker and a link load taker taking prices and link loads as given and choosing flows to maximize their payoff function I I I v j x j p u j x ij l i i x ij p i x ij i 1 i 1 i 1 3 Network Equilibrium To determine the equilibrium behavior if this network we consider the game between selfish users who given prices anticipate the amount of congestion on all routes and choose their own routes according to the notion of the Nash Equilibrium NE Recall that a Nash Equilibrium is a steady state of the play of a strategic game in which no player can profitably deviate given the actions of the other players More formally where a A of actions a i ai a i ai 2 ai Ai Danielle Hinton Nov 3 2004 6 454 No player i has an action yielding an outcome that he prefers to that generated when he chooses ai given that every other player j chooses his equilibrium action a j In the model described above we assumed that the users were both price and latency takers that is they take the latency of the links as given In the NE users take into account the effect of their own flow on congestion In the Wardrop Equilibrium WE each user s flow is assumed to be small relative the total flow on a given link so that when that user switches his flow there is no substantial change in the link latencies Wardrop Principle As such in the WE users ignore the effects of their own flow on congestion Formally the WE says that a vector rl l 1 2 KK L is called a Wardrop equilibrium if for each group l the following holds Let K l K be the set of routes actually used that is the set of classes such that k K l k K l pl k 0 such that Bk r Bk r k K l k K l So the principles are fulfilled because in this state no group can reduce the costs by switching from its current paths to other ones connecting the same origindestination pair Following HaM85 the authors prove that as the number of users becomes large the NE converges to the WE see pp 17 9 And so in this work the equilibrium of the network is characterized in terms of the WE For the model described above the Generalized Wardrop Equilibrium GWE generalized because it is conditioned on a given vector of prices is defined as the vector of flows of all the users x x1 KKK x J in the network such that for each x j x j arg max v j y j p j J 0 y ij Ci i The existence and the uniqueness of the GWE is proved by considering the optimization problem i maximize u j j l i z dz p i i i I 0 subject to j x j i I x ij i i I i j i j J x ij 0 i j The proposition is proved as follows Since the objective function is continuous …