Please use this identifier to cite or link to this item:
Title: Incremental solutions to online multi-unit combinatorial auctions for information feedback
Authors: Ramanathan, Sivaraman
Kasinathan, Avinash
Sen, Anup Kumar
Keywords: Collaborative Information Retrieval
Dynamic Programming
Multi-unit Combinatorial Auction
Winner Determination Problem
Issue Date: 2014
Publisher: SCOPUS
ASONAM 2014 - Proceedings of the 2014 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining
Institute of Electrical and Electronics Engineers Inc.
Abstract: 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. © 2014 IEEE.
Description: Ramanathan, Sivaraman, McKinsey and Company, Chennai, India; Kasinathan, Avinash, McKinsey and Company, Chennai, India; Sen, Anup Kumar, Indian Institute of Management Calcutta, Kolkata, India
ISSN/ISBN - 978-147995877-1
DOI - 10.1109/ASONAM.2014.6921690
Appears in Collections:Management Information Systems

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.