Proportional Pricing Mechanisms for Utility Maximization in Shared Computing Facilities

Nahum Shimkin Technion - Israel Institute of Technology Faculty of Electrical Engineering Technion City Haif
Tuesday, 16 Feb 2010 (all day)
A-212 (STCS Seminar Room)
Motivated by the recent advent of cloud computing facilities that offer online computing power on demand, we consider a large service facility that offers simultaneous service to a large number of heterogeneous jobs, each associated with a distinct user. The execution time of each job depends on the amount of resources applied to it. Our main concern here is in maximizing the social utility, which comprises of the users' service utility minus their delay cost. This requires regulating the distribution of available resources between the active users, as well as controlling the arrival rates of the different job types. In this work, we formulate a fluid queueing model that captures the essential ingredients of this problem. We proceed to characterize the social optimum, and propose a pricing mechanism that uniquely induces that social optimum, without requiring the system to be aware of the users' attributes and preferences. The proposed mechanism divides the available resources between the active users according to their price bids, and is reminiscent of proportionally fair pricing mechanisms of network flow control. We further consider briefly some relations with revenue-maximizing prices, and stability properties of the proposed price setting mechanism (joint work with Ishai Menache and Asu Ozduglar, MIT).