A clock-and-offer auction market for grid resources when bidders face stochastic computational needs

Although significant technical advances have been made in the commercial deployment of grid computing, the pricing and allocation of distributed computing resources remains understudied. We develop a customized clock auction that is able to allocate grid resources and discover separate prices for the different computing resources under the condition that buyers do not know with certainty how much of these resources they will need. The proposed clock auction facilitates the discovery of unit prices for the resources in each time period in a finite-horizon market. Our mechanism exploits the lopsided nature of the grid market where a small number of large-scale jobs are expected to be completed by a large number of heterogeneous, distributed machines. The traditional stopping rule used for clock auctions is not effective in our setting, and therefore we design several adaptations that can be implemented in real time, geared toward ending the auction process quickly while producing a close-to-efficient allocation. Our extensive computations show that our clock-andoffer auction outperforms the traditional clock auction in terms of computational tractability, social welfare, and expected bidder's utility. For large problems of practical interest, we develop a transportation-based heuristic for the NP-complete bid feasibility problem and demonstrate theoretically and computationally that it quickly produces high-quality solutions to the overall problem.