Combinatorial Auction Test Suite

Combinatorial Auction Test Suite (CATS) Version 1.0

Table of Contents

1.   Introduction: What is CATS?
2.   Contents of this distribution
3.   Compiling and executing
4.   File Formats
4.1    Integers versus Real Numbers
4.2    Multi-unit File Format
5.   Contact Information for Comments & Questions
6.   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., to appear 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.

2. Contents of this distribution

This distribution of CATS includes all five distributions described in sections 4.1-4.5 of the paper, and additionally a multi-unit distribution for one real world scenario (paths in space).

paths.c described in section 4.1 Paths in Space. The current version exactly mirrors the one described in the paper.

multipaths.c briefly described in section 4.1.3 Multi-Unit Extensions: Bandwidth Allocation, Commodity Flow. The current version uses the paths codebase with some slight modifications:

When generating the graph, we assign each edge a capacity cap, which is generated by sampling rand_int(1, MAX_CAP).
When generating bids, when we choose two cities between which to ship. we also choose a value capacity which represents the number of units that need to be shipped from city1 to city2. This is done by sampling as before, rand_int(1, MAX_CAP).
When generating possible paths, we only consider those edges which have their maximum capacity >= capacity desired. This eliminates paths which the prospective bidder would not want to purchase because the bidder would not be able to ship all his units on that path.
When pricing bids, instead of using value = d * Euclidean_Distance(city1, city2) we use value = d * Euclidean_Distance(city1, city2) * capacity^(1 + ADDITIVITY) (ADDITIVITY is a new parameter to the distribution.) and as usual we bid value - cost, but this time also redefine cost to be cost = Euclidean_Distance(city1, city2) * capacity^(1 + ADDITIVITY) (In effect, all this does is multiply all bids through by the capacity they desire to the 1+ADDITIVITY power.)

regions.c 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.

The following clarifications should be made regarding the distribution:

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.c described in section 4.3 Arbitrary Relationships. This program builds on the regions bid generation program in exactly the way described in the paper. Notice, however, the corrections and clarifications to the regions bid generation program, described above.

matching.c 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.c described in section 4.5 Temporal Scheduling. The current version mirrors exactly the one described in the paper.

Legacy distributions: at this time, we provide no code to generate legacy distributions. This feature will be forthcoming.

CPLEXConvert.cpp CATS bid file format to CPLEX converter.
Usage: CPLEXConvert file.txt.
This will read in CASS file "file.txt" and write CPLEX input file "file.lp".

make_int_bids.c Converter to change real-valued bids to integer-valued bids.
Usage: make_int_bids [-h] [-alpha FLOAT] [-beta FLOAT]
This program takes a bid file (from standard input) and, for each bid, takes the price x offered and changes it to (alpha * x + beta), rounding the result to the nearest integer, and outputs the bid file that results (to standard output).
If unspecified, ALPHA defaults to 100 and BETA to 0.5.
The -h parameter displays this usage message.

3. Compiling and executing

We have compiled and tested these algorithms on Sun/Solaris using gcc or g++, as appropriate. (.c are C files, .cpp are C++ files) . To compile on Sun/Solaris we needed to link in the math library (with the command line option -lm to gcc); for other systems an analogous option may be necessary. 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.

At the current time, all the parameters for the distributions are defined at the top of each .c file. To change these parameters, you need to change the values in the .c file, then recompile. If there is a strong push to read in parameters for the distributions at the command line, such a change will be made. If wish for the ability to read parameters from the command line, e-mail the person listed under the contact information below with the request. Until command line parameters are added, there is an easy hack one can use to make it seem as if command line parameters exist. For instance, if you wish to set NUMGOODS on the command line, do the following:

Comment out the #define line defining NUMGOODS.
Compile the program with -DNUMGOODS=x. For instance, run "gcc paths.c -o paths -lm -DNUMGOODS=50 ; ./paths" Running command lines like this will make it seem as if NUMGOODS is a comamnd line parameter.

4. File Formats

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

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 the word goods followed by the total number of goods (on the first line). 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.

A program is included in this distribution that converts our file format to a CPLEX input file. See the "contents of this distribution" section for more information.

4.1 Integers versus Real Prices

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 need to convert the files so they have integer valued bids. We recommend generating the bids as usual, then multiplying through each price by a constant factor and rounding to the nearest integer. To do this, we have provided a program called make_int_bids.c; for details see the "content of this distribution" section. 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. If you publicize results of your algorithm on the distribution, be sure to mention what factor you used! :-)

4.2 Multi-unit File Format

At the current time, there is only one multi-unit distribution generator. (This is for the paths-in-space problem, described above.) The file format for the multi-unit case is a slight change from the single-unit one.

First, after the line which gives the number of bids, there is now a line of maximums, which gives the maximum number of units of each good, in order, separated by tabs. Specifically, the line says:

maximums <number_of_units_of_good_0> <number_of_units_of_good_1> ... <number_of_units_of_maxgood>

In addition, following each good requested there is now a tab, the number of units of that good that is required then another tab. That is, instead of printing:

0 5.0 1 3 #

for bid 0 to request goods 1 and 3 at a value of 5.0, the new format is:

0 5.0 1 4 3 1 #

for bid 0 to request 4 units of good 1 and 1 unit of good 3 all at a value of 5.0.

5. Contact Information for Comments & Questions

We welcome feedback on the distributions, default parameters, suggestions for future distributions and ideas of other important real world domains for which combinatorial auctions should be tested. A point of contact is listed below--this is also the person to write if you have any questions about compiling, installing, or running the test set generators, or if wish to report errors, bugs, typos, etc.

Mark Pearson
Stanford Dept. of Computer Science
mpearson@cs.stanford.edu

6. License Agreement

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

CONDITIONS

Redistributions of source code must retain the above copyright notice, this list of conditions, and the following disclaimer.
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.
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.
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.
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