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 Google Scholar Google Scholar Articles by Jones, J. L. Articles by Koehler, G. J. Search for Related Content

A Heuristic for Winner Determination in Rule-Based Combinatorial Auctions

Information Systems and Decision Sciences, College of Business Administration, University of South Florida, 4202 East Fowler Avenue, Tampa, Florida 33620-7800, USA
John B. Higdon Eminent Scholar and Professor of Decision and Information Sciences, Warrington College of Business, University of Florida, Gainesville, Florida 32611, USA
jjones{at}coba.usf.edu
koehler{at}ufl.edu

Combinatorial auctions address the sale of materials where there exist complementarities between items. A major stumbling block to the widespread use of combinatorial auctions is the complexity of the winner-determination problem, which is known to be NP-complete. We consider a rich version of combinatorial auctions, rule-based combinatorial auctions, where bids consist of rules that describe acceptable bundles rather than provide complete enumerations of acceptable bundles. This makes the winner-determination problem potentially harder because the problem must find bundles meeting bid criterion as well as finding an optimal selection of winning bids. This paper describes in detail a heuristic that achieves a satisfying solution to the winner-determination problem for large problems where exact solutions may not be attainable. Our contribution is threefold. First, we give a general approach to providing good approximations to the winner-determination problem for rule-based auctions. Although the approach requires adaptation for specific instances, it is conceptually tractable and implementable. Second, the approach is illustrated and tested on an auction format for selling prime-time television advertising time formed from data and interviews with industry sources. Third, while some researchers have used commercial solvers that appeared to obviate the need for specialized solution approaches to the winner-determination problem, we give evidence that, at least for the problem studied here, specialized approaches are necessary.

Key words: heuristic; combinatorics; bidding-auctions; branch-and-bound
History: received January 2003; revised June 2003; accepted September 2003.