Reducing complexity in winner determination for combinatorial ascending auctions

摘要

This paper describes an algorithm to reduce the computational complexity of winner determination for combinatorial ascending auction where bidding agents can place a bid for a combination of items at an arbitrary timing via the Internet. At e-marketplaces, where many services can be dynamically searched and used, an auction is a key technology for realizing market-based negotiations among ‘software agents’. Although some algorithms for reducing complexity have been proposed, they are only suitable for one-shot auctions where bidders submit bids only once simultaneously. Thus, we reduce computational burdens by using the previous valuation of bids for doing the next valuation. We then verify the effectiveness through evaluation.