A near optimal mechanism for energy aware scheduling

With the increased popularity of cloud computing it is of paramount importance to understand energy-efficiency from a game-theoretic perspective. An important question is how the operator of a server should deal with combining energy-efficiency and the particular interests of the users. Consider a cloud server, where clients/agents can submit jobs for processing. The quality of service that each agent perceives is given by a non-decreasing function of the completion time of her job which is private information. The server has to process the jobs and charge each agent while trying to optimize the social cost, defined as the energy expenditure plus the sum of the values of the cost functions of the agents. The operator would like to design a mechanism in order to optimize this objective, which ideally is computationally tractable, charges the users “fairly” and induces a game with an equilibrium. We describe and analyze one such mechanism called modAVR, which relies on an adaption of the well-known Average Rate (AVR) algorithm for scheduling the jobs. We prove that modAVR combines the aforementioned properties with a constant Price of Anarchy, i.e., despite the fact that it is based on an algorithm designed for optimizing the energy alone, every equilibrium it results in is near-optimal for the total social cost as well. The existence of a Nash equilibrium is proven for both mixed strategies and (in a slightly more restricted setting) pure strategies. A further interesting feature of modAVR is that it is indirect: each user needs only to declare an upper bound on the completion time of her job, and not the cost function. Additionally, we prove that for the corresponding mechanism that uses the classical YDS algorithm for scheduling the jobs no pure Nash equilibrium can exist for a very broad and natural class of cost functions. Finally, we are able to extend several of our results for modAVR to a mechanism based on a slight variation of the YDS algorithm. This variation is known also to not admit Nash equilibria in pure strategies.