Approaches to winner determination in combinatorial auctions

Combinatorial auctions, i.e., auctions where bidders can bid on combination s of items, tend to lead to more efficient allocations than traditional auc tions 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: exhausti ve enumeration, dynamic programming, approximation algorithms, and restrict ing 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 enlarge s the envelope of input sizes for which combinatorial auctions are computat ionally feasible. Finally, we discuss eMediator, our electronic commerce se rver that implements several techniques for automatically facilitating comm erce, including an auction house with generalized combinatorial auctions. T o our knowledge, our implementation is the first Internet auction to suppor t combinatorial auctions, bidding via graphically drawn price-quantity grap hs, and by mobile agents. (C) 2000 Elsevier Science B.V. All rights reserve d.