Incremental solutions to online multi-unit combinatorial auctions for information feedback

With the ease of carrying out an auction through internet, the electronic auction market is expanding rapidly. In online (i.e., continuous) eBay-like combinatorial auctions, bidders are allowed to join and leave the auction at any time, and in the process, bidders can repetitively bid on packages of items of their choice. In such multi-agent e-business systems, the seller is compelled to provide information feedback to the bidders after every bid on the current state of the auction to help them place more informed bids. This requires provisional winners be computed for every package of items after each bid by solving Winner Determination Problems. In multi-unit online combinatorial auctions where the number of bids can be significantly large, the paper presents for the first time dynamic programming approaches which can incrementally solve winner determination problems for every package after each new bid. We propose two dynamic programming algorithms to solve the multi-unit winner determination problem. While our first algorithm computes and stores the optimal values for all packages on arrival of a new bid traversing the packages in a reverse order, the alternative algorithm stores the optimal values only for packages that can fit into available memory but can find out the optimal solutions for every other package. We discuss the salient features of the algorithms, and demonstrate our approach through experiments. We also propose a bottom-up approach to dynamic programming for effective use of memory.