WS-Auction: Mechanism Design for aWeb Services Market

As distributed systems become more complex in terms of the functionality and heterogeneity of their components, the ownership of those components becomes an issue in the allocation phase of the system design. The mechanism design community has addressed the allocation problem in an efficient, truthful, strategyproof way in several settings such as combinatorial auctions, on-line auctions, distributed allocation computation or information elicitation. We are extending the scope of mechanism design by shifting the focus from efficient individual allocations to systemwide efficient allocations. In this setting, we are addressing the spatial and temporal fragmentation of the information characteristic to a distributed market. This paper shows that the necessary mechanism for obtaining an efficient outcome in a distributed market is an indirect auction with provisional allocation and historical information. We also suggest and evaluate the bidding strategy in such an environment, and we show that the truthful strategy is to bid the true valuation at the arrival time in the system.