An Implementation of the Combinatorial Auction Problem in ECLⁱPS^e

In a traditional auction, items are placed “up for bids” in an arbitrary sequence. For many bidders, this model is inadequate because the individual items increase in value when held in conjunction with other items. Combinatorial auctions allow bidders to bid upon multiple items simultaneously. While this resolves the problems for the bidders, it increases the problem of the auctioneer: determining the optimal selection of bids to maximize revenue is NP-complete.

[Sandholm1999] suggests an algorithm that reduces the search space considerably. His algorithm, a DFS of the problem space using an ancillary data structure called a Bidtree, takes advantage of two properties of “real-life” auctions: that the bids submitted would be sparse and that the order in which bids are selected is irrelevant. The Bidtree helps select the next bid to be considered.

The goal of this project is to evaluate the general principles and algorithms developed for constraint processing in recent years, as well as the tools and languages facilitating the use of constraints for problem solving using the auction problem as a benchmark. By comparing general constraint-processing algorithms against methods tailored for this task, the power of such general algorithms can be demonstrated. This project was initiated during a class in the department of Information and Computer Science at the University of California, Irvine. Specifically, the constraint processing language ECLⁱPS^e [ECLiPSe1995] was used, which has as its basic algorithm backtracking with forward-checking and uses branch-and-bound for optimization tasks. There were three subgoals of this project: first, implement the combinatorial auction problem in ECLⁱPS^e; second, implement Sandholm's solution using ECLⁱPS^e; and third, investigate the possibility of improving the search using other heuristics.

It is important to realize that the Bidtree algorithm does not take into account the values the bidders have associated with each bid, nor does it consider (in this form of the algorithm) whether a mechanism for forward checking has been incorporated into the implementation language. Since ECLⁱPS^edoes support forward checking, the Bidtree algorithm simply becomes a static ordering of the variables.

The alternative bid selection rules used dynamic variable ordering to improve performance. The first approach was most constrained bid (MCB), which selected the bid whose set of items had the most non-empty intersections with all of the bids, thus elimintating more feasible future bids.

The second algorithm used the most valuable bid (MVB) rule. MVB selected the bid that had the largest amortized value (the value divided by the size of the set). It was hoped that the MVB selection rule would produce a higher revenue in its initial solution. This is desirable because the auctioneer may wish to stop the search before the algorithm completes. Additionally, a higher revenue discovered earlier would produce a better bound and would result in faster convergence to the optimal solution.

The data sets in the full report were generated by the same methods as in the Sandholm paper, but with scaled parameters because of resource limitations. Two results using unscaled parameters are summarized in Table 1. In most cases the MVB algorithm showed significant improvement over Bidtree in time to completion and the number of refinements to the bound. More experimental results may be seen at http://www.ics.uci.edu/~rmenke/runs/ [files no longer available — rgm].

Results

References

[ECLiPSe1995]

1995. ECLiPSe User Manual, v. 3.5.

[Sandholm1999]

Sandholm, T. W. 1999. An algorithm for optimal winner determination in combinatorial auctions. In International Joint Conference on Artificial Intelligence (IJCAI), 542-547.