TR-15-02 Designing a Strategy-Proof Online Auction Mechanism for Deadline Aware Cloud Resource Allocation

Cloud computing facilitates resource sharing and provides flexibility and affordability. Resource allocation and pricing is critical to the system performance, and auction has been believed as a promising approach for fairness and effi- ciency. To design a practical cloud resource auction, we need to consider five major challenges, including strategy-proofness, online framework, heterogeneous request, deadline-awareness, and social welfare maximization. However, none of existing works have fully addressed these five challenges. In this paper, we present the first strategy-proof online combinatorial auction for deadline-aware cloud resource allocation which jointly considers the five design challenges. Our analyses show that our auction achieves both strategy-proofness and approximate efficiency on social welfare. Our evaluation results verify the efficacy of our design and show that our auction achieves good social welfare without the loss on request completion.