Bill Estimation in Simplified Memory Progressive Second Price Auctions

摘要

Vertical elasticity, the ability to add resources on-the-fly to a virtual machine or container, improves the aggregate benefit clients get from a given cloud hardware, namely the social welfare. To maximize the social welfare in vertical elasticity clouds, mechanisms which elicit resource valuation from clients are required. Full Vickrey-Clarke-Groves (VCG) auctions, which allocate resources to optimize the social welfare, are NP-hard and too computationally-complex for the task. However, VCG-like auctions, which have a reduced bidding language compared with VCG, are fast enough. Such is the Simplified Memory Progressive Second Price Auction (SMPSP). A key problem in VCG-like auctions is that they are not completely truthful, requiring participants, who wish to maximize their profits, to estimate their future bills. Bill estimation is particularly difficult since the bill is governed by other participants' (changing) private bids. We present methods to estimate future bills in noisy, changing, VCG-like auction environments. The bound estimation method we present leads to an increase of 3% in the overall social welfare.