Markets vs auctions: Approaches to distributed combinatorial resource scheduling

Abstract

Grid computations will be enabled by participants trading resources in order to construct bundles of goods or services that constitute experiments in science, engineering and, now emerging, social sciences. A combinatorial auction (CA) is a natural choice for optimal allocation, but the space and time dimensions that characterise a Grid would appear to indicate they are incompatible. This paper proposes that an analogue of a physical commodities market seems more appropriate and that there is a class of bundling problem whose complexity properties appear to make the utilisation of a CA impractical.

A simulation environment, BrickWorld, is described which comprises a distributed tier of “TraderAgents” and multiple distributed single item auctions (MDAs). The issues associated with the complexity of bundling are evaluated, in particular those arising when attempting to provide useful combinations of items in situations when the multi-dimensionality of the bundle would make it impractical to finish the NP-complete optimisation successfully in the soft real-time setting that is the Grid.

Finally, the evaluation strategy presented helps demonstrate that for small bundling problems, a single CA continues to provide a high level of performance, but as the complexity level of the problem increases and the problem becomes distributed a system of MDAs may prove more effective.