Taming the Computational Complexity of Combinatorial Auctions: Optimal and Approximate Approaches

Abstract

In combinatorial auctions, multiple goods are sold simultaneously and bidders may bid for arbitrary combinations of goods . Determining the outcome of such an auction is an optimization problem that is NP-complete in the general case. We propose two methods of overcoming this apparent intractability. The first method, which is guaranteed to be optimal, reduces running time by structuring the search space so that a modified depth-first search usually avoids even considering allocations that contain conflicting bids. Caching and pruning are also used to speed searching. Our second method is a heuristic, market-based approach . It sets up a virtual multi-round auction in which a virtual agent represents each original bid bundle and places bids, according to a fixed strategy, for each good in that bundle. We show through experiments on synthetic data that (a) our first method finds optimal allocations quickly and offers good anytime performance, and (b) in many cases our second method , despite lacking guarantees regarding optimality or running time, quickly reaches solutions that are nearly optimal.