Solving Combinatorial Auctions using Stochastic Local Search

Holger H. Hoos
Department of Computer Science
University of British Columbia
Vancouver, BC V6T 1Z4

Craig Boutilier
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5

Combinatorial auctions (CAs) have emerged as an important model in economics and show promise as a useful tool for tackling resource allocation in AI. Unfortunately, winner determination for CAs is NP-hard and recent algorithms have difficulty with problems involving goods and bids beyond the hundreds. We apply a new stochastic local search algorithm, Casanova, to this problem, and demonstrate that it finds high quality (even optimal) solutions much faster than recently proposed methods (up to several orders of magnitude), particularly for large problems. We also propose a logical language for naturally expressing combinatorial bids in which a single logical bid corresponds to a large (often exponential) number of explicit bids. We show that Casanova performs much better than systematic methods on such problems.

To appear, AAAI-2000

Return to List of Papers