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.
What's up with dummy goods? A number of people have
emailed me over the years to ask how dummy goods work; this evidently needs to
be cleared up. These are goods that aren't really sold in the auction, but that
are added by CATS to enforce additional XOR constraints (specifically, that one
bidder can't win more than one of his bids). Thus, when you ask CATS to generate
an auction with 20 goods, you'll see higher-numbered goods in some of the bids;
these are the dummy goods. The number of dummy goods are given in the header at
the top of the file. You can learn more about them on page 99 of my
thesis.
Dummy goods can also be used to tell which agent each bid comes from.
Every bid that includes the same dummy good comes from the same bidder. Every
bid without any dummy goods is a unique bid from a different bidder. Thus, you
can use CATS to model agents' valuations in a combinatorial auction, as well as
for generating input for winner determination algorithms.
Current Version: 2.2. That version is only available from our new
GitHub repository.
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
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:
GitHub repository. Use this one! It was updated in 2019
and fixes compilation errors that modern compilers threw when faced with our
20-year old code. It also includes a
Windows
executable.
If you find any bugs or other problems with CATS, please report them on the
GitHub page, or better yet,
submit fixes there. At this point the code is no longer able to be supported by
its authors.