An Implementation of the Combinatorial Auction Problem in ECLiPSe

Abstract

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. (Sandholm 1999) 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 constraintprocessing 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 ECLiPSe (ECLiPSe 1995) 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 ECLiPSe; second, implement Sandholm’s solution using ECLiPSe; 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 ECLiPSe does 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