A comparison of distributed and centralised agent based bundling systems

The use of trading agents to manage the allocation and bundling of resources across computer networks is well established and literature to date has focused on a variety of auction and distributed market type mechanisms that use economic principles to determine the ``best'' allocation. An empirical analysis of a number of solver algorithms, principally the Centralised Combinatorial Auction Solver (CASS), has shown that those using bounded search techniques are typically able to solve a majority of cases in linear time, while there remain a number of outlyer cases that are computationally problematic. In contrast, distributed mechanisms are intrinsically less than optimal for sellers, but demonstrate significantly less variance in computation time. A proper understanding of the different performance properties and suitability of the different techniques is necessary in order to make an informed choice between a distributed market and a centralised auction. In this work we have completed a meaningful empirical evaluation of CASS, a centralised mechanism, against two distributed mechanisms: (i) Multiple Distributed Auctions (MDAs) and (ii) Quote Driven Markets (QDMs). Uniquely, we carry out simulations of all three mechanisms using a common dataset, generated by the Combinatorial Auction Test Suite (CATS), providing a real basis for comparison. The main results presented are that distributed mechanisms deliver (i) increases in the number of items traded (ii) a greater proportion of bidder requirements being satisfied, but (iii) potentially less optimal bundle solutions and (iv) consistent run times with low overall variance when compared with centralised algorithms.