Holger H. Hoos
Department of Computer Science
University of British Columbia
Vancouver, BC V6T 1Z4
email: hoos@cs.ubc.ca
Craig Boutilier
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: cebly@cs.toronto.edu
Abstract
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