Approaches to winner determination in combinatorial auctions

Combinatorial auctions, i.e., auctions where bidders can bid on combinations of items, tend to lead to more efficient allocations than traditional auctions in multi-item auctions where the agents' valuations of the items are not additive. However, determining the winners so as to maximize revenue is NP-complete. First, existing approaches for tackling this problem are reviewed: exhaustive enumeration, dynamic programming, approximation algorithms, and restricting the allowable combinations. Then, we overview our new search algorithm for optimal anytime winner determination. By capitalizing on the fact that the space of bids is necessarily sparsely populated in practice, it enlarges the envelope of input sizes for which combinatorial auctions are computationally feasible. Finally, we discuss eMediator, our electronic commerce server that implements several techniques for automatically facilitating commerce, including an auction house with generalized combinatorial auctions. To our knowledge, our implementation is the first Internet auction to support combinatorial auctions, bidding via graphically drawn price-quantity graphs, and by mobile agents. (C) 2000 Elsevier Science B.V. All rights reserved.