Approaches to winner determination in combinatorial auctions

摘要

Combinatorial auctions, i.e., auctions where bidders can bid oncombinations of items, tend to lead to more efficient allocationsthan traditional auctions in multi-item auctions where the agents'valuations of the items are not additive. However, determining thewinners so as to maximize revenue is NT-complete. First, existingapproaches for tackling this problem are reviewed' exhaustiveenumeration, dynamic programming, approximation algorithms, andrestricting the allowable combinations. Then, we overview our newsearch algorithm for optimal anytime winner determination. Bycapitalizing on the fact that the space of bids is necessarilysparsely populated in practice, it enlarges the envelope of inputsizes for which combinatorial auctions are computationally feasible.Finally, we discuss eMediator, our electronic commerce server thatimplements several techniques for automatically facilitatingcommerce, including an auction house with generalized combinatorialauctions. To our knowledge, our implementation is the first Internetauction to support combinatorial auctions, bidding via graphicallydrawn price--quantity graphs, and by mobile agents.