Price differentiation and control in the Kelly mechanism

Abstract

The design and implementation of resource allocation and pricing for computing and network resources are crucial for system and user performance. Among various designing objectives, we target on maximizing the social welfare, i.e., the summation of all user utilities. The challenge comes from the fact that users are autonomous and their utilities are unknown to the system designer. Under the Kelly mechanism, users bid and proportionally share resources. When user population is large and "price-taking" can be assumed, the Kelly mechanism maximizes the social welfare; however, under oligopolistic competitions, this mechanism might induce an efficiency loss up to 25% of the welfare optimum. We generalize the Kelly mechanism by designing a price differentiation and show that the efficiency gap can be closed. In particular, we analyze the resource competition game under the generalized mechanism and show that any price differentiation induces a unique Nash equilibrium and any non-dictatorial resource allocation can be implemented as a Nash equilibrium under price differentiation. We further characterize the optimality condition under which the social welfare is maximized. Based on this optimality condition, we design a feedback price control mechanism that takes observable system parameters as input and adapts to the optimal Nash equilibrium that maximizes the social welfare. © 2013 Elsevier B.V. All rights reserved.