Robert Menke and Rina Dechter, University of California, Irvine
Combinatorial auctions allow bidders to bid upon multiple items simultaneously. This type of auction is attractive because for many bidders the individual items increase in value when held in conjunction with other items. Unfortunately, searching the entire space of the problem is intractable. By taking advantage of the sparsity of bids, a solution can be found in reasonable time. One such implementation of this concept is the Bidtree algorithm by Sandholm. The Bidtree algorithm was implemented in the constraint programming language ECLiPSe and its performance was compared to searches using other heuristics.