This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Adomavicius, G. Articles by Gupta, A. Search for Related Content

Toward Comprehensive Real-Time Bidder Support in Iterative Combinatorial Auctions

Department of Information and Decision Sciences, Carlson School of Management, University of Minnesota, 321 19th Avenue South, Minneapolis, Minnesota 55455
Department of Information and Decision Sciences, Carlson School of Management, University of Minnesota, 321 19th Avenue South, Minneapolis, Minnesota 55455
gedas{at}umn.edu
agupta{at}csom.umn.edu

Many auctions involve selling several distinct items simultaneously, where bidders can bid on the whole or any part of the lot. Such auctions are referred to as combinatorial auctions. Examples of such auctions include truck delivery routes, industrial procurement, and FCC spectrum. Determining winners in such auctions is an NP-hard problem, and significant research is being conducted in this area. However, multiple-round (iterative) combinatorial auctions present significant challenges in bid formulations as well. Because the combinatorial dynamics in iterative auctions can make a given bid part of a winning and nonwinning set of bids without any changes in the bid, bidders are usually not able to evaluate whether they should revise their bid at a given point in time or not. Therefore, in this paper we address various computational problems that are relevant from the bidder's perspective. In particular, we introduce two bid evaluation metrics that can be used by bidders to determine whether any given bid can be a part of the winning allocation and explore their theoretical properties. Based on these metrics, we also develop efficient data structures and algorithms that provide comprehensive information about the current state of the auction at any time, which can help bidders in evaluating their bids and bidding strategies. Our approach uses exponential memory storage but provides fast incremental update for new bids, thereby facilitating bidder support for real-time iterative combinatorial auctions.

Key Words: iterative combinatorial auctions; real-time bidder support; bid evaluation metrics; computational techniques for combinatorial auctions

This article has been cited by other articles:

				G. Adomavicius, A. Gupta, and D. Zhdanov Designing Intelligent Software Agents for Auctions with Limited Information Feedback Information Systems Research, December 1, 2009; 20(4): 507 - 526. [Abstract] [PDF]

				O. Seref, R. K. Ahuja, and J. B. Orlin Incremental Network Optimization: Theory and Algorithms Operations Research, May 1, 2009; 57(3): 586 - 594. [Abstract] [PDF]

				M. Bichler, P. Shabalin, and A. Pikovsky A Computational Analysis of Linear Price Iterative Combinatorial Auction Formats Information Systems Research, March 1, 2009; 20(1): 33 - 59. [Abstract] [PDF]