Combinatorial Auction Test Suite (CATS)

A few bugs have recently been fixed: March 2007.

The Combinatorial Auction Test Suite is a generator of combinatorial auction instances for the testing of CA algorithms. It features five distributions of instances from realistic, economically motivated domains, as well as a collection of artificial distributions that have been used in the literature. Since the release of CATS 1.0 in 2000, it has become a standard benchmark for the evaluation and comparison of CA algorithms.

Current Version: 2.0

Major enhancements over version 1.0:

the ability to generate much harder instances
a revised, more realistic and more efficient "paths" generator
the capacity to create hybrid distributions (distributions over generators) and to sample randomly from a distribution's parameters
the capacity to create custom distributions that emphasize certain qualities of the built-in distributions (as we did for hardness; this feature could also be used to select instances that score highly on a custom "realism" metric, for example)
the ability to generate a specified number of "non-dominated" bids
output in CATS and CPLEX formats
the inclusion of all distributions into a single executable, with a flexible and easy-to-use interface

Documentation:

The README that describes basic CATS usage
The CATS User Guide, which describes how to use the advanced features of CATS 2.0 (pdf format)
The paper that describes the distributions in postscript and pdf.
Towards a Universal Test Suite for Combinatorial Auction Algorithms
Leyton-Brown, K., Pearson, M., & Shoham, Y.
In the Proceedings of ACM Conference on Electronic Commerce (EC-00), 2000.
The paper that describes some of the new, advanced features in CATS 2.0 in postscript and pdf.
Boosting as a Metaphor for Algorithm Design
Leyton-Brown, K., Nudelman, E., Andrew, G., McFadden, J., & Shoham, Y.
A working paper. Two short versions covering different aspects of the full paper were presented at IJCAI '03 and Constraint Programming '03.
There is also a chapter on CATS in the book Combinatorial Auctions (Cramton, Shoham, Steinberg, eds.), MIT Press.

Downloads:

Executable distributions:
Source distributions:
- CATS 2.0 as a tarred gzipped source distribution
- CATS 2.0 as a zipped source distribution
Old version:
- CATS 1.0 as a tarred gzipped source distribution
- CATS 1.0 as a zipped source distribution

If you find any bugs or other problems with CATS, please contact Kevin Leyton-Brown (http://www.cs.ubc.ca/~kevinlb). Please note that I'm not able to address software-support questions; however, I'll do my best to correct any bugs that are found.

Last updated 03/02/2007