A comparison of distributed and centralised agent based bundling systems

ABSTRACT

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 outlier cases that are computationally problematic. In contrast, distributed mechanisms are intrinsically less than optimal for sellers, but demonstrate signifcantly 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. Consequently, we have completed an 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.

REFERENCES

• 1: D. Abramson , R. Sosic , J. Giddy , B. Hall, Nimrod: a tool for performing parametrised simulations using distributed workstations, Proceedings of the 4th IEEE International Symposium on High Performance Distributed Computing, p.112, August 02-04, 1995
• 2: Rachel A. Bourne, John Bigham, and Stefan Poslad. Effect of market type in continuous environments: The need for intermediaries.
• 3: Viet Dung Dang , Nicholas R. Jennings, Optimal clearing algorithms for multi-unit single-item and multi-unit combinatorial auctions with demand/supply function bidding, Proceedings of the 5th international conference on Electronic commerce, p.25-30, September 30-October 03, 2003, Pittsburgh, Pennsylvania [doi>10.1145/948005.948009]
• 4: Stephen J. Fink , Scott B. Baden , Scott R. Kohn, Flexible Communication Mechanisms for Dynamic Structured Applications, Proceedings of the Third International Workshop on Parallel Algorithms for Irregularly Structured Problems, p.203-215, August 19-21, 1996
• 5: Peter Gradwell , Julian Padget, Markets vs auctions: Approaches to distributed combinatorial resource scheduling, Multiagent and Grid Systems, v.1 n.4, p.251-262, December 2005
• 6: Minghua He and Nicholas R. Jennings. Southamptontac: Designing a successful trading agent. In ECAI, pages 8--12, 2002.
• 7: James F. Kurose , Rahul Simha, A Microeconomic Approach to Optimal Resource Allocation in Distributed Computer Systems, IEEE Transactions on Computers, v.38 n.5, p.705-717, May 1989 [doi>10.1109/12.24272]
• 8: Kevin Eric Leyton-Brown , Yoav Shoham, Resource allocation in competitive multiagent systems, Stanford University, Stanford, CA, 2003
• 9: Kevin Leyton-Brown , Eugene Nudelman , Yoav Shoham, Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.556-572, September 09-13, 2002
• 10: Kevin Leyton-Brown , Mark Pearson , Yoav Shoham, Towards a universal test suite for combinatorial auction algorithms, Proceedings of the 2nd ACM conference on Electronic commerce, p.66-76, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352879]
• 11: Kevin Leyton-Brown, Eugene Nudelman, and Yoav Shoham. Empirical Hardness Models for Combinatorial Auctions, chapter 19. MIT Press, 2006.
• 12: Tim Finin et. al. Li Ding. Strategies and Heuristics Used by the UMBCTAC Agent.
• 13: Michael J. North , Nicholson T. Collier , Jerry R. Vos, Experiences creating three implementations of the repast agent modeling toolkit, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.16 n.1, p.1-25, January 2006 [doi>10.1145/1122012.1122013]
• 14: David Parkes. Computational mechanism design - taming the strategic dragon without invoking the complexity monster. Talk given at AAMAS03.
• 15: S. Phelps , M. Marcinkiewicz , S. Parsons, A novel method for automatic strategy acquisition in N-player non-zero-sum games, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160760]
• 16: T. Sandholm. Optimal winner determination algorithms. In Peter Cramton, Yoav Shoham, and Richard Steinberg, editors, Combinatorial Auctions, chapter 14. MIT Press, 2005.
• 17: Tuomas Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence, v.135 n.1-2, p.1-54, 02/01/2002 [doi>10.1016/S0004-3702(01)00159-X]
• 18: Tuomas Sandholm, Subhash Suri, Andrew Gilpin, and David Levine. CABOB: A fast optimal algorithm for combinatorial auctions. In Management Science, Special Issue on Electronic Markets, 2005.
• 19: Rajan Suri and Yu-Chi Ho. Resource management for large systems: Concepts, algorithms, and an application. In IEEE Transactions On Automatic Control Vol 4, pages 651--662, 1980.
• 20: et al. Torsten Eymann. Catallaxy-based grid markets.
• 21: Chee Shin Yeo and Rajkumar Buyya. A taxonomy of market-based resource management systems for utility-driven cluster computing, 2004.
• 22: Kevin Layton-Brown, Yuzo Fujishima and Yoav Shoham. Taming the computational complexity of combinatorial auctions: Optimal and approximate approaches, 1998.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

General Terms:
Algorithms

Keywords:
allocation, combinatorial auctions, distributed market performance, grid, quote driven market, resource, trading agents