A general framework for energy-efficient cloud computing mechanisms

We present a general model for the operation of a cloud computing server comprised of one or more speed-scalable processors. Typically, tasks are submitted to such a cloud computing server in an online fashion, and the server operator has to schedule the tasks and decides on payments without knowledge about the tasks arriving in the future. Although very natural, this cloud computing problem on speed-scalable processors has not been studied from a mechanism design perspective in the online setting. We provide a mechanism for this setting, both for a single and multiprocessor environment, that has several desirable properties: (1) the induced game admits a subgame perfect equilibrium in pure strategies and therefore a pure Nash equilibrium, (2) the Price of Anarchy is constant, (3) the mechanism is budget balanced, i.e., the sum of the payments of the agents is equal to the total energy costs, (4) the communication complexity is low, (5) the mechanism is computationally tractable for both the service operator and the agents, and (6) the agents' payment is also intuitive and easy to communicate to them. We also provide a second mechanism with a better Price of Anarchy, which in turn is more involved to implement. We are able to extend our mechanisms and results to the Bayesian setting, where the type of each agent is drawn independently from some underlying distribution and agents are minimizing their expected costs. In this setting we also show the same approximation factor of our mechanism as in the basic online setting in both the single and the multiprocessor environment.