An efficient approximate algorithm for winner determination in combinatorial auctions

This paper presents an approximate algorithm for the winner determination problem in combinatorial auctions. This algorithm is based on limited discrepancy search (LDS). Internet auctions have become an integral part of Electronic Commerce and can incorporate large-scale, complicated types of auctions including combinatorial auctions, where multiple items are sold simultaneously and bidders can express complementarity among these items. Although we can increase participants utilities by using combinatorial auctions, determining the optimal winners is a complicated constraint optimization problem that is shown to be NP-complete. We introduce the idea of LDS to an existing algorithm based on the IDA* algorithm, which is guaranteed to find an optimal solution. The merit of LDS is that it can avoid time-consuming re-computation of heuristic function h( ), since LDS is less sensitive to the quality of h( ). It can also limit the search efforts to promising regions. Experiments using various problem settings show that LDS can find nearoptimal solutions (better than 95%) very quickly (around 1% of the running time) compared with the existing optimal algorithm.