Combinatorial Auction Test Suite (CATS) Version 2.0

Table of Contents

1.   Introduction: What is CATS?
2.   Contents of this distribution
3.   Compiling and executing
4.   File Formats
5.   License Agreement

1.  Introduction

The Combinatorial Auction Test Suite (CATS) was designed to answer a growing need in the academic community: testing, benchmarking and comparing algorithms for solving the combinatorial auction winner determination problem.  For details about the combinatorial auction winner determination problem, references, and a detailed description of all CATS distributions see:

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.

Abstract:
General combinatorial auctions---auctions in which bidders place unrestricted bids for bundles of goods---are the subject of increasing study. Much of this work has focused on algorithms for finding an optimal or approximately optimal set of winning bids. Comparatively little attention has been paid to methodical evaluation and comparison of these algorithms. In particular, there has not been a systematic discussion of appropriate data sets that can serve as universally accepted and well-motivated benchmarks. We propose a suite of distribution families for generating realistic, economically motivated combinatorial bids in five broad real-world domains. We hope that this work will yield many comments, criticisms and extensions, bringing the community closer to a universal combinatorial auction test suite.

For descriptions of the advanced features new in CATS 2.0 and their applications see:

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.

For a complete list of general CATS parameters, run CATS with the -help flag.  For a list of parameters for any particular distribution, run CATS with the -help flag and -d <dist_name>.  Helpful information about using CATS can be found on this page or in the CATS User Guide, available here in pdf format.

2.  Contents of this distribution

This distribution of CATS includes a single executable that can be used to generate from all five distributions described in sections 4.1-4.5 of the original CATS paper.

Paths is essentially as described in section 4.1 Paths in Space.   The paths distribution has been modified to address two problems that would occur in the original: a significant number of goods (10-30%) would not be part of any bid, and there would often be single bids or groups of bids that did not share any goods with the others.  These situations should not occur in CATS 2.0-- every good occurs in at least one bid, and the bid conflict graph (a graph with a node for every bid and an edge connecting bids that share some good) is guaranteed to be connected.

Regions is described in section 4.2 Proximity in Space.  The current version mirrors the one described in the paper with the following corrections:

• In the bid generation routine, we make bids on DISTINCT bundles. That is, we make XOR bids on all B_i such that two copies of the same bid do not appear.
• The routine Add_Good_To_Bundle now first checks to see if the bundle is already full and, if so, it does nothing.
• On the line for bid generation which contains "For each good, reset p(g) = rand(-deviation * max_good_value, deviation + max_good_value)" there is the typeo. The plus should be another star. That is, the line should read, "For each good, reset p(g) = rand(-deviation * max_good_value, deviation * max_good_value)"
• In the graph generation routine, we use floor(sqrt(num_goods)) rather than the ceiling.

• In the bid generation routine, the phrase "if value(B) <= 0 on B, restart ..." is redundant. We simply mean, "if value(B) <= 0, restart ..."
• In the bid generation routine, notice we generate a bid on B before beginning to search for substitutable bids. If you read the algorithm closely, you notice that we can actually generate MAX_SUBSTITUTABLE_BIDS+1 XORed bids. After all, we bid on B, then we generate at most MAX_SUBSTITUTABLE_BIDS addition XORed bids.

Arbitrary is described in section 4.3 Arbitrary Relationships.  This distribution relies on much of the same code as "regions" in exactly the way described in the paper. Notice, however, the corrections and clarifications to the regions bid generation program, described above.

Matching is described in section 4.4 Temporal Matching.  The current version mirrors the one described in the paper with the following corrections:

• Now use max(LONGEST_FLIGHT_TIME, num_times) whereever LONGEST_FLIGHT_TIME appears. This corrects against problems that can appear if flight time required is actually more time than is for sale.

Scheduling is described in section 4.5 Temporal Scheduling.  The current version mirrors exactly the one described in the paper.

Legacy distributions L1 through L8 as described in the paper are also available.  Due to the difficulty in generating large numbers of non-dominated bids with L1 and L5, a warning message will be shown if they are used.

3.  Compiling and executing

We have compiled and tested these algorithms on Sun/Solaris, Linux and Windows XP using g++.  You will probably have to edit the Makefile to get CATS to compile on your system. If there are compilation problems, check the library and include directories in the Makefile. The current Makefile is configured to compile in Linux. To solve linear programming problems, CATS uses a free library called lp_solve 4.0 by default, which is included with the distribution. If you have access to CPLEX 8.0, we strongly recommend using it in place of lp_solve 4.0. This requires only changing the comments in the Makefile (more precise instructions are in the Makefile).  To compile on UNIX, also remove the -DLINUX flags. To compile on Windows systems, replace the -DLINUX flags with -DWIN32.  Also, to compile under other systems, the following changes will (probably) need to be made:

• srand48() should be replaced with the local system's routine to seed the random number generator with an unsigned long integer.  All the current programs seed the random number generator with a call to the system clock.
• drand48() should be replaced with the local system's routine to generate a random real number between 0 and 1.
• lrand48() should be replaced with the local system's routine to generate a non-negative long integer.

4.  File Formats

Each program in this suite outputs a file with the following format:

% comments

...

goods <NUMBER OF GOODS>
bids <NUMBER OF BIDS>
0   <content of bid 0>
1   <content of bid 1>
...
<NUMBER OF BIDS-2>  <content of bid NUMBER OF BIDS - 2>
<NUMBER OF BIDS-1>  <content of bid NUMBER OF BIDS - 1>

where <content of bid i> (i between 0 and NUMBER OF BIDS-1, inclusive) represents:

<real number representing price>  <good i requested>  <good j requested>  ... <good k requested>  #

where each good number is between 0 and NUMBER OF GOODS-1

Informally, the file format is: any number of comment lines beginning with percent sign, the word "goods" followed by the total number of goods, on the next line, the word "bids" followed by the total number of bids.  Then each following line is the bid number, followed by the price, followed by each good-number requested, all terminated by a pound sign.  Each line that represents a bid is tab-delimited.

It is also possible to output in CPLEX format (in addition to CATS format) with the -cplex flag, and to convert from CATS to CPLEX using the -cats2cplex flag.

Most distributions included in this test suite generate real valued prices.  Should you wish to test on a combinatorial auction solver that only takes integer valued prices (e.g., modeling an auction with a bidding increment), you can add the -int_prices flag to the command line.   Note that this constant factor by which you multiply through must be significant -- for instance, if you rescale the prices to integers between 0 and 5, the difficulty of the problem may change.  The default factor is 1000; you can change it using the -bid_alpha flag followed by the new factor.  If you publicize results of your algorithm on the distribution, be sure to mention what factor you used! :-)

5.  License Agreement

Combinatorial Auction Test Suite (CATS)
Copyright 2003.  All Rights Reserved.
This license information must be included with the CATS code.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

                        CONDITIONS

1. Redistributions of source code must retain the above copyright notice, this list of conditions, and the following disclaimer.
2. Redistributions in binary form must contain the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
3. All modifications to the source code must be clearly marked as such.  Binary redistributions based on modified source code must be clearly marked as modified versions in the documentation and/or other materials provided with the distribution.
4. Notice must be given of the location of the availability of the unmodified current source code, e.g., http://robotics.stanford.edu/CATS/ in the documentation and/or other materials provided with the distribution.
5. No part of the program, its source code, binaries or anything derived from it can be used for profit without written permission from the copyright holders.

                        DISCLAIMER

This software is provided "as is" and any expressed or implied warranties, including, but not limited to, the implied warranties of merchantability and fitness for a particular purpose are disclaimed.  In no event shall any of its authors or contributors be liable for any direct, indirect, incidental, special, exemplary, or consequential damages (including, but not limited to, procurement of substitute goods or services; loss of use, data, or profits; or business interruption) however caused and on any theory of liability, whether in contract, strict liability, or tort (including negligence or otherwise) arising in any way out of the use of this software, even if advised of the possibility of such damage