Solving Combinatorial Auctions Using Stochastic Local Search

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 difÆcultywith problems involving goods and bids beyond the hundreds. We apply a new stochastic local search algorithm, Casanova, to this problem, and demonstrate that it Ændshigh 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. 1