Competitive mechanisms for energy-efficient cloud computing

We present a general model for the operation of a cloud computing server comprised of one or more speed-scalable processors. Typically, agents submit tasks to such a cloud computing server in an online fashion, and the server operator has to schedule the tasks and decide on payments without knowledge of tasks arriving in the future. Moreover, the operator should take the different incentives of the agents into account and aim to minimize the energy expenditure. For both the offline and the online setting we provide mechanisms with several desirable properties: The induced game admits a Nash equilibrium, the mechanism is budget balanced, has low communication complexity, is computationally tractable, is intuitive to explain, but above all, has a constant Price of Anarchy. Therefore, the total costs are not too far off from the social optimum. We extend our results to the case of multiple processors and to the Bayesian setting.