Title: 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.
Publication Year: 1999
Publication Date: 1999-07-31
Language: en
Type: article
Access and Citation
Cited By Count: 457
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot