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 multiitem 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 which implements several techniques for automatically facilitating commerce, including an auction house with generalized combinatorial auctions. To our knowle..