Envy-free auction mechanism for VM pricing and allocation in clouds

A major challenging problem in clouds is designing efficient mechanisms for virtual machine (VM) allocation and pricing. Failure to fully consider the incentives of cloud providers and customers can cause undesirable outcomes, such as no envy-freeness and untruthfulness, which may lead to system instability and relatively low profit for cloud providers. In this study, we proposed a combinatorial auction-based mechanism to address such problem in the presence of multiple types of VMs in a single provider scenario. The proposed mechanism combines two general ideas: consensus estimate that can avoid market manipulation and yields an approximate optimal target revenue with the consensus estimate technology, and RevenueExtraction that can determine the winners and equally shares the target revenue generated by consensus estimate among them with a single sale price. Using the two ideas, the proposed mechanism can simultaneously promise truthfulness and envy-freeness while achieving an approximate optimal revenue. The results of extensive simulation experiments demonstrate that our schemes can efficiently deliver stable and desirable performance, especially in large-scale and over-supplied cloud markets.