Computational Efficient Pricing for Resource Providers in a Grid Environment

Ensuring truthfulness amongst self-interested agents who are bidding against one another in an auction is computationally expensive. The Vickrey-Clarke-Groves mechanism guarantees that each agent’s dominant strategy is to tell the truth, but it requires solving n + 1 optimisation problems for n agents. This paper presents an algorithm for computing prices for all agents in the same asymptotic time complexity as solving just one problem in the case of n agents bidding for m tasks where m < n, thus solving an open problem presented by Nisan and Ronen [14] for the specific case of task scheduling. This problem was also identified by Hershberger and Suri [9]. We also propose the use of constraints in conjunction with Operations Research algorithms to further improve the performance of truthful mechanisms in the context of a grid scenario, where resource providers are competing for tasks in an auction.